Algorithmes : organigrammes, programmation structurée et complexité
Propriétés d'un algorithme, organigrammes et pseudo-code avec l'algorithme d'Euclide, le théorème de Böhm-Jacopini, la notation grand O et la recherche dichotomique.
https://www.electronics-engineering.com/fr/algorithmes-organigrammes-complexite/
Un algorithme est une suite finie d’instructions non ambiguës qui résout un problème. Le mot vient du nom du mathématicien persan al-Khwarizmi, et le premier algorithme que l’on connaisse, celui d’Euclide pour le plus grand commun diviseur, a plus de deux mille ans. Avant d’écrire du code il vaut la peine de concevoir l’algorithme : c’est là qu’on décide si le programme sera correct et rapide. Dans cette leçon nous voyons comment on décrit un algorithme, les structures de base de la programmation structurée et comment on mesure le coût, c’est-à-dire la complexité.
Propriétés d’un algorithme
- Finitude : il se termine après un nombre fini de pas.
- Non-ambiguïté : chaque pas a un sens unique.
- Entrée et sortie : il reçoit des données et produit un résultat.
- Effectivité : chaque pas peut vraiment être exécuté avec les opérations disponibles.
- Généralité : il résout une classe de problèmes, pas un seul cas.
Comment le décrire : organigrammes et pseudo-code
Un organigramme représente l’algorithme avec des blocs reliés par des flèches : des ovales pour le début et la fin, des parallélogrammes pour l’entrée et la sortie, des rectangles pour les opérations, des losanges pour les décisions.

Le pseudo-code décrit le même algorithme dans un langage intermédiaire entre le français et un langage de programmation, plus compact que l’organigramme :
read a, b
while b ≠ 0:
r ← a mod b
a ← b
b ← r
write aPourquoi il fonctionne. Tout diviseur commun de
et
divise aussi
, et vice versa : donc
. Comme
, le second nombre diminue à chaque pas et atteint 0 en un nombre fini de pas, et
.
La programmation structurée
Le théorème de Böhm-Jacopini (1966, deux informaticiens italiens) démontre que tout algorithme peut s’écrire avec seulement trois structures :
- séquence : une instruction après l’autre ;
- sélection : si une condition est vraie on fait une chose, sinon une autre (
if) ; - itération : répéter tant qu’une condition est vraie (
while).
Les sauts arbitraires (goto), qui rendent le code difficile à suivre, ne sont pas nécessaires : c’est la base de la programmation structurée, et du C que nous verrons à partir de la leçon suivante.
La complexité
Deux algorithmes corrects pour le même problème peuvent prendre des temps très différents. La complexité algorithmique mesure comment le nombre d’opérations croît quand la taille
des données croît. On utilise la notation
: un algorithme est
si, pour
grand, il effectue au plus un nombre d’opérations proportionnel à
.
| Complexité | Exemple | ||
|---|---|---|---|
| accéder à un élément d’un tableau | 1 | 1 | |
| recherche dichotomique dans un tableau trié | 10 | 20 | |
| trouver le maximum d’un tableau | |||
| tri fusion, FFT | |||
| tri à bulles, DFT directe | |||
| essayer tous les sous-ensembles | impossible |
À un milliard d’opérations par seconde,
opérations prennent un quart d’heure ;
prennent deux centièmes de seconde. Améliorer l’algorithme compte bien plus qu’acheter un ordinateur plus rapide.
Exemple : combien de pas fait Euclide. Tous les deux pas le premier nombre au moins diminue de moitié (c’est facile à démontrer), donc le nombre de pas est au plus d’environ
du plus petit nombre :
. Pour des nombres de 300 chiffres, comme ceux de la cryptographie RSA, quelques milliers de pas suffisent, une fraction de milliseconde. Essayer tous les diviseurs serait impossible.
Recherche linéaire et recherche dichotomique
Chercher une valeur dans un tableau de
éléments non triés signifie les regarder un par un :
. Si le tableau est trié on peut faire bien mieux : on regarde l’élément du milieu, et selon qu’il est plus grand ou plus petit que la valeur cherchée, on écarte la moitié du tableau. Après
pas il reste
éléments, donc
pas suffisent : 20 comparaisons pour un million d’éléments, 30 pour un milliard.
/* returns the index of x in the sorted array v of n elements, or -1 */
int binary_search(const int v[], int n, int x)
{
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; /* avoids computing lo + hi, which could overflow */
if (v[mid] == x) return mid;
if (v[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Calculer mid comme lo + (hi - lo) / 2 au lieu de (lo + hi) / 2 n’est pas du pédantisme : avec des indices proches de la plus grande valeur d’un int, la somme déborderait. C’est un bogue qui est resté des années dans les bibliothèques standard de plusieurs langages.





Sono l'autore di questa pagina su «Algoritmi: diagrammi di flusso, programmazione strutturata e complessità». Se qualcosa non è chiaro, se vi serve un esempio in più o volete approfondire un punto, scrivetelo qui sotto nei commenti: rispondo personalmente. Se la pagina vi è stata utile, lasciate un voto con le stelle in cima all'articolo.I am the author of this page on “Algorithms: flowcharts, structured programming and complexity”. If something is unclear, if you need another example or want to go deeper into a point, write it in the comments below: I answer personally. If the page was useful, leave a star rating at the top of the article.