Supports d'Enseignement
2011/12, Licence 3: Algorithmique
Le projet à réaliser se trouve ICI.
- Cours 1[*]: Graphes, notions de bases et terminologie, représentations de graphes, parcours en profondeur, détection de circuits, tri topologique, composantes fortement connexes, parcours en largeur
- Cours 2[*]: Les plus courts chemins dans les graphes, algorithme de Dijkstra, algorithme de Bellman-Ford, les plus court chemins dans les graphes acycliques
- Cours 3[*]: Clôture transitive des graphes, algorithme de Warshall, tous les plus courts chemins dans un graphe, algorithme de Floyd-Warshall
- Cours 4[*]: Arbres recouvrant de coût minimal (ARCM), Algorithme de Prim, Algorithme de Kruskal, Implémentation de UNION-CLASS (UNION-FIND)
- Cours 5[*]: Test d'équivalence d'automates finis déterministes avec UNION-CLASS, Flot maximal dans un graphe orienté, Calcul de couplage maximal d'un graphe biparti
- Cours 6[**]: Arbres binaires de recherche, Arbres rouge-noirs
- Cours 7 : Recherche de motif dans les textes : Algorithmes de Knuth-Morris-Pratt, Aho-Corasick, Karp-Rabin
- Cours 8 : Applications de la technique de Knuth-Morris-Pratt. Structures pour index : arbre des suffixes, automate des suffixes, table des suffixes
- Cours 9 : Programmation dynamique. Plus longue sous-séquence commune à deux séquences
[**]cette présentation s'inspire de ce document ↑