Révision
Résumé des algorithmes
Parcours en profondeur
- Initialisation
- La liste des sommets visités est vide
- La pile contient le sommet de départ
- Itération(s)
- Dépiler et sélectionner ce sommet
- Ajouter le sommet sélectionné à la liste des sommets visités
- Pour chaque voisin du sommet sélectionné
- Empiler le voisin s'il n'est pas déjà découvert ou visité (contenu dans la pile ou la liste des sommets visités)
- Condition d'arrêt
- La pile est vide
Parcours en largeur
- Initialisation
- La liste des sommets visités est vide
- La file contient le sommet de départ
- Itération(s)
- Défiler et sélectionner ce sommet
- Ajouter le sommet sélectionné à la liste des sommets visités
- Pour chaque voisin du sommet sélectionné
- Enfiler le voisin s'il n'est pas déjà découvert ou visité (contenu dans la file ou la liste des sommets visités)
- Condition d'arrêt
- La file est vide
Algorithme de Dijkstra
- Initialisation
- Distance infini pour tous les sommets sauf le sommet de départ à 0
- Itération(s)
- Sélectionner le sommet non visité avec la distance minimale
- Garder une trace du chemin parcouru sur le graphe
- Marquer le sommet sélectionné comme visité
- Pour chaque voisin du sommet sélectionné
- Mettre à jour la distance du voisin si elle est plus petite que la distance actuelle
- Garder la distance des autres sommets
- Condition d'arrêt
- Le sommet de destination est visité
Algorithme de Ford-Fulkerson
- Initialisation
- Flot à 0 pour tous les arcs
- Itération(s)
- Recherche d'un chemin existant de S à T
- Le flot maximum du chemin est la capacité minimale des arcs
- Mise à jour du flot des arcs du chemin avec le flot maximum
- Condition d'arrêt
- Il n'existe plus de chemin de S à T
Exercices
Finir les exercices de tous les cours du chapitre.
Exercice : Notation polonaise inverse
La notation polonaise inverse est une façon d'écrire des expressions mathématiques sans utiliser de parenthèses.
Elle utilise une pile pour stocker les opérandes (nombres) et les opérateurs (symboles). On lit chaque symbole de gauche à droite et on applique les règles suivantes :
- Lorsqu'on lit un opérande, on le met sur la pile
- Lorsqu'on lit un opérateur, on dépile deux opérandes, on les combine avec l'opérateur et on met le résultat sur la pile
Par exemple, l'expression 3 10 5 + * en notation polonaise inverse :
Calculez le résultat des expressions suivantes :
3 10 5 + *3 10 5 * +3 5 + 2 *5 2 4 + *6 2 /15 5 - 2 *3 4 5 * 12 3 / - +29 7 6 * - 5 + 92 + 2 /
Réponses
Exercice : Modélisation et parcours
Créez l'arbre de dépendance des habits suivants (ordre d'habillage) en commençant par les sous-vêtements :
- Bonnet
- Chaussettes
- Chaussures
- Écharpe
- Gants
- Pantalon
- Pull
- Sous-vêtements
- T-shirt
- Veste
Correction
Quel serait l'ordre avec un parcours en profondeur ?
Correction
- Sous-vêtements
- Pantalon
- Chaussettes
- Chaussures
- T-shirt
- Pull
- Veste
- Gants
- Écharpe
- Bonnet
Quel serait l'ordre avec un parcours en largeur ?
Correction
- Sous-vêtements
- Pantalon
- Chaussettes
- T-shirt
- Bonnet
- Chaussures
- Pull
- Veste
- Écharpe
- Gants
Exercice : Dijkstra
Appliquer l'algorithme de Dijkstra sur le graphe suivant :
Chemin : A → H
Correction
| A | B | C | D | E | F | G | H | |
|---|---|---|---|---|---|---|---|---|
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |
| A | - | 7 | ∞ | ∞ | 14 | ∞ | ∞ | ∞ |
| B | - | - | 15 | ∞ | 14 | ∞ | ∞ | ∞ |
| E | - | - | 15 | ∞ | - | 33 | ∞ | ∞ |
| C | - | - | - | 21 | - | 33 | ∞ | ∞ |
| D | - | - | - | - | - | 32 | ∞ | ∞ |
| F | - | - | - | - | - | - | 36 | 45 |
| G | - | - | - | - | - | - | - | 44 |
Chemin : A → B → C → D → F → G → H avec une distance de 44
Exercice : Ford-Fulkerson
Appliquer l'algorithme de Ford-Fulkerson pour trouver le flot maximum et ainsi que la coupe minimum sur le graphe suivant :
Correction
Flot maximum : 10 + 5 + 10 + 5 + 10 = 40
Coupe minimum : {S, A, B, C, D} / {T}
Ai-je compris ?
(liste non exhaustive)