Analyse didactique d’un jeu de recherche : vers une situation fondamentale pour la complexité d’algorithmes et de problèmes

En analyse d'algorithmes, on s'interesse souvent a la notion de complexite en temps et dans le pire cas : etant donne un algorithme resolvant un certain probleme, peut-on estimer le nombre d'operations effectuees pour resoudre la pire instance d'une certaine taille ? Une autre notion importante s'interesse a la complexite du probleme lui-meme, in-dependamment d'un algorithme : peut-on demontrer que tout algorithme resolvant ce probleme effectue au moins un certain nombre d'operations ? Nous questionnons la possibilite d'aborder a divers niveaux d'enseigne-ment (scolaire ou superieur) les notions de complexite au pire d'un al-gorithme et de complexite intrinseque d'un probleme. Apres une breve presentation des notions visees, nous presentons une famille d'activites de type « debranche » inspirees du classique « jeu de la devinette », dont nous faisons l'hypothese qu'elles sont de nature a faire emerger ces notions, voire de constituer une situation fondamentale a leur egard. Ces activites reposent en particulier sur la notion d'argument d'adversaire, utilisee en theorie de la complexite. Nous fournissons une analyse a priori de cette famille d'activites et presentons un plan d'experimentation.