Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Informatique

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/

Pas encore de vote : soyez le premier à noter cette page.

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.

Organigramme de l'algorithme d'Euclide pour le plus grand commun diviseur avec son tableau d'exécution
L’algorithme d’Euclide : tant que b n’est pas nul, remplacer le couple (a, b) par (b, a mod b). À droite, l’exécution avec a = 48 et b = 18 : après trois pas b vaut 0 et le résultat est a = 6.

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 a

Pourquoi il fonctionne. Tout diviseur commun de a et b divise aussi r = a - qb, et vice versa : donc \text{GCD}(a, b) = \text{GCD}(b, r). Comme r \lt b, le second nombre diminue à chaque pas et atteint 0 en un nombre fini de pas, et \text{GCD}(a, 0) = a.

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 :

  1. séquence : une instruction après l’autre ;
  2. sélection : si une condition est vraie on fait une chose, sinon une autre (if) ;
  3. 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 n des données croît. On utilise la notation O : un algorithme est O(f(n)) si, pour n grand, il effectue au plus un nombre d’opérations proportionnel à f(n).

ComplexitéExemplen = 1000n = 10^6
O(1)accéder à un élément d’un tableau11
O(\log n)recherche dichotomique dans un tableau trié1020
O(n)trouver le maximum d’un tableau10^310^6
O(n\log n)tri fusion, FFT10^42\times 10^7
O(n^2)tri à bulles, DFT directe10^610^{12}
O(2^n)essayer tous les sous-ensembles10^{301}impossible

À un milliard d’opérations par seconde, 10^{12} opérations prennent un quart d’heure ; 2\times 10^7 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 2\log_2 du plus petit nombre : O(\log n). 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 n éléments non triés signifie les regarder un par un : O(n). 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 k pas il reste n/2^k éléments, donc \log_2 n 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.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x