Analyse didactique d’un jeu de recherche : vers une situation fondamentale pour la complexité d’algorithmes et de problèmes
Résumé
En analyse d'algorithmes, on s'intéresse souvent à la notion de complexité en temps et dans le pire cas : étant donné un algorithme résolvant un certain problème, peut-on estimer le nombre d'opérations effectuées pour résoudre la pire instance d'une certaine taille ? Une autre notion importante s'intéresse à la complexité du problème lui-même, in-dépendamment d'un algorithme : peut-on démontrer que tout algorithme résolvant ce problème effectue au moins un certain nombre d'opérations ? Nous questionnons la possibilité d'aborder à divers niveaux d'enseigne-ment (scolaire ou supérieur) les notions de complexité au pire d'un al-gorithme et de complexité intrinsèque d'un problème. Après une brève présentation des notions visées, nous présentons une famille d'activités de type « débranché » inspirées du classique « jeu de la devinette », dont nous faisons l'hypothèse qu'elles sont de nature à faire émerger ces notions, voire de constituer une situation fondamentale à leur égard. Ces activités reposent en particulier sur la notion d'argument d'adversaire, utilisée en théorie de la complexité. Nous fournissons une analyse a priori de cette famille d'activités et présentons un plan d'expérimentation.
Origine : Fichiers produits par l'(les) auteur(s)