NSI_1ère Charlemagne - N.

Djahnit - Algorithmique1

1 Algorithme : définition informelle

Un algorithme est un assemblage ordonné d’instructions élémentaires dont l’application
permet de résoudre un problème. Un algorithme peut être traduit, grâce à un langage de
programmation, en un programme exécutable par un ordinateur. Un bon algorithme :
— Répond correctement au problème posé,
— Est rapide,
— Gère de façon économique la mémoire.

A Bagdad, au début du IXème siècle, le mathématicien persan Mohammad ibn Moussa

Al-Khawarizmi (780-850) a écrit de nombreux ouvrages : al jabr ( a donné le mot al-
gèbre ), donnant la méthode de résolution des équations du second degré tant sous sa forme
algébrique que géométrique, kitab al jabr wa muqabala : le livre de la remise en place et
de la comparaison, Liber Algoritmi de Numero Indorum, connu seulement dans sa traduc-
tion latine explique le maniement des chiffres dans la numération de position venu d’Inde,
Algoritmus est une latinisation d’Al-Khawarizmi qui a donné le nom algorithme en français.

L’algorithme d’Euclide d’Alexandrie (env 300 ans av JC) est un algorithme fonda-
mental : calcul du pgcd(a,b) le programme en Python donne :

1 def pgcd ( a , b ) :
2 r=a % b
3 while ( r != 0 ) :
4 a,b = b, r
5 r = a % b
6 return b

L’informaticien Donald Knuth (né en 1938) a écrit en 1962 un ouvrage monumental : The
Art of Computer Programming qui décrit les caractéristiques importantes d’un algorithme.
Il a reçu de nombreux prix dont le prix Turing, prix de Kyoto, et de nombreuses médailles
(Von Neumann, Grace Murray Hopper).
Il a aussi montré que des algorithmes étaient déjà utilisés dans les calculs sur des tablettes
(bois, pierres) datant d’environ 2000 ans av JC, à Babylone, au sud de Bagdad en Irak, avec
des calculs en base 60 et des nombres écrits en virgule flottante.
Remarque : C’est aussi lui qui crée TeX : traitement de texte scientifique ( langage avec
des balises) avec lequel j’écris mes cours.

Page 1 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

2 Terminaison et correction :
Un programme A est composé :
— d’un ensemble fini V de variables comprenant une variable d’entrée E (valeur notéee)et
une variable de sortie S (valeur notées).
— d’un ensemble fini O d’opérations élémentaires portant sur les variables (arithmétiques,
logiques, affectation,...)
— d’une structure de contrôle, construite à partir de structures élémentaires : séquence-
ment( ;), test(si...alors...sinon....) , boucles (pour, tantque, répéter,..)
Une structure de contrôle définit de manière unique, pour chaque valeur e de E, la suite
A(e) des opérations de O exécutées.
Remarque : la suite A(e) peut être finie ou infinie. Un algorithme résolvant un problème
P est un programme A qui possède les propriétés de terminaison et validité :
— Terminaison : Pour toute valeur e de E, la suite A(e) est finie.
— Validité (correction partielle) : Si e est le code d’un énoncé I, la variable S contient,
lors de la terminaison, le code du résultat SP (I).
Prouver que A résout P, c’est démontrer que :
Pour tout énoncé I de P,
1. - A se termine et
2. - A est valide : il fournit la solution SP (I).

3 Notions sur les fonctions récursives et les fonctions

itératives
On appelle fonction récursive une fonction qui comporte un appel à elle-même. Une
fonction récursive doit respecter «3 lois de la récursivité» :
1. - Une fonction récursive contient un cas de base
2. - Une fonction récursive doit modifier son état pour se ramener au cas de base
3. - Une fonction récursive doit s’appeler elle-même.
On appelle fonction itérative, une fonction qui utilisera une ou des boucle(s) itérative(s)
Exemple : l’itération sur les tableaux dynamiques. Deux utilisations possibles pour par-
courir les tableaux :
1. - Faire une itération directement sur les éléments du tableau T :
for e in T :
Séquence utilisant e
2. - Faire une itération sur les indices utilisés dans le tableau :
for i in range(0,len(T)) :
Séquence utilisant T[i]
Les deux formes ont leur utilité !
Exemple : Ecrire une version itérative, puis une version récursive pour calculer la fonction
factorielle (notée : n !) d’un entier définie par :
(
n! = 1 si n = 0
n! =
n! = (n − 1)! × n si n >= 1

Page 2 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

Forme itérative : Forme récursive :

Important :
1. - voir la trace d’éxécution de cette fonction suivant la forme itérative et récursive sur le
site :
http ://www.pythontutor.com
2. - par défaut, python limite le nombre d’appels à 1000. Si l’on veut augmenter la
taille limite de la pile d’appels récursifs, il suffit d’utiliser les 2 instructions suivantes :

1 import s y s
2 sys . s e t r e c u r s i o n l i m i t (100000)

3. - Preuve pour une forme récursive :

On souhaite montrer la propriété P(n) pour tout n ≥ n0 :
— Cas de base : la propriété P(n0 )est vraie.
— Etape d’induction :
-Récurrence faible : on suppose P(n-1) : la propriété est vraie au rang n-1
-Récurrence forte : on suppose la propriété P(k) vraie pour tous les rangs n0 ≤ k ≤
n − 1 et on montre P(n) : la propriété est vraie au rang n
— Conclusion : pour tout n ≥ n0 on a P(n).
4. - Preuve pour une forme itérative :
a . On montre que l’algorithme termine.
b . Pour montrer la validité de l’algorithme, on utilise un invariant de boucle P.
C’est une propriété mathématique exprimée sur les variables d’un algorithme itératif,
qui est :
— Vérifiée à une ligne précise du code, pour toutes les itérations.
— P(k) : propriété vraie à la k-ième itération de la boucle. Ceci peut être montré par
récurrence : on montre P(1)(propriété vraie au début de la boucle), puis on montre
P (k − 1) ⇒ P (k).
— Pertinente pour démontrer la validité de l’algorithme. Si n est la dernière itération,
P(n) doit aider à prouver que l’algorithme est valide.

Page 3 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

5. - Autre exemple :
donner
Pn l’algorithme itératif et récursif pour le calcul de la somme des n premiers carrés
( j=1 j 2 ), avec n ≥ 1.
Algorithme itérative : Algorithme récursive :

4 Notions rapides sur la complexité d’algorithmes

Le but est :
— Evaluer le temps d’exécution d’un algorithme en fonction de la longueur de l’énoncé.
— Comparer les performances de différents algorithmes résolvant le même problème.
— Evaluer la taille maximale des énoncés qu’un algorithme peut traiter.
La mesure du temps est indépendante des machines : on compte le nombre d’instructions.
En pratique, on s’intéresse souvent à un ensemble restreint E des opérations de l’al-
gorithme et on évalue souvent la complexité temporelle au pire-cas, notation de Landau :
O(f(n)).
Nous verrons que les deux tris au programme en première : le tri par sélection et le tri
par insertion sont tous deux en O(n2 ) pour n termes à trier, dans le pire des cas.

Page 4 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

Durée d’exécution d’un algorithme suivant le nombre de termes n et de sa complexité :

— Chaque instruction possède une durée de 10−9 seconde.

— f(n) = nombre d’instructions de l’algorithme, pour une donnée de taille n, à des constantes
prés.

5 Les algorithmes de tri

Exercice d’introduction au tri :
Formation de groupe de 4 élèves - prendre un jeu de 5 cartes avec un nombre entier inscrit
au dos de chaque carte, par binôme. Chaque binôme rend sur une feuille une description
claire de sa méthode de tri, avec le nombre de comparaisons effectivement faites et le nombre
maximum de comparaisons par cette méthode, et une justification de ce nombre maximum.
(5min)
Consignes (5min)
— Vous disposez de 5 cartes que vous avez à trier de la plus petite à la plus grande.
— Vous ne pouvez en retourner que deux à la fois au maximum.
— Vous pouvez inverser ou non les positions des 2 cartes avant de les replacer face retour-
née.
— Vous ne devez pas « mémoriser » les valeurs inscrites sur les cartes au fur et à mesure
du travail
— Le but est de se comporter comme un algorithme qui répète les opérations de compa-
raison.
Vous noterez dans un tableau :
— le nombre de comparaisons effectuées
— le nombre de déplacement effectués
— le nombre maximum de comparaisons que votre tri peut engendrer

Vous structurerez votre description en employant obligatoirement des mots parmi les
suivants (10min) :
- D’abord, puis, ensuite, enfin, jusqu’à ce que, tant que, alors.
- Puis essayer en Pseudo-langage avec : Si, sinon, fin de si, tant que, fin de tant que,
pour, fin de pour.

Page 5 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

Votre description doit permettre à tout lecteur de trier tout paquet de cartes en utilisant
votre méthode.

Questions supplémentaires (5min) :

— Quel est le nombre maximum de comparaisons que votre tri pourrait engendrer si vous
aviez dû trier 20 cartes ? 100 cartes ? N cartes, où N est un nombre naturel strictement
supérieur à 1 ?

Phase finale de l’exercice (15min) :

Mise en commun par groupe des divers tris trouvés : explications par le groupe au reste
de la classe.

Page 6 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

6 L’introduction à la séance : Tri par Sélection

Comment trier : une liste d’entiers, un jeu de cartes, des objets selon leur poids, leurs
volumes, une dimension, etc... ?
Ce problème est simple, connu et très riche, et revient fréquemment dans la pratique.
Les nombreux algorithmes de complexités différentes chercheront à être des algorithmes
optimaux, plus efficaces.
Le problème est donc très concret et très ancien. Actuellement les opérations sont réalisées
des milliards de fois par jour par des ordinateurs, le passage à grande échelle, nous pousse
à trier toujours plus vite et toujours plus d’informations...
Rappel oral : Combien de façon de trier une liste connaissez-vous ?
Lister au tableau les réponses
Vous avez vu lors des séances 1 et 2, une introduction au tri par sélection et au tri par
insertion qui sont à votre programme de 1ère NSI.
Cette séance va vous permettre :
— Ecrire un algorithme de tri par sélection
— Montrer un invariant de boucle pour ce tri qui prouvera alors sa correction
— Justifier la terminaison de cet algorithme
— Montrer que le coût de cet algorithme est quadratique, soit dans le pire des cas, la
complexité du tri par sélection est en Θ(n2 )
Le tri par sélection par l’exemple :
Le tri par sélection est une des méthodes de tri des plus simples. On commence par
rechercher le plus grand élément (ou le plus petit) du tableau que l’on va mettre à sa
place, pour nous l’échanger avec le dernier élément, tri par ordre croissant. Puis on reitère
l’opération avec le deuxième élément, etc...
Expliquer au tableau l’algorithme avec cet exemple :

début-> [7, 2, 4, 8, 9, 5]
étape 1-> [7, 2, 4, 8, 5, 9]
étape 2-> [7, 2, 4, 5, 8, 9]
étape 3-> [5, 2, 4, 7, 8, 9]
étape 4-> [4, 2, 5, 7, 8, 9]
étape 5-> [2, 4, 5, 7, 8, 9]
fin-> [2, 4, 5, 7, 8, 9]

7 Les algorithmes :
1. - Algorithme 1 :

Algorithme 1 : MAXI : recherche du plus grand element et de son indice parmi

les n > 0 premières cases d’un tableau d’entiers nommé tab
1 indice← 0
2 maxi←tab[0]
3 for i = 0 à n − 1 do
4 si tab[i] > maxi alors
5 maxi← tab[i] ; // valeur_max
6 indice ← i ; // indice_de_la_valeur_max
7 Retourner (maxi,indice)

2. - Algorithme 2 :

Page 7 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

Algorithme 2 : TRI_SELECTION : trie un tableau tab de n éléments avec n >

0 par ordre croissant
1 for i =taille_de_tab -1 à 0 avec un pas de -1 do
2 j ← MAXI(tab,i+1) [1]
3 si tab[j] > tab[i] alors
4 temp ← tab[j] ; // 3 instructions suivantes :
5 tab[j] ← tab[i] ; // échanger tab[i] et tab[j]
6 tab[i] ← temp ; // grace la variable temp
Retourner tab

8 TP : les programmes python de la séance :

1. - Programme A : les fonctions correspondantes à l’algorithme 1 et 2 codées en python :

1 # Une v e r s i o n i t e r a t i v e de l ’ i m p l e m e n t a t i o n du t r i par s e l e c t i o n :
2
3 02/07/2019
4 @author : N a s s e r D j a h n i t
5 """
6
7 # Tri par s e l e c t i o n c o r r e s p o n d a n t aux a l g o r i t h m e s f a i t s en c o u r s
8
9 # a ) i m p o r t e r l e s modules ou b i b l i o t h e q u e s n e c e s s a i r e s :
10 from random i m p o r t r a n d i n t
11 i m p o r t m a t p l o t l i b . p y p l o t as p l t
12 i m p o r t time
13
14 # a ) D e f i n i r l a f o n c t i o n en r a p p o r t a v e c l ’ a l g o r i t h m e 1 MAXI
15
16 d e f maxi ( l , n ) :
17 ’ ’ ’ l i s t ∗ a l p h a −> ( a l p h a , i n t )
18 Hypothese : l a l i s t e l c o n t i e n t au moins un e l e m e n t
19 Retourne 2 e l e m e n t s : l e maximum d ’ une l i s t e l de n e l e m e n t s
e t l ’ i n d i c e de ce maximum
20 ’’’
21 indice = 0
22 maximum = l [ 0 ]
23 f o r i i n range ( n ) :
24 i f l [ i ] > maximum :
25 indice = i
26 maximum=l [ i n d i c e ]
27 r e t u r n (maximum , i n d i c e )
28
29 # b ) D e f i n i r l a f o n c t i o n en r a p p o r t a v e c l ’ a l g o r i t h m e 2 MAX
30 d e f t r i _ s e l e c t i o n ( l ) :
31 ’ ’ ’ l i s t ( a l p h a ) −> l i s t ( a l p h a )
32 Retourne l a l i s t e t r i e e l par o r d r e c r o i s s a n t
33 ’’’
34 f o r i i n range ( l e n ( l ) −1 ,0 , −1):
35 j = maxi ( l , i + 1 ) [ 1 ]
36 i f l [ j ]> l [ i ] :
37 l[j],l[i] = l[i], l[j]
38 return l
39 # t e s t e l a l i s t e du c o u r s :

Page 8 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

40 l = [ 7 , 2 , 4 , 8 , 9 , 5 ]
41 p r i n t ( t r i _ s e l e c t i o n ( l ) )
42
43 #C o m p l e x i t e
44
45 d e f t e s t e _ t r i _ s e l e c t i o n ( n ) :
46 l i s t e = [ r a n d i n t ( −10 ,10) f o r i i n range ( n ) ]
47 return t r i _ s e l e c t io n ( l i s t e )
48
49 d e f d u r e e ( n ) :
50 d e b u t=time . c l o c k ( )
51 t e s t e _ t r i _ s e l e c t i o n (n)
52 f i n=time . c l o c k ( )
53 r e t u r n f i n −d e b u t
54 #Programme p r i n c i p a l a v e c a p p e l d e s f o n c t i o n s :
55
56 x =[ i f o r i i n range ( 1 0 0 0 ) ]
57 y=[ d u r e e ( i ) f o r i i n x ]
58
59 p l t . t i t l e ( ’TRI_SELECTION ’ )
60 p l t . x l a b e l ( ’ n ’ )
61 p l t . p l o t ( x , y , ’ b − ’ , l a b e l =’ c o m p l e x i t e ’ )
62 p l t . l e g e n d ( )
63 p l t . s a v e f i g ( ’ t r a c e T r i S e l e c t i o n 1 . png ’ )
64 p l t . show ( )

Voici un résultat attendu :

Page 9 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

2. - Programme B : Traçons la courbe de la fonction f(x)=x2 :

1 # T r a v a i l s u r l a c o m p l e x i t e du t r i par s e l e c t i o n :
2 # −∗− c o d i n g : u t f −8 −∗−
3 """
4 Created f o r DIU − Programme NSI
5 @author : Nasser D j a h n i t
6 """
7 # Theme : l e t r i par s e l e c t i o n
8 # a ) i m p o r t e r l e s modules ou b i b l i o t h e q u e s
9 import m a t p l o t l i b . p y p l o t a s p l t
10
11 #C o m p l e x i t e
12
13 x=[ i f o r i in range ( 1 0 0 0 ) ]
14 y1 =[ i ∗∗2 f o r i in x ]
15
16
17 plt . t i t l e ( ’ Courbe ␣ de ␣x ∗∗2 ’ )
18 plt . xlabel ( ’n ’ )
19 plt . p l o t ( x , y1 , ’ b− ’ , l a b e l= ’ x ∗∗2 ’ )
20 plt . legend ()
21 plt . s a v e f i g ( ’ t r a c e Q u a d r a t i q u e . png ’ )
22 plt . show ( )

Voici un résultat attendu :

Page 10 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

9 Etude du tri par insertion :

Le tri par insertion ( classer des documents, jouer à la belote ) : on commence par
prendre le premier élément à trier que l’on place en position 1. Puis on insère les éléments
dans l’ordre en plaçant chaque nouvel élément à sa bonne place.
Par exemple : les étapes pour trier par insertion :
[12,3, 17,9,4,2,16]
[12, 3,17,9,4,2,16]
[3,12, 17,9,4,2,16]
[3,12,17, 9,4,2,16]
[3,9,12,17, 4,2,16]
[3,4,9,12,17, 2,16]
[2,3,4,9,12,17, 16]
[2,3,4,9,12,16,17]
Dans le pire cas ou en moyenne, la complexité du tri par insertion est en Θ(n2 ).
1. - Ecrire une fonction insertion(l,n) qui prend en argument une liste l dont on suppose
que les n premiers éléments sont triés et qui insère l’élément l[n] à sa place parmi les n
premiers éléments de l.
2. - Ecrire une fonction tri_insert(l) qui effectue un tri par insertion de la liste l.
3. - Écrire en Python une fonction genereListe prenant en paramètre un entier n et retour-
nant une liste de taille n dont les éléments sont des nombres aléatoires entre 1 et 1000.
(Indice : utiliser la fonction randint du module random.)
4. - Tester la fonction genereListe, insertion(l,n) et tri_insertion sur quelques exemples.
5. - Pour tester la fonction de tri, nous allons utiliser l’instruction assert. Cette instruction
est suivie d’une condition, et met fin à l’exécution du programme en affichant une erreur
si la condition n’est pas satisfaite.
Tester dans l’environnement Python :

1 a s s e r t 1==1
2 a s s e r t 1==2 # c e t t e i n s t r u c t i o n r e t o u r n e une e r r e u r

6. - Preuve de correction (répondre aux questions) :

Un algorithme est dit correct s’il satisfait deux propriétés :
— Terminaison : un algorithme se termine si pour toutes valeurs d’entrée, la suite
d’instructions formée par cet algorithme est finie (en particulier, l’algorithme ne
boucle pas à l’infini).
En pratique, pour vérifier la propriété de terminaison, nous allons vérifier que le
nombre d’itérations dans les différentes boucles mises en oeuvre est fini.
a . Par quelle valeur peut être borné le nombre d’itérations réalisées par la fonction
insertion si la liste mise en paramètre est de taille au plus n ? Justifier en quelques
mots.
b . Combien d’itérations réalise la fonction tri_insert pour une liste de taille n ?
c . En déduire que la fonction tri_insert vérifie la propriété de terminaison.
— Validité : un algorithme est valide si le résultat produit par celui-ci répond bien au
problème posé.
Pour vérifier la validité d’un algorithme itératif (par opposition à récursif), on utilise
souvent ce que l’on appelle un invariant de boucle. Un invariant de boucle est une
propriété qui est vraie au début, à la fin ou à un point donné de chaque itération.
Remarque :
Pour prouver qu’une propriété est effectivement un invariant de boucle, on utilise le
plus souvent une technique de preuve appelée "preuve par récurrence". Ce genre de
preuve n’est pas au programme de première, nous nous contenterons donc d’énoncer
un invariant de boucle, sans prouver que c’en est un.

Page 11 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

a . On suppose que la fonction insertion est valide. Donner un invariant de boucle

permettant de prouver la validité de la fonction tri_insertion.
7. - Étude de la complexité temporelle :
La complexité temporelle est une mesure du temps que va mettre l’algorithme à être
exécuté. Cela sert notamment à comparer l’efficacité de différents algorithmes répondant
à un même problème. Comme on veut une mesure de complexité indépendante de
la rapidité des processeurs et des mémoires, on définit la complexité temporelle d’un
algorithme comme le nombre d’opérations réalisées par celui-ci.
a . Complexité théorique :
Avec la propriété suivante :
˙ + 1)/2
Pour tout entier n on a : 1 + 2 + 3 + . . . + n = n(n
Prouver que dans le pire des cas , le tri insertion est quadratique. Rappel : lorsque
la complexité temporelle d’une fonction appliquée à des données de taille n est de
l’ordre de n2 , on parle de complexité quadratique.
b . Complexité pratique :
Le but de cet exercice est d’observer la complexité théorique de manière expérimen-
tale. Pour cela, nous allons utiliser le module test_complexite créé pour l’occasion.
a) Télécharger le fichier test_complexite.py et le mettre dans le même dossier que le
script Python des exercices précédents.
b) Dans le script Python des exercices précédents, importer le module à l’aide de
l’instruction :
from test_complexite import *
c) Ce module dispose d’une fonction trace_complexite qui prend en paramètre une
ou plusieurs fonctions de tris, et qui affiche le temps mis par ces fonctions pour trier
de listes de tailles n en fonction de n.
Afficher la courbe de complexité temporelle expérimentale de la fonction tri_insert à
l’aide de trace_complexite(tri_insert) Que constate-t-on ?
d) Le module contient également une autre fonction de tri appelée tri_fusion. Com-
parer la complexité expérimentale des deux fonctions à l’aide de la commande :
trace_complexite(tri_insert, tri_fusion). Que constate-t-on ?
e) le fichier Python3

1 # −∗− c o d i n g : u t f −8 −∗−
2 """
3 Created on Mon Dec 23 1 9 : 4 7 : 4 2 2019
4
5 @author : Admin
6 """
7
8 # −∗− c o d i n g : u t f −8 −∗−
9 """
10 Module de t r a c e de c o u r b e s de c o m p l e x i t e
11 """
12 # −−−−−−−−−−−−−−−−−−−−−− i m p o r t a t i o n s −−−−−−−−−−−−−−−−−−−− #
13 import random
14 import m a t p l o t l i b . p y p l o t a s p l t
15 import time
16 # −−−−−−−−−−−−−−−−−−−−−−−− f o n c t i o n s −−−−−−−−−−−−−−−−−−−−−− #
17
18 def g e n e r e _ l i s t e ( n ) :
19 " " " i n t −> l i s t [ i n t ]
20 hypothese : n est p o s i t i f
21 Retourne une l i s t e d ’ e n t i e r s a l e a t o i r e s de t a i l l e n " " "

Page 12 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

22 liste = []
23 f o r i in range ( n ) :
24 l i s t e . append ( random . r a n d i n t ( 1 , 1 0 0 0 ) )
25 return l i s t e
26
27 def f u s i o n ( l i s t e 1 , l i s t e 2 ) :
28 " " " l i s t [ i n t ] ∗ l i s t [ i n t ] −> l i s t e [ i n t ]
29 h y p o t h e s e : l i s t e 1 e t l i s t e 2 s o n t t r i e e s dans l ’ o r d r e c r o i s s a n t
30 Retourne l a l i s t e t r i e e dans l ’ o r d r e c r o i s s a n t r e s u l a n t de l a f u s i o n d e s
31 deux p a r a m e t r e s " " "
32 liste_triee = []
33 i = 0
34 j = 0
35 while i < len ( l i s t e 1 ) and j < len ( l i s t e 2 ) :
36 if liste1 [ i ] < liste2 [ j ]:
37 l i s t e _ t r i e e . append ( l i s t e 1 [ i ] )
38 i = i + 1
39 else :
40 l i s t e _ t r i e e . append ( l i s t e 2 [ j ] )
41 j = j + 1
42 i f i == len ( l i s t e 1 ) :
43 l i s t e _ t r i e e . extend ( l i s t e 2 [ j : ] )
44 i f j == len ( l i s t e 2 ) :
45 l i s t e _ t r i e e . extend ( l i s t e 1 [ i : ] )
46 return l i s t e _ t r i e e
47
48 def t r i _ f u s i o n ( l i s t e ) :
49 " " " l i s t e [ i n t ] −> l i s t [ i n t ]
50 hypothese : len ( l i s t e ) > 0
51 Retourne l a l i s t e t r i e e " " "
52 n = len ( l i s t e )
53 i f len ( l i s t e ) <= 1 :
54 return l i s t e
55 else :
56 return f u s i o n ( t r i _ f u s i o n ( l i s t e [ : n //2]) , tri_fusion ( l i s t e [ n //2:]) )
57
58 def t r a c e _ c o m p l e x i t e ( ∗ l i s t e _ f o n c t i o n s ) :
59 " " " ∗ f u n c t i o n −> v o i d
60 h y p o t h e s e : l e s f o n c t i o n s p a s s e e s en parametre s o n t d e s f o n c t i o n s de t r i
61 Trace l a c o u r b e de c o m p l e x i t e en f o n c t i o n de l a t a i l l e de l a l i s t e a t r i e r " " "
62 # i n i t i a l i s a t i o n s et declarations
63 n b _ f o n c t i o n s = len ( l i s t e _ f o n c t i o n s )
64 l i s t e _ n = l i s t ( range ( 2 0 , 501 , 2 0 ) )
65 liste_temps = [ 0 ] ∗ nb_fonctions
66 f o r i in range ( n b _ f o n c t i o n s ) :
67 l i s t e _ t e m p s [ i ] = [ 0 ] ∗ len ( l i s t e _ n )
68 # c a l c u l s de d u r e e s
69 f o r i in range ( len ( l i s t e _ n ) ) :
70 n = liste_n [ i ]
71 donnees = g e n e r e _ l i s t e ( n )
72 f o r j in range ( n b _ f o n c t i o n s ) :
73 fonction = liste_fonctions [ j ]
74 t a c = time . c l o c k ( )
75 f o n c t i o n ( donnees )
76 t i c = time . c l o c k ( )
77 liste_temps [ j ] [ i ] = t i c − tac

Page 13 sur 14
NSI_1ère Charlemagne - N. Djahnit - Algorithmique1

78 # couleurs :
79 coul = [ " ␣ blue ␣ " , " red " , " ␣ green ␣ " , " ␣ orange ␣ " ]
80 # trace
81 f o r j in range ( n b _ f o n c t i o n s ) :
82 plt . plot ( liste_n , liste_temps [ j ] , color = coul [ j ] )
83 p l t . show ( )

Page 14 sur 14