Cours :
• Arbres binaires de recherche
  
  • cours 1
    transparents : pdf, html
  • planche de TD/TP 1 (pdf)
• Tas
  
  • cours 2
    transparents : pdf, html
  • planche de TD/TP 2 (pdf)
• Parcours de graphe
  
  • cours 3
    transparents : pdf, html
  • planche de TD/TP 3 (pdf)
• Plus courts chemins et coloration de graphe
  
  • cours 4
    transparents : pdf, html
  • planche de TD/TP 4 (pdf)
• Programmation dynamique 1
  
  • cours 5
    transparents : pdf, html
  • planche de TD/TP 5 (pdf)
• Programmation dynamique 2
  
  • planche de TD/TP 6 (pdf)
• Recherche textuelle
  
  • cours 7
    transparents : pdf, html
  • planche de TD/TP 7 (pdf)
• Algorithmes randomisés
  
  • cours 8
    transparents : pdf, html
  • planche de TD/TP 8 (pdf)
• Calculabilité
  
  • transparents : pdf
  • planche de TD/TP 9 (pdf)
• Complexité
  
  • transparents : pdf
  • planche de TD/TP 10 (pdf)

Parcours de graphes

Benjamin Monmege

Kézako ?

Un algorithme de parcours de graphe est un algorithme qui, partant d’un sommet s d’un graphe appelé source, explore tous les sommets ou tous les arcs accessibles depuis cette source, et aucun autre.

• chaque sommet u, hormis la source, est associé à un sommet prédécesseur pred(u) tel que (pred(u), u) est un arc du graphe
• il existe un entier ℓ tel que pred^ℓ(u) = s
• ainsi, pred^ℓ(u), pred^{ℓ − 1}(u), …, pred(u), u est un chemin de s à u

Parcours de graphe permet de calculer tous les sommets accessibles depuis la source.

La fonction pred détermine une arborescence: un sous-ensemble d’arcs tel que chaque sommet possède un seul arc entrant sauf la source qui n’en a pas, et ne possédant pas de cycles.

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Parcours générique : sommets parcourus et frontière

Structure de données insertion-extraction

Parcours générique

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : file

Parcours en largeur : pseudo-code

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : pile

Parcours en profondeur : écriture récursive