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 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.
Exemples d’algorithmes, de problèmes, d'applications ou domaines d'application
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 (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 informatique (voir aussi Structure de données)
- Algorithmes de recherche, ou comment retrouver une information dans un ensemble structuré ou non (par exemple Recherche dichotomique)
- algorithme de tri, 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, 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 du dragon, le flocon, ...
- Algorithmes dans le domaine des mathématiques
- Algorithmes pour et dans le domaine de l'informatique
Approches pratiques
L'algorithmique 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. 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 é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 de calcul des ordinateurs consiste à regarder tous les cas possibles, cela n'est pour autant possible que dans certains cas particuliers (la combinatoire 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 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, 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é 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 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 informatiques non répertoriés dans leur base, en s’appuyant sur des ressemblances avec des virus connus.