Algorithmique

Un article de Wikivisual, l'encyclopédie libre.

On désigne par algorithmique ou algorithmie l'ensemble des activités logiques qui relèvent des algorithmes. Le mot vient du nom du mathématicien Al Khuwarizmi, qui, au IX^e siècle écrivit le premier ouvrage systématique sur la solution des équations linéaires et quadratiques. Dans le cas général, l'algorithmique s'effectue au moyen de calculs.

Sommaire

1 Définition
2 Historique
- 2.1 Antiquité
- 2.2 Etude systématique
3 Exemples d'algorithme
4 Complexité algorithmique
5 Quelques indications sur l'efficacité des algorithmes
6 Les heuristiques
7 Applications
8 Voir aussi
9 Liens externes
- 9.1 Tutoriaux

[modifier] Définition

Un algorithme est un moyen pour un humain de présenter la résolution par calcul d'un problème à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En effet, un algorithme est un énoncé dans un langage bien défini d'une suite d'opérations permettant de résoudre par calcul un problème. Si ces opérations s'exécutent en séquence, on parle d'algorithme séquentiel. Si les opérations s'exécutent sur plusieurs processeurs en parallèle, on parle d'algorithme parallèle. Si les tâches s'exécutent sur un réseau de processeurs on parle d'algorithme réparti ou distribué.

[modifier] Historique

[modifier] Antiquité

Les algorithmes dont on a retrouvé des descriptions exhaustives ont été utilisés dès l'époque des Babyloniens, pour des calculs concernant le commerce et les impôts.

L'algorithme le plus célèbre est celui qui se trouve dans le livre 7 des Eléments d'Euclide. Il permet de trouver le plus grand commun diviseur de deux nombres. Ce qui y est en particulier remarquable, c'est qu'il contient explicitement une itération et que les propositions 1 et 2 démontrent (maladroitement pour nos contemporains) sa correction.

[modifier] Etude systématique

L'algorithmique a été systématisée par le mathématicien perse arabophone Al Khuwarizmi (vers 780- vers 850), auteur d'un ouvrage (souvent traduit par "L'algèbre et le balancement") qui décrit des méthodes de calculs algébriques (ainsi que d'un autre introduisant le zéro des Indiens).

Le savant arabophone andalou Averroès (1126-1198) évoque une méthode de raisonnement où la thèse s'affine étape par étape (itérativement) jusqu'à une certaine convergence et ceci conformément au déroulement d'un algorithme. A la même époque, au douzième siècle, le moine Adelard de Bath a introduit le terme latin de algorismus (par référence au nom de Al-Khuwarizmi). Ce mot donne algorithme en français en 1554.

Au dix-septième siècle, on pourrait entrevoir une certaine allusion à la méthode algorithmique chez René Descartes dans la méthode générale proposée par le Discours de la méthode (1637), notamment quand, en sa deuxième partie, le logicien français propose de : « diviser chacune des difficultés que j'examinerois, en autant de parcelles qu'il se pourroit, et qu'il seroit requis pour les mieux résoudre. ». Sans évoquer explicitement les concepts de boucle ou d'itération, l'approche de Descartes prédispose la logique à accuellir le concept de "programme", mot qui naît en français en 1677.

L'utilisation du terme algorithme a été remarquable chez lady Ada Lovelace, fille de lord Byron et assistante de Charles Babbage (1792-1871).

Le substantif algorithmique désigne la méthode utilisant des algorithmes. Le terme est également employé comme adjectif.

Un algorithme énonce une résolution sous la forme d'une série d'opérations à effectuer. La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique.

Les informaticiens utilisent fréquemment l'anglicisme implémentation pour désigner cette mise en œuvre. L'écriture en langage informatique est aussi fréquemment désignée par le terme « codage », qui n'a ici aucun rapport avec la cryptographie, mais qui se réfère au terme « code source » pour désigner le texte, en langage de programmation, constituant le programme. L'algorithme devra être plus ou moins détaillé selon le niveau d'abstraction du langage utilisé ; autrement dit, une recette de cuisine doit être plus ou moins détaillée en fonction de l'expérience du cuisinier.

[modifier] Exemples d'algorithme

Il existe un certain nombre d'algorithmes classiques, utilisés pour résoudre des problèmes ou plus simplement pour illustrer des méthodes de programmation. On se réfèrera aux articles suivants pour de plus amples détails :

Tours de Hanoï, problème célèbre illustrant la programmation récursive.
Problème du tri, ou comment trier un ensemble de nombres le plus rapidement possible.
Problème des huit dames, placer huit dames sur un échiquier sans qu'elles puissent se prendre entre elles.
Algorithme récursif, quelques présentations d'algorithmes récursifs simples.
Algorithme du Simplex, qui minimise une fonction d'insatisfaction sur l'ensemble d'une répartition (programmation linéaire).

[modifier] Complexité algorithmique

Image:Searchtool.svg Voir l’article Complexité algorithmique.

Les principales notions mathématiques dans le calcul du coût d'un algorithme précis sont les notions de domination (notée O(f(n)), « grand o »), où f est une fonction mathématique de n, variable désignant la quantité d'informations (en bits, en nombre d'enregistrements…) manipulée dans l'algorithme. En algorithmique on trouve souvent des complexités du type :

<math>O(1)</math> indépendant de la taille de la donnée
<math>O(log(n))</math>, complexité logarithmique
<math>O(n)</math>, complexité linéaire
<math>O(n log(n))</math>, complexité quasi-linéaire
<math>O(n^{2})</math>, complexité quadratique
<math>O(n^{3})</math>, complexité cubique
<math>O(n^p)</math>, complexité polynômiale
<math>O(n^{\log(n)})</math>, complexité quasi-polynômiale
<math>O(2^{n})</math>, complexité exponentielle
<math>O(n!)</math>, complexité factorielle

Sans entrer dans les détails mathématiques, on peut dire que lorsque l'on calcule l'efficacité d'un algorithme (sa complexité algorithmique), on cherche à connaître deux données importantes: tout d'abord, l'évolution du nombre d'instructions de base en fonction de la quantité de données à traiter (par exemple, dans un algorithme de tri, le nombre de lignes à trier), que l'on privégéliera sur le coût exact en secondes, ensuite l'appréciation de la quantité de mémoire nécessaire pour effectuer les calculs. Baser le calcul de la complexité d'un algorithme sur le temps ou la quantité effective de mémoire qu'un ordinateur particulier prend pour effectuer ledit algorithme ne permet pas de prendre en compte la structure interne de l'algorithme, ni la particularité de l'ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d'accès aux données, l'exécution de l'algorithme (qui peut faire intervenir le hasard) ou son organisation de la mémoire, le temps d'exécution et la quantité de mémoire ne seront pas les mêmes.

On trouvera dans l'article sur la théorie de la complexité d'autres évaluations de la compléxité qui vont en général au delà des valeurs proposées ci-dessus et qui répartissent les problèmes (plutôt que les algorithmes) en classes de compléxité.

[modifier] Quelques indications sur l'efficacité des algorithmes

Souvent, l'efficacité d'un algorithme n'est connue que de manière asymptotique, c'est-à-dire pour de grandes valeurs du paramètre n. Lorsque ce paramètre est suffisamment petit, un algorithme de complexité supérieure peut en pratique être plus efficace. Ainsi, pour trier un tableau de 30 lignes (c'est un paramètre de petite taille), il est inutile d'utiliser un algorithme évolué comme Quicksort (l'un des algorithmes de tri les plus efficaces en moyenne) : l'algorithme de tri le plus trivial sera suffisamment efficace.

À noter aussi : entre deux algorithmes dont la complexité est identique, on cherchera à utiliser celui dont l'occupation mémoire est la plus faible. L'analyse de la complexité algorithmique peut également servir à évaluer l'occupation mémoire d'un algorithme. Enfin, le choix d'un algorithme plutôt qu'un autre doit se faire en fonction des données que l'on s'attend à lui fournir en entrée. Ainsi, le Quicksort (ou tri rapide), lorsque l'on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l'applique à une liste de valeur... déjà triée ! Il n'est donc pas judicieux de l'utiliser si on prévoit que le programme recevra en entrée des listes déjà presque triées.

Un autre paramètre à prendre en compte est la localité de l'algorithme. Par exemple pour un système à mémoire virtuelle qui dispose de peu de mémoire (par rapport au nombre de données à traiter), le Tri rapide sera normalement plus efficace que le Tri par tas car le premier ne passe qu'une seule fois sur chaque élément de la mémoire tandis que le second accède à la mémoire de manière discontinue (ce qui augmente le risque de "swapping").

Enfin, il existe certains algorithmes dont la complexité est dite amortie. Cela signifie que, pour certaines exécutions de l'algorithme (car marginaux), la complexité de l'algorithme sera très supérieure au cas moyen. Bien sûr, on n'utilise la notion de compléxité amortie que dans les cas où cette réaction est très marginale.

[modifier] Les heuristiques

Pour certains problèmes, les algorithmes ont une complexité beaucoup trop grande pour obtenir un résultat en temps raisonnable, même si l'on pouvait utiliser une puissance de calcul phénoménale. On est donc amené à rechercher une solution la plus proche possible d'une solution optimale en procédant par essais successifs. Puisque toutes les combinaisons ne peuvent être essayées, certains choix stratégiques doivent être faits. Ces choix, généralement très dépendants du problème traité, constituent ce qu'on appelle une heuristique. Le but d'une heuristique est donc de ne pas essayer toutes les combinaisons possibles avant de trouver celle qui répond au problème, afin de trouver une solution approchée convenable (qui peut être exacte dans certains cas) dans un temps raisonnable. C'est ainsi que les programmes de jeu d'échecs, de jeu de go (pour ne citer que ceux-là) font appel de manière très fréquente à des heuristiques qui modélisent l'expérience d'un joueur. Certains logiciels antivirus se basent également sur des heuristiques pour reconnaître des virus informatiques non répertoriés dans leur base, en s'appuyant sur des ressemblances avec des virus connus.