Informatique B

Notations et définitions.

Le graphe orienté fini $G$ a pour ensemble de sommets $V$.

Plusieurs arcs peuvent avoir la même source et la même cible, avec des étiquettes différentes.

Le dictionnaire Python G associe à chaque sommet la liste de ses successeurs.

L’indice d’un élément dans cette liste est l’étiquette de l’arc correspondant.

Les hypothèses générales sont les suivantes :

Pour $(s,t)\in V^2$, la notation $s\rightsquigarrow t$ signifie qu’un chemin orienté relie $s$ à $t$.

Le chemin de longueur nulle est autorisé, donc $s\rightsquigarrow s$.

Les dictionnaires globaux époque et sortie associent un entier à chaque sommet.

Les variables globales présent et compteur sont des entiers.

Dans les formules, notons $p\in\mathbb{Z}$ la valeur de présent, et $\tau,\sigma:V\to\mathbb{Z}$ les applications définies par les valeurs de époque et sortie :

Les invariants suivants sont disponibles hors de l’exécution de pp :

La fonction pp(s) effectue les opérations suivantes :

On admet la propriété de parcours en profondeur annoncée dans l’énoncé.

On utilise également, lorsqu’elle suffit, la préservation de A2, A3 et A4 par un appel complet à pp.

La fonction accessible(s, t) renvoie immédiatement False lorsque

ou lorsque les époques sont égales et $\sigma(s)<\sigma(t)$.

Sinon, elle incrémente présent, exécute pp(s), puis renvoie le résultat du test époque[t] == présent.

La fonction lier(u, s) appelle accessible(s, u).

Si cet appel renvoie False, elle ajoute s à la liste G[u] et renvoie True.

Sinon, elle renvoie False sans ajouter d’arc.

Le graphe de l’exemple est défini par les listes suivantes :

Pour Q1, les valeurs initiales des deux dictionnaires sont toutes nulles, compteur vaut zéro et présent vaut un.

Les accès aux dictionnaires, les tests de présence dans un dictionnaire, les accès aux listes, len, append et pop ont les coûts constants admis par l’énoncé.