#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
""" Correction du DS de vendredi 11 décembre 2015.
Voici ci-dessous la documentation de la correction complète du sujet d'écrit d'informatique (Polytechnique et ENS, 2015), pour PSI et PT.
Ce sujet d'écrit a été posé en devoir écrit surveillé (DS) pour le cours d'informatique pour tous en prépa MP au Lycée Lakanal.
Veuillez `consulter le code source pour tous les détails <_modules/X_PSI_PT__2015__minimal_solution.html>`_ svp.
Ci dessous se trouve simplement la *documentation* de ce programme.
- *Date :* Vendredi 11 décembre 2015,
- *Auteur :* Lilian Besson, pour le cours d'informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
- *Licence :* MIT Licence (http://lbesson.mit-license.org).
.. note::
Cette correction contient beaucoup de documentation, des exemples et des détails.
Pour une correction beaucoup plus concise, voir `cette page <_modules/X_PSI_PT__2015__minimal_solution.html>`_.
.. warning::
Les fonctions sont ici listées par ordre alphabétique, et pas dans l'ordre du fichier source.
D'habitude, j'arrive à `corriger ça <http://sphinx-doc.org/ext/autodoc.html#confval-autodoc_member_order>`_, mais là non. Désolé.
Je trouverai comment régler ce problème !
"""
from __future__ import print_function # Python 2 compatibility
if __name__ == '__main__':
print(__doc__)
# %% Partie 0 : Fonctions supposées données
print("\n\nPartie 0 : Fonctions supposées données")
# On donne une implémentation simple des fonctions supposées données par l'énoncé
[docs]def creerTableau(n):
""" (*Préliminaires*) On implémente cette fonction avec un tableau Python (de type ``list``).
- Créé un tableau *vide* de taille ``n`` et le renvoie.
- *Elle n'était pas demandée, mais supposée donnée*.
- Les valeurs initiales du tableau sont arbitraires (``None`` en pratique).
- Exemple :
>>> n = 5; t = creerTableau(n)
>>> for i in range(n):
... t[i] = i + 2
>>> affiche(t)
[2, 3, 4, 5, 6]
"""
t = [None] * n
return t
[docs]def creerTableau2D(p, q):
r""" (*Préliminaires*) Exemple de création d'un tableau bi-dimensionnel, de taille :math:`p \times q`, ie. un tableau ``a`` de ``p`` tableaux de taille ``q``.
- *Elle n'était pas demandée*, mais est donnée ici à titre d'illustration,
- Exemple :
>>> p = 2; q = 2;
>>> a = creerTableau2D(p, q)
>>> for i in range(p):
... for j in range(q):
... a[i][j] = i+j
>>> affiche(a)
[[0, 1], [1, 2]]
"""
# Ce code là était donné, tel quel.
a = creerTableau(p)
for i in range(p):
a[i] = creerTableau(q)
return a
[docs]def affiche(*args):
""" (*Préliminaires*) Affiche les arguments un à un, séparés par des espaces.
- *Elle n'était pas demandée, mais supposée donnée*,
- Exemple :
>>> x = 1; y = x+1
>>> affiche("x = ",x," et y = ",y)
x = 1 et y = 2
"""
print(*args, sep='')
# %% Partie I : Préliminaires : Listes dans redondance
affiche("\n\nPartie I : Préliminaires : Listes dans redondance")
affiche("Note : une liste non-ordonnée et sans redondance est exactement un set de Python, mais nous ne devons pas nous en servir.")
# %% Question 1
[docs]def creerListeVide(n):
""" (**Question 1**) Crée, initialise et renvoie un tableau de longueur ``n + 1`` correspondant à la liste vide ayant une capacité de ``n`` éléments.
- Chaque case du tableau est initialisé à ``None`` pour garder trace qu'elle est vide,
- Exemple :
>>> n = 5; liste = creerListeVide(n)
>>> affiche(liste)
[0, None, None, None, None, None]
"""
liste = creerTableau(n+1)
liste[0] = 0
for i in range(1, n+1):
liste[i] = None
return liste
# %% Question 2
[docs]def estDansListe(liste, x):
""" (**Question 2**) Teste si l'élement x apparaît dans la représentée par le tableau ``liste`` (répond ``True`` ou ``False``).
- Complexité en *temps* : :math:`O(n)` (dans le pire des cas, car on doit alors parcourir tout le tableau),
- Complexité en *mémoire* : :math:`O(1)` (toujours),
- Exemple :
>>> # Exemple d'une liste non ordonnée contenant 1,2,3,4,5
>>> liste = [5, 5, 4, 2, 1, 3]
>>> affiche(estDansListe(liste, 0))
False
>>> affiche(estDansListe(liste, 5))
True
>>> affiche(estDansListe(liste, 194652))
False
"""
n = liste[0]
for i in range(1, n+1):
# On ne cherche pas parmi les valeurs inutilisées
if x == liste[i]:
# On a trouvé x dans le tableau !
return True
return False
# %% Question 3
[docs]def ajouteDansListe(liste, x):
""" (**Question 3**) Modifie de façon appropriée le tableau ``liste`` pour y ajouter ``x``, si l'entier ``x`` n'appartient pas déjà à la liste, et ne fait rien sinon.
- Cette procédure ne fait *rien du tout* si la liste est pleine initialement (Le sujet ne demandait pas de traiter ce cas),
- Complexité en *temps* : :math:`O(n)` (dans le pire des cas, car on doit alors parcourir tout le tableau),
- Complexité en *mémoire* : :math:`O(1)` (toujours),
- Exemple :
>>> n = 5; liste = creerListeVide(n)
>>> for i in range(1, n+1):
... ajouteDansListe(liste, 4**i)
>>> affiche(liste)
[5, 4, 16, 64, 256, 1024]
>>> # Très similaire à un ensemble défini par compréhension :
>>> ensemble = { 4**i for i in range(1, n+1)}
>>> affiche(ensemble) # L'ordre est arbitraire ! set([16, 64, 4, 256, 1024])
{16, 64, 256, 1024, 4}
- On peut vérifier qu'ajouter un élément quand la liste est déjà pleine ne marche pas (la liste n'est pas modifiée) :
>>> ajouteDansListe(liste, 2015)
Impossible d'ajouter l'élément x = 2015 à la liste [5, 4, 16, 64, 256, 1024] qui est déjà pleine (n = 5).
- *Note :* ce message d'erreur n'était pas demandée.
"""
if estDansListe(liste, x):
pass
else:
n = liste[0]
capacite = len(liste) - 1
if n < capacite:
liste[n+1] = x
liste[0] = n + 1
else:
affiche("Impossible d'ajouter l'élément x = ", x, " à la liste ", liste, " qui est déjà pleine (n = ", n, ").")
# %% Partie II. Création et manipulation de plans
affiche("\n\nPartie II. Création et manipulation de plans")
# Les 4 lignes suivantes n'étaient pas demandées
affiche("Plan de la figure 1 :")
plan0 = [[5, 4],
[1, 2, None, None, None],
[3, 4, 1, 5, None],
[0, None, None, None, None],
[2, 2, 5, None, None],
[2, 4, 2, None, None],
]
affiche("""plan0 = [[5, 4],
[1, 2, None, None, None],
[3, 4, 1, 5, None],
[0, None, None, None, None],
[2, 2, 5, None, None],
[2, 4, 2, None, None],
]
""")
affiche(plan0)
# %% Question 4 (exemple de plans)
affiche("Premier plan :")
plan1 = [[5, 7],
[2, 2, 3, None, None],
[3, 1, 3, 5, None],
[4, 1, 2, 4, 5],
[2, 3, 5, None, None],
[3, 2, 3, 4, None],
]
# Les deux lignes suivantes n'étaient pas demandées
affiche("""plan1 = [[5, 7],
[2, 2, 3, None, None],
[3, 1, 3, 5, None],
[4, 1, 2, 4, 5],
[2, 3, 5, None, None],
[3, 2, 3, 4, None],
]
""")
affiche(plan1)
affiche("Deuxième plan :")
plan2 = [[5, 4],
[1, 2, None, None, None],
[3, 1, 3, 4, None],
[1, 2, None, None, None],
[2, 2, 5, None, None],
[1, 4, None, None, None],
]
# Les deux lignes suivantes n'étaient pas demandées
affiche("""plan2 = [[5, 4],
[1, 2, None, None, None],
[3, 1, 3, 4, None],
[1, 2, None, None, None],
[2, 2, 5, None, None],
[1, 4, None, None, None],
]
""")
affiche(plan2)
# %% Question 5
[docs]def creerPlanSansRoute(n):
""" (**Question 5**) Crée, remplit et renvoie le tableau de tableaux correspondant au plan à ``n`` villes n'ayant aucune route.
- Complexité en *temps* : :math:`O(n)` (toujours),
- Complexité en *mémoire* : :math:`O(n)` (toujours),
- Exemple :
>>> n = 4; plan = creerPlanSansRoute(n)
>>> affiche(plan)
[[4, 0], [0, None, None, None, None, None], [0, None, None, None, None, None], [0, None, None, None, None, None], [0, None, None, None, None, None]]
- *Note :* les ``None`` affichées plus haut correspondent aux ``*`` dans le sujet.
"""
plan = creerTableau(n+1)
m = 0 # Par défaut, aucune route
plan[0] = [n, m]
for i in range(1, n+1):
plan[i] = creerListeVide(n+1)
return plan
# %% Question 6
[docs]def estVoisine(plan, x, y):
r""" (**Question 6**) Renvoie ``True`` si les villes ``x`` et ``y`` sont voisines dans le plan codé par le tableau de tableaux ``plan``, et renvoie ``False`` sinon.
- On utilise une structure qui peut représenter des graphes dirigés (ie. non symétrique, on peut avoir :math:`x \to y` sans avoir :math:`y \to x`), mais *tout le reste du sujet n'utilisera que des graphes non dirigés* (tous les chemins sont symétriques, donc :math:`x \sim y \Leftrightarrow x \to y \;\;\text{et}\;\; y \to x`),
- Complexité en *temps* : :math:`O(n)` (dans le pire des cas, car on doit alors parcourir toutes les voisines de ``x`` et de ``y``),
- Complexité en *mémoire* : :math:`O(1)` (toujours),
- Exemple :
>>> plan = [[5, 4], [1, 2, None, None, None], [3, 1, 3, 4, None], [1, 2, None, None, None], [2, 2, 5, None, None], [1, 4, None, None, None]] # plan2, cf ci-dessus
>>> x = 1; y = 2
>>> affiche(estVoisine(plan, x, y))
True
>>> x = 1; y = 5
>>> affiche(estVoisine(plan, x, y))
False
"""
# return estDansListe(plan[x], y) or estDansListe(plan[y], x)
return estDansListe(plan[x], y) and estDansListe(plan[y], x)
# %% Question 7
[docs]def ajouteRoute(plan, x, y):
""" (**Question 7**) Modifie le tableau de tableaux ``plan`` pour ajouter une route entre les villes ``x`` et ``y`` si elle n'était pas déjà présente et ne fait rien sinon.
- Le sujet disait *"On prendra garde à bien mettre à jour toutes les cases concernées dans le tableau de tableaux ``plan``"*, ce qui montre bien qu'ils veulent garder le graphe symétrique (cf. explication de la fonction précédente).
- Le sujet demandait *"Y a-t-il un risque de dépassement de la capacité des listes ?"*, et non car on les a initialisé avec une capacité de ``n+1`` (cf. :py:func:`creerPlanSansRoute`),
- Complexité en *temps* : :math:`O(n)` (dans le pire des cas, car on doit alors parcourir toutes les voisines de ``x`` et de ``y``),
- Complexité en *mémoire* : :math:`O(1)` (toujours),
- Exemple :
>>> plan = [[5, 4], [1, 2, None, None, None], [3, 1, 3, 4, None], [1, 2, None, None, None], [2, 2, 5, None, None], [1, 4, None, None, None]] # plan2, cf ci-dessus
>>> affiche("Ce plan a m = ", plan[0][1], " route(s).")
Ce plan a m = 4 route(s).
>>> x = 1; y = 5
>>> affiche(estVoisine(plan, x, y))
False
>>> ajouteRoute(plan, x, y)
>>> affiche("Ce plan a m = ", plan[0][1], " route(s).")
Ce plan a m = 5 route(s).
>>> affiche(estVoisine(plan, x, y))
True
"""
if not estVoisine(plan, x, y):
m = plan[0][1]
# On ajoute deux nouvelles voisines :
ajouteDansListe(plan[x], y) # y voisine de x
ajouteDansListe(plan[y], x) # x voisine de y
# Une route de plus (et pas deux, x -> y et y -> x sont identiques)
plan[0][1] = m + 1
# %% Question 8
[docs]def afficheToutesLesRoutes(plan):
""" (**Question 8**) Affiche à l'écran la liste des routes du plan codé par le tableau de tableaux ``plan``, où chaque route apparaît **exactement** une seule fois.
- Par exemple, pour le graphe codé par le tableau de tableaux de la figure 1, cette procédure affiche à l'écran :
>>> plan = [[5, 4], [1, 2, None, None, None], [3, 4, 1, 5, None], [0, None, None, None, None], [2, 2, 5, None, None], [2, 4, 2, None, None]]
>>> afficheToutesLesRoutes(plan)
Ce plan contient 4 route(s): (1-2) (2-4) (2-5) (4-5)
- Le sujet demandait *"Quelle est la complexité en temps de votre procédure dans le pire cas en fonction de n et m ?*" :
1. Complexité en *temps* : :math:`O(n^3)` (dans le pire des cas, car on doit alors parcourir tous les couples de sommets ``(x, y)``, vérifier à chaque fois s'ils sont connectés en :math:`O(n)`),
2. Note : il me semble possible de pouvoir faire mieux, mais l'algorithme deviendrait bien plus compliqué (sans utiliser :py:func:`estVoisine` mais un parcours malin des listes d'adjacence),
3. Complexité en *mémoire* : :math:`O(m)` (on doit stocker la chaîne de caractère des ``m`` routes ``(i-j)``).
Plan 1 :
.. image:: X_PSI_PT__2015__plan1.png
:scale: 60%
:align: center
Plan 2 :
.. image:: X_PSI_PT__2015__plan2.png
:scale: 60%
:align: center
"""
n = plan[0][0]
m = plan[0][1]
longue_chaine = ""
for x in range(1, n+1):
for y in range(x+1, n+1):
# Prendre y > x assure qu'on ajoute une route (x,y) et (y,x) une seule fois !
if estVoisine(plan, x, y):
# longue_chaine += " ({}-{})".format(x, y)
longue_chaine = longue_chaine + " (" + str(x) + "-" + str(y) + ")"
affiche("Ce plan contient ", m, " route(s):", longue_chaine)
# %% Partie III. Recherche de chemins arc-en-ciel
affiche("Partie III. Recherche de chemins arc-en-ciel")
import random
[docs]def entierAleatoire(k):
r""" (**Préliminaires partie III**) Renvoie un entier aléatoire uniforme entre ``1`` et ``k``.
C'est à dire qu'on a :math:`\mathbb{P}r\{ \mathtt{entierAleatoire}(k) = c \} = 1/k` pour tout entier :math:`c \in \{ 1, \dots, k \}`), exactement comme demandé.
- Elle n'était pas demandée, mais supposée donnée,
- (*Hypothèse*) Complexité en *temps* : :math:`O(1)` (toujours),
- (*Hypothèse*) Complexité en *mémoire* : :math:`O(1)` (toujours),
- C'est exactement :py:func:`random.randint`... renommée en français.
- Exemple :
>>> random.seed(0) # Pas d'aléa ici, pour la reproductibilité de l'exemple
>>> entierAleatoire(10)
7
>>> entierAleatoire(2)
2
- Hypothèse : on suppose pour cette fonction et la suite qu'on dispose d'un "bon" générateur de nombres aléatoires (PRNG, Pseudo-Random Number Generator) qui assure (mathématiquement) que ces entiers sont tous *indépendants*, et que les tirages sont effectivement *identiquement distribués*. Voir `la documentation Python du module random <https://docs.python.org/3/library/random.html#module-random>`_ ou `cette page Wikipédia <https://fr.wikipedia.org/wiki/G%C3%A9n%C3%A9rateur_de_nombres_pseudo-al%C3%A9atoires>`_ pour plus d'informations.
"""
return random.randint(1, k)
# %% Question 9
[docs]def coloriageAleatoire(plan, couleur, k, s, t):
r""" (**Question 9**) Génère un coloriage aléatoire pour le plan ``plan``.
- Prend en argument un plan ``plan`` de ``n`` villes, un tableau ``couleur`` de taille ``n + 1``, un entier ``k``, et deux villes ``s`` et ``t`` (:math:`s,t \in \{ 1, \dots, n \}`),
- Remplit le tableau ``couleur`` avec une couleur aléatoire *uniforme* dans ``\{ 1, \dots, k \}``, choisie *indépendamment* pour chaque ville :math:`i \in \{ 1, \dots, n \} \setminus \{s, t\}`,
- On impose les couleurs ``0`` et ``k + 1`` pour ``s`` et ``t`` respectivement,
- La case ``couleur[0]`` n'est pas utilisée (elle reste égale à ``None``, ou n'importe quelle valeur arbitraire).
- Complexité en *temps* : :math:`O(n)` (toujours),
- Complexité en *mémoire* : :math:`O(n)` (toujours),
- Exemple :
>>> plan = [[5, 4], [1, 2, None, None, None], [3, 1, 3, 4, None], [1, 2, None, None, None], [2, 2, 5, None, None], [1, 4, None, None, None]] # plan2, cf ci-dessus
>>> n = plan[0][0]
>>> couleur = creerTableau(n+1) # Tableau vide
>>> affiche(couleur)
[None, None, None, None, None, None]
>>> k = 2; s = 1; t = 5
>>> random.seed(0) # Pas d'aléa ici, pour la reproductibilité de l'exemple
>>> coloriageAleatoire(plan, couleur, k, s, t)
>>> affiche(couleur)
[None, 0, 2, 2, 1, 3]
"""
couleur[s] = 0
n = plan[0][0]
for i in range(1, n+1):
if i != s and i != t:
# On suppose que entierAleatoire est en O(1) (temps constant)
couleur_aleatoire = entierAleatoire(k)
couleur[i] = couleur_aleatoire
couleur[t] = k+1
# %% Question 10
[docs]def voisinesDeCouleur(plan, couleur, i, c):
r""" (**Question 10**) Crée et renvoie un tableau codant la liste (sans redondance) des villes de couleur ``c`` voisines de la ville ``i`` dans le plan ``plan`` colorié par le tableau ``couleur``.
- Complexité en *temps* : :math:`O(n + m)`. On doit créer en :math:`O(n)` la liste initialement vide des possibles voisines de i de couleurs c. Ensuite, pour chaque ville ``j`` voisine avec ``i``, on doit vérifier si ``couleur[j] = c`` (en temps constant :math:`O(1)`), et le nombre :math:`\delta(i)` de voisines de i est un :math:`O(m)`, cf. :py:func:`estVoisine`,
- Complexité en *mémoire* : :math:`O(n)` (toujours),
- Exemple :
>>> plan = [[5, 4], [1, 2, None, None, None], [3, 1, 3, 4, None], [1, 2, None, None, None], [2, 2, 5, None, None], [1, 4, None, None, None]] # plan2, cf ci-dessus
>>> n = plan[0][0]
>>> couleur = [None, 0, 2, 2, 2, 3] # Un coloriage
>>> i = 2
>>> c = 2
>>> affiche(voisinesDeCouleur(plan, couleur, i, c))
[2, 3, 4, None, None, None]
>>> couleur = [None, 0, 2, 1, 2, 3] # Autre coloriage
>>> i = 4
>>> c = 3
>>> affiche(voisinesDeCouleur(plan, couleur, i, c))
[1, 5, None, None, None, None]
"""
n = plan[0][0]
voisines_de_i_de_couleur_c = creerListeVide(n)
# - Autre idée : pour chaque ville ``j`` de couleurs ``couleur[j] = c``, on doit vérifier si elle est voisine avec ``i``, ce qui est en temps :math:`O(\delta(i))` le nb de voisins de i, cf. :py:func:`estVoisine`, donc en sommant on devrait obtenir la même chose,
# for j in range(1, n+1):
# if i != j and couleur[j] == c and estVoisine(plan, i, j):
# ajouteDansListe(voisines_de_i_de_couleur_c, j)
nb_voisines_de_i = plan[i][0]
for k in range(1, nb_voisines_de_i+1):
j = plan[i][k]
if i != j and couleur[j] == c:
ajouteDansListe(voisines_de_i_de_couleur_c, j)
return voisines_de_i_de_couleur_c
# %% Question 11
[docs]def voisinesDeLaListeDeCouleur(plan, couleur, liste, c):
r""" (**Question 11**) Crée et renvoie un tableau codant la liste (sans redondance) des villes de couleur ``c`` voisines d'une des villes présente dans la liste (sans redondance) ``liste`` dans le plan ``plan`` colorié par le tableau ``couleur``.
- Cette seconde fonction semble compliquée, mais c'est simplement *une union* sur les :math:`i \in \mathtt{liste}` des ``voisinesDeCouleur(plan, couleur, i, c)`` donnée par la fonction d'avant !
- Complexité en *temps* : :math:`O(\# liste \times (n + m))` (pour chaque ville ``k`` de la liste ``liste``, on appelle la fonction précédente :py:func:`voisinesDeCouleur`, qui est en temps :math:`O(n + m)`),
- Complexité en *mémoire* : :math:`O(n)` (toujours),
- Exemple :
>>> plan = [[5, 4], [1, 2, None, None, None], [3, 1, 3, 4, None], [1, 2, None, None, None], [2, 2, 5, None, None], [1, 4, None, None, None]] # plan2, cf ci-dessus
>>> n = plan[0][0]
>>> couleur = [None, 0, 2, 2, 1, 3] # Un coloriage
>>> liste = creerListeVide(n+1) # liste = {} ensemble vide
>>> ajouteDansListe(liste, 1) # liste = {1}
>>> ajouteDansListe(liste, 2) # liste = {1, 2}
>>> c = 2
>>> affiche(voisinesDeLaListeDeCouleur(plan, couleur, liste, c))
[2, 2, 3, None, None, None]
- Dans ces deux exemples, on regarde tous les voisines de ``1`` ou de ``2`` (en fait, ``liste`` représente l'ensemble :math:`\{1,2\}`), et on affiche ceux de couleur ``c = 2`` (soit ``2`` comme voisine de ``1`` et ``3`` comme voisine de ``2``),
- Et ci-dessous, on affiche les voisines de ``1`` ou de ``2`` qui sont de couleur ``c = 1`` (soit uniquement ``4`` comme voisine de ``2``).
>>> c = 1
>>> affiche(voisinesDeLaListeDeCouleur(plan, couleur, liste, c))
[1, 4, None, None, None, None]
.. image:: X_PSI_PT__2015__plan2.png
:scale: 60%
:align: center
"""
# print("voisinesDeLaListeDeCouleur:") # DEBUG
n = plan[0][0]
voisines_des_k_dans_liste_de_couleur_c = creerListeVide(n)
# print("n :", n) # DEBUG
# print("liste :", liste) # DEBUG
for indice_k in range(1, liste[0]+1):
k = liste[indice_k]
voisines_de_k_de_couleur_c = voisinesDeCouleur(plan, couleur, k, c)
# print(" 1:", indice_k, k, voisines_de_k_de_couleur_c) # DEBUG
for indice_j in range(1, voisines_de_k_de_couleur_c[0]+1):
j = voisines_de_k_de_couleur_c[indice_j]
ajouteDansListe(voisines_des_k_dans_liste_de_couleur_c, j)
# print(" 2:", indice_j, j) # DEBUG
return voisines_des_k_dans_liste_de_couleur_c
affiche("Plan de la figure 2 :")
plan3 = [[11, 13],
[2, 2, 6, None, None, None, None, None, None, None, None, None],
[2, 1, 7, None, None, None, None, None, None, None, None, None],
[2, 4, 8, None, None, None, None, None, None, None, None, None],
[2, 3, 8, None, None, None, None, None, None, None, None, None],
[2, 6, 10, None, None, None, None, None, None, None, None, None],
[3, 2, 6, 8, None, None, None, None, None, None, None, None],
[3, 1, 5, 7, None, None, None, None, None, None, None, None],
[4, 3, 4, 7, 9, None, None, None, None, None, None, None],
[2, 8, 11, None, None, None, None, None, None, None, None, None],
[2, 5, 11, None, None, None, None, None, None, None, None, None],
[2, 9, 10, None, None, None, None, None, None, None, None, None],
]
# Les deux lignes suivantes n'étaient pas demandées
affiche("""plan3 = [[11, 13],
[2, 2, 6],
[2, 1, 7],
[2, 4, 8],
[2, 3, 8],
[2, 6, 10],
[3, 1, 5, 7],
[3, 2, 6, 8],
[4, 3, 4, 7, 9],
[2, 8, 11],
[2, 5, 11],
[2, 9, 10],
]
""")
affiche(plan3)
afficheToutesLesRoutes(plan3)
# %% Question 12
[docs]def existeCheminArcEnCiel(plan, couleur, k, s, t):
r""" (**Question 12**) Renvoie ``True`` s'il existe dans le plan ``plan``, un chemin :math:`s \sim v_1 \sim \dots \sim v_k \sim t`, tel que :math:`\mathtt{couleur}[v_j] = j` pour tout :math:`j \in \{ 1, \dots, k\}`, et renvoie ``False`` sinon.
- L'objectif de cette partie est d'écrire une procédure qui détermine s'il existe un chemin de longueur ``k + 2``, allant de ``s`` à ``t``, dont la ``j``-ème ville intermédiaire a reçu la couleur ``j``.
- Complexité en *temps* : :math:`O(n (n+m))`. On fait des appels à la fonction précédente :py:func:`voisinesDeLaListeDeCouleur` (qui était en :math:`O(n+m)`) avec des listes ``liste`` de tailles variables, mais dont la somme ne sera pas plus que le nombre de villes ``n`` (en effet une ville ne peut être qu'une seule fois dans une ``liste``). (C'est ce qu'on appelle une complexité cumulée.)
- Complexité en *mémoire* : :math:`O(n)` (toujours).
.. image:: X_PSI_PT__2015__plan3.png
:align: center
- Premier exemple, avec le plan de la figure 2, qui trouve un chemin arc-en-ciel (de taille ``k = 3``) entre ``s = 6`` et ``t = 4`` : :math:`6 \sim 7 \sim 8 \sim 3 \sim 4` :
>>> plan = [[11, 13], [2, 2, 6], [2, 1, 7], [2, 4, 8], [2, 3, 8], [2, 6, 10], [3, 1, 5, 7], [3, 2, 6, 8], [4, 3, 4, 7, 9], [2, 8, 11], [2, 5, 11], [2, 9, 10]]
>>> s = 6
>>> t = 4
>>> k = 3
>>> couleur = [None, 1, 2, 3, k+1, 1, 0, 1, 2, 3, 3, 1]
>>> affiche(existeCheminArcEnCiel(plan, couleur, k, s, t))
True
- Le même exemple mais dans l'autre sens, qui trouve un chemin arc-en-ciel (de taille ``k = 3``) entre ``s = 4`` et ``t = 6`` : :math:`4 \sim 3 \sim 8 \sim 7 \sim 6` :
>>> plan = [[11, 13], [2, 2, 6], [2, 1, 7], [2, 4, 8], [2, 3, 8], [2, 6, 10], [3, 1, 5, 7], [3, 2, 6, 8], [4, 3, 4, 7, 9], [2, 8, 11], [2, 5, 11], [2, 9, 10]]
>>> s = 4
>>> t = 6
>>> k = 3
>>> couleur = [None, 3, 2, 1, 0, 3, k+1, 3, 2, 1, 1, 3]
>>> affiche(existeCheminArcEnCiel(plan, couleur, k, s, t))
True
- Un autre exemple similaire, qui trouve un aussi chemin arc-en-ciel (de taille ``k = 3``), entre ``s = 11`` et ``t = 7`` : :math:`11 \sim 10 \sim 5 \sim 6 \sim 7` :
>>> plan = [[11, 13], [2, 2, 6], [2, 1, 7], [2, 4, 8], [2, 3, 8], [2, 6, 10], [3, 1, 5, 7], [3, 2, 6, 8], [4, 3, 4, 7, 9], [2, 8, 11], [2, 5, 11], [2, 9, 10]]
>>> s = 11
>>> t = 7
>>> k = 3
>>> couleur = [None, 1, 2, 3, 3, 2, 3, k+1, 2, 1, 1, 0]
>>> affiche(existeCheminArcEnCiel(plan, couleur, k, s, t))
True
- Un autre exemple similaire, qui trouve un aussi chemin arc-en-ciel (de taille ``k = 2``), entre ``s = 11`` et ``t = 7`` : :math:`11 \sim 9 \sim 8 \sim 7` :
>>> plan = [[11, 13], [2, 2, 6], [2, 1, 7], [2, 4, 8], [2, 3, 8], [2, 6, 10], [3, 1, 5, 7], [3, 2, 6, 8], [4, 3, 4, 7, 9], [2, 8, 11], [2, 5, 11], [2, 9, 10]]
>>> s = 11
>>> t = 7
>>> k = 2
>>> couleur = [None, 1, 2, 3, 3, 2, 3, k+1, 2, 1, 1, 0]
>>> affiche(existeCheminArcEnCiel(plan, couleur, k, s, t))
True
- Un autre exemple similaire, qui ne pas trouve de chemin arc-en-ciel (de taille ``k = 3``), car le coloriage est "mauvais" :
>>> plan = [[11, 13], [2, 2, 6], [2, 1, 7], [2, 4, 8], [2, 3, 8], [2, 6, 10], [3, 1, 5, 7], [3, 2, 6, 8], [4, 3, 4, 7, 9], [2, 8, 11], [2, 5, 11], [2, 9, 10]]
>>> s = 11
>>> t = 7
>>> k = 3
>>> couleur = [None, 1, 2, 3, 3, 2, 3, k+1, 2, 1, 1, 0]
>>> # On change la couleur de la ville 6 (qui était dans le chemin arc-en-ciel précédent)
>>> couleur[6] = 1
>>> affiche(existeCheminArcEnCiel(plan, couleur, k, s, t))
False
- Notez que le graphe étant complet, il y a toujours un chemin entre ``s`` et ``t``, mais pas forcément de chemin arc-en-ciel pour un certains ``k``, et ``couleur``.
"""
n = plan[0][0]
# On se lance, en partant de s
liste = creerListeVide(n) # Sommets de couleur 0
ajouteDansListe(liste, s) # Sommets de couleur 0
# Couleur courant 0 (note : c aussi = diamètre de l'exploration courante)
c = 0
# affiche("existeCheminArcEnCiel part de s = ", s, ", va vers t = ", t, " et k = ", k) # DEBUG
# affiche(" Coloriage : couleur = ", couleur) # DEBUG
# affiche(" Au début, liste = ", liste) # DEBUG
while c <= t and not estDansListe(liste, t): # On n'est pas arrivé
c += 1 # On passe à la couleur d'après
# affiche(" Actuellement, c = ", c) # DEBUG
# affiche(" Et liste = ", liste) # DEBUG
# On filtre les voisines des villes dans liste qui sont de couleurs c
bonnes_voisines = voisinesDeLaListeDeCouleur(plan, couleur, liste, c)
# affiche(" Et bonnes_voisines = ", bonnes_voisines) # DEBUG
# Et ou bien on peut continuer à explorer, ou bien on doit arrêter
if bonnes_voisines[0] <= 0:
# On doit s'arrêter
return False
else:
# On peut continuer, et désormais on part des villes suivantes
liste = bonnes_voisines
# On a t dans la liste, donc on a un chemin partant de s jusqu'à t
return True
# %% Partie IV. Recherche de chemin passant par exactement k villes intermédiaires distinctes
affiche("Partie IV. Recherche de chemin passant par exactement k villes intermédiaires distinctes")
# %% Question 13
[docs]def existeCheminSimple(plan, k, s, t):
r""" (**Question 13**) Renvoie ``True`` avec probabilité au moins :math:`1 - 1/e` s'il existe un chemin de ``s`` à ``t`` passant par exactement ``k`` villes intermédiaires toutes distinctes dans le plan ``plan``, et renvoie toujours ``False`` sinon.
- Exécute :math:`k^k` fois la fonction :py:func:`existeCheminArcEnCiel` et renvoie ``True`` dès qu'une de ses exécution a trouvé un coloriage (aléatoire) qui permet de trouver un chemin "arc-en-ciel".
- Complexité en *temps* : :math:`O(k^k n (n+m))`. Dans le pire des cas on fait :math:`k^k = \mathtt{nombre\_executions}` essais avec :py:func:`existeCheminArcEnCiel` qui est en temps :math:`O(n (n+m))` (et générer un coloriage est en temps :math:`O(n)` donc négligeable),
- Note : c'est bien la complexité annoncée, avec :math:`f(k) = k^k` (le nombre d'essai, dépandant uniquement de ``k``) et :math:`g(n,m) = n (n+m)` (la taille du ``plan``).
- Complexité en *mémoire* : :math:`O(n)` (toujours).
.. warning:: C'est un algorithme *probabiliste* !
Il faut garder en tête que cette fonction n'est **pas exacte** mais probabiliste (on parle aussi d'un algorithme *randomisé*, et `c'est un sujet à part entière <https://wikimpri.dptinfo.ens-cachan.fr/doku.php?id=cours:c-1-24&#probabilistic_aspects_of_computer_science_48h_6_ects>`_, voir `cette page par exemple <https://fr.wikipedia.org/wiki/Algorithme_probabiliste>`_ ou `celle-là <https://en.wikipedia.org/wiki/Randomized_algorithm>`_) :
- Si elle dit ``True``, c'est qu'il existe un chemin, et on en est sûr (voir la question d'après pour en trouver un, on dit alors qu'on fournit un *certificat* de réponse), et ça a pris au plus :math:`O(k^k n (n+m))`,
- Si elle dit ``False``, c'est peut-être vrai, avec une bonne probabilité, mais aucune garantie 100% (et ça a pris exactement :math:`O(k^k n (n+m))`).
- S'il existe un chemin, on a une bonne probabilité de le trouver (mais si on le trouve pas ce n'est pas une garantie qu'il n'y en a pas),
- S'il n'y a pas de chemin, on a une bonne probabilité de répondre ``False`` (mais jamais une garantie qu'il n'y en a pas).
.. image:: X_PSI_PT__2015__plan3.png
:align: center
- Un exemple, avec le plan de la figure 2, qui va trouver un chemin arc-en-ciel (de taille ``k = 3``) entre ``s = 6`` et ``t = 4`` : :math:`6 \sim 7 \sim 8 \sim 3 \sim 4`. On peut donc faire confiance à 100% à cette réponse positive !
>>> plan = [[11, 13], [2, 2, 6], [2, 1, 7], [2, 4, 8], [2, 3, 8], [2, 6, 10], [3, 1, 5, 7], [3, 2, 6, 8], [4, 3, 4, 7, 9], [2, 8, 11], [2, 5, 11], [2, 9, 10]]
>>> s = 6
>>> t = 4
>>> k = 3
>>> random.seed(0) # Pas d'aléa ici, pour la reproductibilité de l'exemple
>>> # Ca peut prendre du temps...
>>> affiche(existeCheminSimple(plan, k, s, t))
True
>>> # Mais on n'est pas sûr de cette réponse !
- Un deuxième exemple, avec un plan légèrement modifié inspiré de celui de la figure 2, où on enlève le lien :math:`8 \sim 3`, et donc on ne trouvra pas un chemin arc-en-ciel (de taille ``k = 3``) entre ``s = 6`` et ``t = 4``. Notez qu'avec cette méthode, on ne peut pas faire confiance à 100% à cette réponse négative !
>>> plan = [[11, 12], [2, 2, 6], [2, 1, 7], [1, 4], [2, 3, 8], [2, 6, 10], [3, 1, 5, 7], [3, 2, 6, 8], [3, 4, 7, 9], [2, 8, 11], [2, 5, 11], [2, 9, 10]]
>>> s = 6
>>> t = 4
>>> k = 3
>>> random.seed(0) # Pas d'aléa ici, pour la reproductibilité de l'exemple
>>> # Ca peut prendre du temps...
>>> affiche(existeCheminSimple(plan, k, s, t))
False
>>> # Mais on n'est pas sûr de cette réponse !
- Hypothèse : on dispose d'un bon générateur de nombres aléatoires (PRNG, Pseudo-Random Number Generator) qui assure mathématiquement que ces exécutions sont toutes *indépendantes*, et que les coloriages sont effectivement *uniformément distribués*. Voir `la documentation Python du module random <https://docs.python.org/3/library/random.html#module-random>`_ ou `cette page Wikipédia <https://fr.wikipedia.org/wiki/G%C3%A9n%C3%A9rateur_de_nombres_pseudo-al%C3%A9atoires>`_ pour plus d'informations.
"""
n = plan[0][0]
nombre_executions = k ** k
# affiche("Début de existeCheminSimple(plan, k, s, t)") # DEBUG
# affiche("Avec k = ", k, ", s = ", s, ", t = ", t) # DEBUG
# affiche("On va tenter k**k = ", nombre_executions, " coloriages aléatoires.") # DEBUG
for num_ex in range(nombre_executions):
# On génère un coloriage aléatoire
# affiche(" ", num_ex, " tentative.") # DEBUG
couleur = creerTableau(n+1) # Tableau vide
coloriageAleatoire(plan, couleur, k, s, t)
# affiche(" Coloriage aléatoire = ", couleur) # DEBUG
# On espère qu'il convient pour trouver un chemin arc-en-ciel
if existeCheminArcEnCiel(plan, couleur, k, s, t):
# affiche(" ===> On a trouvé un chemin arc-en-ciel !") # DEBUG
return True
# affiche(" Échec, on continue...") # DEBUG
return False
# %% Question 14
[docs]def question14():
""" (**Question 14**) Le programme à modifier est existeCheminArcEnCiel. En un mot : il faut faire en sorte de garder en mémoire les listes liste successives.
Plus de détails :
- Voici une solution possible pour calculer le chemin, plus détaillée : utiliser un tableau des prédécesseurs ``pred``, permettant de reconstituer le chemin a posteriori.
- Plus précisément : on utilise un tableau ``pred`` à ``n`` cases
tel que pour toute ville ``x``, ``pred[x]`` est le numéro d'une
ville ``y`` reliée à ``x`` et qui précède ``x`` dans un éventuel
chemin de ``s `` à ``t``.
- Ce tableau est créé et complété au fur et à mesure par la fonction :py:func:`existeCheminArcEnCiel` :
lors de chaque appel à la fonction auxiliaire :py:func:`voisinesDeLaListeDeCouleur`
appliquée ``(plan, couleur, liste, j)`` on met à jour le tableau ``pred`` :
pour chaque ville ``x`` de couleur ``j`` voisine d'une ville ``y`` de la liste,
on affecte ``pred[x] = y`` (il y a une route de ``y`` à ``x``, et si le chemin
passe par ``x``, il sera passé par ``y`` juste avant).
(pour cela, on ajoute le tableau ``pred`` dans les arguments de la fonction
auxiliaire :py:func:`voisinesDeLaListeDeCouleur` et celle-ci effectue elle-même la
mise à jour, en même temps qu'elle calcule la nouvelle liste de voisines).
- À la fin, si un chemin est détecté, on le reconstitue
en partant de la fin (c'est classique) grâce au tableau ``pred`` :
``pred[t] = y1``, ``pred[y1] = y2``, ``pred[y2] = y3``, etc,
jusqu'à retomber sur ``s : pred[yk] = s``, alors le chemin est
``s -> yk -> ... -> y2 -> y1 -> t``
(ce chemin est de longueur ``k+2`` par construction).
.. note:: Exemple avec le plan de la figure 2 :
- À la 1e étape, ``liste`` contient ``1, 5, 7`` (les voisins de ``s=6`` de couleur ``1``),
on affecte ``pred[1] = pred[5] = pred[7] = 6``.
- À la 2e étape, ``liste`` contient ``2, 8`` (les voisins de ``1, 5, 7`` de couleur ``2``),
on affecte ``pred[2] = 1`` (ou ``7`` au choix), ``pred[8] = 7``.
- À la 3e étape, ``liste`` contient ``3, 9``,
on affecte ``pred[3] = pred[9] = 8``.
- À la 4e étape, ``liste`` contient ``4``,
on affecte ``pred[4] = 3``.
Pour notre exemple : en partant de la fin (``t=4``) on a
``pred[4] = 3``, ``pred[3] = 8``, ``pred[8] = 7``, ``pred[7] = 6``
le chemin reconstitué est ``6 -> 7 -> 8 -> 3 -> 4``, et on peut vérifier
sur le plan de la figure 2 que c'est bien un chemin valide :
.. image:: X_PSI_PT__2015__plan3.png
:scale: 60%
:align: center
.. note:: Cette fonction ne fait rien, elle donne juste la correction de la dernière question (14) du DS.
"""
pass
# %% Fin de la correction.
if __name__ == '__main__':
from doctest import testmod
print("Test automatique de toutes les doctests écrites dans la documentation (docstring) de chaque fonction :")
testmod(verbose=True)
testmod()
print("\nPlus de détails sur ces doctests sont dans la documentation de Python:\nhttps://docs.python.org/3/library/doctest.html (en anglais)")
# Fin de X_PSI-PT_2015.py