Repères-IREM. N° 86. p. 27-50. Complexité d’un algorithme : une question cruciale et abordable.

English Title : Complexity of an algorithm: a crucial and affordable question. (ZDM/Mathdi)

Une version texte intégral est en téléchargement sur le site Bibliothèque numérique des IREM et de l’APMEP Télécharger

Auteurs : Aldon Gilles ; Germoni Jerôme ; Mény Jean-Manuel

Résumé

Lorsqu’on écrit un algorithme, trois problèmes se posent immédiatement. L’algorithme va-t-il donner une réponse ? C’est la question de la terminaison. Va-t-il donner la bonne réponse ? C’est la validité ou la correction de l’algorithme. Va-t-il donner la réponse en un temps acceptable ? Cela conduit à étudier la complexité de l’algorithme, en gros le nombre d’opérations élémentaires à effectuer en fonction de la taille des données. A travers l’étude détaillée d’exemples simples (Euclide, Fibonacci…), l’article tente de montrer que ces questions peuvent être étudiées de façon théorique, mais aussi expérimentale (mesure de temps de calcul), et que, outre leur intérêt dans le champ de l’informatique, elles motivent des questions qui figurent dans les programmes de mathématiques de lycée (notamment pour la logique ou l’étude des suites).

Notes

Cet article est publié dans Repères-IREM N° 86 .

Repères-IREM est la revue du réseau national des Instituts de Recherche sur l’Enseignement des Mathématiques (IREM), elle a été créée en octobre 1990. De nombreux articles peuvent être utilisés en formation initiale des enseignants.
Tous ses articles, jusqu’au dernier numéro paru, sont consultables et téléchargeables librement en ligne sur le site de l’IREM de Grenoble.

Données de publication

Éditeur TOPIQUES éditions Nancy , 2012 Format 16 cm x 23,7 cm, p. 27-50 Index Bibliogr. p. 50
ISSN 1157-285X

Public visé chercheur, enseignant, formateur

Type article de périodique ou revue Langue français Support papier