Algorithmes

Exemple d'algorithme

Je peux dire à quelqu'un : "sert moi une tasse de café, s'il te plait".
En admettant que la personne comprenne ma langue ( et soit assez aimable ), il est probable que cette phrase suffise.

Il est impossible de demander une tasse de café de la même manière à un processeur.
Je dois donc découper ma demande :

1. Fais bouillir de l'eau.
2. Mets du café dans la tasse.
3. Mets de l'eau dans la tasse.

Nous avons donc notre premier algorithme.
Comme notre processeur ne sait toujours pas ce que signifie "faire bouillir de l'eau", nous devons affiner l'algorithme :

1. Fais bouillir de l'eau :
   1. Remplis la bouilloire.
   2. Allume la bouilloire.
   3. Attends que l'eau soit bouillante.
   4. Éteins la bouilloire.
2. Mets du café dans la tasse.

Nous devons donc affiner notre algorithme jusqu'au moment où chaque instruction peut être réalisée par le processeur.

Table des matières Haut

Logique, syntaxe et sémantique

Avant d'aller plus en avant, il est important de comprendre les notions de syntaxe et de sémantique.
Ces deux notions sont étroitement liées à notre futur algorithme, et en cas d'erreur, nous situerons précisément ce qu'il faut corriger.
Lors de l'utilisation d'un IDE (environnement intégré de développement), les messages d'erreurs retournés par notre compilateur spécifieront par exemple si l'erreur est syntaxique.

La syntaxe est un ensemble de conventions qui régissent l'écriture.
Par exemple, chaque phrase débute par une majuscule et se termine par un point.

La sémantique est le sens, la signification de la phrase ou de l'instruction.
Par exemple, la phrase "Un est plus grand que deux." est syntaxiquement correcte, mais présente une erreur de sémantique.

Exemple : calcul de l'addition de deux nombres a et b.

r = a - b ;
Une erreur de logique ne peut être détectée par le compilateur : les instructions s'effectuent correctement, mais le résultat n'est pas celui attendu.

r = a; + b
Le délimiteur de fin d'instruction (;) est placé au milieu de l'instruction.
Une erreur de syntaxe est détectée à la compilation.

r = a + 'b' ;
Le programme est prévu pour additionner deux nombres, et b est considéré ici comme un caractère et pas comme une variable.
La syntaxe de l'instruction est correcte, mais pas la sémantique.
Une erreur de sémantique est détectée à la compilation.

Table des matières Haut

Structure des algorithmes

Nous verrons dans les pages suivantes que diverses notions nous seront nécessaires dans la conception des algorithmes :

• Séquence.
• Sélection.
• Itération ( boucles ).
• Modularité.
• Récursivité.

La structure de nos algorithmes répondra le plus souvent à trois grands principes :

• Combinaisons : nous n'allons pas réinventer la roue, donc nous utiliserons des fonctions simples, que nous combinerons pour obtenir des fonctions plus élaborées
• Branchements : nous agirons de manière différente selon certains états ou selon les résultats de certains tests (si ceci est vrai alors je fais ceci, sinon je fais celà)
• Itérations : nous utiliserons des boucles ou des récursions afin d'éviter de coder chaque passage dans une opération répétitive (dont nons ne pouvons parfois même pas déterminer le nombre de passages à l'avance)

Table des matières Haut

Avant de conçevoir un algorithme

Avant de travailler sur un algorithme, nous devons nous poser quelques questions :

• réalisabilité : nous devons nous demander si la tâche à exécuter est réalisable par un ordinateur (computability). Par exemple, il est peu réaliste de tenter un algorithme de création d'algorithmes.
• complexité : la tâche à accomplir est réalisable par un ordinateur, mais les ressources que nécessiterait l'exécution d'un tel algorithme ne sont-elles pas trop élevées ?
• robustesse : nous devons aussi penser à une série de tests pour vérifier les résultats de l'algorithme, mais pouvons-nous avoir la certitude de l'exactitude sans faille dans tous les cas de notre algorithme ? La seule certitude que nous pouvons avoir est celle d'un échec, au moment où l'algorithme dévoile ses failles devant une situation hors norme.

Table des matières Haut

Complexité des algorithmes

Nous pouvons considérer la complexité d'un algorithme de différentes manières : dans le temps (temps nécessaire àl'exécution), dans l'espace (quantité de mémoire nécessaire), au niveau des resources (charge du processeur, etc.), mais nous allons nous intéresser ici à la complexité en temps en fonction de la quantité de données à traiter, sans dépendre de facteurs extérieurs tels que la machine sur laquelle l'algorithme est exécuté. Nous parlerons d'ordre de grandeur.

Afin de donner un ordre de gandeur de la complexité d'un algorithme, nous utiliserons la notion d'instruction élémentaire.

Tp(n) correspond au Temps d'exécution de p en fonction de la taille de données n (dans le pire des cas), ce qui correspond au nombre maximal d'instructions élémentaires qui seront exécutées par p sur n'importe quelle entrée de taille n.

Tableau d'ordres de grandeur

Le tableau ci-dessous reprend donc les complexités des algorithmes les plus fréquentes.

| Notation | Type de complexité | Exemple |

  | (1) | complexité constante (indépendante de la taille de la donnée) | fonction head() |

  | (log(n)) | complexité logarithmique (ou sub-linéaires) | |

  | (n) | omplexité linéaire | recherche simple du plus grand élément d'un tableau |

  | (n log(n)) | complexité quasi-linéaire | tri par fusion |

  | (n²) | complexité quadratique | tri par sélection |

  | (n³) | complexité cubique | multiplication de matrices |

  | (n^log(n)) | complexité quasi-polynomiale | |

  | (n^k) | complexité polynomiale | |

  | (2^√n) | complexité superpolynomiale | |

  | (2ⁿ) | complexité exponentielle | borne supérieure d'un calcul inéfficace d'une suite de Fibonacci |

  | (nⁿ) | complexité superexponentielle | |

  | ((2²ⁿ) | complexité superexponentielle | |

  | (n!) | complexité factorielle | |

Table des matières Haut

Théorèmes sur la complexité des algorithmes

Situation : variable n ≥ 0, constantes k, l ≥ 0, fonction f(n) ≥ 0

Théorème | Condition | Informations |

(k*f(n)) = f(n)) | | Multiplier une fondtion par une constante ne modifie pas l'ordre de grandeur de la fonction |

(f(n) + g(n)) = (f(n)) | si (g(n)) ≤ (f(n)) | Nous conservons celui qui croît le plus rapidement |

(f(n)^k) ≤ (f(n)^l) | si 0 ≤ k ≤ l | |

(n^l) ≤ (kⁿ) | si k > 1 | Les fonctions exponentielles croissent plus rapidement que les fonctions polynomes |

(lⁿ) ≤ (kⁿ) | si k > l | Dans le cas de 2 fonctions de même exposant, nous conservons la plus grande base |

(f(n)) * (g(n)) = (f(n) * g(n)) | | |

(max(f(n),g(n))) = (f(n)) | si (g(n)) ≤ (f(n)) | |

Table des matières Haut

Quelques liens relatifs aux algorithmes

You are on the French version of the site, but your system indicates that you prefer to use the English language.
The entire site is not translated yet, but the menus and buttons on the interface are largely translated.

Would you like to reach the page in English?
Click here to continue in English: Consult the English version of this page

U bevindt zich op de Franse versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Sie befinden sich in der französischen Version der Website, Ihr System gibt jedoch an, dass Sie die deutsche Sprache bevorzugen.
Die gesamte Site ist noch nicht übersetzt, aber die Menüs und Schaltflächen auf der Benutzeroberfläche sind weitgehend übersetzt.

Möchten Sie die Seite auf Deutsch erreichen?
Klicken Sie hier, um fortzufahren: Konsultieren Sie die deutsche Version dieser Seite