Accueil |

Algorithmique

                  

L'algorithmique ou algorithmie est la science des algorithmes, visant à  étudier les opérations nécessaires à  la réalisation d'un calcul.

C'est un néologisme : en effet il est absent des dictionnaires o๠seul l'adjectif algorithmique est défini pour ce qui utilise ou se réfère aux algorithmes, par exemple une méthode algorithmique.

Un algorithme est une méthode de résolution de problème énoncée 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 se réfère au terme "code source" pour désigner le texte, en langage de programmation, qui constitue 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.

Sommaire
1 Exemple d'algorithme
2 Complexité algorithmique
3 Quelques indications sur l'efficacité des algorithmes
4 Les heuristiques
5 Applications
6 Voir aussi

Exemple d'algorithme

  1. entrer dans le magasin
  2. acheter 100g de bonbons
  3. compter ses sous
  4. s'il reste plus de 2 francs alors retourner au point 2
  5. sinon sortir du magasin

L'algorithmique doit beaucoup au mathématicien persan
Al Kwarizmi (780-850), son nom est d'ailleurs l'origine du mot algorithme ; mais une excellente définition est celle de René Descartes dans le Discours de la Méthode : "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.".

Complexité algorithmique

La principale notion mathématique dans le calcul du coà»t d'un algorithme précis, sont les notions de négligeablité (notée o(f(n)), "petit o") et de domination (notée O(f(n)), "grand o"), o๠f est une fonction mathématiques de n, variable désignant la quantité d'informations (en bits, en nombre d'enregistrements...). Les fonctions mathématiques relèvent de l'analyse. En algorithmique on trouve souvent des complexités du type :

Sans entrer dans les détails mathématiques, on peut dire que lorsque l'on calcule l'efficacité d'un algorithme (sa complexité algorithmique), on cherche davantage à  connaître l'évolution du nombre d'instructions de base en fonction de la quantité de données à  traiter (par exemple, dans un algorithme de tri, le nombre de lignes à  trier), que le coà»t exact en secondes et en quantité de mémoire. Baser le calcul de la complexité d'un algorithme sur le temps qu'un ordinateur particulier prend pour effectuer le-dit algorithme ne permet pas de prendre en compte la structure interne de l'algorithme et la particularité de l'ordinateur : selon sa charge de travail, la vitesse de son processeur, la vitesse d'accès aux données ou même l'exécution de l'algorithme (qui peut faire intervenir du hasard) le temps d'exécution ne sera pas le même.

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 n, alors que pour une utilisation dans des conditions réalistes de l'algorithme, ce paramètre reste de taille modérée. Ainsi pour trier un tableau de 30 lignes (c'est un paramètre de petite taille) pas besoin d'algorithmes évolués comme Quicksort (un des algorithmes de tri les plus efficaces en moyenne) : l'algorithme de tri le plus trivial est très efficace. A noter aussi : 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) se comporte de façon désastreuse si on l'applique à  une liste de valeur ... 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 à  peu près triées.

Les heuristiques

Pour certains problèmes, les algorithmes ont une complexité beaucoup trop grande, et donc il faudrait un temps astronomique avec les puissances de calcul dont nous disposons actuellement pour obtenir un résultat. Pour certains problèmes bien spécifiques, on est donc amené à  rechercher la solution optimale en procédant par essais successifs, et en testant différentes combinaisons calculées grà¢ce à  des fonctions heuristiques qui permettent de s'approcher de la solution. (Les heuristiques n'ont pas d'autres buts que de ne PAS essayer toutes les combinaisons possibles avant de trouver celle qui répond au problème) 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 non répertoriés dans leur base, en s'appuyant sur des ressemblances avec des virus connus.

Applications

Voir aussi