Algorithmique 1 (INFO503_INFO)

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.