Algorithmique avancée en maîtrise de Bio-Info en 2002/2003
- Cours n° 1 : révisions
- Listes
- listes simplement chaînées et doublement chaînées
- implémentation des opérations de base : ajout et suppression
d'un élément
- Piles et files
- opérations élémentaires
- implémentation par tableaux et par listes
- Arbres
- arbres binaires
- représentation des arbres à nombre de fils quelconques avec des
arbres binaires
- parcours infixe, préfixe et suffixe
- programmation du parcours préfixe avec une pile
- Cours n° 2 : arbres binaires de recherches
- Arbres binaires de recherche
- insertion d'un élément
- recherche du successeur d'un élément
- suppression d'un élément
- Arbres rouges et noirs
- rotations
- insertion d'un élément
- suppression d'un élément
- Cours n° 3 : graphes
- Définitions et terminologie
- graphes orientés ou non
- chemin, cycle
- Représentations
- représentation par matrice d'adjacence
- représentation par liste d'adjacence
- Parcours en largeur
- Cours n° 4 : plus courts chemins à origine unique
- Arborescence de plus courts chemins
- Relâchement
- Algorithme de Bellman-Ford
- Cours n° 5 : algorithme de Dijkstra
- Cours n° 6 : parcours en profondeur dans un graphe
- Parcours général d'un graphe
- Parcours en profondeur
- programmation récursive
- programmation itérative
- Détection des cycles
- Tri topologique
- Cours n° 7 : composantes fortement connexes
- Définitions
- Algorithme de Tarjan
- Graphe réduit
- Cours n° 8 :
recherche d'un motif dans un texte
- Algorithme naïf
- Algorithme de Morris et Pratt
- Cours n° 9 : recherche d'un motif dans un texte
- Algorithme de Knuth, Morris et Pratt
- Algorithme de Boyer et Moore
- Cours n° 10 : recherche de motifs dans un texte
- Algorithme de Aho et Corasick