Révision

• Revoir les exercices des chapitres précédents.
• Revoir les Kahoot!.

Objectifs

L'évaluation se portera sur les critères suivants :

• Théorie des graphes
  • Modéliser un problème sous forme de graphe.
  • Identifier les caractéristiques d'un graphe.
• Parcours de graphe
  • Effectuer un parcours en profondeur.
  • Effectuer un parcours en largeur.
  • Différencier une pile et une file.
• Problème du plus court chemin
  • Appliquer l'algorithme de Dijkstra.
  • Trouver le plus court chemin entre deux sommets.
• Réseau de flot
  • Appliquer l'algorithme de Ford-Fulkerson.
  • Trouver la coupe minimale d'un réseau de flot.

Note	1	2	2.5	3	3.5	4	4.5	5	5.5	6
Nombre de critères validés	0	1	2	3	4	5	6	7	8	9

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

Ai-je compris ?

(liste non exhaustive)

• Connaître les caractéristiques d'un graphe
  • Sommet
  • Arête et Arc (Graphe orienté et non orienté)
  • Boucle
  • Voisinage et degré d'un sommet
  • Poids d'une arête ou d'un arc (graphe pondéré)
  • Chaîne/Chemin
  • Cycle/Circuit
• Associer un graphe à des topologies
• Modéliser un problème sous forme de graphe
• Appliquer les algorithmes de parcours en profondeur et en largeur
• Utiliser et différencier une pile et une file
• Appliquer l'algorithme de Dijkstra pour trouver le plus court chemin
• Appliquer l'algorithme de Ford-Fulkerson pour trouver le flot maximum
• Calculer la capacité d'une coupe d'un réseau de flot
• Trouver la coupe minimale d'un réseau de flot

Exercices

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 \times (10 + 5)$ s'écrit 3 10 5 + * en notation polonaise inverse :

Calculer le résultat des expressions suivantes :

1. 3 10 5 + *
2. 3 10 5 * +
3. 3 5 + 2 *
4. 5 2 4 + *
5. 6 2 /
6. 15 5 - 2 *
7. 3 4 5 * 12 3 / - +
8. 29 7 6 * - 5 + 92 + 2 /

Solution

1. 3 10 5 + * : $3 \times (10 + 5) = 45$ détail
2. 3 10 5 * + : $3 + (10 \times 5) = 53$ détail
3. 3 5 + 2 * : $(3 + 5) \times 2 = 16$ détail
4. 5 2 4 + * : $5 \times (2 + 4) = 30$ détail
5. 6 2 / : $6 / 2 = 3$ détail
6. 15 5 - 2 * : $(15 - 5) \times 2 = 20$ détail
7. 3 4 5 * 12 3 / - + : $3 + (4 \times 5) - (12 / 3) = 19$ détail
8. 29 7 6 * - 5 + 92 + 2 / : $((29 - (7 \times 6)) + 5 + 92) / 2 = 42$ détail

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

Solution

Quel serait l'ordre avec un parcours en profondeur ?

Solution

• Sous-vêtements
• Pantalon
• Chaussettes
• Chaussures
• T-shirt
• Pull
• Veste
• Gants
• Écharpe
• Bonnet

Quel serait l'ordre avec un parcours en largeur ?

Solution

• Sous-vêtements
• Pantalon
• Chaussettes
• T-shirt
• Bonnet
• Chaussures
• Pull
• Veste
• Écharpe
• Gants

Dijkstra

Appliquer l'algorithme de Dijkstra sur le graphe suivant :

Chemin : A → H

Solution

	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

Ford-Fulkerson

Appliquer l'algorithme de Ford-Fulkerson pour trouver le flot maximum et ainsi que la coupe minimum sur le graphe suivant :

Solution

Flot maximum : 10 + 5 + 10 + 5 + 10 = 40

Coupe minimum : {S, A, B, C, D} / {T}

Références

Illustrations

• https://commons.wikimedia.org/wiki/File:CPT-RPN-example1.svg