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

Autre cours sur internet