Algorithmique I (INFO505_INFO)

Volume horaire

Plan du cours

Résumé du cours

Introduction à la notion d’algorithme. Complexité des algorithmes. Ordre de grandeur asymptotique. Les arbres : structure et métrique. Arbre binaires de recherche et arbres équilibrés. Algorithmes de tri interne : tri par insertion, fusion, échanges et sélection. Tri de Shell, tri rapide et tri par tas. Tris linéaires : tri par dénombrement. Tris externes. Terminaison des algorithmes itératifs : méthode de Floyd, compteurs de Knuth. Terminaison des algorithmes récursifs.

TD et TP

Approfondissement des concepts vus en cours et ouverture vers d’autres types d’algorithmes. B-arbres, en particulier arbres 2-3-4. Arbres rouges et noirs. Codage d’un arbre binaire dans un tableau.  Variantes des algorithmes de tri vus en cours.  Jeu de la vie. Algorithmes d’approximation. Etude de la terminaison d’algorithmes.

Diplômes intégrant ce cours

• Licence Informatique (L1, L2, L3)
• Cursus master en ingénierie : informatique