Stanislas Memento Python PSI
2019-2020
  
I. Présentation des écrits
• Les commentaires doivent précéder les programmes. Ces derniers peuvent être commentés (]).
• Utiliser une barre verticale pour matérialiser les indentations.

II. Erreurs classiques
SyntaxError Le signe = est un symbole d'aectation et il n'est pas symétrique. Le nom de l'objet
est à gauche, son contenu à droite.
IndexError Les bornes de la fonction range. L'appel range(a, b, pas) crée un itérateur qui par-
court les entiers qui s'écrivent sous la forme a 6 a + k · pas < b.
Les indices des éléments de la liste liste vont de 0 à len(liste) - 1.
TypeError L'appel à la fonction f s'eectue via f(2). L'accès aux indices de la liste (ou chaîne de
caractères) liste via liste[2]. Les erreurs de type surviennent également si les opérandes ne
sont pas correctes, par exemple 2 + [3].
• L'indentation de return dans une boucle ou conditionnelle.
• L'oubli de return dans une fonction. Le résultat de l'évaluation de cette fonction est alors None.
• Lors de la manipulation des listes, les copies avec alias. Une copie sans alias peut s'eectuer via
n_liste = liste.copy() ou n_liste = liste[:].

III. Complexité
III.1 Recommandations

• Pour ajouter des éléments à des listes, la méthode liste.append(element) est en temps constant,
contrairement à liste = liste + [element] qui est en temps linéaire.
• Un stockage vaut mieux que plusieurs appels de fonction !
• On peut parfois préférer les boucles conditionnelles while aux boucles for. En Python, l'instruction
return interrompt les boucles et permet d'obtenir un comportement analogue.
III.2 Classes de complexité

Si Tn est le nombre d'opérations (la nature des opérations dépend du contexte : multiplications, additions,
comparaisons, appels de fonctions,. . . ) eectuées pour un argument de taille n et an est le terme général
d'une suite,
Tn = O(an ) ⇔ ∃ (M, n0 ) ∈ R?+ × N ; ∀ n > n0 , Tn 6 M an .
Tn = Θ(an ) ⇔ Tn = O(an ) et an = O(Tn ).
• Θ(1) : en temps constant. • Θ(n2 ) : quadratique.
Ex. : Échange de deux valeurs. Ex. : Tri par insertion.
• Θ(ln n) : logarithmique. • Θ(nβ ) : polynomiale (β > 1).
Ex. : Recherche dichotomique. Ex. : Multiplication matricielle.
• Θ(n) : linéaire. • Θ(an ) : exponentielle.
Ex. : Recherche du maximum. Ex. : Tours de Hanoï.
• Θ(n ln n) : quasi-linéaire.
Ex. : Tri fusion.
III.3 Complexité sur les listes

Lors de la création d'une liste en Python, une grande place mémoire est allouée. Certaines opérations sont
alors relativement ecaces, tant que cette place n'est pas toute utilisée. . . Les primitives Python sur les
listes ont les complexités suivantes (source : https://wiki.python.org/moin/TimeComplexity) :
length O(1) Parcours O(n)
Lecture d'un item O(1) Copie O(n)
Modication d'un item O(1) Insertion d'un élément O(n)
append(1) O(1) Suppression d'un élément O(n)
(1) Complexité en moyenne, peut être parfois beaucoup plus grande.

Stanislas 1 A. Camanes
 PSI




III.4 Exemples de calculs de complexité



def h o r n e r (P , x ) : def fibo (n ) :
n = len (P) if n==0 or n==1 :
Px = P [ n − 1] return 1
for i in range ( 1 , n ) : else :
Px = Px * x + P [ n−i − 1] return f i b o ( n − 1) + f i b o ( n − 2)
return Px
En notant Tn le nombre d'appels pour évaluer
À chaque passage dans la boucle : fibo(n),
• 1 multiplication,
• 1 addition. T0 = 1
Le nombre d'opérations vaut alors T1 = 1
nX
−1 Tn = Tn−1 + Tn−2 + 1
2 = 2(n − 1)
i=1 On montre alors que 1+Tn
2 est le nème nombre de
Fibonacci.


IV. Preuves de programmes : 3 exemples

IV.1 Programme itératif

L'invariant doit être vrai en début de boucle, maintenu par le corps de boucle et sa validité en sortie de
boucle doit assurer la correction de la fonction.
def h o r n e r (P , x ) :
n = len (P) − 1
Px = P [ n ]
for i in range ( 1 , n+1) :
Px = Px * x + P [ n− i ]
return Px

iP
−1
On note P = [a0 , . . . , an ]. L'invariant de boucle : En entrée de l'itération i, Px contient an−k xi−1−k .
k=0
0
• Précondition. Avant l'entrée en boucle, Px contient an = an−k x0−k .
P
k=0
iP
−1
• Hérédité. Supposons qu'à l'entrée de la i-ème itéation, Px contienne an−k xi−1−k .
k=0
iP
−1 i
Alors, après le corps d'instructions, Px contient x · an−k xi−1−k + an−1−i−1 = an−k xi−k ..
P
k=0 k=0
n n
• Postcondition. À la n de la boucle, i contient n et Px contient an−k xn−k = ak xk .
P P
k=0 k=0


Programme avec boucle conditionnelle


def racine_entiere (n) :
m = 0
while (m+1) * (m+1) <= n :
m = m + 1
return m


Correction. Invariant I : n − m2 > 0. • En sortie, n − m2 > 0 et n − (m + 1)2 < 0, soit
• Avant l'entrée dans la boucle, n − m2 = n > 0.
• Supposons que n − (m + 1)2 > 0. Dans le m=
√ 
n .
corps de boucle, m est incrémenté, donc en
sortie n − m2 > 0.

Stanislas 2 A. Camanes
 PSI




Terminaison. Variant V : n − m2 > 0. boucle.
• V est à valeurs entières. • Le programme termine.
• V décroît de 1 à chaque passage dans la


Programme récursif


def f (n , p):
if n = 0:
return 47
else :
return f ( n −1 , f ( n − 1 , p +7))

On montre par récurrence sur n que pour tout p entier, f(n, p) termine et renvoie 47.
Initialisation. Si n = 0, alors pour tout p, f(n, p) renvoie 47.
Hérédité. Soit n ∈ N∗ . On suppose que la propriété est vraie pour tout entier inférieur ou égal à n. Soit
p un entier. Comme n − 1 < n, alors f(n-1, p+...