Programmation algorithmique/Nombre d'opérations optimal

Programmation algorithmique

• Introduction
• Nombre d'opérations optimal
• Mathématiques simples
• Tableaux : parcours, recherches
• Tris de tableaux
• Structures de données
  • Listes simplement chaînées
  • Listes doublement chaînées
  • Arbres

La rapidité d'un algorithme est exprimée sous la forme du nombre d'opérations effectuées par celui-ci. En général, ce nombre dépend des données d'entrée.

Il existe différents nombres d'opérations :

• le nombre d'opérations minimal, qui se produit dans le meilleur des cas,
• le nombre d'opérations maximal, qui se produit dans le pire des cas,
• le nombre moyen d'opérations, qui est une moyenne de ce que l'on peut espérer d'un algorithme dans la plupart des cas.

Exemple : un algorithme de tri d'un tableau de n éléments effectuera un nombre moyen d'opérations dépendant de n (la taille du tableau) :

• L'algorithme de tri à bulle s'effectue en O(n²) ;
• L'algorithme de tri rapide (appelé Quicksort) s'effectue en moyenne en O(n*log(n)).

Comparaison de quelques algorithmes

Calcul de n^p

But: Élever un nombre entier n à la puissance p (entier également).

Algorithme simple

L'implémentation simple de cet algorithme est la suivante :

ENTIER resultat
resultat <- 1
pour i de 1 à p
faire
  resultat <- resultat * n
finfaire

Cet algorithme s'effectue en O(p)

Algorithme plus compliqué

Cet algorithme est plus compliqué, mais effectue moins d'opérations que le précédent :

ENTIER resultat
resultat <- 1
tantque p > 0
faire
  si p ET 1 <> 0 alors          # test du bit 0 de p
    resultat <- resultat * n
  finsi
  n <- n * n
  p <- p / 2   # division entière ou décalage de bits
finfaire

Cet algorithme s'effectue en O(log(p))

Cet algorithme fonctionne de la façon suivante :

• A chaque itération de la boucle, n vaut successivement $n$, $n^{2}$, $n^{4}$, $n^{8}$, ...
• La valeur de l'exposant p en binaire s'exprime de la façon suivante :

$p=\sum _{i=0}^{\infty }p_{i}\times 2^{i}$

• Chaque bit $i$ de p est testé, s'il vaut 1, il faut multiplier le résultat temporaire par $n^{2^{i}}$. La relation mathématique entre les puissances est utilisée. Par exemple : $n^{2^{1}}\times n^{2^{3}}=n^{2^{1}+2^{3}}$. Donc pour tous les bits de $p$, on a :

${\begin{matrix}&&p_{0}\times n^{2^{0}}\times p_{1}\times n^{2^{1}}\times \cdots \\=&&n^{p_{0}\times 2^{0}+p_{1}\times 2^{1}+\cdots }\\=&&n^{p}\end{matrix}}$

Nous avons donc ici deux algorithmes qui calculent le même résultat mais en effectuant des opérations différentes. Le second algorithme est bien plus rapide que le premier car lorsque $n$ devient très grand, $log(n)$ devient négligeable devant $n$. Pour de petites valeurs de $n$, le second algorithme peut être plus lent.

Dans cet exemple, l'algorithme le plus rapide est aussi le plus compliqué à écrire et à comprendre, mais ce n'est pas toujours le cas.

Machine séquentielle, machine parallèle, machine quantique

Toutes les complexités indiquées ici valent pour des machines séquentielles, c'est à dire une machine munie d'un seul processeur, ou bien une machine multi-processeurs sur laquelle on n'utiliserait qu'un seul cœur. D'ailleurs, le langage algorithmique que nous utilisons décrit uniquement des séquences d’instructions et d'opérations.

Notons que le facteur d'accélération amené par une machine parallèle, c'est-à-dire munie de plusieurs processeurs, est limité. Par exemple, pour une machine à 64 processeurs, on peut espérer aller 64 fois plus vite au maximum. Pour un algorithme en $O(2^{n})$ et $n$ valant 100, le nombre d'opérations sur une machine séquentielle est de l'ordre de $2^{100}$, tandis que sur une machine à 64 processeurs on peut espérer un ordre de $(2^{100})/64$ soit $(2^{100})/(2^{6})$ ou $2^{94}$ opérations. On voit bien ici que le nombre de processeurs, forcément limité, n'influence pas forcément la complexité en temps. Ceci s'explique également par le fait qu'un facteur multiplicatif constant (ici $1/64$) est négligeable devant un carré ou une exponentielle quand la taille du problème devient grande.

Quant aux machines quantiques, qui sont loin d'être exploitables actuellement, leur utilisation remettrait à plat l'état de l'art en algorithmique et en complexité. Par exemple, pour des problèmes dont on ne connaît que des algorithmes de complexité en temps exponentielle, on connaît des algorithmes quantiques de complexité linéaire. Alors qu'il faut actuellement des dizaines d'années à des machines parallèles surpuissantes pour casser une clé de chiffrement, un ordinateur quantique mettrait quelques instants.