1.

Méthodes de programmation

I - Quelques principes de base

1) Conception
• Spécifications : préciser le “cahier des charges” (données reçues en entrée, préconditions, résultats
renvoyés en sortie, postconditions. . . ).
• Analyse descendante : en cas de tâches complexes, procéder par raffinements successifs.
• Modularité : découper l’algorithme en “modules” aussi indépendants que possible les uns des autres
(utiliser des fonctions, avec transmission des données sous forme de paramètres et création de
variables locales, plutôt que des procédures agissant sur des variables globales).
• Portabilité : éviter d’abuser de particularités d’un langage précis ou d’une machine donnée.

2) Présentation
• Indentation : elle est obligatoire en Python, puisqu’elle structure le programme !
• Identificateurs : choisir autant que possible des identificateurs explicites pour les noms des objets
utilisés.
• Commentaires : il peut être utile d’insérer dans le code de brefs commentaires (précédés de #),
précisant par exemple les spécifications d’un module, des éléments de justification. Pour des com-
mentaires de plusieurs lignes, sur une copie notamment, on les rédigera de préférence dans un
paragraphe précédant ou suivant le code concerné. On peut toutefois transformer en commentaire
une partie du code en l’entourant de triples quotes.

3) Preuve
Il faut justifier la terminaison de l’exécution du programme et sa correction (le fait qu’il fournit le
résultat annoncé. . . ).

4) Notion de complexité
Pour évaluer l’efficacité d’un algorithme, on s’intéresse notamment :
• à la quantité de mémoire nécessaire (complexité spatiale) ;
• au nombre d’opérations à effectuer (complexité temporelle).
Pour cette dernière, on dénombre le plus souvent un seul type d’opération (en général la plus coû-
teuse) : il est bon de préciser “complexité en nombre de comparaisons”, “complexité en nombre de
multiplications”. . .
Pour comparer des algorithmes s’appliquant à un certain type de données, de taille variable, on définit
une taille de données N (par exemple : valeur absolue d’un entier, longueur d’une liste, taille d’un
tableau, degré d’un polynôme, ordre d’une matrice carrée. . . ).
Si C (d) désigne la complexité de l’algorithme étudié pour le traitement de la donnée d, élément de
l’ensemble D (N) des données de taille N, on définit :

• la complexité dans le pire des cas : Tau pire (N) = sup {C (d) , d ∈ D (N)} ;
• la complexité dans le meilleur des cas : Tau mieux (N) = inf {C (d) , d ∈ D (N)} ;
• la complexité en moyenne : Tmoyen (N) = P (d) C (d) où P (d) est la probabilité d’apparition
d∈D(N)
de la donnée d, cela sous réserve de convergence. . .
Lorsque D (N) est infini, on effectue souvent une “sommation par paquets” en regroupant les données
selon leurs caractéristiques.
1. Méthodes de programmation Page 2

Notation Θ (f (N)) (complément hors programme)

T et f étant deux fonctions de N dans R+ , on écrit T (N) = Θ (f (N)) si et seulement si l’on a
simultanément T (N) = O (f (N)) et f (N) = O (T (N)) lorsque N tend vers l’infini, autrement dit
s’il existe α et β positifs tels que, pour N assez grand, on ait :
αf (N) ≤ T (N) ≤ βf (N)
(i.e. T (N) et f (N) sont asymptotiquement “du même ordre de grandeur ”).
La hiérarchie des ordres de grandeur permet effectivement une comparaison des algorithmes indépen-
damment de la machine utilisée, car les temps de calcul T1 (N) et T2 (N) sur deux machines de perfor-
mances différentes sont grosso modo des fonctions proportionnelles de N (le facteur de proportionnalité
mesurant la différence de rapidité des deux machines).
Exemples de temps d’exécution
À titre indicatif, le tableau ci-dessous donne des valeurs approchées du temps de calcul nécessaire à
une machine, capable d’exécuter 109 opérations par seconde, pour mettre en œuvre des algorithmes
de complexités variées (les unités j, a, u désignant respectivement le jour, l’année et l’âge estimé de
l’univers).

N log2 N N N log2 N N2 N3 2N N!
5 2.10−9 s 5.10−9 s 1.10−8 s 3.10−8 s 1.10−7 s 3.10−8 s 1.10−7 s
10 3.10−9 s 1.10−8 s 3.10−8 s 1.10−7 s 1.10−6 s 1.10−6 s 4.10−3 s
20 4.10−9 s 2.10−8 s 9.10−8 s 4.10−7 s 8.10−6 s 1.10−3 s 77 a
50 6.10−9 s 5.10−8 s 3.10−7 s 3.10−6 s 1.10−4 s 13 j 7.1037 u
100 7.10−9 s 1.10−7 s 7.10−7 s 1.10−5 s 1.10−3 s 3.103 u
500 9.10−9 s 5.10−7 s 5.10−6 s 3.10−4 s 0.1 s
1 000 1.10−8 s 1.10−6 s 1.10−5 s 1.10−3 s 1s
5 000 1.10−8 s 5.10−6 s 6.10−5 s 0.03 s 13 s
10 000 1.10−8 s 1.10−5 s 1.10−4 s 0.1 s 17 min
50 000 2.10−8 s 5.10−5 s 7.10−4 s 2.5 s 35 h
100 000 2.10−8 s 1.10−4 s 2.10−3 s 10 s 12 j

II - Itération et récursivité
1) Structures de boucle
a) Boucles conditionnelles
Il s’agit du cas où la répétition est conditionnée par l’évaluation d’une expression booléenne (en Python,
instruction while).
L’utilisation de telles boucles nécessite une justification claire de la terminaison !
b) Boucles inconditionnelles
Elles sont utilisées lorsqu’on connaît à l’entrée dans la boucle la liste (finie !) des valeurs à utiliser
durant la boucle (en Python, instruction for in).
Attention ! La terminaison d’une boucle for est assurée par la nature même de la boucle, à condition
que la liste de valeurs ne soit pas modifiée en cours de boucle (c’est possible en Python,
mais formellement déconseillé !).

c) Notion d’invariant de boucle

Dans le cas d’algorithmes non triviaux, qui nécessitent une justification du résultat obtenu, il peut être
judicieux de mettre en évidence un “invariant de boucle”, c’est-à-dire une propriété qui reste vraie après
chaque exécution du corps de la boucle et qui permet de justifier la correction de l’algorithme !
Pour cela, il est souvent commode de nommer mathématiquement (par exemple à l’aide d’indices)
les valeurs successives contenues dans les variables informatiques utilisées.
1. Méthodes de programmation Page 3

Exemple : exponentiation rapide itérative

def exprap(x,n):
result=1
while n!=0:
if n%2==1:
result*=x
x*=x
n//=2
return result
La terminaison de la boucle while est justifiée par la décroissance stricte de l’entier contenu dans n.
Il est clair que la complexité de cette fonction est un Θ (log2 n), d’où son nom, par comparaison avec
l’exponentiation naïve qui est en Θ (n).
En revanche, il n’est pas clair à l’œil nu que cette fonction renvoie xn . . . Pour le justifier, on peut
démontrer que result*x^n n’est pas modifié par un passage dans la boucle. Il en résulte par récurrence
que cette expression a la même valeur à la sortie de la boucle qu’à l’entrée, d’où le résultat !
Pour rédiger une preuve, il pourra être plus clair de noter rk , xk et nk les valeurs contenues respective-
ment dans les variables result, x et n après le k-ième passage dans la boucle
On montre alors par récurrence sur k que, pour tout k, rk · xnk k = xn . . .

2) Récursivité
La programmation récursive (i.e. utilisant une fonction ou une procédure qui s’appelle elle-même) est
souvent élégante, naturellement adaptée aux suites définies par récurrence (cf. n!, xn , f (n) . . . ) et à la
stratégie “diviser pour régner ” (cf. § III). Elle permet parfois d’éviter le recours à des variables locales
et à des boucles. Elle est en revanche exigeante en ressources machine (sauvegarde et restauration du
contexte) et peut conduire à des temps de calculs prohibitifs en cas d’utilisation irréfléchie (cf. suite de
Fibonacci au § 3)c)).
Tout algorithme récursif doit être soigneusement justifié :
• preuve de la terminaison de l’algorithme : les appels récursifs doivent être soumis à une condition
et il faut montrer qu’elle devient fausse au bout d’un nombre fini d’appels imbriqués. Typiquement,
il suffit d’associer aux paramètres transmis lors de l’appel récursif un entier naturel qui décroît
strictement lors de chaque nouvel appel récursif, ledit appel étant soumis à un test vérifiant que
l’entier en question est supérieur à une certaine valeur ;
• preuve de la validité du résultat : en général par récurrence ;
• calcul de complexité : souvent à l’aide d’une relation de récurrence !

3) Exemples
a) Factorielle

Version itérative Version récursive

def fact(n): def fact(n):
result=1 if n<2:
for k in range(2,n+1): return 1
result*=k else:
return result return n*fact(n-1)

b) Exponentiation naïve

Version itérative Version récursive

def puiss(x,n): def puiss(x,n):
result=1 if n==0:
for k in range(n): return 1
result*=x else:
return result return x*puiss(x,n-1)
1. Méthodes de programmation Page 4

c) Suite de Fibonacci
Rappelons qu’elle est définie – a et b étant deux réels donnés – par
u0 = a, u1 = b et ∀n ≥ 2 un = un−1 + un−2 .

Version itérative Version récursive

def fib(n,a,b): def fib(n,a,b):
if n==0: if n==0:
return a return a
elif n==1: elif n==1:
return b return b
else: else:
for k in range(n-1): return fib(n-1,a,b)+fib(n-2,a,b)
a,b=b,a+b
return b
Les justifications sont banales, l’évaluation de la complexité est édifiante. Déterminons le nombre
d’additions effectuées sur les termes de la suite (donc sans compter la gestion des indices ; ce choix se
justifie par le fait que les additions sur les réels ou les grands entiers sont plus coûteuses que celles sur
les indices).
Pour le calcul de fib(n), la version itérative effectue n − 1 additions, pour tout n ≥ 2, ce qui est
raisonnable.
Par contre, si je note C(n) le nombre d’additions effectuées par la version récursive ci-dessus, pour le
calcul de fib(n), il apparaît que C (n) est défini par
C (0) = C (1) = 0 et ∀n ≥ 2 C (n) = C (n − 1) + C (n − 2) + 1.
La suite de terme général C (n) + 1 est donc la suite de Fibonacci de premiers termes 1 et 1 !
√
On en déduit classiquement que C (n) est de l’ordre de φn , où φ = 1+ 5
2 ≈ 1, 618 (nombre d’or ).
Cette complexité exponentielle est rédhibitoire. On constate expérimentalement que le calcul de fib(30)
prend déjà plusieurs secondes, même sur une machine rapide. . . Cela provient des calculs redondants
impliqués par le double appel récursif.
Il est possible de se ramener à un seul appel récursif en remarquant que
∀n ≥ 1 fib (n, a, b) = fib (n − 1, b, a + b)
d’où la fonction suivante, qui effectue bien n − 1 additions pour n ≥ 2.
def fib(n,a,b):
if n==0:
return a
elif n==1:
return b
else:
return fib(n-1,b,a+b)
On parle dans ce cas de récursivité terminale, car l’appel récursif constitue une expression à lui tout
seul, ce qui simplifie le “dépilage” des calculs en attente. . .

Mémoïsation (complément hors programme)

Une autre idée pour éviter les appels redondants est de mémoriser au fur et à mesure (dans une variable
globale !) les valeurs prises par la fonction programmée. Idée à manipuler avec précaution puisqu’elle
a un coût en espace mémoire. . .
Avec Python, la structure naturelle de stockage de valeurs associées à une clé est le dictionnaire (cf. la
documentation de Python). Lorsque les clés sont les entiers naturels successifs, on peut aussi utiliser
une liste. . .
Au moment de calculer f (n) on commence par vérifier s’il existe dans le dictionnaire une entrée de la
forme n : f (n) ; si oui, on renvoie directement la valeur stockée, sinon on calcule récursivement f (n),
sans oublier de stocker cette nouvelle valeur dans le dictionnaire !
1. Méthodes de programmation Page 5

Voici un exemple de mise en œuvre, où je déclare une fonction locale récursive fibo avec pour seul
paramètre n.

def fib_mem(n,a,b):
table={0:a,1:b}

def fibo(n):
if not(n in table):
table[n]=fibo(n-1)+fibo(n-2)
return table[n]

return fibo(n)

Noter le test n in table, qui renvoie vrai ou faux selon que n est ou non la clé de l’une des entrées du
dictionnaire, tandis que l’affectation table[n]=... crée une nouvelle entrée si n ne figure pas encore
parmi les clés, modifie la valeur associée à la clé n si elle existe déjà.

d) Recherche dichotomique dans un tableau trié

La recherche linéaire dans un tableau quelconque a une complexité linéaire mais, lorsque le tableau est
préalablement trié, on peut (il faut !) en profiter pour accélérer la recherche : l’idée est de comparer la
valeur cherchée à la valeur médiane et de relancer la recherche dans la “bonne” moitié du tableau, tant
que le tableau comporte au moins deux valeurs (avec au plus une valeur la “recherche” est vite faite !).
Comme on divise par deux (à peu près. . . ) la taille du tableau à chaque étape, la complexité est de
l’ordre de log2 n où n est la taille du tableau.
L’algorithme se prête aussi bien à une programmation itérative que récursive. Il faut juste prendre
garde à couper le tableau en deux parties de taille strictement inférieure à n.
On vérifie que c’est bien le cas lorsque, partant de la tranche t [i : j] (avec i < j − 1), on pose
m = (i + j) //2 et l’on considère les deux tranches t [i : m] et t [m : j]. Dans ce cas m sera l’indice
de la première valeur de la tranche de droite.
Attention aux algorithmes qui ne se terminent pas, avec un autre choix des deux “moitiés” qui
partagerait 2 en 2 + 0 ou 0 + 2. . .

Voici les traductions en Python, deux programmes recevant x et t et renvoyant True ou False selon
que x est présent ou non dans t (précondition : t est non vide et trié en ordre croissant) :

Version itérative Version récursive

def Cherche(x,t): def Cherche(x,t):
i=0 #fonction auxiliaire récursive
j=len(t) def DansTranche(i,j):
while i<j-1: if i==j-1:
m=(i+j)//2 return t[i]==x
if t[m]<=x: else:
i=m m=(i+j)//2
else: if t[m]<=x:
j=m return DansTranche(m,j)
return t[i]==x else:
return DansTranche(i,m)
#fonction principale triviale
return DansTranche(0,len(t))

Remarquer l’utilisation des expressions booléennes : l’évaluation de t[0]==x renvoie True ou False,
pas besoin de test pléonastique !
Attention aux “pythonneries” du genre Cherche(x,t[:m]) qui fournissent une version récursive sé-
duisante, mais recèlent un coût caché linéaire, car Python doit recopier les valeurs de la tranche con-
sidérée. . .
1. Méthodes de programmation Page 6

III - “Diviser pour régner”

1) Principes généraux
Pour traiter un “problème” de taille N, il est parfois efficace de :

a) partager le problème en k sous-problèmes de taille ⌊N/2⌋ ou ⌈N/2⌉ (k ∈ N∗ )

b) résoudre les k problèmes ainsi obtenus (souvent récursivement. . . )

c) fusionner les résultats ainsi obtenus pour fournir la solution

Analyse de la complexité (complément hors programme)

Il existe diverses versions de ce que l’on appelle dans la littérature le “master theorem”, permettant
d’obtenir une estimation asymptotique du coût de la résolution d’un problème de taille N selon ce
principe.
Ledit coût C (N) vérifie une relation de récurrence de la forme :
C (N) = k · C (N/2) + f (N)
où f (N) représente le coût total de partage et fusion.
Pour simplifier, on convient d’écrire k ·C (N/2) au lieu de l’expression exacte a·C (⌊N/2⌋)+b·C (⌈N/2⌉)
(où a + b = k). On peut montrer en effet que le résultat ne dépend pas du couple (a, b) tel que a + b = k.
On a par exemple le résultat suivant, avec des hypothèses simples sur f (mais pas toujours satisfaites. . . ).
Si k > 1, f croissante et f (N) = Θ (N p ) pour un certain p de N, alors, en posant ω = log2 k, on a :
• si 2p < k (i.e. p < ω), alors C (N) = Θ (N ω ) ;
• si 2p = k (i.e. p = ω), alors C (N) = Θ (N ω log2 N) ;
• si 2p > k (i.e. p > ω), alors C (N) = Θ (N p ).
Remarques
1) On peut remplacer Θ par O.
2) On peut généraliser le résultat au cas du partage en sous-problèmes de taille N/d, où d est un entier
au moins égal à 3.
3) Pour des résultats plus généraux, tapez master theorem dans votre moteur de recherche préféré !

2) Exemples
a) Exponentiation rapide
L’algorithme récursif est le suivant, pour le calcul de xN : x0 = 1 et
si N est pair, alors xN = (x ∗ x)⌊N/2⌋ , sinon xN = x ∗ (x ∗ x)⌊N/2⌋ ,
Déterminons le type de relation de récurrence vérifiée par le nombre C (N) de multiplications de réels
nécessaires au calcul de xN : ici le “partage” (calcul de x ∗ x avant l’appel récursif) nécessite une
multiplication, la “fusion” des résultats zéro ou une, selon la parité de N ; ainsi :
C (N) = C (⌊N/2⌋) + Θ (1)
Noter qu’ici la version ci-dessus du master theorem ne s’applique pas (f n’est pas croissante. . . ), mais
on constate que, si l’écriture en base 2 de N est
n
N = [bn . . . , b0 ]2 (i.e. N = bj 2j avec bn = 1 et bj ∈ {0, 1} pour tout j),
j=0
alors celle de ⌊N/2⌋ est [bn . . . , b1 ]2 tandis que b0 = N mod 2.
n−1
On en déduit facilement que C (N) = n + bj , or n = ⌊log2 N⌋ d’où
j=0
C (N) = Θ (log2 N) avec précisément ⌊log2 N⌋ ≤ C (N) ≤ 2 ⌊log2 N⌋ .
1. Méthodes de programmation Page 7

L’implémentation en Python est naturelle (ne pas oublier la condition d’arrêt !) :

def exprap(x,n):
if n==0:
return 1
elif n%2==0:
return exprap(x*x,n//2)
else:
return x*exprap(x*x,n//2)

b) Produit de polynômes par la méthode de Karatsuba (hors programme)

Étant donnés deux polynômes P (X) et Q (X) de degré au plus N = 2n , on écrit :
P = A + X N/2 · B et Q = C + X N/2 · D où A, B, C, D sont de degré au plus N/2
et l’on développe :
P · Q = A · C + X N/2 · (A · D + B · C) + X N · (B · D) .
On peut se contenter de trois produits de polynômes de degré au plus N/2, à savoir
A · C, B · D, (A + B) · (C + D)
en remarquant que
A · D + B · C = (A + B) · (C + D) − A · C − B · D.
Ainsi, le coût C (N) en nombre de multiplications vérifie la relation de récurrence :
C (N) = 3 · C (N/2)
et l’on en déduit :
C (N) = Θ (N ω ) où ω = log2 3 ≈ 1, 585.
Remarques :
• Avec l’algorithme naïf, C (N) = Θ N 2 ; on a par exemple N ω < N 2 /2 pour N ≥ 6 et N ω < N 2 /10
pour N ≥ 257.
• La transformée de Fourier rapide fournit un algorithme de calcul approché en Θ (N log2 N).

c) Produit de matrices carrées par la méthode de Strassen (hors programme)

De même, pour effectuer le produit de deux matrices carrées d’ordre N = 2n , en les découpant en
quatre blocs d’ordre N/2, on peut se contenter de sept produits de matrices d’ordre N/2. Ainsi, le coût
C (N) en nombre de multiplications vérifie la relation de récurrence :
C (N) = 7 · C (N/2)
et l’on en déduit :
C (N) = Θ (N ω ) où ω = log2 7 ≈ 2, 807.
Ici, le coût de l’application naïve de la définition du produit matriciel est un Θ N 3 .

Pour les détails, afin de calculer :

A B E F AE + BG AF + BH
× = ,
C D G H CE + DG CF + DH
on calcule les sept produits :
M1 = (B − D) × (G + H) ; M2 = (A + D) × (E + H) ; M3 = (A − C) × (E + F ) ;
M4 = (A + B) × H ; M5 = A × (F − H) ; M6 = D × (G − E) ; M7 = (C + D) × E
et l’on remarque (habilement !) que :
AE + BG = M1 + M2 − M4 + M6
AF + BH = M4 + M5
CE + DG = M6 + M7
CF + DH = M2 − M3 + M5 − M7