Le sujet du concours général de NSI (Numérique et sciences informatiques) de cette année a enfin été publié sur le site du ministère. Le concours général concerne les meilleurs élèves de terminale de France, et en mathématiques, les énoncés peuvent être d'une très grande difficulté. Je voulais donc en profiter pour découvrir de quoi il retournait en informatique, et en proposer une correction. Si l'expérience est concluante, pourquoi pas faire la même chose avec d'autres sujets ! Si des erreurs se glissent quelque part, merci de me le signaler.
Le sujet, qui doit être fait en 5h, contient un exercice d'algorithmique et un long problème en plusieurs parties. Lançons-nous sans plus attendre.
Exercice : lancer d’œufs
On s'intéresse à un procédé qui teste la résistance d’œufs lorsqu'on les lance d'un immeuble ; le but étant de déterminer l'étage critique, c'est-à-dire le premier étage d'où l’œuf se casse. Le problème est que la stratégie de détermination va dépendre du nombre \(k\) d’œufs dont on dispose (ils ont tous la même résistance), et du nombre \(n\) d'étages de l'immeuble.
On suppose que l'on dispose d'une fonction python lacher(i) qui lâche un oeuf depuis l'étage \(i\) et renvoie True si et seulement s'il se casse. Elle provoque une erreur s'il ne reste plus d'oeuf disponible.
Question 1
Dans le cas simple où l'on dispose d'un seul oeuf, on nous demande d'implémenter la fonction verif_etage_critique(c) qui vérifie si l'entier \(c\) est bien l'étage critique (avec \(c>1\)).
Nous n'avons pas besoin de parcourir tous les étages pour faire cette vérification : tout ce qu'il faut, c'est vérifier si l'oeuf se casse depuis \(c - 1\), et si ce n'est pas le cas, vérifier s'il se casse depuis \(c\).
def verif_etage_critique(c):
if lacher(c - 1):
return False
return lacher(c)
On fait bien attention à ne pas déclencher d'erreur en testant d'abord pour l'étage inférieur.
Question 2
Dans cette question, nous ne disposons toujours que d'un seul oeuf, et nous devons implémenter la fonction critique_un_seul_oeuf(n) qui détermine cette fois-ci l'étage critique. Nous n'avons pas d'autre choix que de lancer l'oeuf à chaque étage en partant du bas jusqu'à ce qu'il se brise.
def critique_un_seul_oeuf(n):
i = 1
while i <= n:
if lacher(i):
return i
i = i + 1
return n + 1
On renvoie \(n + 1\) si l'étage critique n'existe pas.
Question 3
Autre cas extrême : \(k = n\). Alors nous ne sommes plus limités par le nombre d'oeufs. On va implémenter une méthode dichotomique pour déterminer l'étage critique.
1) Nous pouvons le faire car en-dessous de l'étage critique, l'oeuf ne se casse pas, et il se casse à l'étage critique et ceux au-dessus. On peut donc à chaque lancer éliminer la moitié des étages, selon le résultat du lancer au milieu de deux bornes.
2) À chaque étape le nombre d'étages candidats est réduit au minimum de moitié ; d'où un nombre maximal d'étapes de l'ordre de \(\log_2(n)\).
3) On programme maintenant cette stratégie. Comme d'habitude avec la dichotomie, il faut bien prendre garde aux cas particuliers et aux erreurs d'indice du type "off by one".
def critique_dichotomie(n):
a = 1
b = n
while a <= b:
m = (a + b) // 2
if lacher(m):
b = m - 1
else:
a = m + 1
return b + 1
Nous devons justifier notre choix de renvoyer b + 1 :
- soit
b n'est jamais modifié, auquel cas l'oeuf ne se casse jamais, on renvoie donc bien n + 1.
- soit il l'est ; alors nous savons qu'à chaque étape (c'est un invariant de boucle) l'étage
b + 1 est "cassant" (puisque lacher(m) a renvoyé True pour une certaine valeur de m, qui est égale au b + 1 actuel). Et quand la boucle se termine, c'est que le b actuel n'est pas cassant.
4) Nous prouvons la terminaison de notre fonction par un variant de boucle : à chaque tour de boucle la valeur entière b - a décroît strictement, elle deviendra donc nécessairement strictement négative, et la boucle se terminera.
Question 4
Cette question donne peu d'indications et il peut être plus compliqué de trouver l'algorithme attendu. Il s'agit de montrer qu'on peut déterminer l'étage critique d'un immeuble tel que \(n = p^2\), avec \(k = 2\) oeufs, en un nombre de lancers de l'ordre de \(2p\) seulement.
L'idée est la suivante : que se passe-t-il si on lance un oeuf depuis l'étage \(p\) ?
- Soit il se casse : alors il ne reste que les étages 1 à \(p - 1\) qui peuvent être l'étage critique. La stratégie décrite question 2 pour un oeuf nous donnera l'étage critique en \(p\) lancers maximum au total !
- Soit il ne se casse pas : alors nous avons toujours deux oeufs, et nous relançons le premier depuis l'étage \(2p\). S'il se casse, il ne reste que les étages \(p + 1\) à \(p + p - 1\), sinon, on continue.
Le premier oeuf nous sert donc à couper les \(p^2\) étages en \(p\) intervalles de \(p\) étages, et à déterminer en au plus \(p\) lancers dans quel intervalle l'étage critique se trouve. Une fois cet intervalle trouvé, on trouve avec le deuxième oeuf l'étage critique en maximum \(p\) lancers parmi cet intervalle, avec la stratégie décrite question 2. Il va sans dire que si le premier oeuf ne se casse jamais, il n'y a pas d'étage critique et on renvoie \(n + 1\).
Au total : on réalise bien au maximum \(2p\) lancers.
Question 5
À partir de maintenant, le sujet nous fait implémenter la stratégie dans le cas général, par programmation dynamique. L'énoncé nous donne la sous-structure optimale : s'il reste \(e\) étages à tester et \(r\) oeufs, on note le nombre minimal \(L(e, r)\) de lancers nécessaires au pire cas. On cherche à nous faire établir la relation de récurrence qui caractérise \(L\).
Dans cette question, \(e = n\). On suppose que \(r > 0\) et qu'on lâche un oeuf depuis l'étage \(i\).
1) S'il se casse, alors il reste \(r - 1\) oeufs, et \(i - 1\) étages à tester.
2) Sinon, il reste toujours \(r\) oeufs, et il reste à tester les étages supérieurs, de \(i + 1\) à \(n\), soit \(n - i\) étages.
Question 6
Cette question nous fait établir une relation de récurrence compliquée à première vue, mais qui se comprend bien grâce à la question précédente.
N'oublions pas que \(L(e, r)\) concerne le pire cas. D'après la question 5, si \(r > 0\) et \(e = n\), après un lancer depuis l'étage \(i\), nous sommes dans l'un de deux cas. Le nombre de lancers qu'il reste dans le pire cas est donc la pire des deux valeurs \(L(i - 1, r - 1), L(n - i, r)\), c'est-à-dire le maximum des deux valeurs. Enfin, \(L(n, r)\) est égal au nombre minimal de lancers qu'il reste dans le pire cas après ce lancer depuis un étage \(i\) (le meilleur choix entre 1 et \(n\)), plus 1 pour le lancer en question, et donc on trouve bien la formule pour \(e = n\).
Mais la formule pour tout \(e\) ne diffère absolument pas : en effet, s'il reste \(e\) étages à tester, ils sont forcément contigus ! Si l'on connait le résultat d'un lancer depuis un étage, on connait soit le résultat de tous les étages inférieurs (si l'oeuf ne s'est pas cassé), soit celui de tous les supérieurs (dans le cas contraire). Avoir \(e\) étages restants de \(h + 1\) à \(h + e\) revient donc à déterminer l'étage critique d'un immeuble à \(e\) étages, auquel on rajoute \(h\). Le nombre minimal de lancers à réaliser au pire cas vaut donc :
$$L(e, r) = 1 + min_{i = 1}^{e}max(L(i - 1, r - 1), L(e - i, r))$$
Question 7
Nous devons maintenant mettre la formule précédente en application pour calculer la fonction L algorithmiquement. Nous voyons que la formule se prête à un calcul par une fonction récursive ; le problème étant que nous devons respecter un coût d'exécution en \(re^2\), ce qui demande de ne pas recalculer les solutions déjà rencontrées. En effet, les appels récursifs peuvent se recouper, et exploser de manière exponentielle. Plutôt que mettre en place la mémoïsation, nous allons procéder à une approche "bottom-up" (de bas en haut), ce qui nous permettra dans la question suivante de nous adapter facilement au calcul de la stratégie optimale. Nous stockons nos calculs intermédiaires dans un tableau à deux dimensions ; la question 8 parle également d'un dictionnaire, les deux choix ont leurs avantages.
def L(e, r):
solutions = [[0] * (r + 1)]
for i in range(1, e + 1):
solutions.append([0] * (r + 1))
solutions[i][0] = Infty
# Calcul de bas en haut
for e0 in range(1, e + 1):
for r0 in range(1, r + 1):
m = max(solutions[0][r0 - 1], solutions[e0 - 1][r0]) # = solutions[e0 - 1][r0]
for i in range(2, e0 + 1):
x = max(solutions[i - 1][r0 - 1], solutions[e0 - i][r0])
if x < m:
m = x
solutions[e0][r0] = 1 + m
return solutions[e][r]
Il faut faire attention à plusieurs choses dans l'écriture de cette fonction : outre les erreurs faciles d'indices, il faut s'assurer que toutes les valeurs nécessaires (dont on dépend) ont été mises à jour lors du calcul de solutions[e0][r0]. Ici, c'est bien le cas, car toutes les positions que l'on regarde dans le tableau ont soit leur indice de colonne égal à r0 - 1, soit égal à r0, avec un indice de ligne strictement inférieur à e0. Grâce à notre ordre de parcours dans les deux boucles imbriquées (e0 et r0 croissants), nous ne faisons pas d'erreur.
Par ailleurs, nos trois boucles imbriquées ont bien une complexité de l'ordre de \(re^2\).
Question 8
La fonction précédente s'adapte simplement pour garder une trace du meilleur choix de i à chaque instant : à notre recherche de minimum, nous ajoutons une trace de l'indice qui réalise le minimum et l'ajoutons à un autre tableau à deux dimensions.
def Lprec(e, r):
solutions = [[0] * (r + 1)]
prec = [[0] * (r + 1)]
for i in range(1, e + 1):
solutions.append([0] * (r + 1))
prec.append([0] * (r + 1))
# les cas de base ne nous intéressent pas dans prec mais nous les gardons pour que
# les indices correspondent
solutions[i][0] = Infty
for e0 in range(1, e + 1):
for r0 in range(1, r + 1):
m = solutions[e0 - 1][r0]
indm = 1
for i in range(2, e0 + 1):
x = max(solutions[i - 1][r0 - 1], solutions[e0 - i][r0])
if x < m:
m = x
indm = i
solutions[e0][r0] = 1 + m
prec[e0][r0] = indm
return prec
Question 9
C'est le moment d'utiliser l'ensemble des résultats précédents pour implémenter la stratégie optimale dans la détermination de l'étage critique ! Nous allons suivre le conseil du sujet qui recommande d'écrire une fonction récursive qui prend pour paramètres le plus bas et le plus haut des étages encore considérés. Nous nous servirons de plus de la matrice de précédence calculée plus haut pour trouver à chaque instant le meilleur choix dans le pire des cas.
def strategie(prec, n, k):
def strat_rec(prec, k, niv_bas, niv_haut):
# Cas de base
if niv_bas == niv_haut:
if lacher(niv_bas):
return niv_bas
else:
return niv_haut + 1
# Cas récursif
i = prec[niv_haut - niv_bas + 1][k]
if lacher(niv_bas + i): # il faut respecter le décalage
return strat_rec(prec, niv_bas, niv_bas + i - 1, k - 1)
else:
return strat_rec(prec, niv_bas + i + 1, niv_haut, k)
return strat_rec(prec, k, 1, n)
On ne nous demande pas de prouver la terminaison de notre fonction : on pourrait noter que niv_haut - niv_bas décroît strictement dans les appels récursifs.
Conclusion
Cet exercice me semble avoir la dose parfaite de difficulté : les fonctions peuvent être assez subtiles, entre les possibles erreurs d'indices et de "off by one", mais les questions les plus coriaces viennent avec des conseils et des rappels, de sorte qu'on peut éviter les erreurs les plus dommageables.
Problème : données en trois dimensions
Le problème étudie différentes manières de représenter des données en trois dimensions. Dans cette première partie, le sujet fait calculer des fonctions sur des représentations sous forme de cubes de côté 1, nommés "voxels".
Question 10
La première fonction doit simplement calculer les 6 faces d'un voxel, donné sous la forme de son sommet aux coordonnées les plus petites :
def faces(voxel):
x, y, z = voxel
faces = []
# faces à z constant
faces.append([(x, y, z), (x + 1, y, z), (x + 1, y + 1, z), (x, y + 1, z)])
faces.append([(x, y, z + 1), (x + 1, y, z + 1), (x + 1, y + 1, z + 1), (x, y + 1, z + 1)])
# faces à y constant
faces.append([(x, y, z), (x + 1, y, z), (x + 1, y, z + 1), (x, y, z + 1)])
faces.append([(x, y + 1, z), (x + 1, y + 1, z), (x + 1, y + 1, z + 1), (x, y + 1, z + 1)])
# faces à x constant
faces.append([(x, y, z), (x, y + 1, z), (x, y + 1, z + 1), (x, y, z + 1)])
faces.append([(x + 1, y, z), (x + 1, y + 1, z), (x + 1, y + 1, z + 1), (x + 1, y, z + 1)])
return faces
Rien de compliqué, si ce n'est de ne pas faire d'erreur dans l'écriture des coordonnées des faces (données sous la forme d'un tableau de 4 sommets, dans l'ordre).
Question 11
Dans cette question, étant donné un volume représenté par un tableau de voxels, nous devons compter le nombre de faces visibles de ce volume. Par exemple, deux voxels côte à côte ne présentent que 10 faces visibles et pas 12.
Pour cela, il suffit d'une fonction quadratique en le nombre de voxels. Nous écrivons d'abord une fonction auxiliaire permettant de tester l'égalité entre deux faces :
def faces_egales(f1, f2):
f1.sort()
f2.sort()
return f1[0] == f2[0] and f1[2] == f2[2]
Si les faces sont triées, l'égalité équivaut en effet à avoir deux sommets égaux autour d'une diagonale de la face (on pourrait simplement tester l'égalité de tous les sommets une fois les faces triées).
Nous comptons ensuite le nombre de faces visibles, en regardant, pour chaque face de chaque voxel, si un autre voxel possède la même face, et en la comptant seulement si ce n'est pas le cas.
def nb_faces_visibles(volume):
compte = 0
for i in range(len(volume)):
faces1 = faces(volume[i])
for f1 in faces1:
vis = True
for j in range(i):
faces2 = faces(volume[j])
for f2 in faces2:
if faces_egales(f1, f2):
vis = False
if vis:
compte += 1
return compte
La taille d'un tableau représentant une face étant fixée à 4, notre compte se fait bien en un temps quadratique, à cause de nos deux boucles imbriquées parcourant l'ensemble des voxels.
Comme l'énoncé nous le demande, nous pourrions rendre notre fonction linéaire en parcourant les faces de chaque voxel, et stockant les faces rencontrées dans un ensemble (set()). En effet, le test d'appartenance à un ensemble est constant, et un seul parcours linéaire suffirait donc.
Question 12
Une géode est un volume connexe possédant un trou unique en son centre. L'énoncé nous demande pourquoi connaître la surface externe suffit à connaître la surface interne : comme nous pouvons calculer le nombre total de faces visibles, nous pouvons en effet retrouver la surface interne en ôtant la surface externe à ce total.
Question 13
Autre question simple, qui nous fait déterminer une face externe à partir d'un voxel de plus petite coordonnée x0 sur x. J'insiste sur un voxel, car contrairement à ce que sous-entend le sujet ce voxel n'est pas forcément unique. En l'occurence, si un tel voxel est représenté sous la forme (x0, y0, z0), alors la face [(x0, y0, z0), (x0, y0 + 1, z0), (x0, y0 + 1, z0 + 1), (x0, y0, z0 + 1)] (à x constant) est nécessairement visible (et externe). Si elle ne l'était pas, il existerait un voxel en x0 - 1.
Question 14
Dans la suite, nous considérons une structure de graphe sur les faces visibles : deux faces sont connectées si elles partagent une arête.
Que peut-on dire de l’ensemble des faces accessibles dans ce graphe depuis une face de la surface externe ?
Le sujet passe un peu vite sur la notion de volume connexe : cela veut-il dire que tous les voxels possèdent une face en commun avec un autre ? C'est ce que nous supposons d'après cette question, et les dessins du sujet.
Dans ce cas, l'ensemble des faces accessibles est précisément l'ensemble des faces de la surface externe.
En revanche, si le fait que le volume soit connexe concerne les arêtes en commun, il y a un problème. On pourrait alors connecter surface externe et interne dans le graphe ! Je laisse le lecteur trouver un exemple.
Question 15
D'après la question précédente, un parcours (par exemple en profondeur) partant de la face externe décrite question 13 permettrait de trouver toute sa composante connexe, et donc de trouver l'ensemble des faces de la surface externe.
Question 16
Cette question à la formulation simple demande de mettre en place le calcul que nous venons de décrire. En revanche, il reste encore plusieurs tâches à remplir dans le cheminement :
-
Nous ne connaissons pas encore toutes les faces visibles ; il faut modifier la fonction nb_faces_visibles en une fonction faces_visibles qui construit un tableau contenant les faces, au lieu de simplement renvoyer leur nombre.
-
Le graphe reste à construire ; nous n'avons pas de contrainte de coût, nous allons donc le créer en un temps quadratique en le nombre de faces. Nous programmons d'abord une fonction qui teste si deux faces possèdent une arête en commun :
def arete_commun(f1, f2):
f1.sort()
f2.sort()
for k in range(4):
for j in range(4):
if f1[k] == f2[j] and f1[(k + 1) % 4] == f2[(j + 1) % 4]:
return True
return False
Nous nous basons encore une fois sur un tri des faces pour simplifier les tests.
- Nous pouvons enfin calculer la surface externe d'une géode avec un parcours. Notre fonction comporte 4 étapes : construire le graphe en un temps quadratique, sous forme de listes d'adjacence, rechercher une face externe comme décrit question 13 par recherche de minimum, retrouver linéairement l'indice de cette face dans le tableau des faces visibles, et enfin implémenter le parcours proprement dit avec une pile. Nous retournons bien à la fin le nombre des faces visibles visitées lors du parcours.
def surface_externe(geode):
faces = faces_visibles(geode)
# Construction du graphe
n = len(faces)
graphe = [[] for i in range(n)]
for i in range(n):
for j in range(i):
if arete_commun(faces[i], faces[j]):
graphe[i].append(j)
graphe[j].append(i)
# Recherche d'une face externe
x0 = 10 ** 10
for x, y, z in geode:
if x < x0:
x0 = x
# Indice de la première face
f0 = [(x0, y0, z0), (x0, y0 + 1, z0), (x0, y0 + 1, z0 + 1), (x0, y0, z0 + 1)]
f0.sort()
ind0 = 0
while ind0 < n:
faces[ind0].sort()
if f0 == faces[ind0]:
break
ind0 += 1
# Parcours en profondeur
visites = set(ind0)
pile = [ind0]
while len(pile) > 0:
ind = pile.pop()
for j in graphe[ind]:
if j not in visites:
visites.add(j)
pile.append(j)
return len(visites)
La construction du graphe reste l'étape la plus coûteuse, et rend notre calcul quadratique en le nombre de voxels. Une amélioration possible serait de trier le tableau des faces visibles dans un certain ordre afin de réduire l'espace de recherche des faces voisines.
Question 17
En vue de programmer une sorte de jeu de la vie à trois dimensions, nous devons ici calculer les 26 voxels voisins d'un voxel donné. Rien de compliqué avec trois boucles imbriquées, sans oublier d'exclure le voxel lui-même du calcul de ses voisins.
def voisins(voxel):
x, y, z = voxel
vois = []
for dx in range(-1, 2):
for dy in range(-1, 2):
for dz in range(-1, 2):
if dx != 0 or dy != 0 or dz != 0:
vois.append((x + dx, y + dy, z + dz))
return vois
Question 18
Nous devons ici programmer une étape de ce "jeu de la vie", en renvoyant le tableau des voxels actifs modifié après une étape. Nous commençons par construire un dictionnaire, permettant de compter le nombre de voisins actifs de tous les voxels pouvant être activé au tour suivant (actif ou voisin d'un actif). La construction du nouveau tableau se fait simplement à partir de ce dictionnaire, en appliquant les règles.
def evolution(actifs):
# Compte du nombre de voisins actifs de tous les voxels concernés
nvois = {}
est_actif = set()
for voxel in actifs:
est_actif.add(voxel)
for voisin in voisins(voxel):
if voisin in nvois:
nvois[voisin] += 1
else:
nvois[voisin] = 1
# Construction du nouveau tableau des actifs
nouv_actifs = []
for vox, nv in nvois.items():
if (vox in est_actif and nv == 2) or (nv == 3):
nouv_actifs.append(vox)
return nouv_actifs
Nous avons par ailleurs reconstruit le tableau des actifs dans un ensemble, ce qui permet de vérifier si un voxel est actif en temps constant et d'assurer un coût total linéaire à notre fonction.
Question 19
Ici commence la deuxième partie, où l'on s'intéresse à une représentation des volumes non plus par des voxels mais par un maillage constitué de polygones. On manipule des coordonnées flottantes ; cette question nous demande de rappeler que le test d'égalité entre deux flottants n'offre pas de garantie d'exactitude, comme dans le cas 0.1 + 0.2 == 0.3. On vérifie d'ordinaire plutôt si la différence entre les deux nombres considérés est inférieure à un certain seuil acceptable. Heureusement, nous pouvons oublier ce problème dans la suite.
Question 20
Retour à des fonctions plus terre-à-terre : nous devons calculer l'ensemble des faces possédant un sommet d'indice donné.
def faces_adjacentes_sommet(F, p):
adj = []
for i, face in enumerate(F):
if p in face:
adj.append(i)
return adj
Question 21
Rien de compliqué non plus dans la généralisation à une face ; attention cependant à ne pas ajouter plusieurs fois une face qui aurait deux sommets communs avec la nôtre.
def faces_adjacentes_cote(F, k):
adj = []
for i, face in enumerate(F):
for p in F[k]:
if p in face:
adj.append(i)
break
return adj
Question 22
Le coût de faces_adjacentes_sommet est en \(ns\) ; et faces_adjacentes_cote est en \(ns^2\), où \(n\) est le nombre de faces dans F et s le plus grand nombre de sommets sur une face.
Question 23
Pour réduire la complexité du calcul des faces adjacentes, on va trianguler les faces, c'est-à-dire les diviser en triangles. On nous demande dans cette question de calculer une représentation équivalente d'une surface en trois dimensions, sous forme de faces triangulaires uniquement.
La formulation du sujet oublie une précision cruciale : on ne sait pas si les faces sont convexes. La triangulation d'un polygone quelconque est un problème vaste en soi, et au vu des indications du sujet, j'ai supposé pour cette question que les faces considérées étaient convexes, c'est-à-dire qu'on peut relier n'importe quelle paire de sommets sans "sortir" de la figure. C'est le cas du pentagone de l'exemple, mais pas d'une étoile à 5 branches. De toute façon, au vu de la signature de la fonction demandée, nous ne connaissons pas les coordonnées des sommes considérés, et il serait donc impossible de déterminer une triangulation. Dans le cas plus général en effet, on ne sait pas a priori où est l'intérieur du polygone. La méthode des oreilles décrite dans l'article ci-dessus serait une option.
Notre méthode pour trianguler un polygone convexe est très simple : d'un sommet, on peut relier tous les autres sommets, ce qui découpe bien la figure en triangles.
def triangule(F):
triangles = []
for face in F:
s0 = face[0]
for i in range(2, len(face)):
triangles.append([face[0], face[i - 1], face[i]])
return triangles
Question 24
On considère maintenant une description des surfaces par des demi-arêtes, en programmation objet. Les demi-arêtes servent à distinguer l'intérieur et l'extérieur des surfaces. Il y a beaucoup de nouveau code à comprendre, mais cette première question part d'un exemple simple.
1) Sur le dessin, nous pouvons accéder à l'arête b avec l'expression suivante : a.suivant.suivant.miroir.suivant.suivant.miroir.suivant.miroir.suivant.suivant. L'opération miroir sur une arête séparant deux faces nous fait en effet "basculer" dans l'autre face possédant cette arête, dans le sens anti-horaire. Nous devons ici faire trois changements de face.
2) Plus simplement, on accède à la face f : a.suivant.suivant.miroir.suivant.suivant.miroir.face.
Question 25
Nous devons vérifier si les conditions de validité définies pour faces et sommets sont bien vérifiées :
def valide_sommet(somm):
return somm.darete is not None and somm.darete.source == somm
def valide_face(f):
return f.darete is not None and f.darete.face == f
Nous prenons bien soin de vérifier la définition des attributs avant d'accéder à leurs champs, avec l'évaluation paresseuse des booléens. Nous n'avons pas ici à vérifier les conditions intérieur/extérieur.
Question 26
De même, nous devons vérifier la validité des demi-arêtes.
def valide_darete(dar):
if dar.miroir is None:
return False
if dar.miroir.source != dar.but or dar.miroir.but != dar.source:
return False
debut = dar.source
fin = dar.but
face = dar.face
while dar.but != debut:
if dar.face != face:
return False
if dar.suivant is None or dar.but != dar.suivant.source:
return False
dar = dar.suivant
return dar.but == fin
Il faut bien vérifier qu'il existe un cycle bien défini de demi-arêtes appartenant à la même face, ce que nous faisons ici.
Question 27
La structure des demi-arêtes étudiées, munies de l'attribut suivant, définit une structure de liste circulaire.
Question 28
Nous allons supposer que tout est bien valide, et renvoyer le tableau de toutes les faces partageant une demi-arête avec une face donnée. Pour rappel, on peut changer de face grâce à l'attribut miroir.
def faces_voisines(f):
dar = f.darete
debut = dar.source
voisins = []
while dar.but != debut:
dar = dar.suivant
voisins.append(dar.miroir.face)
return voisins
Question 29
Nous devons maintenant calculer la composante connexe d'une face donnée ; à l'aide de la fonction précédente, nous allons implémenter un parcours en profondeur à l'aide d'une pile. Une difficulté est de pouvoir maintenir l'ensemble des faces déjà visitées, puisque les objets Face sont mutables et ne peuvent donc pas être stockés tels quels dans des ensembles. Plusieurs possibilités s'offrent à nous : nous pourrions augmenter les structures de données afin d'offrir un identifiant entier à chacune des faces, et donc de pouvoir stocker ces entiers dans un ensemble des faces visitées. Nous allons plutôt utiliser un tableau des faces déjà visitées, ce qui est plus coûteux, car vérifier si une face donnée a été visitée aura un coût linéaire dans le pire cas. Nous pourrons ensuite simplement renvoyer ce tableau des éléments visités.
def composante_connexe(f):
visites = [f]
pile = [f]
while len(pile) > 0:
f = pile.pop()
voisins = faces_voisines(f)
for face in voisins:
if face not in visites:
visites.append(f)
pile.append(f)
return visites
Notre fonction a donc un coût au pire cas quadratique en le nombre de faces.
Question 30
Cette fois-ci, nous devons séparer une face en deux, tout en gardant la validité des objets.
def separe_face(f, a, b):
# Création des nouveaux objets
nouv_dar = Darete(a, b, f)
f.darete = nouv_dar
nouv_face = Face()
nouv_dar_mir = Darete(b, a, nouv_face)
nouv_face.darete = nouv_dar_mir
nouv_dar_mir.miroir = nouv_dar
nouv_dar.miroir = nouv_dar_mir
# Reconnexion avec les demi-arêtes existantes
dar_a = a.darete
dar_b = b.darete
nouv_dar.suivant = dar_b
nouv_dar_mir.suivant = dar_a
while dar_b.but != a:
dar_b = dar_b.suivant
dar_b.suivant = nouv_dar
while dar_a.but != b:
dar_a.face = nouv_face
dar_a = dar_a.suivant
dar_a.face = nouv_face
dar_a.suivant = nouv_dar_mir
return nouv_dar
Nous avons pris soin de bien définir tous les objets :
-
création des deux demi-arêtes a -> b et b -> a ;
-
création d'une nouvelle face, pour laquelle la demi-arête b -> a est intérieure ;
-
il faut raccorder les demi-arêtes préexistantes, partant et arrivant de a et b, afin de préserver deux structures circulaires.
-
enfin, il faut modifier la face associée aux demi-arêtes du même cycle que b -> a.
Question 31
Dans ces deux dernières questions, on manipule une base de données sur les objets considérés.
Dans le schéma proposé, les clés primaires pour chacune des tables sont leur attribut id. Par ailleurs, les attributs darete des deux tables sommet et face sont une clé étrangère vers la table demiarete ; de même, les attributs source et but de la table demi-arête sont des clés étrangères vers sommet, et face vers la table du même nom.
Question 32
Il nous reste à sérialiser les données, c'est-à-dire les insérer dans la base de données. Il est important de vérifier que les identificateurs sont bien définis, tout comme les clés étrangères à la fin de toutes les insertions. Les requêtes étant des chaînes de caractères, nous allons devoir faire quelques opérations sur les chaînes afin d'exprimer les requêtes de manière efficace. Cela se fait simplement avec des chaînes formatées.
Nous commençons par ajouter des identifiants directement dans les objets Python : cela permettra d'ajouter une fois pour toutes les entrées dans la base avec leurs champs complets.
def serialise(S, F, A):
for i, s in enumerate(S):
s.id = i
for i, f in enumerate(F):
f.id = i
for i, dar in enumerate(A):
dar.id = i
request_sommets = "INSERT INTO sommet VALUES "
for i in range(len(S) - 1):
s = S[i]
request_sommets += f"({s.id}, {s.x}, {s.y}, {s.z}, {s.darete.id}), "
s = S[len(S) - 1]
request_sommets += f"({s.id}, {s.x}, {s.y}, {s.z}, {s.darete.id});"
sql_execute(request_sommets)
request_faces = "INSERT INTO face VALUES "
for i in range(len(F) - 1):
f = F[i]
request_faces += f"({f.id}, {f.darete.id}), "
f = F[len(F) - 1]
request_faces += f"({f.id}, {f.darete.id});"
sql_execute(request_faces)
request_daretes = "INSERT INTO demiarete VALUES "
for i in range(len(A) - 1):
dar = A[i]
request_daretes += f"({dar.id}, {dar.source.id}, {dar.but.id}, {dar.face.id}, {dar.miroir.id}, {dar.suivant.id}), "
dar = A[len(A) - 1]
request_daretes += f"({dar.id}, {dar.source.id}, {dar.but.id}, {dar.face.id}, {dar.miroir.id}, {dar.suivant.id});"
sql_execute(request_aretes)
return
Notons qu'à cause du caractère immuable des chaînes dans Python, nos concaténations ne sont pas très efficaces. Si on voulait vraiment l'être, on pourrait utiliser la méthode join.
Conclusion
Le problème est assez difficile, car il y a un grand nombre de fonctions dont l'écriture sur feuille doit s'avérer fastidieuse. Heureusement, on ne s'aventure jamais trop loin conceptuellement, car de nouvelles représentations sont introduites assez souvent. Cependant dans un contexte d'épreuve il peut être exigeant de devoir régulièrement comprendre de nouvelles structures de données. Par ailleurs, certaines complexités sont difficiles à atteindre, et le sujet demande une très bonne maîtrise des structures de données du type ensemble/dictionnaire.
En définitive, le sujet de ce concours général est très programmatoire, et demande de savoir écrire du code Python vite et bien. Certaines questions demandent une grande rigueur, voire une qualité de décomposition en sous-problèmes pour certaines questions où la démarche est peu détaillée, comme la question 16. J'ai aimé l'exploration de différents algorithmes et structures de données pour modéliser des problèmes très concrets, ce qui permettra aux plus curieux de se renseigner sur les logiciels de modélisation 3D comme Blender ; et je trouve que l'énoncé arrive à exploiter des algorithmes utilisés régulièrement en NSI (comme la recherche de minimum ou la recherche dichotomique) en leur apportant des modifications significatives, qui poussent l'élève à prendre du recul.
Je me lancerai peut-être dans les sujets 2022 et 2023 si j'en trouve le temps !