Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Algorithmique

Introduction

L'algorithmique est l?ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus systématiques de résolution, par le calcul, d'un problème permettant de décrire les étapes vers le résultat. En d'autres termes, un algorithme est une suite finie et non-ambiguë d?opérations permettant de donner la réponse à un problème.

Si les opérations d'un algorithme s?exécutent les unes après les autres, c'est un algorithme séquentiel, si elles s?exécutent en parallèle, c'est un algorithme parallèle. Si l'algorithme exploite des tâches s?exécutant sur un réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des informations. Par analogie avec un filet (un réseau est un « petit rets », c'est-à-dire un petit filet), on...) de processeurs on parle d?algorithme réparti, ou distribué.

Le mot « algorithme » vient du nom du mathématicien (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute personne faisant des mathématiques la base de son...) Al Khuwarizmi (latinisé au Moyen Âge en Algoritmi), qui, au IXe siècle écrivit le premier ouvrage systématique (En sciences de la vie et en histoire naturelle, la systématique est la science qui a pour objet de dénombrer et de classer les taxons dans un certain ordre, basé sur des...) sur la solution des équations linéaires et quadratiques.

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 permet de trouver le plus grand diviseur (En mathématiques, un nombre entier d est un diviseur d'un entier n lorsque la division euclidienne de n par d donne un reste égal à zéro. Autrement dit, il existe...) commun, ou PGCD, de deux nombres. Un point (Graphie) particulièrement remarquable est qu?il contient explicitement une itération et que les propositions 1 et 2 démontrent (maladroitement pour nos contemporains) sa convergence (Le terme de convergence est utilisé dans de nombreux domaines :).

Étude systématique

L?algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à...) a été systématisée par le mathématicien perse Al Khuwarizmi (né vers 780 - mort (La mort est l'état définitif d'un organisme biologique qui cesse de vivre (même si on a pu parler de la mort dans un sens cosmique plus général, incluant par...) vers 850), auteur d?un ouvrage dont le titre est souvent traduit en L?algèbre et le balancement, qui décrit des méthodes de calculs algébriques et dans lequel l'auteur introduit le zéro (Le chiffre zéro (de l’italien zero, dérivé de l’arabe sifr, d’abord transcrit zefiro en italien) est un symbole marquant une position vide dans l’écriture des nombres...) des Indiens.

Le savant arabe Averroès (Abu'l-Walid Muhammad ibn Rouchd de Cordoue (né en 1126 - année supposée de sa naissance - à Cordoue en Andalousie, actuelle Espagne...) (1126-1198) évoque une méthode de raisonnement où la thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à l'égard du sujet ou du thème qu'il évoque.) s?affine (En mathématiques, affine peut correspondre à :) é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 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), 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, d?itération ou de dichotomie, l?approche de Descartes prédispose la logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la...) à accueillir le concept de programme, mot qui naît en français en 1677.

L?utilisation du terme algorithme est remarquable chez Ada Lovelace (Augusta Ada King, comtesse Lovelace, généralement appelée Ada Lovelace, née à Londres le 10 décembre 1815 et morte à Londres le 27 novembre 1852, est principalement...), fille de Lord Byron et assistante de Charles Babbage (Charles Babbage (né le 26 décembre 1791 à Teignmouths, Devonshire, Angleterre, mort le 18 octobre 1871) était un mathématicien britannique et le précurseur...) (1791-1871).

É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 :

  • Ainsi, pour décrire les algorithmes, des structures algorithmiques ont été mises en évidences : structures de contrôle (Le mot contrôle peut avoir plusieurs sens. Il peut être employé comme synonyme d'examen, de vérification et de maîtrise.) (boucle, conditionnelle, ...) et structures de données (variables, listes, ...).
  • Pour justifier de la qualité des algorithmes les notions de correction, de complétude (On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématiques qu'il est complet pour exprimer que rien ne peut lui...) et de terminaison ont été mises en place.
  • Enfin, pour comparer les algorithmes entre eux, une théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui...) des algorithmes a été définie.

Structures algorithmiques

Les concepts en ?uvre en algorithmique, par exemple selon l'approche de N. Wirth pour les langages les plus répandus (Pascal, C, etc..), sont en petit nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».), ils appartiennent à deux classes :

  • les structures de contrôle
    • séquences
    • conditionnelles
    • boucles
  • les structures de données
    • constantes
    • variables
    • tableaux
    • structures récursives (listes, arbres, graphes)

Ce découpage est parfois difficile à percevoir pour certains langages (Lisp, Prolog, ...) plus basés sur la notion de récursivité où certaines structures de contrôle sont implicites (et, donc, 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 (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) fini. Les preuves de terminaisons font habituellement intervenir une fonction entière positive strictement décroissante à chaque "pas" de l'algorithme.

Étant donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) 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é (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en...) 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 (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres, les figures, les...) de n, variable (En mathématiques et en logique, une variable est représentée par un symbole. Elle est utilisée pour marquer un rôle dans une formule, un prédicat ou un algorithme. En statistiques, une...) désignant la quantité (La quantité est un terme générique de la métrologie (compte, montant) ; un scalaire, vecteur, nombre d’objets ou d’une autre...) d?informations (en bits, en nombre d?enregistrements, etc.) manipulée dans l?algorithme. En algorithmique on trouve souvent 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 (La fonction exponentielle est l'une des applications les plus importantes en analyse, ou plus généralement en mathématiques et dans ses domaines d'applications. Il...)
O(n!) complexité factorielle (En mathématiques, la factorielle d'un entier naturel n, notée n!, ce qui se lit soit « factorielle de n » soit « factorielle n », est le produit des nombres entiers strictement positifs inférieurs ou égaux à n.)

Sans entrer dans les détails mathématiques, le calcul de l?efficacité d?un algorithme (sa complexité algorithmique), consiste en la recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche scientifique désigne également le...) de deux quantités importantes. La première quantité est l?évolution du nombre d?instructions de base en fonction de la quantité de données à traiter (par exemple, pour un algorithme de tri (Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d'organiser une collection d'objets selon un ordre déterminé. Les...), il s'agit du nombre de données à trier), que l?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 ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde d'arc est une mesure d'angle...) quantité estimée (La quantité estimée est une notion, introduite par des directives de la CEE, concernant l'harmonisation (rapprochement des législations) et le marquage des produits préemballés des états membres (en volume ou en masse).) est la quantité de mémoire (D'une manière générale, la mémoire est le stockage de l'information. C'est aussi le souvenir d'une information.) 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 (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques...) particulier prend pour effectuer ledit algorithme ne permet pas de prendre en compte la structure interne (En France, ce nom désigne un médecin, un pharmacien ou un chirurgien-dentiste, à la fois en activité et en formation à...) de l?algorithme, ni la particularité de l?ordinateur : selon sa charge (La charge utile (payload en anglais ; la charge payante) représente ce qui est effectivement transporté par un moyen de transport donné, et qui donne lieu à un paiement ou un bénéfice non pécuniaire pour...) de travail, la vitesse (On distingue :) de son processeur (Le processeur, ou CPU (de l'anglais Central Processing Unit, « Unité centrale de traitement »), est le composant de l'ordinateur qui exécute les programmes informatiques. Avec la mémoire notamment, c'est...), la vitesse d?accès aux données, l?exécution de l?algorithme (qui peut faire intervenir le hasard) ou son organisation (Une organisation est) de la mémoire, le temps d?exécution et la quantité de mémoire ne seront pas les mêmes.

Il existe également un autre aspect de l'évaluation de l'efficacité d'un algorithme : les performances en moyenne (La moyenne est une mesure statistique caractérisant les éléments d'un ensemble de quantités : elle exprime la grandeur qu'auraient chacun des membres de l'ensemble s'ils étaient tous identiques sans...) de cet algorithme. Elle suppose d'avoir un modèle de la répartition des données de l'algorithme, tandis que la mise en ?uvre des techniques d'analyse implique des méthodes assez fines de combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.) et d'évaluation asymptotique, utilisant en particulier les séries génératrices et des méthodes avancées d'analyse complexe. L'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble),...) de ces méthodes sont regroupées sous le nom de combinatoire analytique.

On trouvera dans l?article sur la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur l’observation...) de la complexité des algorithmes d?autres évaluations de la complexité 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 complexité.

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 (Un paramètre est au sens large un élément d'information à prendre en compte pour prendre une décision ou pour effectuer un calcul.) 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 (Tableau peut avoir plusieurs sens suivant le contexte employé :) 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 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 valeurs 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é (Une localité est une agglomération habitée de taille indéterminée, en général peu importante, qui peut éventuellement être le chef-lieu d'une...) de l?algorithme. Par exemple pour un système à mémoire virtuelle (Le mécanisme de mémoire virtuelle a été mis au point dans les années 1960. Il est basé sur l'utilisation d'une mémoire de masse (type disque dur ou anciennement un tambour), pour le...) 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 (cas marginaux), la complexité de l?algorithme sera très 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 très marginale.

Source: Wikipédia publiée sous licence CC-BY-SA 3.0. Vous pouvez soumettre une modification à cette définition sur cette page.

La liste des auteurs de cet article est disponible ici.
Page générée en 0.013 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - Informations légales