NUMÉRIQUE ET
SCIENCES ALGORITHMIQUE Cours 1ere
INFORMATIQUES
1 L’ALGORITHMIQUE : GÉNÉRALITÉS
DÉFINITION Un algorithme prend en entrée des données et fournit, en un
nombre fini d’étapes, la réponse à un problème.
ALGORITHME VS PROGRAMME
Un algorithme est un concept, tandis qu'un programme est l'implémentation de
ce concept. Ainsi, un programme est entièrement dépendant de la machine qui
va l'exécuter, contrairement à un algorithme.
Un algorithme est une idée, formulée sous forme d'instructions. Il ne dépend
d'aucun formalisme, et ne constitue qu'une suite d'étapes permettant d'atteindre un but, quelle que soit la manière dont ces
étapes sont décrites. Un algorithme ne dépend donc d'aucun support. Exemple : recette de cuisine, trajet routier..
Un programme quant à lui est une représentation en mémoire d'une suite d'instructions exécutables par une unité de traitement
logique (processeur). Il s'agit de l'écriture de l’algorithme, dans un langage qui puisse être interprété par la machine. Parmi ces
langages de programmation, vous pouvez par exemple trouver le C, C++, Java, Python, …
La distinction entre un algorithme et un programme est de la même nature que celle qui différencie une histoire et un livre.
1.A PROUVER LES ALGORITHMES
Comme dans toutes les sciences, on prouve en informatique ce que l’on avance. La preuve ne se fait pas d’une manière
expérimentale comme en physique ou en svt, mais de manière plus formelle, comme en mathématiques.
La preuve d’un algorithme se fait en 2 étapes: preuve de terminaison et preuve de correction
1. Preuve de terminaison
Il faut s’assurer que le programme se termine, c'est-à-dire que l’on ne reste pas bloqué dans une boucle (boucle infinie).
Pour prouver cela, nous allons utiliser un variant de boucle.
Variant de boucle On appelle variant d’une boucle une expression dont la valeur varie à chacune des itérations de la
boucle.
Il s’agit généralement d’une quantité entière qui :
● doit être positive ou nulle pour rester dans la boucle ;
● doit décroître strictement à chaque itération.
Si vous trouvez une telle quantité, il est évident que l’on va nécessairement sortir de la boucle au bout d’un nombre fini
d’itérations, puisque un entier positif ne peut décroître indéfiniment.
2. Preuve de correction
Il faut ensuite vérifier que notre fonction nous renvoie bien le résultat attendu (que notre boucle fait bien ce que l’on attend
d’elle). Pour cela il faut trouver un invariant de boucle.
Invariant de boucle On appelle invariant de boucle une propriété qui ne change pas lors d’une itération de boucle : Si
elle est vraie avant, alors elle est vraie après la boucle.
1.2 LA COMPLEXITÉ
L'objectif premier d'un calcul de complexité algorithmique est de pouvoir comparer l’efficacité d’algorithmes résolvant le même
problème. Dans une situation donnée, cela permet donc d'établir lequel des algorithmes disponibles est le meilleur.
Il existe deux types de complexité :
1. Complexité temporelle
L’objectif d’un calcul de complexité algorithmique temporelle est de pouvoir comparer l’efficacité d’algorithmes résolvant le
même problème. Réaliser un calcul de complexité en temps revient donc à compter le nombre d’opérations élémentaires
(affectation, calcul arithmétique ou logique, comparaison…) effectuées par l’algorithme.
2. Complexité spatiale
La complexité en espace est quant à elle la taille de la mémoire nécessaire pour stocker les différentes structures de données
utilisées lors de l'exécution de l'algorithme.
NSI Algorithmique: Cours page 1/7
2 LES ALGORITHMES DE TRIS
Qu’est ce que le tri ?
Il peut être intéressant de ranger les valeurs d’un tableau dans un ordre croissant ou décroissant. Trier un tableau, c’est donc
ranger les éléments de ce tableau dans un ordre défini (croissant ou décroissant).
Le tri possède d’innombrables applications. Une fois que les données sont triées, il est très rapide de comparer deux tableaux par
exemple. Cela peut nous permettre aussi de déterminer simplement la valeur min, la valeur max, la médiane etc…
De quoi avons-nous besoin ?
Pour fonctionner correctement, un algorithme de tri doit respecter la spécification suivante :
IN
: Tableau d’éléments tous comparables deux à deux par un ordre
OUT : Tableau d’éléments triés selon cet ordre du plus petit au plus grand
2.A TRI PAR SÉLECTION
PRINCIPE Le tri par sélection (ou tri par échange) est sans doute le tri le plus simple à imaginer. Le principe est de chercher
le plus petit élément du tableau et de le mettre en premier. Ensuite, repartir du second élément et chercher le plus petit
élément du tableau restant pour le mettre en second, etc..
EXPLICATION Le tri par sélection parcourt le tableau de la gauche vers la droite, en maintenant sur la gauche une partie
déjà triée et à sa place définitive :
0 i
t éléments déjà triés plus grand non triés EXEMPLE
A chaque étape, il faut chercher le plus petit élément dans la partie
droite non triée, puis l’échanger avec l’élément le plus à gauche de la
partie non triée. Ainsi, la première étape va déterminer le plus petit
élément et le placer tout à gauche du tableau. Puis la deuxième étape va
déterminer le deuxième plus petit élément et le placer dans la deuxième
case du tableau et ainsi de suite.
Par construction, la partie gauche déjà triée ne contient que des
éléments inférieurs ou égaux à ceux de la partie de droite restant à trier.
FONCTION PYTHON
def tri_selection(tab):
"""Trie par ordre croissant un tableau contenant des éléments comparables
IN: un tableau tab de longueur n
OUT: retourne le tableau trié par ordre croissant"""
for i in range(len(tab)):
indice_min = i
for j in range(i+1,len(tab)) :
if tab[j] < tab[indice_min] :
indice_min = j
if indice_min != i :
temp = tab[i]
tab[i] = tab[indice_min]
tab[indice_min] = temp
return tab
assert tri_selection([0,8,3,4,9,50,2]) == [0, 2, 3, 4, 8, 9, 50]
Il est légitime de se demander si c’est là une façon efficace de trier un tableau.
NSI Algorithmique: Cours Mélodie Passieux page 2/7
COMPLEXITÉ TEMPORELLE La complexité de l’algorithme de tri par sélection est de type (n²) : on dit qu’elle est
quadratique. C'est-à-dire que pour un tableau de taille 5, le nombre d’opérations élémentaires nécessaires pour trier ce
tableau avec l’algorithme de tri par sélection sera de l’ordre de 5² = 25 opérations (ici l’opération élémentaire prise en compte
est la comparaison de 2 éléments).
Si je double la taille du tableau (donc considérons maintenant un tableau de taille 10), le nombre d’opérations sera lui multiplié
par 4 (pour un tableau de taille 10, on considère qu’il faut 100 opérations). C’est pour cela, que l’on dit que la complexité du tri
par sélection est quadratique. Ceci est dû aux deux boucles For imbriquées qui parcourent l’ensemble du tableau.
PREUVE DE TERMINAISON Les boucles For se terminent obligatoirement. Les variants sont les variables d’itérations du
For soit ici les variables i pour le 1er For et j pour le second.
PREUVE DE CORRECTION Un invariant n’est pas nécessairement un nombre, cela peut être une propriété plus générale.
L’invariant que l’on utilise dans le cadre du tri par sélection, est : “la partie gauche du tableau est toujours triée”
● Au début de la ième étape , les i-1 premiers éléments du tableau sont triés par ordre croissant.
● Au début de la ième étape , les éléments de rang supérieurs ou égal à i sont tous supérieurs au i-1 ème élément.
2.B TRI PAR INSERTION
PRINCIPE C’est le tri du joueur de cartes. On fait comme si les éléments à trier étaient donnés un par un, le premier élément
constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément pour constituer une liste triée de
longueur 2, puis on range le troisième élément pour avoir une liste triée de longueur 3 et ainsi de suite...
Le principe du tri par insertion est donc de parcourir tous les éléments du tableau, chaque élément étant inséré à sa place dans
les éléments déjà triés qui le précèdent.
EXEMPLE
5 3 1 8 5 2 9 i=0
EXPLICATION
Le principe du tri par insertion est de trier les éléments du tableau comme
3 5 1 8 5 2 9 i=1
avec des cartes :
● On prend nos cartes mélangées dans notre main.
● On crée deux ensembles de cartes, l’un correspond à l’ensemble de 1 3 5 8 5 2 9 i=2
cartes triées, l’autre contient l’ensemble des cartes restantes (non
triées).
● On prend au fur et à mesure, une carte dans l’ensemble non trié et 1 3 5 8 5 2 9 i=3
on l’insère à sa bonne place dans l’ensemble de carte triée.
● On répète cette opération tant qu’il y a des cartes dans l’ensemble
1 3 5 5 8 2 9 i=4
non trié.
1 2 3 5 5 8 9 i=5
1 2 3 5 5 8 9 i=6
FONCTION PYTHON
def tri_insertion(tab):
"""Trie par ordre croissant un tableau contenant des éléments comparables
IN: un tableau tab de longueur n
OUT: retourne le tableau trié par ordre croissant"""
for i in range(1,len(tab)):
element = tab[i]
j = i
while j>0 and tab[j-1]>element:
tab[j]=tab[j-1]
j = j-1
tab[j]=element
return tab
assert tri_insertion([0,8,3,4,9,50,2]) == [0, 2, 3, 4, 8, 9, 50]
COMPLEXITÉ La complexité de l’algorithme de tri par insertion est également quadratique, c’est-à-dire de type (n²)
NSI Algorithmique: Cours Mélodie Passieux page 3/7
Cependant, la complexité dans le meilleur des cas (c’est-à-dire un tableau déjà trié) devient linéaire, c’est-à-dire de type (n).
Cet algorithme est donc intéressant à utiliser dans les cas où on sait que le tableau est quasiment trié.
PREUVE DE TERMINAISON Comme pour le tri par sélection, nous n’avons pas besoin de preuve de terminaison pour la
boucle for.
En revanche, en ce qui concerne la boucle while, il nous faut trouver un variant de boucle.
La condition d’arrêt de la boucle while est : j>0 and tab[j-1] > element
La boucle while se termine donc si une des 2 sous conditions est fausse.
Comme j décrémente de 1 à chaque itération, il finira obligatoirement par arriver à 0.
Le variant de boucle est donc tout simplement j .
PREUVE DE CORRECTION Ici l’invariant de boucle est que les i premiers éléments sont triés.
● C’est vrai dès le départ car on commence à i = 1
● Cela reste vrai car on ajoute le nouvel élément à sa place.
2.C TRI FONCTION SORTED()
En python, il existe une fonction sorted() qui prend en paramètre un tableau et renvoie un nouveau tableau trié :
tab1 = [5,7,6,4] [4,5,6,7]
tab2 = sorted(tab1) [5,7,6,4]
print(tab2)
print(tab1)
Il existe également une méthode sort() qui trie le tableau objet de la méthode :
L1 = [5,7,6,4] [4,5,6,7]
[Link]()
print(L1)
3 RECHERCHE DICHOTOMIQUE
La recherche d’un élément dans un tableau fait partie des problèmes récurrents en informatique. Lorsque le tableau est trié, la
recherche dichotomique est beaucoup plus rapide que la recherche séquentielle.
PROBLÈME POSÉ Nous cherchons si un élément e est présent dans un tableau tab trié.
Exemple : L’élément 17 est- il présent dans le tableau tab = [1, 2, 5, 9, 10, 14, 17, 24, 41] ?
Avec une recherche séquentielle, il faut parcourir le tableau du début à la fin en comparant chaque valeur à e.
Dans le pire des cas (si e est plus grand que la dernière valeur dans tab), le tableau doit être parcouru en entier.
Dans l’exemple précédent, si le nombre cherché est 42, il faudrait faire 9 comparaisons
Comme le tableau de départ est trié, il existe un moyen pour améliorer les performances de la recherche : la méthode
par dichotomie ou recherche dichotomique.
FONCTION PYTHON
Voici la programmation python de la fonction recherche dichotomique d’un élément dans un tableau trié.
def recherche_dichotomique( nbr_cherche, tableau_trie ):
"""Renvoie vrai si nbr_cherche est présent dans tableau_trie sinon renvoie faux
IN: nbr_cherche est un nombre entier, tableau_trie est un tableau d'entier rangé
par ordre
croissant
OUT: Renvoie le booléen True si nbr_cherche est présent dans le tableau, False
sinon"""
indice_min = 0
indice_max = len(tableau_trie) -1
trouve = False
while not trouve and indice_min <= indice_max :
indice_milieu = (indice_min + indice_max) // 2
if tableau_trie[indice_milieu] == nbr_cherche :
trouve = True
NSI Algorithmique: Cours Mélodie Passieux page 4/7
elif nbr_cherche > tableau_trie[indice_milieu] :
indice_min = indice_milieu + 1
else :
indice_max = indice_milieu -1
return trouve
PRINCIPE
Tant qu’il reste au moins 1 case à explorer dans l’intervalle
Prendre la valeur de la case centrale du tableau et comparer cette valeur avec l’élément recherché :
Si la valeur est celle recherchée : la recherche est terminée et l’élément est trouvé (True)
Si la valeur est strictement plus petite que l’élément recherché, reprendre la méthode avec la première moitié du tableau
Sinon reprendre la méthode avec la seconde moitié du tableau.
Recherche de l’élément 14 dans le tableau trié Recherche de l’élément 18 dans le tableau trié
[1, 2, 5, 9, 10, 14, 17, 24, 41] [1, 2, 5, 9, 10, 14, 17, 24, 41]
⬇ ⬇
1 2 5 9 10 14 17 24 41 1 2 5 9 10 14 17 24 41
⬆ 10 < 14 ⬆ ⬆ 10 < 18 ⬆
Indice_min Indice_max Indice_min Indice_max
⬇ ⬇
1 2 5 9 10 14 17 24 41 1 2 5 9 10 14 17 24 41
17 > 14 ⬆ ⬆ ⬆ ⬆
Indice_min Indice_max 17 < 18 Indice_min Indice_max
⬇ ⬇
1 2 5 9 10 14 17 24 41 1 2 5 9 10 14 17 24 41
⬆⬆ ⬆
Indice_min ⬆
24 > 18 Indice
14 trouvé Indice_max Indice_min
_max
Dans cet exemple, il suffit donc de 3 tours de boucle, pour ⬇
trouver l’élément 14 dans le tableau. Avec une recherche 1 2 5 9 10 14 17 24 41
séquentielle, 6 tours auraient été nécessaires. ⬆ ⬆
Indice Indice
indice_max < indice_min
_max _min
18 non trouvé
Dans cet exemple, il suffit donc de 3 tours de boucle pour
conclure qu’un élément n’est pas présent dans un tableau de
taille 9. Avec la recherche séquentielle, 8 tours auraient été
nécessaires.
PREUVE DE TERMINAISON Pour le cas qui nous occupe, le variant de boucle est la taille du tableau à traiter (qui diminue à
chaque itération). La valeur indice_max - indice_min correspond à cette taille. La condition de la boucle while étant
indice_min <= indice_max (la boucle se termine dès que indice_max > indice_min) cela correspond à ce que le variant
soit positif ou nul.
PREUVE DE CORRECTION Dans le cas de la recherche dichotomique, on veut prouver que si le nombre cherché
appartient au tableau initial, alors il est toujours compris entre tableau_trie[indice_min] et tableau_trie[indice_max].
On peut donc dire que si nbr_cherche est dans tableau_trie alors:
tableau_trie[indice_min ] <= nbr_cherche <= tableau_trie[indice_max]
Pour effectuer la preuve par correction, il faut prouver que cet invariant est vrai avant et après l’exécution de la boucle, ainsi
qu’à chaque itération.
COMPLEXITÉ Afin de mesurer l’efficacité de la recherche dichotomique par rapport à celle de la recherche séquentielle, nous
allons considérer le “pire des cas” : il s’agit ici du cas où le nombre cherché est supérieur au dernier élément du tableau (pour la
recherche séquentielle).
Nous allons nous intéresser au nombre de valeurs examinées pendant l'exécution des fonctions, c'est-à-dire au nombre
d’itérations de la boucle while.
Taille du tableau 0 1 2 4 8 16 30 50 128 1024 N
NSI Algorithmique: Cours Mélodie Passieux page 5/7
Recherche séquentielle 0 1 2 4 8 16 30 50 128 1024 N
Recherche dichotomique 0 1 2 3 4 5 5 6 8 11 log₂(N)+1
Pour information : log₂(8) = 3 car 23 = 8.
On admettra que la complexité de l’algorithme de recherche dichotomique est logarithmique, c’est-à-dire O(log₂(n)). Il est
donc meilleur que l’algorithme de recherche séquentielle qui est de complexité linéaire, c’est-à-dire O(n) .
4 CONCLUSION SUR LES ALGORITHMES PRÉCÉDENTS
Le tri par sélection est un tri facile à implémenter. Il est
cependant peu efficace car il a un coût quadratique (n²)
que ce soit dans le pire des cas (tableau trié par ordre
décroissant) ou dans le meilleur (tableau déjà trié).
Le tri par insertion est également peu efficace car il a un
coût quadratique (n²) dans la plupart des cas.
Cependant, il devient très intéressant dans le cas où le
tableau est trié (ou quasiment trié) car sa complexité
devient linéaire (n) .
Pour information, les algorithmes comme le tri fusion, le
tri rapide ou le tri de python sorted(), ont une complexité
en (nlog(n)) (donc plus performants que les deux
précédents). On dit qu’ils sont linéarithmiques.
Enfin, l’algorithme de recherche dichotomique est un
algorithme très optimisé. Sa complexité est
logarithmique (log₂(n)). Cet algorithme fait partie
des algorithmes de recherche les plus performants.
5 ALGORITHMES GLOUTONS
DÉFINITION Un algorithme glouton (greedy algorithm) désigne une stratégie universelle dont l’objectif est de “gagner le plus
possible à chaque étape de l’algorithme”, sans jamais se soucier des conséquences des choix effectués.
PRINCIPE Utiliser un algorithme glouton consiste à optimiser la résolution d’un problème en utilisant l’approche suivante :
on procède étape par étape , en faisant, à chaque étape, le choix qui semble le meilleur, sans jamais remettre en question les
choix passés.
AVANTAGE Le principal avantage des algorithmes gloutons est leur facilité de mise en œuvre ainsi que leur faible coût
exécution
INCONVÉNIENT Le principal défaut est qu'ils ne renvoient pas toujours la solution optimale
PROBLÈME DU RENDU DE LA MONNAIE Ce problème consiste à
définir comment rendre la monnaie avec le minimum de pièces et de
billets.
L’algorithme glouton donnera une réponse optimale uniquement si le
système monétaire est canonique ( c'est-à -dire que l’on peut rendre
toute somme d’argent de manière optimale à l’aide d’un algorithme
glouton), comme c’est le cas pour le système monétaire européen.
PROBLÈME DU SAC À DOS Ce problème consiste à remplir un sac, de capacité
maximale fixée, de manière optimale, en choisissant uniquement certains objets dans
une liste d’objets proposés. Cette classe de problèmes ne peut pas être résolue de façon
optimale avec une stratégie gloutonne.
Le problème du sac à dos fait partie des 21 problèmes dit NP-complets identifiés par
Richard Karp en 1972.
NSI Algorithmique: Cours Mélodie Passieux page 6/7
Comme les problèmes NP-complets sont réputées pour etre des problèmes les plus
difficiles à résoudre en optimisation combinatoire, un prix de 1 million de dollars
récompensera celui qui saura les résoudre dans un temps raisonnable
6 ALGORITHME DES K PLUS PROCHES VOISINS
Algorithme des k plus proches voisins
[Link]
[Link]
NSI Algorithmique: Cours Mélodie Passieux page 7/7