Résumé
Ce travail cherche à mettre en évidence les potentialités didactiques, pour l'enseignement de concepts algorithmiques, d'une activité débranchée autour de jeux de devinettes. Grâce à un dispositif de « jeu algorithmique » inspiré de la théorie de la complexité, cette activité vise à faire émerger les concepts de complexité au pire d'algorithme et de complexité de problème. Elle mobilise aussi d'autres concepts présents dans les programmes de NSI, comme l'approche « diviser pour régner », ainsi que des savoir-faires plus généraux comme celui de formuler et prouver un énoncé. Nous décrivons une expérimentation de cette situation didactique dans plusieurs classes de lycée françaises de la spécialité Numérique et Sciences Informatiques (NSI), et fournissons des éléments d'analyse des données recueillies. Nous nous appuyons sur divers éléments théoriques et méthodologiques issus de la didactique des disciplines, ainsi que sur une analyse épistémologique et didactique préalable.