Algorithmique
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....) 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 d'information. Le terme est toutefois utilisé dans certains contextes dans le sens plus restrictif...) 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 secrets...), 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...), 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 cuisine est diverse à travers le monde, fruit des ressources...) 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...) 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 machines telles que les ordinateurs,...) (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...), 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...) 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...), 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 dorsaux étaient 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 lignes polygonales et les cercles sont des courbes.) 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 transformations. 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 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...), 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 programmation.) 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 serait-ce que parce qu'ils donnent localement une...),
    • 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 (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.)
    • Informatique musicale
    • algorithme génétique (La génétique (du grec genno γεννώ = donner naissance) est la science qui étudie l'hérédité...) 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 systématiques de...) 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) ayant une queue velue. Sa...). 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 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 seconde est une unité de mesure du temps. La seconde d'arc est...) é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, dégénèrent sous...) 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 élément y tel que...), 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 une forme extracellulaire ou intracellulaire. Sous la forme intracellulaire...) 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.082 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