24-NSIJ1JA1-2

  1. Il s'agit d'un graphe orienté car chaque arc a un sens qui représente une dépendance entre deux tâches.

    • f puis g : Oui
    • g puis f : Non
    • i puis j : Oui
    • j puis i : Oui
  2. Il faut avoir réalisé les tâches a, h, c, i et j pour pouvoir réaliser la tâche k.

  3. Non, ce graphe ne contient pas de cycle.

  4. Un ordre possible serait 0, 2, 1, 3, 5, puis 4. Il s'agit d'un ordre topologique.

  5. Non, il n'existe pas d'ordre permettant de réaliser les tâches de ce graphe, car il contient un cycle, à savoir 1 — 2 — 3. Ce cycle crée une dépendance circulaire : chaque tâche dépend d'une autre dans la boucle, donc aucune ne peut être réalisée en premier.

  6. La variable ok contient False à l'issue de ces instructions.

    Appel mystere ouverts fermes
    Avant l'appel mystere [F,F,F,F,F] [F,F,F,F,F]
    mystere(M, 1, 5, [F,F,F,F,F], [F,F,F,F,F], None) [F,T,F,F,F] [F,F,F,F,F]
    mystere(M, 2, 5, [F,T,F,F,F], [F,F,F,F,F], None) [F,T,T,F,F] [F,F,F,F,F]
    mystere(M, 3, 5, [F,T,T,F,F], [F,F,F,F,F], None) [F,T,T,T,F] [F,F,F,F,F]
    mystere(M, 1, 5, [F,T,T,T,F], [F,F,F,F,F], None) [F,T,T,T,F] [F,F,F,F,F]
  7. Cette fonction renvoie False si et seulement s'il existe un cycle à partir du sommet s.

  8. Après exécution de ces instructions, la variable elt contient 2.

  9. resultat.empiler(s)  # à la ligne 24