Algorithmique avancée en master de Bio-Info 2004/2005

• Bibliographie
• Tds
• Années 2002/2003 et 2003/2004

• Présentation
• 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 en largeur avec une file
• Cours n° 2 : arbres binaires de recherche
  • Parcours en profondeur d'un arbre
    • programmation récursive
    • programmation du parcours préfixe avec une pile
  • 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 des 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 : problème de flots dans un graphe
  • Présentation du problème sur un exemple
  • Définitions
  • capacité
  • flot dans un graphe
  • capacité résiduelle et graphe résiduel
  • chemin d'augmentation
  • Algorithme de Ford-Fulkerson
  • Théorème flot maximal/coupe minimale
  • Algorithme d'Edmonds-Karp
• Cours n° 9 : recherche d'un motif dans un texte
  • Algorithme naïf
  • Algorithme de Morris et Pratt
• Cours n° 10 : recherche d'un motif dans un texte (suite)
  • Algorithme de Knuth, Morris et Pratt
  • Algorithme de Boyer et Moore