Code source de X_PSI_PT__2015

#! /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