Épreuve d’informatique №2 (corrigé)
Mme. S. Darragi et M. A. Ammar - IPEST : (PCSI/MPSI) 12 février 2022
Exercice 1 : Étude d’algorithmes
Q1. — fonction toto :
La fonction toto calcule n! = ∏ni=1 i. Son coût est :
C1 (n) = 2n + 2 donc sa classe de complexité est O(n)
— fonction titi :
La fonction titi calcule ∑ni=1 i!. Son coût est :
n(n + 1)
C2 (n) = 2 + ∑ni=1 (2 + C1 (i)) = 2 + ∑ni=1 (4 + 2i) = 2 + 4n + 2 donc sa classe de
2
complexité est O(n2 )
— fonction tata :
La fonction tata calcule ∑ni=1 (∑ni=1 i!). Son coût est :
n(n + 1)(2n + 1)
C3 (n) = 2 + ∑ni=1 (2 +C2 (i)) > ∑ni=1 i2 = donc sa classe de complexité est
6
3
O(n )
Q2. Oui, nous pouvons programmer une version linéaire de la fonction tata qui peut être écrite
comme suit :
1 def tata_lin(n):
2 s1=s2=0
3 f=1
4 for i in range(1,n+1):
5 f=f*i
6 s1=s1+f
7 s2+=s1
8
9 return s2
Exercice 2 : Multiplication égyptienne
1 def mult_égyptienne(x,y):
2 P=0
3 while y!=0:
4 if y%2==0:
5 x=x*2
6 y=y//2
7 else:
8 P=P+x
Page 1
9 y=y-1
10 return P
Exercice 3 : Algorithme de tri
Q1. Nous avons
>>> L = [5, 2, 3, 1, 4]
>>> n = len(L) # n --> 5
Il s’agit d’un algorithme de tri par insertion, on obtient après 4 itérations successives une liste
triée :
1. i = 1; x = 2 # L --> [2, 5, 3, 1, 4]
2. i = 2; x = 3 # L --> [2, 3, 5, 1, 4]
3. i = 3; x = 1 # L --> [1, 2, 3, 5, 4]
4. i = 4; x = 4 # L --> [1, 2, 3, 4, 5]
Q2. Soit la propriété P(i) : ”la liste L[0 : i+1] est triée par ordre croissant à l’issue de l’itéra-
tion i”
Montrons que cette propriété constitue un invariant de boucle.
Initialisation (est ce vrai avant d’entrer dans la boucle ?) : si i=0, au rang 0 on a
[L[0]] ou encore L[0:0+1] : constituée d’un seul terme, elle est donc triée : La propriété
P(0) est vraie.
Conservation = hérédité (reste vraie après une itération, si elle était vraie avant) :
À la fin de l’itération i, L[0 : i+1]=[L[0],L[1],...,L[i]] est supposée triée dans l’ordre
croissant si P(i) est vraie : on effectue un nouveau tour de boucle donc à l’itération i+1. La
boucle effectue le tri
1 while i+1 > 0 and L[i+1] < L[i] : # teste si L[i+1] est mal placé
2 L[i+1] = L[i] # déplacement
3 ...
Alors la liste L[0 : i+2]=[L[0],L[1],...,L[i], L[i+1]] devient triée dans l’ordre crois-
sant. P(i + 1) reste vraie.
Terminaison (donne le résultat attendu en fin de boucle) : En sortie de boucle, i a
pris sa dernière valeur i= n-1 et la boucle permet d’effectuer le tri au rang n-1
Page 2
1 while n-1 > 0 and L[n-1] < L[n-2] : # teste si L[n-1] est mal placé
2 L[n-1] = L[n-2] # déplacement
3 ....
Malgré l’absence de renvoi (return en python) le tri est effectué sur la liste L, modifiée à
chaque tour de boucle. La liste t est triée dans l’ordre croissant et la fonction tri a rempli
son objectif.
Q3. Le nombre de comparaisons pour une liste de taille n est :
6n×(n−1)
• Au pire des cas : 2+ ∑n−1
i=1 (1+2+4+6i+2) = 9n−7+ 2 = O(n2 ) si liste ”inversée”.
La boucle while est toujours exécutée jusqu’à ce que j = 0.
• Au meilleur des cas : 2 + ∑n−1
i=1 (1 + 2 + 4 + 0 + 2) = 9n − 7 = O(n) si liste déjà ”triée”.
La boucle while n’est jamais exécutée (n-1 exécution de la boucle for).
Dans le pire comme dans le meilleur des cas, le tri fusion (utilise une approche diviser pour
régner) est plus efficace car de complexité logarithmique en O(n ln(n)).
Q4. À partir de tri, on peut proposer
1 def tri_chaine(L):
2 n = len(L)
3 for i in range(1, n):
4 j = i
5 x = L[i]
6 while j>0 and x[1] < L[j-1][1]:
7 L[j] = L[j-1]
8 j -=1
9 L[j] = x
Exercice 4 : L’enclot du robot
Q1.
1 def sudouest(x1 ,y1 ,x2 ,y2):
2 return (x1 <= x2 and y1 <= y2)
3
4 def nordouest(x1 ,y1 ,x2 , y2):
5 return (x1 <= x2 and y1 >= y2)
6
7 def sudest(x1, y1, x2, y2) :
8 return (x1 >= x2 and y1 <= y2)
9
10 def nordest(x1, y1, x2, y2):
11 return (x1 >= x2 and y1 >= y2)
Page 3
Q2. On prend soin de ne pas écraser les données en passant par une variable intermédiaire c.
La fonction echange ne retourne rien, elle se contente de permuter des éléments dans les
tableaux a et b.
1 def echange(a, b, i, j) :
2 c = a[i]; a[i] = a[j]; a[j] = c;
3 c = b[i]; b[i] = b[j]; b[j] = c ;
Q3. Dans l’exemple de l’énoncé, la partie sud-ouest de l’enveloppe est formée de 2 points qui
sont P1 et P0 .
Q4.
1 def frontiereSO(a, b):
2 n = len (a)
3 k = 0
4 for i in range(n):
5 ok = True ;
6 for j in range(n):
7 if (sudouest(a[j], b[j], a[i], b[i]) and (a[i ] != a[j] or b[i] != b[j])):
8 ok = False
9 if ok :
10 echange(a, b, k, i)
11 k = k+1
12 return k
Q5. Il suffit de remplacer la fonction sudouest du programme précédent par la fonction nordouest.
1 def frontiereNO(a, b):
2 n = len (a)
3 k = 0
4 for i in range(n):
5 ok = True ;
6 for j in range(n):
7 if (nordouest(a[j], b[j], a[i], b[i]) and (a[i ] != a[j] or b[i] != b[j])):
8 ok = False
9 if ok :
10 echange(a, b, k, i)
11 k = k+1
12 return k
Q6. Les fonctions frontiereSE et frontiereNE s’écrivent tout aussi simplement sous la forme
suivante :
1 def frontiereNE(a, b):
2 n = len (a)
3 k = 0
4 for i in range(n):
Page 4
5 ok = True ;
6 for j in range(n):
7 if (nordest(a[j], b[j], a[i], b[i]) and (a[i ] != a[j] or b[i] != b[j])):
8 ok = False
9 if ok :
10 echange(a, b, k, i)
11 k = k+1
12 return k
13
14 def frontiereSE(a, b):
15 n = len (a)
16 k = 0
17 for i in range(n):
18 ok = True ;
19 for j in range(n):
20 if (sudest(a[j], b[j], a[i], b[i]) and (a[i ] != a[j] or b[i] != b[j])):
21 ok = False
22 if ok :
23 echange(a, b, k, i)
24 k = k+1
25 return k
Exercice 5 : Triangle de Sierpinski
Le triangle de Sierpinski est une fractale construite de la façon suivante :
1. on part d’un triangle équilatéral auquel on ôte le triangle construit à partir du milieu des 3
côtés.
2. on obtient alors 3 nouveaux triangles auxquels on réapplique le procédé.
3. on répète cette construction à l’infini.
Figure 1 – La position relative des points u, v, w en fonction de a, b, c.
On peut donc écrire :
import matplotlib.pyplot as plt
import math as m
Page 5
# Q1.
def polygon(*args):
X, Y = [], []
for arg in args:
X.append(arg[0])
Y.append(arg[1])
plt.fill(X, Y)
# Q2.
def sierpinski(n, a=[0, 0], b=[1, 0], c=[.5, m.sqrt(3)/2]):
if n == 1:
polygon(a, b, c)
else:
u = [(b[0]+c[0])/2, (b[1]+c[1])/2]
v = [(c[0]+a[0])/2, (c[1]+a[1])/2]
w = [(a[0]+b[0])/2, (a[1]+b[1])/2]
sierpinski(n-1, a, w, v)
sierpinski(n-1, w, b, u)
sierpinski(n-1, v, u, c)
Figure 2 – Le résultat des fonctions sierpinski(n) pour n = 1, 2, 3.
Page 6
