Exemple d'algorithme

Algorithme 1

Ecrire un algorithme qui permet de lire un entier "n" strictement positif et qui calcule la somme des "n" premier nombres positifs.

1) Algorithme

1a: somme
var N: entier
S: réel
debut
répéter
lire(N)
jusqu'à N>0
S←N*(N+1)/2
écrire('la somme de ',n,'premiers termes est: ,'S)
fin
Ici on a 3 opérations fixes

2) Algorithme

1b: somme
var n, i, S: entier
debut
écrire('Entrez un entier positif')
lire(x)
tant que n<=0 faire
écrire('Veuillez ressaisir votre nombre')
lire(x)
fin tant que
S←0
pour i=1 à n faire
S←i+S
fin pour
écrire('la somme des,'n', premier nombres positifs est ,'S)
fin
Ici on a n opération qui vont varier en fonction de n

Algorithme 2

Ecrire un algorithme qui permet de lire un entier "n" strictement positif et qui affiche tous les multiples de 3 inférieurs ou égaux à "n"

1) Algorithme 2a: multiple 3
var i, n: entier
debut
répéter
lire(n)
jusqu'à n>0
pour i=1 à n faire
si imod(3)=0 alors
écrire(i)
fin si
fin tant que
fin

2) Algorithme 2b: multiple 3
var i, n: entier
debut

répéter
lire(n)
jusqu'à n>=0
i←1
tant que i<=n faire
si imod3=0 alors
écrire(i)
fin si
i←i+1
fin tant que
fin

 

---

Efficacité et complexité d'un algorithme

Dans l'algorithme 1a, on a fait n additions.
Dans l'algorithme 1b, on a fait 3 opérations (une addition, une multiplication et une division)
Dans l'algorithme 2a, on a fait 2n+3 comparaisons, et n+1 opérations.
Des algorithmes produisant les mêmes résultats peuvent être très différent du point de vu des principes utilisés et du point de vu principes utilisés et du temps nécessaire pour obtenir les résultats.
On dit qu'un algorithme a, est plus efficace qu'un algorithme b si l'algorithme a fait bon usage des ressources de temps de traitement et mémoire par rapport à b. La mesure de l'efficacité d'un algorithme s'effectue en utilisant les notions de complexité théorique.

La complexité pratique (T_n)

C'est la mesure précise du temps et de la taille mémoire nécessaire à l'exécution d'un algorithme. T_n: Temps d'exécution

Complexité théorique

C'est un ordre de grandeur des coûts théoriques indépendants des conditions pratiques l'exécution (c'est une généralisation de la complexité pratique).

Exercice 2:

Calculer la complexité théorique de l'algorithme qui effectue la multiplication de deux matrices.
Pour des données de même taille le temps d'exécution peut être fonction de la valeur des données dans ce cas on définit deux types de complexité:

 

---

La recherche dans un vecteur

Recherche séquentielle linéaire

Il s'agit de rechercher un élément dans un vecteur en effectuant un parcours séquentiel. La fonction correspondante est la suivante.

fonction recherche_sequentielle(V: vecteur, n, val, pos: entier): booléen
debut
i←2
tant que i<=N et val≠V[1] faire
i←i+1
fin tant que
si val=V[i] alors
recheche-sequentielle ← vraie
pos ← i
sinon
recherche-sequentielle ← faux
fin si
fin

Temps favorable (T_n)
T_N=3T_C
vals = 7

V :	7 4 2 1 3 5

Temps défavorable (T_D)
val = 7

V :	5 4 2 1 3 7

T_N = 5T_a+13T_C = (n-1)T_a+(2n+1)T_C

Recherche séquentielle avec sentinelle

fonction recherche_sequentielle(V: vecteur, N, val, pos: entier): booleen
var i: entier
debut
V[N+1] ← val
i ← i+1
fin tant que
si i<=N alors
recherche_sequentielle ←- vraie
pos ← i
sinon
recherche_sequentielle ← faux
fin si
fin

Recherche dichotomique

La recherche dichotomique suppose que le vecteur dans lequel on recherche une valeur "val" donnée est triée. Supposons que le vecteur est trié dans l'ordre croissant. Soit "min" et "max" les valeurs minimales et maximales de l'ensemble des indices du vecteur V. Le principe de la recherche dichotomique est le suivant:

fonction rech(V: vecteur, n, val, pos: entier): booléen
var, mil, min, max: entier
trouve: booléen
debut
min ← 1
max ← n
trouve ← faux
tant que (min < max) et (non trouve) faire
mil ← (min+max)div2
si val < V[mil] alors
max ← mil
sinon
si val > V[mil] alos
mil ← mil+1
fin si
trouve ← val=V[mil]
fin tant que
rech ← trouve
fin

Les algorithmes simples de tri

Trier un ensemble de n informations consiste à classer ces fonctions selon certains critères (ordre croissant, ordre décroissant, ordre alphabétique)

Le tri sélection

La procédure correspondante est la suivante

procédure tri_selection(V: vecteur, n: entier)
var i, j, aux, pos: entier
debut
pour i=1 à n-1 faire
pos <-- i
pour j=i+1 à n faire
si V[pos] > V[j] alors
pos ← j
fin si
fin pour
aux ← V[pos]
V[pos] ← V[i]
V[i] ← aux
fin pour
fin

Exercice:

Réécrire cet algorithme en remplaçant la boucle "pour" par la boucle "répéter" et par la boucle "tant que".

Le tri par insertion

La procédure correspondante est la suivante:

procédure tri_insertion(V: vecteur, n: entier)
var i, j, x: entier
debut
pour i=2 à n faire
j ← i-1
x ← V[i]
tant que V[j]>x et j>0 faire
V[j+1] ← V[j]
j ← j-1
fin tant que
V[j+1] ← x
fin pour
fin

Exercice:

Réécrire cette procédure en remplaçant la boucle "tant que" par la boucle "répéter" et la boucle "pour" par "tant que".

Le tri par échange ou tri bulle

La procédure correspondante est la suivante:

procédure tri_bulle(V: vecteur, n: entier)
var i, aux: entier
T: booléen
debut
répéter
T ← vraie
pour i=1 à n-1 faire
si V[i]>V[i+1] alors
aux ← V[i]
V[i] ← V[i+1]
V[i+1] ← aux
T ← faux
fin si
fin pour
jusqu'à T {T=vrai}
fin

Exercice:

Réécrire cet algorithme en remplaçant la boucle "répéter" par la boucle "tant que"