Algorithmique

Cette section est dédiée à l'algorithmique, et plus précisément à ses applications en informatique. Un algorithme est une méthode systématique permettant d'aboutir à un résultat donné. Pour plus d'informations, vous pouvez consulter l'article d'introduction à l'algorithmique. Nous aborderons ici les notions fondamentales de l'algorithmique, ainsi que plusieurs algorithmes classiques.

Articles

Généralités

Introduction à l'algorithmique : premier contact avec le terme « algorithme ».
Introduction à la récursivité : découverte de la récursivité par l'exemple.
Calcul intuitif de complexités : approche intuitive de la notation $\small \cal O$ utilisée en algorithmique.

Algorithmes classiques

Dijkstra : plus court chemin lorsque les pondérations des arcs sont positives.
Ford-Bellman : plus court chemin quelles que soient les pondérations des arcs. Pas de cycle améliorant.
Kruskal : arbre couvrant de poids minimal.
Union-Find : algorithme des ensembles disjoints.

Graphes

Arbre couvrant : définition de la notion d'arbre couvrant.
Circuit Eulérien : algorithme et définition du circuit Eulérien.

Mathématiques

Algorithmes arithmétiques : un feuillet Maple où l'on implémente des fonctions arithmétiques classiques.

Liens externes

France-IOI

Si vous souhaitez vous exercer, je vous recommande vivement de visiter le site de l'association France-IOI, qui propose des articles, cours et fiches méthode ainsi qu'une grande collection de problèmes que vous pourrez résoudre en-ligne.

Le système de soumission est interactif et, en cas de problème, des entraîneurs seront là pour vous aider et vous conseiller. La liste des langages disponibles est fournie et il est peu probable que votre langage favoris ne soit pas au menu. Ce site est donc un très bon outil pour progresser. De plus, c'est la voie de sélection privilégiée pour les Olympiades internationales d'informatique.

Ressources en anglais

On trouve aussi et surtout des articles d'algorithmique en anglais sur le net. Si la langue de Shakespeare ne vous fait pas peur, vous pourrez consulter avec profit les pages suivantes :

Dictionary of Algorithms and Data Structures : répertoire d'algorithmes et structures de données classiques.
The Stony Brook Algorithm Repository : implémentations de plus de 70 algorithmes classiques.