Sujet du CAPES 2017, épreuve d'informatique¶
Problème 2 - Enveloppe convexe¶
Source: http://www4.ac-nancy-metz.fr/capesmath/data/uploads/EP1_Info_2017.pdf
N.B.: Ceci ne représente ni LA solution ni LE corrigé de cette épreuve mais uniquement la façon avec laquelle je répondrais à une telle série d'exercices.
Partie A - Préliminaires¶
In [1]:
from math import sqrt
Question 1¶
Écrire en Python une fonction distance prenant en arguments deux points P et Q du plan et renvoyant
la valeur de la distance euclidienne entre ces deux points.
In [2]:
# Q.1
def distance(p, q):
""" Renvoie la distance euclidienne entre deux points du plan. """
return sqrt((p[0] - q[0])**2 + (p[1] - q[1])**2)
Question 2¶
Un élève a écrit une fonction qui prend en argument un nuage de points de taille supérieure à 2 et qui détermine la distance minimale entre deux points de ce nuage. Voici le code de son programme en Python:
def distance_minimale(L):
n = len(L)
minimum = distance(L[0],L[1])
i,j=0,0
while i < n:
while j < n:
a = distance(L[i],L[j])
if a < minimum:
minimum = a
j +=1
i +=1
return minimum
2.a Combien d’appels à la fonction distance sont effectués par cette fonction ?¶
2.b Quelle est la valeur renvoyée par cette fonction distance_minimale ?¶
2.c Corriger le programme de l’élève afin que la fonction distance_minimale soit correcte.¶
In [3]:
# Q.2a
# n**2 + 1
# Q.2b
# 0 car il y aura distance(L[i], L[i]) à un moment, donc 0
# Q.2c
def distance_minimale(L):
""" Renvoie la plus petite distance entre chaque paire de points distincts du nuage. """
n = len(L)
minimum = distance(L[0], L[1])
i, j = 0, 0
while i < n:
while j < n:
if j != i:
a = distance(L[i], L[j])
if a < minimum:
minimum = a
j += 1
i += 1
return minimum
In [4]:
distance_minimale([[0, 0], [1, 1], [3, 0]])
Out[4]:
Question 3¶
Écrire une fonction distance_maximale qui prend en argument un nuage de points L et qui renvoie
la distance maximale entre deux points du nuage L en effectuant exactement $n(n − 1)/2$
appels à la fonction distance.
La fonction distance_maximale renverra également les indices d’un couple de
points réalisant le maximum voulu. Par exemple:
>>> distance_maximale(L)
(0.9243140331952826, 1, 8)
Dans le nuage de points L donné en argument, la distance $P_1P_8$ est égale à 0.9243140331952826 qui est la distance maximale obtenue.
In [5]:
# Q.3
def distance_maximale(L):
""" Renvoie la distance la plus grande entre chaque paire de points, ainsi que les indices de ces points. """
n = len(L)
maximum = -1
for i in range(n):
for j in range(i+1, n):
a = distance(L[i], L[j])
if a > maximum:
maximum = a
indices = [i, j]
return maximum, indices[0], indices[1]
In [6]:
distance_maximale([[0, 0], [1, 1], [3, 0]])
Out[6]:
Question 4¶
Écrire une fonction point_abs_min qui prend en paramètre un nuage de points L et qui renvoie l’indice
du point de plus petite abscisse parmi les points du nuage de L. Si plusieurs points ont une abscisse
minimale alors la fonction renverra parmi ces points, l’indice du point d’ordonnée minimale. Préciser
la complexité temporelle de votre fonction lorsque le nuage est composé de n points.
In [7]:
# Q.4
def point_abs_min(L):
""" Renvoie l'indice du point d'abscisse minimal (et d'ordonnée minimale en cas d'égalité). """
# compléxité en O(n)
minimum = L[0]
indice = 0
for i, p in enumerate(L[1:], 1): # évite un for i in range(len(L)) puis p = L[i]
if p[0] < minimum[0]:
minimum = p
indice = i
elif p[0] == minimum[0]:
if p[1] < minimum[1]:
minimum = p
indice = i
return indice
In [8]:
point_abs_min([[0, 0], [-1, 1], [3, 0]])
Out[8]:
Question 6¶
Écrire une fonction orientation qui prend en arguments 3 points du plan P, Q et R et qui renvoie
1 si le triplet (P, Q, R) est en sens direct, 0 si le triplet (P, Q, R) est un alignement, et -1 si le triplet
(P, Q, R) est en sens indirect.
In [9]:
# Q.6
def orientation(p, q ,r):
""" Renvoie 1 si le triplet (P, Q, R) est en sens direct,
0 si le triplet (P, Q, R) est un alignement,
et -1 si le triplet (P, Q, R) est en sens indirect. """
v_pq = (q[0] - p[0], q[1] - p[1]) # vecteur PQ
v_pr = (r[0] - p[0], r[1] - p[1]) # vecteur PR
det = v_pq[0]*v_pr[1] - v_pq[1]*v_pr[0] # le déterminant des deux vecteurs
if det > 0:
return 1
if det < 0:
return -1
return 0
In [10]:
# test du cas direct
orientation([0, 0], [2, 1], [-1, 2])
Out[10]:
In [11]:
# test du cas indirect
orientation([0, 0], [-1, 2], [2, 1])
Out[11]:
In [12]:
# test du cas des points alignés
orientation([0, 0], [1, 1], [2, 2])
Out[12]:
Question 7¶
la fonction tri_bulle ci-dessous prend en argument une liste L de nombres flottants et en effectue le
tri en ordre croissant:
def tri_bulle(L):
n = len(L)
for i in range(n):
for j in range(n-1,i,-1):
if L[j]<L[j-1]:
L[j],L[j-1]=L[j-1],L[j] # échange d’éléments
In [13]:
# Q.7
def tri_bulle(L, debug=False):
""" Tri (en place) une liste par l'algorithme du tri à bulle. """
n = len(L)
for i in range(n):
for j in range(n-1, i, -1):
if L[j] < L[j - 1]:
L[j], L[j - 1] = L[j - 1], L[j] # échange d’éléments
if debug:
print(L)
Q.7a¶
Lors de l’appel tri_bulle(L) où L est la liste [5,2,3,1,4], donner le contenu de la liste L à la
fin de chaque itération de la boucle for i in range(n):.
In [14]:
# Q.7a
tri_bulle([5, 2, 3, 1, 4], True)
Question 8¶
Soit la fonction tri_fusion suivante:
In [15]:
# Q.8
def tri_fusion(L):
""" Fonction qui prend en argument une liste L de nombres flottants
et qui trie cette liste
"""
n = len(L)
if n <= 1:
return L
else:
m = n // 2
return fusion(tri_fusion(L[:m]), tri_fusion(L[m:]))
Q.8a¶
Écrire une fonction fusion qui prend en arguments deux listes triées L1 et L2 et qui renvoie une
seule liste triée contenant les éléments de L1 et L2.
La fonction fusion devra avoir une complexité en $O(n_1 + n_2)$ où $n_1$ et $n_2$ sont les tailles respectives
des listes L1 et de L2.
Par exemple l’appel fusion([2,4,7],[3,5,6,9]) renverra la liste [2,3,4,5,6,7,9].
In [16]:
# methode itérative
def fusion(L1, L2):
""" Renvoie la liste triée issue de la fusion des deux listes triées données en paramètre. """
L_fusion = [] # la liste résultat
m = len(L1)
n = len(L2)
i, j = 0, 0
while i < m and j < n:
if L1[i] <= L2[j]:
L_fusion.append(L1[i])
i += 1
else:
L_fusion.append(L2[j])
j += 1
else:
# une des deux listes a été entièrement traitée, on ajoute ce qu'il reste de l'autre
if i == m:
L_fusion += L2[j:]
else:
L_fusion += L1[i:]
return L_fusion
In [17]:
fusion([2, 4, 7], [3, 5, 6, 9])
Out[17]:
In [18]:
# méthode récursive
def fusion_bis(L1, L2):
if not L1:
# si la liste L1 est vide on retourne directement L2
return L2
if not L2:
# idem mais avec L2
return L1
if L1[0] <= L2[0]:
return [L1[0]] + fusion_bis(L1[1:], L2)
else:
return [L2[0]] + fusion_bis(L1, L2[1:])
In [19]:
fusion_bis([2, 4, 7], [3, 5, 6, 9])
Out[19]:
Partie B - Enveloppe convexe d'un nuage de points¶
Question 9¶
Voici une fonction «naı̈ve» qui permet de déterminer les sommets de l’enveloppe convexe d’un nuage de points :
In [20]:
# Q.9
def jarvis(L):
""" Fonction qui reçoit en argument un nuage de points et qui renvoie
une liste contenant les indices des sommets de l'enveloppe
convexe de ce nuage
"""
n = len(L)
EnvConvexe = []
for i in range(n):
for j in range(n):
Listeorientation = []
if i != j:
for k in range(n):
if k != i and k != j:
Listeorientation.append(orientation(L[i], L[j], L[k]))
a = Listeorientation[0]
sommet = True
for v in Listeorientation:
if v != a:
sommet = False
if sommet and (i not in EnvConvexe):
EnvConvexe.append(i)
if sommet and (j not in EnvConvexe):
EnvConvexe.append(j)
return EnvConvexe
In [21]:
# Q.9a Les lignes de 16 à 20 permettent de déterminer si toutes les orientations de l'itération sont identiques
# Q.9b O(2*n^3)
Question 9c) Le script suivant trace-t-il le polygone formé par les sommets de l’enveloppe convexe du nuage L? Justifier.¶
In [22]:
# Q.9c
L = [[0, 0], [2, 1], [-1, 2]]
import matplotlib.pyplot as plt
Enveloppe = jarvis(L)
plt.xlim((-1.5, 2.5)) # ajouté pour nieux voir la figure
plt.ylim((-0.5, 2.5)) # idem
plt.plot([L[i][0] for i in Enveloppe], [L[i][1] for i in Enveloppe])
# partie ajoutée juste pour afficher le nom des points
labels = ['$P_{0}$'.format(i) for i in range(len(L))]
for label, x, y in zip(labels, [p[0] for p in L], [p[1] for p in L]):
plt.annotate(label, xy=(x, y), va='bottom', ha='right', size='large', color='black')
plt.grid(True)
plt.show()
In [23]:
# Le polygone n'est pas fermé, il faudrait boucler entre le dernier et le premier sommet
In [24]:
L = [[0, 0], [2, 1], [-1, 2]]
import matplotlib.pyplot as plt
Enveloppe = jarvis(L)
X = [L[i][0] for i in Enveloppe]
X.append(L[Enveloppe[0]][0])
Y = [L[i][1] for i in Enveloppe]
Y.append(L[Enveloppe[0]][1])
plt.xlim((-1.5, 2.5))
plt.ylim((-0.5, 2.5))
plt.plot(X, Y)
labels = ['$P_{0}$'.format(i) for i in range(len(L))]
for label, x, y in zip(labels, [p[0] for p in L], [p[1] for p in L]):
plt.annotate(label, xy=(x, y), va='bottom', ha='right', size='large', color='black')
plt.grid(True)
plt.show()
In [25]:
# on regarde avec l'exemple de l'énoncé
M = [[0.2, 3.35], [1.4, 2.45], [2.75, 0.35], [4.9, 3.35], [2.4, 3.6],
[4.35, 1.65], [3.7, 4.45], [0.5, 0.7], [5.85, 0.9]]
In [26]:
plt.scatter([x for x,y in M], [y for x,y in M])
labels = ['$P_{0}$'.format(i) for i in range(len(M))]
for label, x, y in zip(labels, [p[0] for p in M], [p[1] for p in M]):
plt.annotate(label, xy=(x, y), va='bottom', ha='right', size='large', color='black')
plt.grid(True)
plt.show()
In [27]:
# on défini une fonction pour afficher re nuage de points et son enveloppe convexe
def affiche_enveloppe(L, algorithme):
""" Affiche l'enveloppe convexe du nuage de points selon l'algorithme sélectionné. """
import matplotlib.pyplot as plt
Enveloppe = algorithme(L)
X = [L[i][0] for i in Enveloppe]
X.append(L[Enveloppe[0]][0])
Y = [L[i][1] for i in Enveloppe]
Y.append(L[Enveloppe[0]][1])
plt.xlim((-1, 7))
plt.ylim((0, 5))
plt.plot(X, Y)
labels = ['$P_{0}$'.format(i) for i in range(len(L))]
for label, x, y in zip(labels, [p[0] for p in L], [p[1] for p in L]):
plt.annotate(label, xy=(x, y), va='bottom', ha='right', size='large', color='black')
plt.grid(True)
plt.show()
In [28]:
affiche_enveloppe(M, jarvis)
plt.show()
In [29]:
# aïe, y a comme un problème
# vérifions le résultat de l'algorithme
jarvis(M)
Out[29]:
In [30]:
# les sommets sont bons mais ils ne sont pas reliés dans le bon ordre, il manque cette notion d'ordre
Question 10¶
Donner le classement des points du nuage de la figure ci-dessus pour la relation d’ordre $\preccurlyeq_{P_6}$.
In [31]:
# Q.10
# P0 < P4 < P1 < P7 < P2 < P5 < P8 < P3
Question 11¶
Écrire une fonction prochain_sommet qui prend en arguments un nuage de points L et l’indice d’un
sommet P de ce nuage de points qui est un sommet de l’enveloppe convexe et qui renvoie l’indice du
prochain sommet de l’enveloppe convexe. Cette fonction devra avoir une complexité en $O(n)$ où n est
le nombre de points du nuage.
In [32]:
# Q.11
def prochain_sommet(L, i, debug=False):
""" Renvoie l'indice du prochain sommet de l'enveloppe convexe. """
valeurs = []
for j in range(len(L)):
if j == i:
continue
v = 0
for k in range(len(L)):
if k == i or k == j:
continue
v += orientation(L[i], L[j], L[k]) # on calcul la somme des orientations assossiées à un sommet
valeurs.append((j, v))
if debug:
print(valeurs)
valeurs.sort(key=lambda x: x[1]) # on tri (croissant) selon la valeur d'orientation associée au sommet
if debug:
print(valeurs)
return valeurs[-1][0]
In [33]:
prochain_sommet(L, 0)
Out[33]:
In [34]:
prochain_sommet(L, 1)
Out[34]:
In [35]:
prochain_sommet(M, 2, True)
Out[35]:
Question 12¶
Recopier et compléter la fonction suivante afin qu’elle renvoie l’enveloppe convexe d’un nuage de points L.
def jarvis2(L):
i=point_abs_min(L)
suivant=prochain_sommet(L,i)
Enveloppe=[i,suivant] # initialisation de la liste des indices des sommets de l’enveloppe convexe
while (.......):
......
......
return Enveloppe
In [36]:
# Q.12
def jarvis2(L):
""" Renvoie la liste des sommets formant l'enveloppe convexe d'un nuage de points. """
i = point_abs_min(L)
suivant = prochain_sommet(L, i)
Enveloppe = [i, suivant] # initialisation de la liste des indices des sommets de l'enveloppe convexe
while prochain_sommet(L, suivant) != i:
suivant = prochain_sommet(L, suivant)
Enveloppe.append(suivant)
return Enveloppe
In [37]:
jarvis2(L)
Out[37]:
In [38]:
jarvis2(M)
Out[38]:
In [39]:
affiche_enveloppe(M, jarvis2)
In [40]:
# cette fois il semble que les points et leur ordre de liaison soit bon
Question 14¶
Voici en Python la fonction qui permet d’obtenir l’enveloppe convexe :
In [41]:
# Q.14
def graham_andrew(L, debug=False):
print(L)
L = tri_nuage(L)
print(L)
EnvSup = []
EnvInf = []
for i in range(len(L)):
if debug:
if len(EnvSup) >= 2:
o = orientation(L[i], L[EnvSup[-1]], L[EnvSup[-2]])
print('Sup : ' + str(o))
while len(EnvSup) >= 2 and orientation(L[i], L[EnvSup[-1]], L[EnvSup[-2]]) <= 0:
EnvSup.pop()
EnvSup.append(i)
if debug:
if len(EnvInf) >= 2:
o = orientation(L[EnvInf[-2]], L[EnvInf[-1]], L[i])
print('Inf : ' + str(o))
while len(EnvInf) >= 2 and orientation(L[EnvInf[-2]], L[EnvInf[-1]], L[i]) <= 0:
EnvInf.pop()
EnvInf.append(i)
if debug:
print(EnvSup, EnvInf)
return EnvInf[:-1] + EnvSup[::-1]
In [42]:
# on va définir les fonctions manquantes pour trier le nuage par un tri fusion: fusion_points et tri_fusion_points
# il me semble que la programmation objet n'est pas au programme donc on reste simple
In [43]:
# méthode récursive de fusion de listes de points
def fusion_points(L1, L2):
if not L1:
# si la liste L1 est vide on retourne directement L2
return L2
if not L2:
# idem mais avec L2
return L1
# on tri selon l'abscisse
if L1[0][0] < L2[0][0]:
return [L1[0]] + fusion_bis(L1[1:], L2)
if L1[0][0] > L2[0][0]:
return [L2[0]] + fusion_bis(L1, L2[1:])
# cas en plus du fait qu'il faut ensuite trier selon l'ordonnée si il y a égalité
if L1[0][1] <= L2[0][1]:
return [L1[0]] + fusion_bis(L1[1:], L2)
else:
return [L2[0]] + fusion_bis(L1, L2[1:])
In [44]:
# tri fusion aves des points
def tri_fusion_points(L):
""" Fonction qui prend en argument une liste L de points du plan
et qui trie cette liste
"""
n = len(L)
if n <= 1:
return L
else:
m = n // 2
return fusion_points(tri_fusion_points(L[:m]), tri_fusion_points(L[m:]))
In [45]:
def tri_nuage(L):
""" Renvoie la liste des points du nuage de points, triée par abscisse puis ordonnée croissante. """
return tri_fusion_points(L)
In [46]:
graham_andrew(L)
Out[46]:
In [47]:
graham_andrew(M, True)
Out[47]:
In [48]:
# Ce n'est pas du tout les bons sommets !!!
# C'est normal, ces indices sont ceux du nuage trié, pas celui d'origine
# il faut modifier l'algorithme pour retourner les bons indices d'origines
In [49]:
# Q.14
def graham_andrew_bis(L_origin, debug=False):
L = tri_nuage(L_origin)
if debug:
print(L_origin)
print(L)
# on va créer un tableau d'association entre les indices des deux listes
association = {i: L_origin.index(L[i]) for i in range(len(L))}
EnvSup = []
EnvInf = []
for i in range(len(L)):
if debug:
if len(EnvSup) >= 2:
o = orientation(L[i], L[EnvSup[-1]], L[EnvSup[-2]])
print('Sup : ' + str(o))
while len(EnvSup) >= 2 and orientation(L[i], L[EnvSup[-1]], L[EnvSup[-2]]) <= 0:
EnvSup.pop()
EnvSup.append(i)
if debug:
if len(EnvInf) >= 2:
o = orientation(L[EnvInf[-2]], L[EnvInf[-1]], L[i])
print('Inf : ' + str(o))
while len(EnvInf) >= 2 and orientation(L[EnvInf[-2]], L[EnvInf[-1]], L[i]) <= 0:
EnvInf.pop()
EnvInf.append(i)
if debug:
print(EnvSup, EnvInf)
sommets = EnvInf[:-1] + EnvSup[::-1]
# on convertit les indices
return [association[i] for i in sommets]
In [50]:
graham_andrew_bis(M)
Out[50]:
In [51]:
affiche_enveloppe(M, graham_andrew_bis)
In [52]:
# vérification visuelle des trois algorithmes avec l'exemple donné
In [53]:
M = [[0.2, 3.35], [1.4, 2.45], [2.75, 0.35], [4.9, 3.35], [2.4, 3.6],
[4.35, 1.65], [3.7, 4.45], [0.5, 0.7], [5.85, 0.9]]
In [54]:
# on défini une fonction pour afficher re nuage de points et son enveloppe convexe
def affiche_enveloppe_bis(L, algorithme):
""" Affiche l'enveloppe convexe du nuage de points selon l'algorithme sélectionné. """
import matplotlib.pyplot as plt
Enveloppe = algorithme(L)
X = [L[i][0] for i in Enveloppe]
X.append(L[Enveloppe[0]][0])
Y = [L[i][1] for i in Enveloppe]
Y.append(L[Enveloppe[0]][1])
plt.xlim((-1, 7))
plt.ylim((0, 5))
plt.plot(X, Y)
plt.title(algorithme.__name__)
labels = ['$P_{0}$'.format(i) for i in range(len(L))]
for label, x, y in zip(labels, [p[0] for p in L], [p[1] for p in L]):
plt.annotate(label, xy=(x, y), va='bottom', ha='right', size='large', color='black')
plt.grid(True)
# plt.show()
In [56]:
plt.figure(figsize=(12, 8))
plt.subplot(221)
plt.scatter([x for x,y in M], [y for x,y in M])
labels = ['$P_{0}$'.format(i) for i in range(len(M))]
for label, x, y in zip(labels, [p[0] for p in M], [p[1] for p in M]):
plt.annotate(label, xy=(x, y), va='bottom', ha='right', size='large', color='black')
plt.title('Nuage de points')
plt.grid(True)
plt.subplot(222)
affiche_enveloppe_bis(M, jarvis)
plt.subplot(223)
affiche_enveloppe_bis(M, jarvis2)
plt.subplot(224)
affiche_enveloppe_bis(M, graham_andrew_bis)
plt.show()
