Algorithmique / Algorithme

On sert à désigner par algorithmique la totalité des activités logiques qui relèvent des algorithmes ; surtout, en informatique, cette discipline sert à désigner la totalité des règles...



Catégories :

Algorithmique

Recherche sur Google Images :


Source image : areaprog.com
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • PARI54. Chapitre 1. Algorithmique et complexité. K. Bertet... Problème calculable : il existe un algorithme pour le résoudre... •Elle sert à comparer des algorithmes, ou de vérifier si un algorithme est raisonnable... (source : perso.univ-lr)

On sert à désigner par algorithmique la totalité des activités logiques qui relèvent des algorithmes ; surtout, en informatique, cette discipline sert à désigner la totalité des règles et des techniques qui sont impliquées dans la définition et la conception des algorithmes. Le mot vient du nom du mathématicien Al Khuwarizmi (latinisé au Moyen Âge en Algoritmi), qui, au IXe 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.

Il est quelquefois fait usage du mot algorithmie, quoique ce dernier ne figure pas dans la majorité des dictionnaires.

Définition

Un algorithme est un processus systématique de résolution, par le calcul, d'un problème servant à présenter les étapes vers le résultat à une autre personne physique (un autre humain) ou virtuelle (un calculateur). En d'autres termes, un algorithme est un énoncé d'une suite finie et non-ambiguë d'opérations servant à donner la réponse à 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é.

Historique

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 Éléments d'Euclide. Il sert à trouver le plus grand diviseur commun, ou PGCD, de deux nombres. Un point spécifiquement remarquable est qu'il contient explicitement une itération et que les propositions 1 et 2 démontrent (maladroitement pour nos contemporains) sa convergence.

Étude systématique

L'algorithmique a été systématisée par le mathématicien perse Al Khuwarizmi (né vers 780 - mort vers 850), auteur d'un ouvrage (fréquemment traduit par L'algèbre et le balancement) qui décrit des méthodes de calculs algébriques (en plus d'introduire le zéro des Indiens).

Le savant arabe 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. À la même époque, au XIIe 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 XVIIe 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), surtout lorsque, en sa deuxième partie, le logicien français propose de «diviser chacune des difficultés que j'examinerois, en tout 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 à accueillir le concept de programme, mot qui naît en français en 1677.

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

Vocabulaire

Le substantif algorithmique sert à désigner la méthode utilisant des algorithmes. Le terme est aussi employé comme adjectif.

Un algorithme décrit 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 forme alors la brique de base d'un programme informatique.

Les informaticiens utilisent souvent l'anglicisme implémentation pour désigner cette mise en œuvre. L'écriture en langage informatique est aussi souvent 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é ; c'est à dire, une recette de cuisine doit être plus ou moins détaillée selon l'expérience du cuisinier.

Étude formelle

De nombreux outils formels ou théories ont été développés pour décrire les algorithmes, les étudier, exprimer leurs qualités, pouvoir les comparer entre eux :

Structures algorithmiques

Les concepts en œuvre en algorithmique, par exemple selon l'approche de N. Wirth pour les langages les plus communs (Pascal, C, etc.. ), sont en petit nombre, ils appartiennent à deux classes :

Ce découpage est quelquefois complexe à percevoir pour certains langages (Lisp, Prolog, ... ) plus basés sur la notion de récursivité où certaines structures de contrôle sont implicites (et, par conséquent, semblent disparaître).

Correction, complétude, terminaison

Ces trois notions "correction", "complétude", "terminaison" sont liées, et supposent qu'un algorithme est écrit pour résoudre un problème.

La terminaison est l'assurance que l'algorithme terminera en un temps fini. Les preuves de terminaisons font généralement intervenir une fonction entière positive strictement décroissante à chaque "pas" de l'algorithme.

Étant donnée la garantie qu'un algorithme terminera, la preuve de correction doit apporter l'assurance que si l'algorithme termine en donnant une proposition de solution, alors cette solution est correcte, elle est effectivement une solution au problème posé.

La preuve de complétude garanti que pour un espace de problèmes donné, l'algorithme, s'il termine, donnera des propositions de solutions.

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, etc. ) manipulée dans l'algorithme. En algorithmique on trouve fréquemment des complexités du type :

Notation Type de complexité
O (1) complexité constante (indépendante de la taille de la donnée)
O (log (n) ) complexité logarithmique
O (n) complexité linéaire
O (nlog (n) ) complexité quasi-linéaire
O (n2) complexité quadratique
O (n3) complexité cubique
O (np) complexité polynomiale
O (nlog (n) ) complexité quasi-polynomiale
O (2n) complexité exponentielle
O (n!) complexité factorielle

Sans entrer dans les détails mathématiques, le calcul de l'efficacité d'un algorithme (sa complexité algorithmique), consiste en la recherche de deux quantités importantes. La première quantité est l'évolution du nombre d'instructions de base selon la quantité de données à traiter (par exemple, pour un algorithme de tri, il s'agit du nombre de données à trier), qu'on privilégiera sur le temps d'exécution mesuré en secondes (car ce dernier dépend de la machine sur laquelle l'algorithme s'exécute). La seconde quantité estimée est la quantité de mémoire indispensable 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 spécifique 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.

Il existe aussi un autre aspect de l'évaluation de l'efficacité d'un algorithme : les performances en moyenne de cet algorithme. Elle suppose d'avoir un modèle de la répartition des données de l'algorithme, alors que la mise en œuvre des techniques d'analyse implique des méthodes assez fines de combinatoire et d'évaluation asymptotique, utilisant surtout les séries génératrices et des méthodes avancées d'analyse complexe. La totalité de ces méthodes sont regroupées sous le nom de combinatoire analytique.

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

Quelques indications sur l'efficacité des algorithmes

Fréquemment, l'efficacité d'un algorithme n'est connue que de manière asymptotique, c'est-à-dire pour de grandes valeurs du paramètre n. Quand 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 le Tri rapide (l'un des algorithmes de tri les plus efficaces en moyenne)  : l'algorithme de tri le plus trivial sera suffisamment efficace.

Entre deux algorithmes dont la complexité est semblable, on cherchera à utiliser celui dont l'occupation mémoire est la plus faible. L'analyse de la complexité algorithmique peut aussi servir à évaluer l'occupation mémoire d'un algorithme. Enfin, le choix d'un algorithme plutôt qu'un autre doit se faire suivant les données qu'on s'attend à lui apporter en entrée. Ainsi, le Quicksort (ou tri rapide), quand on choisit le premier élément comme pivot, se comporte de façon désastreuse si on l'applique à une liste de valeurs déjà triée. Il n'est par conséquent 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 dispositif à mémoire virtuelle qui dispose de peu de mémoire (comparé 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 alors 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 veut dire que, pour certaines exécutions de l'algorithme (cas marginaux), la complexité de l'algorithme sera particulièrement supérieure au cas moyen. Bien sûr, on n'utilise la notion de complexité amortie que dans les cas où cette réaction est particulièrement marginale.

Approches pratiques

L'algorithmique a développé quelques stratégies pour résoudre les problèmes :


Les heuristiques

Pour certains problèmes, les algorithmes ont une complexité énormément trop grande pour obtenir un résultat en temps raisonnable, même si on pouvait utiliser une puissance de calcul phénoménale. On est par conséquent amené à rechercher une solution la plus proche envisageable d'une solution optimale en procédant par essais successifs. Puisque l'ensemble des combinaisons ne peuvent être essayées, certains choix stratégiques doivent être faits. Ces choix, le plus souvent particulièrement dépendants du problème traité, forment ce qu'on nomme une heuristique. L'objectif d'une heuristique n'est par conséquent pas d'essayer l'ensemble des combinaisons envisageables pour trouver celle répondant au problème, mais de trouver une solution approchée convenable (qui peut être exacte occasionnellemen) 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 particulièrement fréquente à des heuristiques qui modélisent l'expérience d'un joueur. Certains logiciels antivirus se basent aussi 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.

Exemples d'algorithmes et d'applications

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 :


Applications

Voir aussi

Liens externes

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Algorithmique.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu