Vous avez toujours voulu briller en société, mais, malheureusement, vos 5k!llz à Quake 3 ou vos compétences culinaires ne vous en ont jamais laissé la possibilité ? Pas de problème, il vous suffira de lire cet article afin de maîtriser les bases de l'algorithmique. À vous les soirées mondaines, le champagne et les filles au décolleté plongeant ! Tout d'abord, définissons ce qu'est un algorithme : ce serait dommage de perdre la face devant vos futures groupies. Un algorithme est une méthode utilisée afin de parvenir de manière certaine à un but précis, en décomposant la démarche nécessaire en un nombre fini d'étapes élémentaires. On atteint des sommets de clarté, je sais : pour résumer, disons que c'est un peu comme une recette.
Par exemple, mettons que vous vouliez boire un verre d'eau; on pourrait écrire l'algorithme permettant d'y arriver ainsi:
- prendre un verre
- le positionner sous le robinet
- ouvrir le robinet d'eau froide
- tant que le verre n'est pas plein, le laisser sous le robinet
- fermer le robinet
- porter le verre à la bouche
- incliner le verre

Bien entendu, on utilise rarement des algorithmes pour boire des verres d'eau. En général, on les utilise plutôt en mathématiques - par exemple, pour calculer le PGCD de deux nombres avec l'algorithme d'Euclide, ou dans le cadre de démonstrations comme le théorème des valeurs intermédiaires - ou en informatique.
En programmation, quasiment tout tourne autour des algorithmes: pour déterminer l'ensemble des polygones à afficher dans un moteur 3D, pour trouver le chemin le plus court entre deux points dans un jeu vidéo, ou pour résoudre une grille de Sudoku.
En effet, un ordinateur ne peut effectuer, basiquement, que des opérations simples. Pour effectuer quelque chose de complexe, comme par exemple trier une liste de nombres par ordre croissant, il est nécessaire de le décomposer et d'écrire un algorithme, qu'on traduira ensuite en langage de programmation (on dit qu'on implémentera l'algorithme: encore un mot à placer dans toute bonne conversation pour provoquer des lueurs d'admiration béate).

Je ne vais pas vraiment tout détailler, parce que je n'ai pas les compétences, le savoir et le temps nécessaires, mais je vais faire de mon mieux pour présenter différents sujets, illustrés par des exemples simples: les algorithmes itératifs, les algorithmes récursifs, et la complexité d'un algorithme.

Mais d'abord, quelques concepts de base :

Structures conditionnelles

Par "structures conditionnelles", on désigne deux sortes de choses: les "tests" et les boucles. Mettons que je souhaite que des opérations ne soient effectuées que si l'âge du capitaine est égal à 76 ans, et que, dans le cas contraire, on fasse du café, je vais utiliser un test de ce genre:
SI age = 76 ALORS
// FAIRE QUELQUE CHOSE
SINON
FAIRE_CAFÉ()
FIN SI var is_code=true;
(le code ici, et tout au long de l'article, n'est pas écrit dans un réel langage de programmation: c'est du "pseudo code", destiné à rendre les algorithmes clairs)

Voici la forme générale:
SI [condition] ALORS
[instructions]
SINON SI [condition] ALORS
[instructions]
SINON
[instructions]
FIN SI var is_code=true;

Maintenant, les boucles. Cela consiste à exécuter un bloc d'instructions plusieurs fois sur des données dont les valeurs peuvent changer, tant qu'une condition est réalisée. Voici les deux principaux types de boucles :
TANT QUE [condition] FAIRE
[instructions]
FIN TANT var is_code=true;
POUR variable = [valeur de départ] À [valeur de fin]
[instructions]
FIN POUR var is_code=true;
Dans la seconde sorte de boucle, on utilise un compteur (ici i) qui sera incrémenté à chaque tour de boucle qui sera répétée tant que la condition (i<=5) est vérifiée :
POUR i = 0 À 5
AFFICHER(i)
FIN POUR var is_code=true;
Renverra : 0 1 2 3 4 5

Algorithmes itératifs

Ce terme désigne, un peu pompeusement, des algorithmes qui sont basés sur des boucles. Ainsi, si je veux calculer la somme des n premiers nombres (sans appliquer une chose aussi bassement dénuée d'intérêt qu'une formule), je peux passer en revue tous ces nombres, dans une boucle, et les ajouter au fur et à mesure:
fonction SOMME( entier n )
{
RESULTAT = 0
POUR i = 1 À n
RESULTAT = RESULTAT + i
FIN POUR
RENVOYER RESULTAT
} var is_code=true;

Pour calculer n! (factorielle n, c'est-à-dire le produit de tous les entiers de 1 à n):
fonction FACT( entier n )
{
PRODUIT = 1
POUR i = 2 À n
PRODUIT = PRODUIT * i
FIN POUR
RENVOYER PRODUIT
} var is_code=true;

Voilà, le tour rapide des algorithmes itératifs est bouclé. Passons maintenant aux algorithmes récursifs, qui sont bien plus marrants.

Algorithmes récursifs
Récursif, adj.: INFORMAT. Qui s'appelle ou se met en jeu répétitivement et automatiquement. Voir "récurrent".
Un algorithme récursif, c'est un algorithme qui s'appelle lui-même, encore et encore: un bon exemple vaut mieux qu'un long discours, réécrivons l'algorithme des factorielles de manière récursive:
fonction FACT( entier n )
{
SI n = 0 ALORS RENVOYER 1
SINON RENVOYER ( n * FACT(n - 1) )
FIN SI
} var is_code=true;
Première observation: c'est plus court. En revanche, il un peu plus difficile de se représenter mentalement ce que ça va faire.
Si j'appelle FACT(3), que va-t-il se passer ?
FACT(3) : (RENVOYER 3 * FACT(2) )
FACT(2) : (RENVOYER 2 * FACT(1) )
FACT(1) : (RENVOYER 1 * FACT(0) )
FACT(0) : RENVOYER 1 var is_code=true;
La fonction renverra donc 3 * 2 * 1 * 1, soit 6 (et, heureusement, on a bien 3! = 6). Personnellement, je trouve cela bien plus élégant que la version itérative, mais chacun son truc.

Deux remarques, toutefois:
* Chaque algorithme récursif doit comporter une condition d'arrêt (ici, "SI n = 0"). Dans le cas contraire, la récursion se fera de manière infinie, ou, plus précisément, jusqu'à ce que l'ordinateur soit sur les genoux - vu que l'algorithme ne s'arrêtera en théorie jamais. Il est très important de bien concevoir sa condition d'arrêt: par exemple, si j'appelle ma fonction FACT avec un nombre négatif, je risque d'avoir un petit problème.
* La grande majorité (voire la totalité ?) des algorithmes récursifs peuvent s'écrire sous forme itérative. On préfère une forme à l'autre pour des raisons d'élégance (un algorithme récursif de 3 lignes contre un algorithme itératif de 20, ou l'inverse), de clarté ou de performances (un appel récursif de fonction introduit une petite consommation de mémoire supplémentaire, la "pile" de la fonction: c'est négligeable, sauf quand la fonction est appelée récursivement un milliard de fois).

Complexité d'un algorithme

Pour évaluer l'efficacité d'un algorithme, il y a quelques dizaines d'années, on disait "tel algorithme a mis tant de temps à s'effectuer sur tel ordinateur, en tel langage". Vu le nombre de modèles d'ordinateurs différents, de types de processeurs différents et de langages différents, il a fallu trouver quelque chose de plus révélateur.
En gros, on parle désormais de complexité algorithmique, désigné par O(f(n)), f étant une fonction mathématique et n le nombre de données à traiter (par exemple, dans le cadre d'un algortihme visant à trier une liste, n serait le nombre d'éléments de la liste).

Un algorithme en O(1) est constant, quel que soit le nombre de données ; un autre en O(n) est dit en complexité linéaire.
Par exemple, un algorithme en O(100n) est moins efficace qu'un en O(n²) tant que n < 100. La plupart du temps, un algorithme en O(log(n)) est le plus performant.

La complexité d'un algorithme est la plupart du temps une complexité moyenne : pour certaines valeurs de n ou dans certaines conditions, un algorithme censé être le plus performant peut se révéler un très mauvais choix. De plus, il faut également tenir compte de contraintes matérielles (mémoire disponible sur la machine, notamment).
Bref, la complexité est un indicateur, mais ne résume pas tout (quoique, à choisir entre un algorithme en O(n) et un en O(n^8), il est peu probable que le second soit le meilleur).

Voilà, c'est plus ou moins fini. J'aurais bien aimé parler des applications des algorithmes en IA ou dans les jeux vidéo, mais j'ai trop peur de dire des idioties :)