Les éléments d'algorithmique présents dans le programme de seconde suffisent pour aborder des problèmes déjà difficiles, même si dans la pratique, l'idée semble plutôt de faire concevoir ou programmer des calculs simples aux élèves.
Une fois un algorithme établi, se pose rapidement le problème de son efficacité. Pour cela, l'outil adapté est la notion de complexité. La complexité d'un algorithme peut être tellement grande qu'il est tout simplement inutile de le mettre en œuvre sur une machine avec des données réelles : le programme ne se terminerait pas avant plusieurs années. Cela peut d'ailleurs devenir un avantage : c'est sur la difficulté pratique de factoriser un nombre de deux cents chiffres que repose la sécurité de presque tous les systèmes de cryptographie. S'impose alors la nécessité de concevoir de nouveaux algorithmes plus efficaces, parfois fonder des concepts mathématiques nouveaux eux aussi.
L'algorithmique porte sur des données. Il peut être utile, avant de les traiter, de structurer ces données.
Prenons l'exemple classique des algorithmes de tri (il s'agit de trier une liste de données selon un ordre total - par exemple, l'ordre naturel sur les entiers ou l'ordre lexicographique sur les chaînes de caractères). Le tri à bulles est un algorithme naïf et peu efficace. Le tri rapide est en moyenne plus efficace. Il repose sur une idée féconde, "diviser pour régner", mais les données sont stockées dans un tableau sans structure particulière. De plus, il présente un défaut important : pour certaines listes, le temps de tri "explose" au point d'en faire une faille de sécurité de certains systèmes.
Le tri par tas est conceptuellement plus innovant. Il utilise les tas, qui sont des arbres binaires presque complets où chaque nœud porte une étiquette plus grande que celle de ses fils. A partir d'une liste non ordonnée, on construit petit à petit un tel tas qui stocke les données à trier. Trier consiste alors à enlever une à une les données du tas. Le tri par tas est, en moyenne, presque aussi efficace que le tri rapide, mais sa complexité dans le cas le pire est du même ordre de grandeur qu'en moyenne. Voyez un exemple de tri par tas (tiré de la Wikipedia).
Les arbres sont ubiquitaires en informatique. En fait, la description d'un arbre semble incarner l'idée de récursivité : un arbre, c'est un nœud (muni d'une étiquette) qui peut avoir des fils, lesquels sont eux-mêmes des arbres...
La compression de données par l'algorithme de Huffman est un autre exemple où les arbres jouent un rôle crucial. Il intervient dans des formats tels que jpeg et mp3, si communs pour les fichiers d'images et de vidéos. Pour compresser un fichier, l'idée consiste à faire un index des expressions (lettres ou mots ou groupes de chiffres) qu'on y trouve et à les ranger dans un arbre binaire. On remplace alors une expression par un code qui définit sa position dans l'arbre. Sachant que les nœuds proches de la racine de l'arbre ont un code plus court, on y range les expressions les plus fréquentes. Si on applique cette idée à un texte aléatoire, le gain sera nul, voire pire. Mais si certaines expressions reviennent souvent, comme c'est souvent le cas dans le code d'une image ou d'une musique, le gain peut être énorme.
On trouve aussi des arbres pour faciliter les recherches dans les données complexes, pour gérer les priorités (des requêtes à une base de données par exemple), c'est par des arbres qu'on peut représenter toutes les expressions arithmétiques, la liste des coups possibles dans un jeu à deux joueurs, etc.
Donald Knuth , professeur émérite à Stanford, auteur de l'ouvrage de référence sur l'algorithmique, en plusieurs volumes, intitulé The Art of Computer Programming (L'art de la programmation informatique), considère d'ailleurs les arbres comme "la structure la plus fondamentale de toute l'informatique".
Nous venons de mentionner quelques représentations de données par des structures arborescentes. Un autre type de structuration de données fonde l'algorithme d'indexation par pertinence PageRank de Google . Le résultat d'une requête à ce moteur de recherche est une liste de pages. Elle est triée, non par ordre croissant de taille ou par ordre alphabétique de titre (comme c'était le cas aux débuts d'Alta Vista...), mais selon une contrainte qui résulte de la structure du web. Plus précisément, l'algorithme PageRank attribue à chaque page un score censé en refléter la pertinence. Tout se passe comme si on parcourait le web en suivant des liens au hasard, tout en notant combien de fois on passe sur chaque page. Le score d'une page est la fréquence à laquelle on y passe. Le credo, c'est que plus souvent on passe sur une page, plus elle est importante/intéressante/utile/pertinente. Pour modéliser le problème, on considère un graphe orienté dont les sommets sont les pages et dont les arêtes sont les liens hypertextes. Les probabilités - la théorie des chaînes de Markov finies avec, en l'espèce, un peu d'algèbre linéaire - permettent de calculer le score ci-dessus.
Les structures mathématiques interviennent à deux niveaux en algorithmique :
elles permettent de tenir compte de la structure des données (on code l'ordre par un tas, les liens hypertextes par un graphe orienté) ;
il est parfois nécessaire d'inventer de nouvelles structures pour calculer avec les données et plus généralement les manipuler.
Montrons par un exemple que cette question de structure est bien un problème conceptuel mathématique et pas un problème d'implémentation : on peut utiliser des formats de données naïfs pour coder des structures complexes. Par exemple, un tas peut se coder par un simple tableau. Si on lit l'arbre de haut en bas et de gauche à droite et qu'on écrit l'étiquette correspondante dans un tableau, les fils du nœud qui apparaît en position k se retrouve en positions 2k et 2k+1 ; le père du nœud en position p est en position p/2 ou (p-1)/2 (selon la parité). D'ailleurs, le but du site australien Computer Science Unplugged est "de révéler un secret peu connu : l'informatique, ça n'a rien à voir avec les ordinateurs !"
Ainsi, l'informatique met à jour des structures mathématiques abstraites pertinentes pour résoudre des problèmes algorithmiques. Ces structures deviennent alors des objets mathématiques à part entière, des objets d'étude qui ont un intérêt intrinsèque. Pensons par analogie à la naissance du calcul différentiel pour modéliser le mouvement : ne retrouve-t-on pas dans cette dialectique le même type d'interactions qu'entre physique et mathématiques ?
Masquer ce qui précède
