Ecologie Informatique

Comme nous l’avons vu plus haut, le processeur le plus sophistiqué ne sait toujours qu’effectuer des opérations très simples, qui pourraient aussi être réalisées par la tortue de Von Neumann.Toutes les opérations légèrement plus complexes que celles-ci, comme représenter en trois dimensions un avion évoluant dans le Grand Canyon, ne se fait qu’en combinant astucieusement ces instructions élémentaires. Ceci est possible grâce aux travaux d’Al-Khawarizimi, savant arabe du IXème siècle, à qui l’on doit également le mot “algèbre”. Le nom de ce savant ne comportant pas de Y, on appelle “algorithme” avec un I sa méthode de décomposition des opérations compliquées en opérations plus simples qui est, entre autres utilités, à la base de la programmation.

Tout programme informatique utilise essentiellement une combinaison d’algorithmes plus ou moins sophistiqués pour résoudre un problème. La connaissance des algorithmes et de leurs cas d’application est aussi vitale pour la réalisation d’un programme que la maîtrise d’un langage de programmation.

Quelques algorithmes

Les boucles sont omniprésentes en algorithmique : la quasi-totalité des méthodes de résolution de problèmes logiques ou mathématiques est basée sur la répétition d’opérations simples.

Commençons avec deux exemples simples d’algorithmes que vous connaissez certainement:

1. l’addition en colonnes, permettant d’additionner des nombres aussi grands que l’on veut en effectuant plusieurs additions de nombres compris entre 0 et 9
2. la recherche d’un mot dans un dictionnaire. Comme on sait que les mots y sont listés dans l’ordre alphabétique, on procède par “recherche dichotomique” en ouvrant le dictionnaire vers la moitié, on regarde si le mot cherché se situe avant la page ouverte, si oui on ouvre le dictionnaire à la moitié de la première moitié, sinon à la moitié de la seconde moitié et on procède ainsi jusqu’à trouver la page contenant le mot cherché.

D’autres algorithmes sont nettement moins évidents, par exemple comment trier des nombres par ordre croissant. Manuellement, on est tenté de procéder ainsi : chercher le plus petit nombre, le biffer et l’écrire en tête de liste triée, puis chercher le plus petit des nombres restants et procéder ainsi de suite. Pourtant, nous verrons plus bas qu’il existe des méthodes bien plus rapides que celle-ci.

Enfin, il existe des problèmes pour lesquels des siècles de recherche n’ont pas apporté d’algorithmes meilleurs que ceux auxquels on pense immédiatement. Parmi ceux-ci on peut citer par exemple:

1. la décomposition d’un nombre en facteurs premiers. Il n’y a pas d’autre méthode que d’essayer de diviser le nombre successivement par les nombres premiers consécutifs. Et pour déterminer si un nombre est premier, pas d’autre solution que d’essayer de le décomposer. Si vous pensez que ces problèmes ne concernent que les mathématiciens, c’est que vous ne savez pas encore que tous les systèmes de sécurité informatique reposent sur les nombres premiers…
2. Le problème du voyageur de commerce : quel est le circuit le plus court passant par des points fixes ? Pas d’autre solution que d’essayer tous les circuits possibles. Si on tente de se montrer plus malin en cherchant un critère permettant d’éviter d’essayer certaines solutions, on risque de manquer la solution optimale
3. Les jeux de stratégie, comme les échecs. Si on voulait déterminer de façon absolue le coup gagnant à jouer, il faudrait jouer toutes les parties possibles…

Complexité des algorithmes

Quelle importance de s’intéresser aux algorithmes lorsqu’on programme sur une machine capable d’effectuer des milliards d’opérations par seconde ? C’est que certains problèmes demandent des centaines de milliards, ou des millions de milliards d’opérations et vont donc prendre entre quelques minutes et quelques années à résoudre. Lorsqu’une étape du programme prend plus de quelques secondes, il est utile d’afficher une information indiquant la progression, pour que l’utilisateur ne s’impatiente pas trop.

D’autres programmes doivent obligatoirement s’effectuer en un temps limité, par exemple pendant le 100^ème de seconde qui sépare deux affichages d’images sur un écran.

Un autre problème fréquemment rencontré est celui de la “scalabilité” : un programme fonctionne très bien avec quelques données de test, et sa performance s’effondre lorsque la taille des données augmente.

Le critère essentiel permettant de juger et de comparer des algorithmes s’appelle la complexité. C’est la forme de la fonction qui lie le nombre d’opérations à la taille des données notée N. Un algorithme dont le temps de fonctionnement est proportionnel au nombre de donnée a une complexité linéaire, notée O(N). C’est par exemple le cas de la recherche du plus petit nombre d’une liste non triée : si on cherche dans une liste de taille double, cela prendra (en moyenne) le double du temps.

O(log N) mon amour

La recherche dichotomique dans une liste déjà triée a une complexité plus faible que O(N). Combien d’opérations faut-il pour trouver un mot dans un dictionnaire de 1000 pages ? Après une opération, on sait dans quelle moitié de 500 pages se trouve notre mot, après la seconde opération on le situe dans 250 pages etc. en divisant chaque fois le nombre de pages par 2. Le nombre d’étapes est donc au maximum du logarithme en base 2 de N, noté O(log N), qui donne 10. Si la taille du dictionnaire double, on n’a besoin que d’une étape de plus, donc pour chercher dans 2000 pages le temps de calcul ne sera rallongé que de 10%.

Le tri

Quelle est la complexité de notre algorithme de tri “intuitif” ? Il faut faire des recherches successives sur N, puis sur N-1, puis sur N-2 nombres et ainsi de suite jusqu’à ce que tous les nombres de la liste soient biffés et soigneusement copiés dans la liste triée. Comme la recherche prend chaque fois un temps proportionnel au nombre de nombres restants, ça prendra un temps proportionnel à N+(N-1)+(N-2)+…+3+2+1. Foin de détails, ce temps est proportionnel à N au carré, complexité O(N²) donc. Si on a 2x plus de nombres à trier, ça prendra 4x plus de temps. Si vous faites un programme dans lequel ce tri se fait en 1 seconde et que votre client l’exécute sur 100x plus de données, ça prendra 10′000 fois plus longtemps, soit près de 3 heures! Il est probable que l’utilisateur estimera que votre programme a planté bien avant cela.

Peut-on faire mieux ? Oui, les algorithmes de tri “Quick-sort” et “Bubble-sort” ont une complexité O(N.logN). En utilisant de tels algorithmes dans l’exemple ci-dessus, le tri sur 100x plus de données ne prendra “que” 100xLog(100) = 700 fois plus longtemps, soit 11 minutes “seulement”.

Quand les spaghettis frapperont.

Existe-t-il un algorithme de tri encore plus rapide que O(N.Log N) ? Les disciples de Von Neumann sont catégoriques : c’est non. Mais en y réfléchissant, des spaghettis pourraient réussir là où la tortue patine:

1. on coupe un spaghetti à la longueur indiquée par le premier nombre non trié. On coupe un autre spaghetti à la longueur du second nombre, et ainsi de suite pour tous les nombres, et en un temps O(N) on obtient N spaghettis.
2. on pose verticalement la botte de spaghettis sur une table plane de façon à tasser tous les spaghettis contre la table. Ceci prend un temps constant, indépendant de N et ne compte donc pas dans la complexité globale
3. on extrait le spaghetti le plus long de la botte, on le mesure, on le note au bas de la liste triée et on recommence N fois, pour tous les spaghettis.

Voilà, les spaghettis permettent de trier nos nombres en un temps proportionnel à N ! Trier 100x plus de spaghettis prendra 100x plus de temps, mais pour effectuer notre tri en une minute et demie seulement il faut remplacer notre processeur/tortue par un processeur/spaghetti, et on ne sait pas très bien comment faire, et encore moins si le processeur/spaghetti saurait faire autre chose que du tri.

La leçon des spaghettis ne doit cependant pas être oubliée : la complexité des algorithmes dépend de l’architecture des processeurs, et il est possible que des processeurs spécialisés ou des montages physiques expérimentaux puissent résoudre en un temps acceptable des problèmes qui prendraient des siècles aux tortues dont nous disposons.

Problèmes polynomiaux

La plupart des algorithmes utilisés en informatique ont une complexité polynômiale, c’est-à dire O(N^a) ou a est un nombre entier.

Déterminer ce nombre a lorsqu’on programme est très facile : il suffit de compter le nombre de boucles imbriquées qui parcourent les données. Ceci sera détaillé dans le paragraphe ci-dessous.

Quand a=1, la complexité est linéaire et on peut se réjouir d’une “scalabilité” maîtrisée. Fréquemment, a=2 et il faut commencer à se poser les bonnes questions. Si a=3 ou plus, on peut dire à coup sur qu’on va au devant de difficultés si le programme doit être effectué sur des données “nombreuses”, et l’on peut simultanément être quasiment certain qu’il existe une solution avec une complexité plus faible.

Un exemple classique est la résolution de systèmes d’équations linéaires, de la forme

a₁₁.x₁+a₁₂.x₂+…+a_1n.x _n =b₁

a₂₁.x₁+a₂₂.x₂+…+a_2n.x _n =b₂

_{………………………………………….}

a_n1.x₁+a_n2.x₂+…+a_nn.x _n =b_n

ou, sous forme matricielle, A.x=b. Mathématiquement, la solution s’écrit x=A^-1.b, et on pourrait donc être tenté de résoudre le problème en inversant la matrice A. La méthode scolaire pour ce faire se base sur le calcul des déterminants, et je me réjouis de rappeler à certains la belle époque ou vous saviez le faire à la main sur des matrices 3×3 ou 4×4. J’informe ceux qui n’ont pas connu ces joies que la complexité de ceci est O(n³), à quoi il faut ensuite ajouter la multiplication matricielle qui est O(n²). Gauss, Choleski et d’autres mathématiciens des siècles passés avaient des problèmes de taille 50×50 à résoudre à la main, et effectuer plus de 50*50*50=125′000 multiplications les excitait beaucoup moins que de chercher une méthode permettant d’en faire beaucoup moins. Les méthodes dites de décomposition L.U résolvent un système linéaire en O(n²) sans inverser la matrice, et permettent même d’inverser la matrice avec la même complexité si nécessaire.

Lorsqu’on sait que de nombreux problèmes d’optimisation pratiques se ramènent à des systèmes linéaire de dimension pouvant atteindre 1000, c’est une accélération d’un facteur 1000 qui peut être obtenue en utilisant ces algorithmes.

Quand NP ne veut plus dire “No Problem”…

… mais “non polynomial”, les vrais ennuis commencent. Les algorithmes exponentiels ont une complexité de type O(e^N) qui résulte souvent de la façon dont N est défini. Par exemple la décomposition d’un nombre N en facteurs premiers, appelée aussi “factorisation” a un coût proportionnel à la racine carrée de N, donc polynômial O(N^1/2) . Mais si l’on définit N comme le nombre de chiffres du nombre, ce coût devient O(10^N/2). En cryptographie par exemple, cracker un code de sécurité de 128 bits revient à factoriser un nombre d’environ 40 chiffres. Ecrire que ceci a un coût proportionnel à N=10²⁰ n’a que peu de sens, alors qu’écrire un coût exponentiel correspond mieux à la dure réalité pratique : ajouter un seul bit à une clé de sécurité double la difficulté de la cracker. Moore dirait: il faut ajouter un bit aux clés de sécurité tous les 18 mois pour qu’elle soit toujours aussi difficile à cracker…

Un problème exponentiel fait figure de jeu d’enfant à côté des problèmes “non-polynomiaux complets”, NP-Complets pour les intimes: ceux-ci ne se ramènent en aucun cas à des problèmes polynomiaux. Leur complexité est donnée par les lois impitoyables de l’algèbre combinatoire : les factorielles. Pour mémoire, 10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 = 3′628′800, 13! dépasse déjà le milliard, 21! franchit le milliard de milliard, bref, un problème O(N!) est totalement hors de portée de l’informatique moderne lorsque N dépasse environ 20… Or, comme on l’a mentionné plus haut, il existe plusieurs problèmes pratiques pour lesquels les seuls algorithmes connus sont NP-complets, par exemple le voyageur de commerce. Choisissez 20 villes sur une carte de votre pays, et cherchez le circuit routier le plus court possible qui passe par toutes ces villes. En partant d’une ville de départ, vous pouvez vous diriger vers n’importe laquelle des 19 autres villes, puis de celle-ci vers une des 18 autres etc jusqu’à la dernière. Vous trouverez peut-être des “recettes de cuisine” qui vous économiseront des essais : arrêter dès que le chemin devient plus long que le plus court déjà trouvé, ne pas permettre au circuit de se croiser etc, mais dans l’ensemble vous n’y couperez pas : il faudra essayer une bonne partie des 19! chemins possibles

La récursivité

De quand date votre dernier « Wow ! » ? Cet instant où on s’émerveille en comprenant une chose toute simple, dont on sait instantanément qu’on s’en rappellera toute notre vie ? Je me souviens encore de celui que j’ai éprouvé vers 1980 en voyant ces quelques lignes de Pascal :

integer function fact(n : integer)
begin;
if n>1 then return n*fact(n-1); else return 1;
end;

Wow! Un sous-programme qui s’appelle lui-même ! Nous avons ici l’exemple type d’un algorithme dit « récursif » :

• si on sait résoudre un problème dans le cas trivial, ici 1 !=1
• et si on sait ramener le problème général à un cas juste un peu moins compliqué, ici n! = n*(n-1)!
• alors on sait le résoudre dans tous les cas.

En fait, nous pourrions tout aussi bien écrire notre fonction factorielle avec une simple boucle.

Pas de quoi faire « wow », mais certainement plus efficace que la version récursive, notamment car la pile n’est pas mise à contribution.

Est-il toujours possible de « dé-récursifier » des algorithmes récursifs, en les implantant avec des boucles ? Oui, mais ce n’est pas toujours simple. On a parfois besoin d’utiliser une structure de données de type « pile », ou même une structure plus complexe.

En fait, lorsqu’un algorithme est simple à formuler de manière récursive, mais difficile à dé-récursifier, on peut être pratiquement certain que sa complexité est forte, ou même pire.

L’explosion combinatoire

Les algorithmes à forte complexité se rencontrent surtout dans les problèmes d’optimisation, dans lesquels on cherche la « meilleure » combinaison parmi toutes celles possibles. Ces algorithmes fonctionnent de la manière suivante :

1. à partir d’une situation donnée, générer tous les choix possible
2. pour chaque choix, obtenir la situation résultante et appeler récursivement la fonction à partir de cette situation
3. renvoyer en résultat le meilleur choix.

Prenons comme exemple un jeu de stratégie comme les échecs. La fonction qui détermine le meilleur coup à jouer fonctionne ainsi :

1. faire la liste de tous les coups conformes aux règles pour les blancs (qui commencent), S’il n’y en a pas c’est que les blancs sont échec et mat et ont perdu.
2. pour chaque coup possible, déterminer l’échiquier résultant et appeler récursivement la fonction, mais en se mettant du point de vue de l’adversaire.
3. jouer le coup qui maximise le bénéfice entre la « valeur » de la situation obtenue et la meilleure situation que l’adversaire pourra en tirer.

Cet algorithme met le programme dans une situation favorable dès le premier coup et joue ensuite sans aucun risque de perdre. En fait, en exécutant l’algorithme une seule fois et en stockant les résultats intermédiaires, l’ordinateur pourrait savoir ce qu’il faut jouer dans toutes les situations possibles de toutes les parties d’échec possibles.

Est-ce possible ? La complexité exacte du jeu d’échecs est difficile à évaluer. D’une part le nombre de coups légaux n’est pas constant. A l’ouverture, il y en a 20 (avancer chacun des 8 pions de 1 ou 2 cases, avancer un des 2 chevaux à gauche ou à droite). En fin de partie, un roi isolé n’aura peut-être que 2 ou 3 coups possibles. Si on admet que chaque joueur ait en moyenne 20 coups légaux à chaque tour, on peut considérer la complexité de notre algorithme comme exponentielle O(20^N) ou N est le nombre de tours de « profondeur » de la recherche. On commence à voir arriver les difficultés…

Une partie d’échecs peut prendre entre 8 tours (le mat le plus rapide) et des centaines. Il faut d’ailleurs ajouter à l’algorithme une détection de partie nulle pour éviter les parties infinies.

Si on admet ici encore qu’une partie prend « en moyenne » 50 tours, notre algorithme parfait devrait évaluer environ 20 à la puissance 50 situations possibles, soit plus qu’il n’y a d’atomes dans l’Univers, et beaucoup plus que le nombre de nanosecondes écoulées depuis le BigBang.

Le terme d’explosion combinatoire désigne ce phénomène : un algorithme relativement simple à formuler engendre un nombre de combinaisons phénoménal, ingérable en pratique.

Que retenir de cette petite leçon d’humilité infligée par les échecs :

1. Qu’il faut se méfier des algorithmes dont la complexité n’est pas facile à établir. Notamment, la combinaison « récursivité + boucle » est aussi explosive que « nitro + glycérine »
2. Que la puissance de tous les ordinateurs du monde est largement insuffisante à résoudre certains problèmes de manière exacte, ce qui oblige à considérer des alternatives approximatives. Nous en parlerons plus en détail au paragraphe « Certitude quand tu nous tiens ».
3. Qu’outre les jeux de stratégie et les problèmes d’optimisation déjà mentionnés, ce qu’on appelle souvent « Intelligence Artificielle » utilise communément des algorithmes similaires. L’explosion combinatoire est l’obstacle principal rencontré par les « systèmes experts » et les langages comme Prolog que nous aborderons au Chapitre 9 : Langages, Compilateurs et Interpréteurs
4. Que les humains traitent les problèmes nécessitant de l’intelligence d’une manière fondamentalement différente, mais mal connue. A un journaliste lui demandant combien de coups il analysait avant de jouer, Gary Kasparov, champion du monde d’échecs répondit : « un seul : le bon ! »

Ecologie des boucles

Comme on l’a vu, les algorithmes intuitifs sont rarement les plus efficaces. On peut être tenté de se reposer sur la puissance des ordinateurs pour se passer de rechercher, de se former et d’utiliser des algorithmes plus sophistiqués. Mais si l’on réalise qu’il est parfois possible d’accélérer certaines opérations d’un facteur 10, 1000, 1′000′000 voire plus en utilisant un meilleur algorithme, on réalise mieux l’avantage que peut apporter quelques minutes de réflexion.

Les bonnes habitudes

En algorithmique, l’objectif du programmeur écologiste est donc simple : réduire au maximum le nombre de boucles imbriquées de son code, y compris les boucles induites par récursivité. Ceci implique d’acquérir quelques réflexes:

1. Savoir à chaque appel de sous-programme quelle est sa complexité. Le plus simple est de mettre en commentaires de courtes annotations du genre
   en C++ : sort(liste) ; // O(NlogN)
   en VB : mafonction(c as Collection) ‘ O(N2)
2. Savoir en chaque point du code combien de boucles l’englobent. En particulier, il faut prêter attention à la complexité des algorithmes dès qu’ils sont utilisés de manière répétitive. Considérons par exemple que l’on doive déterminer si des mots figurent dans une liste ou non. Cette recherche est O(N/2) si la liste n’est pas triée, O(logN) si elle l’est, et le tri lui-même coûte O(N.Log N). Donc si l’on doit vérifier plus de 2xLog(N) mots, il sera plus rapide de commencer par trier la liste, puis de bénéficier de la recherche rapide. Pour N=1000, le tri demandera 10′000 comparaisons, puis chaque recherche 10 seulement, alors qu’une recherche sur liste non triée demandera 500 comparaisons. Dès 21 recherches, il sera rentable de trier la liste d’abord.
3. Eviter la récursivité, qui masque la complexité réelle des algorithmes, et surtout le cas « récursivité + boucle ».
4. Eviter d’utiliser des algorithmes plus puissants que nécessaire. C’est le sujet du paragraphe suivant.
5. Ne pas hésiter à consommer un peu de mémoire pour gagner beaucoup de temps. C’est le thème du paragraphe d’après.

L’algorithme trop puissant

Lorsque le programmeur dispose de librairies d’algorithmes, il a tendance à les appliquer dès que leur utilisation lui évite d’écrire quelques lignes de plus lui-même. Quelle est la valeur la plus grande dans une liste non triée ? Il est tentant de prendre le dernier élément de la liste triée. Et il est vrai qu’en pseudo-code “max=liste.sort().last()” sonne mieux que “max=0; for each i in liste, if i>max then max=i;”, pas vrai ?

Mais la fonction de tri est O(N.Log(n)) alors que la recherche du maximum est O(N). Il y a peu a gagner ici mais il faut considérer que le gaspillage affecte aussi la mémoire, puisqu’une liste triée est allouée de manière temporaire, dont seul le dernier élément est utile.

L’indice permettant de détecter ces situations est justement ce gaspillage d’information : lorsqu’on a besoin que d’une petite partie du résultat d’un algorithme, c’est qu’on n’a pas utilisé le bon.