[23-24]-Algorithmique 1 (Y. Vaxes, S. Grandcolas)

L'objectif de cette unité est d'introduire les structures de données et les techniques de conception de base de l'algorithmique, et d'étudier les outils d'analyse et de preuve de correction des algorithmes.

  • Notions de base pour l'analyse des algorithmes ; algorithmes de tri

  • Algorithmes de tri, optimalité asymptotique (notamment preuve de borne inférieure) ; tris linéaires

  • Tas binaire ; tri par tas

  • Dictionnaire ; arbre binaire de recherche non-équilibré, insertion et suppression de clés

  • Équilibrage des arbres binaires de recherche ; files de priorité (hors tas binaire)

  • Tables de hachage, chainage simple ; nombre de collisions ; extension : filtre de Bloom ou table coucou

  • Énumération et algorithmes par rebroussement (SAT, sac-à-dos, problèmes logiques)

  • Programmation dynamique, principe et exemples (ordonnancement sur une machine, sous-

    séquence monotone la plus longue)

  • Graphes et représentation par listes d'incidence ; plus court chemins, algorithme de Dijkstra

  • Algorithmes de plus courts chemins : Bellman-Ford, Floyd-Warshall

  • Arbres couvrants de poids minimum : algorithme de Prim, algorithme de Kruskal ; structure d'union-find.