Concours CPGE EPITA-IPSA-ESME 2022
— Option Sciences du Numérique
Consignes Python
Tout code doit être écrit dans le langage Python, à l’exception des requêtes SQL de la section E.
• Veuillez indenter votre code correctement.
• Tout ce dont vous avez besoin (fonctions, méthodes) est indiqué ci-dessous.
• Vous pouvez écrire vos propres fonctions, dans ce cas elles doivent être documentées (on doit savoir ce qu’elles font). Dans tous les cas, la dernière fonction écrite doit être celle qui répond à la question.
Fonctions et méthodes autorisées
• Itérateurs fournis par la fonction range.
• Slicing (extraction de portions) sur les listes.
• La fonction len donne la taille d’une liste.
• Les méthodes utilisables sur les listes sont append et pop, toute autre méthode (insert, sort…) est exclue.
• Fonctions pour les fichiers :
— f=open(fichier, mode) ouvre un « wrapper » vers un fichier.
Le mode peut-être 'r' (lecture), 'w' (écriture) ou 'a' (ajout).
— f.close() ferme le « wrapper ».
— f.write(s) : avec f un tel « wrapper » vers un fichier ouvert en écriture ou ajout, écrit dans le fichier la chaîne de caractères s.
— + : concaténation de chaînes de caractères.
— '\n' : caractère spécial de saut de ligne.
Introduction
Le sujet de l’option informatique contient six sections, reliées par un thème commun.
Les trois dernières sont assez largement indépendantes des trois premières.
Jeu de la vie sur un univers fini
Le jeu de la vie est un automate cellulaire imaginé par John Horton Conway en 1970. Malgré sa définition via des règles très simples, il recèle une incroyable complexité.
Ce sujet en présente une variante, où l’univers est fini.
L’univers considéré est un quadrillage de dimension {N\times N}, mais les cases de la première ligne sont voisines de celles de la dernière, de même que celles de la colonne de droite sont voisines de celles de la colonne de gauche.
Ainsi, chaque case de l’univers possède exactement 8 voisines (voir figure 1), adjacentes horizontalement, verticalement, ou diagonalement.
Chaque case du jeu de la vie est soit vivante, soit morte.
À partir d’une situation initiale au temps {t=0}, la situation du jeu évolue entre les instants {t} et {t+1} en suivant les deux règles suivantes.
— une cellule morte possédant exactement trois cellules voisines vivantes devient vivante (elle naît) ;
— une cellule vivante possédant deux ou trois cellules voisines vivantes le reste, sinon elle meurt.
Représentation en Python. Un univers de taille {N\times N} est représenté par une liste comportant {N} listes toutes de tailles {N}.
La {i}-ème liste de U (c’est-à-dire U[i], pour {0\le i\lt N-1}) représente la {i}-ème ligne de la grille en partant du haut, en faisant démarrer l’indexation à zéro. Les colonnes sont également indexées de {0} à {N-1}.
La case indicée par {(i,j)} (c’est-à-dire U[i][j]) contient un booléen indiquant la présence d’une cellule vivante. La figure suivante montre un univers de taille {4\times4} et sa représentation sous forme de liste de listes.
Dans toute la suite, on désigne par univers une liste de listes U contenant des booléens, qui sera supposée carrée : avec {N} la taille de U, toutes les listes de U ont elles-mêmes une taille {N}. L’entier {N} sera supposé toujours au moins égal à 3.
A.
Évolution de l’univers
La fonction suivante, renvoyant un univers de taille {N\times N} contenant uniquement des cases mortes, pourra être utilisée dans la suite, si nécessaire.
|
1 2 3 4 5 |
def univers_mort(N): L=[] for i in range(N): L.append([False]*N) return L |
random, sans argument, supposée importée, renvoie un réel aléatoire de l’intervalle {[0,1[}.
Écrire une fonction init(N) prenant en entrée un entier strictement positif, et renvoyant un univers {N\times N} (sous forme de liste de listes), chaque case contenant une cellule vivante avec probabilité {1/3}.
Par exemple :
|
1 2 3 |
>>> U = init(4) ; U [[True, False, False, False], [False, False, True, True], [False, False, False, False], [True, False, True, False]] |
nb_cellules_vivantes(U) prenant en entrée un univers U et comptant le nombre de cellules vivantes dans l’univers. Cette fonction ne sera pas utilisée dans la suite.
|
1 2 |
>>> nombre_cellules_vivantes(U) #U est la liste prise en exemple en question 1 5 |
voisins(i,j,N) prenant en entrée 3 entiers avec {0\le i\lt N} et {0\le j\lt N}, et renvoyant la liste des listes de taille 2 d’indices des 8 voisins de {(i,j)} dans un univers {N\times N}.
Remarque : on fera usage du modulo % pour ne pas avoir à traiter à part le cas des cases d’un bord. Par exemple :
|
1 2 |
>>> voisins(2,3,4) [[1, 2], [1, 3], [1, 0], [2, 2], [2, 0], [3, 2], [3, 3], [3, 0]] |
Votre fonction pourra renvoyer ces listes de taille 2 dans un ordre quelconque.
evolue(U) qui prend en argument un univers à un instant {t}, et qui renvoie un nouvel univers, résultat de l’évolution de U entre les instants {t} et {t+1}. Attention : vous ne devez pas modifier U.
|
1 2 3 |
>>> evolue(U) [[True, False, True, False], [False, False, False, True], [False, True, True, False], [False, True, False, True]] |
evolue(U), en fonction de {N}, la taille de U ?B. Période et temps d’attraction
À {N} fixé, l’ensemble des univers possibles est gros, mais fini. Il s’ensuit que lorsqu’on fait évoluer l’univers, à partir d’un certain temps on retombe sur un état déjà atteint. À partir de ce moment, l’évolution est périodique.
Autrement dit, en notant {U_0} l’univers initial, il existe un plus petit {r} tel que l’univers {U_r} réapparaîtra, et un plus petit {p>0} tel que {U_r=U_{r+p}}, qu’on appelle respectivement temps d’attraction et période (voir figure 3).
On souhaite calculer temps d’attraction et période dans la suite. La situation se généralise comme suit : on se donne un ensemble fini {S} et une fonction {f:S\to S}.
Un exemple de telle fonction avec {S=\{0,\ldots,8\}} est donné figure 4, avec le graphe de {f} représenté également (un autre exemple est la fonction evolue, et {S} l’ensemble des univers possibles en taille fixée).
On se donne de plus un élément {u_0} de {S} quelconque. On considère la suite {(u_n)_{n\in\mathbb N}} définie par l’application répétée de {f}, c’est-à-dire {u_{n+1}=f(u_n)} pour tout {n\ge0}.
Comme l’ensemble {S} est fini, la suite ne peut prendre une infinité de valeurs distinctes : à partir d’un certain rang, celle-ci est donc périodique. On note dans la suite {r} le plus petit indice à partir duquel la suite est périodique, et {p} sa période.
Plus précisément, {r} et {p} sont définis comme suit : {\begin{array}{l}r=\min\{n\ge0:\exists k>n,\ u_k=u_n\},\\[8pt]p=\min\{k>0:u_{r+k}=u_r\}.\end{array}}Avec {f} la fonction de la figure 4, on a par exemple :
— si {u_0=7}, les valeurs de la suite sont {7,4,4,4,\ldots}, on a donc {r=p=1} ;
— si {u_0=8}, les valeurs de la suite sont {8,0,6,3,1,6,3,1,6,\ldots}, on a donc {r=2} et {p=3} ;
— si {u_0=1}, les valeurs de la suite sont {1,6,3,1,6,\ldots}, on a donc {r=0} et {p=3}.
indice(L,x) prenant en entrée une liste L et un élément x, et renvoyant le plus petit indice i tel que L[i] = x s’il existe, {-1} sinon.
|
1 2 3 4 |
>>> indice([3, 4, 1, 0], 3) 0 >>> indice([3, 4, 1, 0], 2) -1 |
2. Donner sa complexité en fonction de la taille {n} de la liste, en supposant que le test d’égalité s’effectue en temps constant.
rang_periode(f,u0) prenant en entrée une fonction {f:S\to S} où {S} est un ensemble fini, {u_0\in S}, et renvoyant une liste contenant les entiers {r} et {p} définis ci-dessus. Attention : l’ensemble {S} n’est pas précisé : on sait simplement que {f} est bien une fonction d’un ensemble fini vers lui-même.
On pourra stocker des termes de la suite dans une liste, et utiliser la fonction précédente. Avec f la fonction de l’exemple, on a :
|
1 2 3 4 5 6 |
>>> rang_periode(f,7) [1, 1] >>> rang_periode(f,8) [2, 3] >>> rang_periode(f,1) [0, 3] |
rang_periode(f,u0), en fonction des entiers {r} et {p} calculés.
On suppose qu’un appel à la fonction {f} s’effectue avec une complexité constante, de même que le test d’égalité entre deux éléments de {S}.
C. Calcul efficace : algorithme de Floyd
Pour le jeu de la vie, l’approche précédente demande de stocker en mémoire beaucoup d’univers, si bien qu’elle est inapplicable en pratique dès que {N} est grand.
De plus, les appels à evolue et le test d’égalité sur des univers ont une complexité qui dépend également de l’entier {N}.
On cherche à diminuer à la fois la complexité de la fonction précédente, ainsi que l’espace mémoire utilisé. On propose donc une autre approche. Voici le squelette d’une fonction calculant les entiers {r} et {p}, que l’on va compléter.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
def rang_periode(f,u0): u=u0 v=u0 t=0 """ stocke dans t le plus petit élément non nul de A, dans u la valeur u_t et v la valeur v_t """ while [... à compléter (question 11) ...]: u=f(u) v=f(f(v)) t+=1 """ Ici, t est le plus petit élément non nul de A, u contient u_t, v contient v_t. On calcule p """ [... à compléter (question 12) ...] """ Calcul de r """ u=u0 w=u0 [... à compléter (question 13.1) ...] """ Ici on a w=u_p, u=u_0 """ [... à compléter (question 13.2) ...] return [r,p] |
Dans la suite, vous avez interdiction d’utiliser des listes : le but est de ne stocker qu’un nombre fini d’éléments de {S}.
Compléter la condition de la boucle while du script pour que celle-ci permette de stocker dans la variable t la valeur précédemment définie, ainsi que les valeurs {u_t} dans u et {v_t} dans v.
p.On admet que le premier indice {k} tel que {w_k=u_k} est précisément {r}. 1. Compléter le code (question 13.1) pour stocker dans la variable w la valeur {w_0=u_p}. 2. Enfin, compléter le code (question 13.2), pour stocker dans la variable r la valeur {r} définie dans l’énoncé.
Justifier.
D. Les univers ayant les plus longues périodes
À l’aide des fonctions des sections précédentes, on a pu générer des univers aléatoires, et calculer les périodes des suites démarrant par ces univers.
Ces paires sont stockées sous la forme de listes à 2 éléments [U, p] où U est un univers, et p est la période de la suite de premier terme U. On a construit une liste de telles listes de taille 2. On souhaite la trier par période décroissante.
On veut faire usage du tri fusion, on a pour cela écrit la fonction suivante :
|
1 2 3 4 5 6 7 |
def tri(L): """ Tri d'une liste non vide de listes [U,p] """ if len(L)==1: return [L[0]] else: L1, L2 = separation(L) return fusion(tri(L1), tri(L2)) |
separation(L) prenant en entrée une liste L ayant au moins deux éléments, et renvoyant une liste [L1, L2] avec L1 et L2 de même taille à un élément près, telles que les éléments de L soient répartis dans L1 et L2.fusion(L1, L2), prenant en entrée deux listes contenant des éléments de la forme [U, p], supposées triées par période décroissante, et renvoyant une liste contenant tous les éléments de L1 et L2, triée par période décroissante.
On impose une complexité linéaire en la somme des tailles de L1 et L2.
tri(L) ?E. SQL
On a sélectionné certains univers menant à des situations intéressantes, et regroupé ceux-ci dans une base de données à deux tables.
• La table univers comporte quatre champs de type entier, et un champ de type chaîne de caractères.
— id : identifiant l’univers, c’est la clé primaire de la table ;
— n : l’univers est de taille {n\times n} ;
— p et r : période et rang d’attraction de la suite de premier terme l’univers ;
— nom : un petit nom donné à l’univers, comme 'planeur' ou 'canon'.
• La table cellules comporte également trois champs de type entier :
— idu : un identifiant d’univers, c’est une clé étrangère qui référence le champ id de univers ;
— i et j : servent à référencer les cellules vivantes de l’univers.
Ces tables sont telles qu’un univers d’identifiant id possède en {(i,j)} une cellule vivante si et seulement si (id, i, j) est dans la table cellules.
univers. 2. Donner la liste des couples {(i,j)} d’indices de cellules vivantes de l’univers appelé 'canon'.
On suppose qu’un tel univers est présent dans la table univers et que ce nom est unique. 3. Donner, pour chaque période présente dans univers, le nombre d’univers de la table ayant cette période. 4. Donner la liste des couples d’identifiants d’univers différents de même période et même rang d’attraction.
F. Stockage dans un fichier
On souhaite communiquer nos meilleurs univers à des collègues. Pour cela, il s’agit de les écrire dans des fichiers !
imprime(U, nom), prenant en entrée un univers U et une chaîne de caractères nom (par exemple 'planeur.txt'), et créant un fichier de nom nom dans le répertoire courant, et y écrivant l’univers.
Chaque ligne de l’univers sera associée à une ligne du fichier, on écrira les caractères T et F à la place de True et False, et on séparera les entrées par des points-virgules.
Par exemple, si U vaut
|
1 2 |
[[True, False, False, False], [False, False, True, True], [False, False, False, False], [True, False, True, False]] |
les lignes du fichier seront :
|
1 2 3 4 |
T;F;F;F F;F;T;T F;F;F;F T;F;T;F |
QCM
Ce QCM est un peu particulier : chaque question peut comporter 0, 1, ou plusieurs bonnes réponses ! Cocher une réponse correcte fait gagner des points, cocher une réponse fausse en fait perdre.
Vous gagnez une partie des points sur une question si vous avez coché une réponse correcte et aucune réponse incorrecte, même si vous n’avez pas coché toutes les réponses correctes.
La majorité des questions suivantes sont formulées au singulier ou au pluriel, par commodité pour la grammaire française, mais sans corrélation directe avec le nombre de réponses correctes.
□ Le processeur
□ La carte mère
□ Le clavier
□ L’écran
□ Aucune réponse correcte
□ Le calcul avec des nombres flottants est aléatoire.
□ 0 est représentable exactement comme nombre flottant 64 bits.
□ Le calcul avec des nombres flottants 32 bits produit des erreurs d’arrondis, mais pas avec des flottants 64 bits.
□ Sur 64 bits, additionner 10 fois le flottant 0.1 ne fait pas tout à fait 1.
□ Aucune réponse correcte
□ Pascale Hutton
□ Ada Lovelace
□ Haskell Curie
□ Rust Taylor
□ Cplusplus Lisp
□ Aucune réponse correcte
□ {x(t+h)\simeq hx^{\prime}(t)+x(t)}□ {x(t+h)\simeq x^{\prime}(t)+hx(t)}
□ {x(t+h)\simeq f(x(t),t)+hx(t)}
□ {x(t+h)\simeq hf(x(t),t)+x(t)}
□ Aucune réponse correcte
□ {O(n^2)}
□ {O(n\log n)}
□ {O(n^3)}
□ {O(n)}
□ {O(\log n)}
□ Aucune réponse correcte
□ 1
□ 10
□ 100
□ 1000
□ 10000
□ 100000
□ 1000000
□ Aucune réponse correcte