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)

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
Formation à l'enseignement, initiale et continue.
 B39L'enseignement secondaire
Formation à l'enseignement, initiale et continue.
 B50La formation des enseignants (formation initiale et formation continue)
Général, difficile à classer
 F60Théorie des nombres. Congruences. Nombres premiers.
Général, difficile à classer
 P20Informatique 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)
Général, difficile à classer
 U39Livres du Maitre et aides à l'enseignement (documents d'accompagnement, matériel didactique)
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 des Instituts de Recherche sur l'Enseignement des Mathématiques (IREM), elle a été créée en 1990. Un grand nombre de ces articles peuvent être utilisés en formation initiale ESPE (ex IUFM).
Vous pouvez consulter les éditoriaux et les articles un an après leur parution, à partir du sommaire de chaque numéro de Repères-IREM disponible sur le Portail des IREM : cliquez sur "Repères IREM", puis sur "Consultation en ligne". Dans chaque numéro plus récent, un des articles l'est également. Vous pouvez aussi soumettre un article à la revue en l'adressant au rédacteur en chef à l'adresse : reperes-irem@univ-irem.fr

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

Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 09/09/2019
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