ALGO1 : Introduction à l'algorithmique

Licence 3 d'informatique (parcours recherche) et magistère de Mathématiques de Rennes - ENS Rennes - Année 2021/2022

Intervenants

Cours : François Schwarzentruber
Travaux dirigés : Kerian Thuillier
Raphaël Truffet (groupe info)

Plan du cours

Complexité

Définition des notations de Landau. Fiche

Séance 1 : Problème des mariages stables

Cours introductif. Invariant. Variant. Problème des mariages stables. Algorithme de haut niveau. Types abstraits et structures de données. Problème des mariages stables Types Abstraits et Structures de Données Basiques

Séance 2 : File de priorité et tas binaire

Bubble-up et bubble-down. Complexité logarithmique pour l'enfilement et le défilement. Tri par tas. Construction d'un tas en temps linéaire. Tas binomiaux fusionnables. File de priorité et tas binaire Tas binomiaux

Séance 3 : Quelques structures de données pour dictionnaire

Arbre binaire de recherche. Structure de données persistantes. Equilibrage. B-arbre. Lien avec arbres rouge-noir. Arbres binaires de recherche et équilibrage Table de hachage par chaînage. Hypothèse de hachage uniforme. Hachage universel. Hachage parfait. Table de hachage Table de hachage

Séance 4 : Diviser pour régner

Théorème maître. Algorithme de Karatsuba. Algorithme de Strassen. Transformée de Fourier discrète rapide (FFT). Problème de sélection du k-ème élément. Diviser pour régner

Séance 5 : Parcours en profondeur

Algorithme générique de parcours en profondeur. Tri topologique. Cycle. Algorithme de Kosaraju. Parcours en profondeur

Séance 6 : Parcours en largeur

Parcours en largeur. Dijkstra. Tas de Finabonacci. Parcours en largeur Tas de Fibonacci

Séance 7 : Algorithmes gloutons

Algorithme de Kruskal. Union-find. Compression de chemins. Algorithme de Kruskal Union-find

Séance 8 : Programmation dynamique

Plus longue sous-suite croissante. Distance d'édition. Plus courts chemins dans un graphe acyclique. Algorithme de Bellman-Ford. Algorithme de Floyd-Warshall. Sac à dos avec répétition et sans. Mémoïsation. Programmation dynamique

Séance 9 : Flots

Réseau de flots. Graphe résiduel. Algorithme de Ford-Fulkerson. Théorème de dualité max flow/min cut. Flots

Séance 10 : NP-complétude

Problème de recherche. Classe NP. Certificat. Vérificateur. Algorithme non déterministe. Réductions en temps polynomial. NP-dureté. Théorème de Cook. 3-coloration est NP-complet. NP-complétude Catalogue de réductions

Examens des années précédentes

Références

Introduction à l’algorithmique, T. H. Cormen, C. E. Leiserson, R. L. Rivest, Dunod. (une référence, couvre beaucoup de choses, un peu lourd et quelques erreurs)
Algorithms de S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. (couvre l'essentiel, une approche intéressante et concise)
Algorithms, R. Sedgewick, Addison-Wesley.
Éléments d’algorithmique, D. Beauquier, J. Berstel, Ph. Chrétienne, Masson. (merci aux auteurs de donner le livre sur Internet)
Types de données et algorithmes, C. Froidevaux, M.-C. Gaudel, M. Soria, McGraw-Hill-InterEditions. (intéressant pour les structures de données)
Algorithmics, The Spirit of Computing. David Harel. (une façon originale de présenter le paysage des algorithmes : "les limites", "relâcher les règles (parallélisme, proba)", "algorithme dans la création de logiciels")
Algorithm design, Jon Kleinberg et Eva Tardos. (ouvrage riche en bons exemples) http://www.aw-bc.com/info/kleinberg/index.html