Accueil Publimath  Aide à la recherche   Recherche Avancée   Imprimer la fiche   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional
Auteur(s) : Aldon Gilles ; Germoni Jerôme ; Mény Jean-Manuel

Titre : 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 sur le site Bibliothèque numérique des IREM et de l'APMEP  Télécharger 

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

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

Public visé : chercheur, enseignant, formateur

Classification : A39Revues, article de revue, article sur un site internet
Formation à l'enseignement, initiale et continue.
 P29Informatique théorique (structuration des données, codage des données, théorie du codage et de l'information, analyse des algorithmes et problèmes de complexité, modes de calcul et complexité calculatoire, langages formels)
Formation à l'enseignement, initiale et continue.
 

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 :
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 octobre1990. De nombreux articles peuvent être utilisés en formation initiale des enseignants.
Tous les articles parus dans Repères-IREM sont consultables et téléchargeables librement en ligne sur le Portail des IREM, dès la parution du numéro, à partir de son sommaire : cliquez sur l'onglet "Repères IREM", puis sur "Consultation en ligne".
Vous pouvez aussi soumettre un article à la revue en l'adressant en document attaché au rédacteur en chef de la revue à l'adresse : reperes-irem@univ-irem.fr


Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 16/09/2020
Accueil Publimath  Aide à la recherche   Recherche Avancée   Imprimer la fiche   Aidez-nous à améliorer cette fiche  Vidéo d'aide
Certification IDDN Valid HTML 4.01 Transitional