Skip to content

Révision

Revoir les quiz sur Kahoot

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

CPT-RPN-example1

Calculez 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 /
Réponses
  1. 3 10 5 + * : 3×(10+5)=45 détail
  2. 3 10 5 * + : 3+(10×5)=53 détail
  3. 3 5 + 2 * : (3+5)×2=16 détail
  4. 5 2 4 + * : 5×(2+4)=30 détail
  5. 6 2 / : 6/2=3 détail
  6. 15 5 - 2 * : (155)×2=20 détail
  7. 3 4 5 * 12 3 / - + : 3+(4×5)(12/3)=19 détail
  8. 29 7 6 * - 5 + 92 + 2 / : ((29(7×6))+5+92)/2=42 détail

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
ABCDEFGH
0
A-714
B--1514
E--15-33
C---21-33
D-----32
F------3645
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)