Algorithmique - Définition et Explications

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Vocabulaire

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 (Un langage de programmation est un langage informatique, permettant à un être humain d'écrire un code source qui sera analysé par une machine, généralement un ordinateur. Le code source...) et constitue alors la brique de base d’un programme informatique (Un programme informatique est une liste d'ordres indiquant à un ordinateur ce qu'il doit faire. Il se présente sous la forme d'une ou plusieurs séquences d'instructions, comportant souvent des données de base, devant...).

Les informaticiens utilisent fréquemment l’anglicisme implémentation pour désigner cette mise en œuvre. L’écriture en langage informatique (On appelle langage informatique un langage formel utilisé lors de la conception, la mise en œuvre, ou l'exploitation d'un système...) est aussi fréquemment désignée par le terme « codage », qui n’a ici aucun rapport avec la cryptographie (La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de...), mais qui se réfère au terme « code source » pour désigner le texte, en langage de programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de matériel, cf. VHDL).), 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 (La cuisine est l'ensemble des techniques de préparation des aliments en vue de leur consommation par les êtres humains (voir cuisinerie). La...) doit être plus ou moins détaillée en fonction de l’expérience du cuisinier (Cuisine).

Exemples d’algorithmes, de problèmes, d'applications ou domaines d'application

Il existe un certain nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 (voir aussi liste des algorithmes) :

  • Algorithmes ou problèmes classiques (du plus simple ou plus complexe)
    • échange, ou comment échanger les valeurs de deux variables : problème classique illustrant la notion de 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...) informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des...) (voir aussi Structure de données)
    • Algorithmes de 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 cadre...), ou comment retrouver une information dans un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) structuré ou non (par exemple Recherche dichotomique)
    • 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 objets à trier font donc partie d'un ensemble muni...), ou comment trier un ensemble de nombres le plus rapidement possible ou en utilisant le moins de ressources possible
    • problème du voyageur de commerce, problème du sac à dos (En anatomie, chez les animaux vertébrés parmi lesquels les humains, le dos est la partie du corps consistant en les vertèbres et les côtes. Les...), problème SAT et autres algorithmes ou approximations de solutions pour les problèmes combinatoires difficiles (dit NP-complets)
  • Algorithmes ou problèmes illustrant la programmation récursive (voir aussi algorithme récursif)
    • tours de Hanoï
    • huit dames, placer huit dames sur un échiquier sans qu’elles puissent se prendre entre elles,
    • suite de Conway,
    • algorithme de dessins récursifs pour le Tapis_de_Sierpiński_(programme_informatique), la Courbe (En géométrie, le mot courbe, ou ligne courbe désigne certains sous-ensembles du plan, de l'espace usuels. Par exemple, les droites, les segments, les...) du dragon, le flocon, ...
  • Algorithmes dans le domaine des mathématiques (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 structures et les...)
    • calcul de la 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...) d'un nombre, de la Fonction d'Ackermann ou de la suite de Fibonnacci,
    • algorithme du simplexe, qui minimise une fonction linéaire (Dans les mathématiques élémentaires, les fonctions linéaires sont les fonctions les plus simples que l'on rencontre. Ce sont des cas particuliers d'applications linéaires.) de variables réelles soumises à des contraintes linéaires,
    • fraction continue (En mathématiques, une fraction continue ou fraction continue simple ou encore fraction continuée est une expression de la forme :) d'un nombre quadratique, permettant d'extraire une racine carrée (La racine carrée d’un nombre réel positif x est le nombre positif dont le carré vaut x. On le note ou x½; dans cette expression, x est appelé le radicande.), cas particulier de la méthode de Newton
    • dans le domaine de l'algèbre : l'algorithme d'unification (Le concept d'unification est une notion centrale de la logique des prédicats ainsi que d'autres systèmes de logique et est sans doute ce qui distingue le plus Prolog des autres langages de...) et le calcul d'une base de Gröbner d'un idéal (En mathématiques, un idéal est une structure algébrique définie dans un anneau. Les idéaux généralisent de façon féconde l'étude de la divisibilité pour les entiers. Il est ainsi possible...) de polynôme (En mathématiques, un polynôme est la combinaison linéaire des puissances d'une variable, habituellement notée X. Ces objets sont largement utilisés en pratique, ne...),
    • en théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :) qui donne lieu à de nombreux algorithmes.
  • Algorithmes pour et dans le domaine de l'informatique
    • cryptologie et compression de données (La compression de données ou codage de source est l'opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les...)
    • Informatique musicale
    • algorithme génétique (Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes. Leur but est d'obtenir une solution approchée...) en informatique décisionnelle
    • Analyse et compilation des langages formels (voir Compilateur et Interprète (informatique))
    • allocation 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.) (ramasse-miettes)

Approches pratiques

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 à dire de processus...) a développé quelques stratégies pour résoudre les problèmes :

  • algorithme glouton : un premier algorithme peut souvent être proposé en ne regardant que les cas simples, ou ceux apparaissant le plus souvent, on parle alors d'algorithme glouton (Le Glouton ou Carcajou (Gulo gulo) est une espèce de mammifère omnivore, mais dans une plus grande mesure carnivore, de la famille des mustélidés. Il ressemble à un petit ours (10 à 15 kg)...). L'algorithme glouton n'est souvent qu'une première étape dans la rédaction d'un algorithme plus performant.
  • diviser pour régner : pour améliorer les performances des algorithmes, une technique usuelle consiste à diviser les données (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,...) d'un problème en sous-ensembles de tailles plus petites, jusqu'à obtenir des données que l'algorithme pourra traiter au cas par cas. Une 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...) étape dans ces algorithmes consiste à "fusionner" les résultats partiels pour obtenir une solution globale. Ces algorithmes sont souvent associés à la récursivité.
  • recherche exhaustive (ou combinatoire) : une méthode utilisant l'énorme puissance (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :) de calcul des ordinateurs consiste à regarder tous les cas possibles, cela n'est pour autant possible que dans certains cas particuliers (la 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.) est souvent plus forte que l'énorme puissance des ordinateurs, aussi énorme soit elle)
  • aléatoire, ou par approximations successives : certains algorithmes utilisent des recherches aléatoires, ou par approches successives donnant de meilleurs résultats (en moyenne) que des recherche directes ou explicites.
  • décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès l'instant qu'ils sont privés de vie,...) top-down / bottom-up : les décompositions top-bottom consistent à essayer de décomposer le problème en sous-problèmes à résoudre successivement, la décomposition allant jusqu'à des problèmes triviaux faciles à résoudre. L'algorithme global est alors donné par la composée des algorithmes définis au cours de la décomposition. La démarche bottom-up est la démarche inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de composition interne · notée multiplicativement, est un...), elle consiste à partir d'algorithmes simples, résolvant qu'une étape du problème, pour essayer de les composer pour obtenir un algorithme global.
  • pré-traitement / post-traitement : parfois, certains algorithmes comportent un ou deux phases identifiées comme des pré-traitements (à faire avant l'algorithme principal), ou post-traitement (à faire après l'algorithme principal) pour simplifier l'écriture de l'algorithme général.

Les heuristiques

Pour certains problèmes, les algorithmes ont une complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en...) beaucoup trop grande pour obtenir un résultat en temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) 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 (L'heuristique (du grec heuriskêin, « trouver ») est l'utilisation de règles empiriques :). Le but d’une heuristique n'est donc pas d'essayer toutes les combinaisons possibles afin de trouver celle répondant au problème, mais 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 (Un virus est une entité biologique qui nécessite une cellule hôte, dont il utilise les constituants pour se multiplier. Les virus existent sous...) informatiques non répertoriés dans leur base, en s’appuyant sur des ressemblances avec des virus connus.

Page générée en 0.804 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 - A propos - Informations légales
Partenaire: HD-Numérique