Notion d'Algorithme, de temps de calculs
Un exemple concret
Problèmes abordés
Chronologie du module
Notion d'Algorithme, de temps de calculs
Un exemple concret
Problèmes abordés
Chronologie du module
Un algorithme est une méthode pour résoudre
une classe de problèmes sur un ordinateur. La complexité d'un
algorithme se mesure par son coût en temps de calcul, mémoire
utilisée ou toute autre unité significative, lors de son utilisation
pour résoudre un de ces problèmes.
Ce module d'informatique traite d'algorithmes et de complexité.
On présentera quelques méthodes pour résoudre des problèmes
sur ordinateurs, ainsi que le coût de ces méthodes. En particulier,
on étudiera des problèmes relevant de la théorie des
graphes ou de la recherche opérationnelle comme l'algorithme de Ford.
Les calculs prennent du temps. Certains problèmes
prennent un temps très long, d'autres peuvent être traités
rapidement. Certains problèmes semblent être longs,
et quelqu'un découvre un jour un moyen plus rapide de les traiter.
L'étude de la somme d'opérations nécessaires pour effectuer
certains types de calculs constitue l'étude de la complexité
de calcul.
Naturellement, on s'attend à ce qu'un problème
portant sur des millions de bits d'entrée prenne plus de temps qu'un
problème plus réduit portant par exemple sur une dizaine de
bits. On exprime donc la complexité d'un calcul comme une fonction
de la somme de données nécessaire pour décrire le problème
à l'ordinateur.
Considérons par exemple l'affirmation:
"Je viens d'acheter un logiciel d'inversion de matrices,
avec lequel je peux inverser une matrice n * n en 1,2n3
minutes."
Nous sommes ici confrontés à une description typique de
la complexité d'un algorithme. Le temps d'exécution du programme
est décrit comme une fonction de la taille de la matrice de départ.
Un programme plus rapide pour le même travail pourrait s'exécuter
en 0,8n3 minutes. Si quelqu'un faisait une découverte
importante, cela pourrait peut-être abaisser l'exposant, au lieu de
diminuer la constante multiplicative. Ainsi, un programme qui inverserait
une matrice en seulement 7n2.8 minutes constituerait
une franche amélioration de l'état de l'art.
Dans la littérature consacré à la
complexité, un calcul prenant au plus un temps c*n3
pour des données de taille n sera considéré
comme "facile". Un calcul de temps au plus n10
est également facile. Si un calcul sur une matrice n*n devait
nécessiter 2n minutes, ce serait un problème
"difficile". Naturellement, certains calculs que nous qualifions
de "faciles" peuvent prendre un temps fou, mais de notre
point de vue la distinction portera sur des temps polynômiaux ou non.
La regle générale est que si le temps de
calcul est au plus un polynôme des données d'entrées,
le problème est facile, sinon il est difficile.
Beaucoup de problèmes d'informatique sont réputés
faciles. Pour convaincre quelqu'un qu'un problème est facile, il
suffit de décrire une méthode rapide pour le resoudre.
Pour convaincre quelqu'un qu'un problème est difficile, il faut prouver
qu'il est impossible de trouver un moyen rapide de faire ce calcul. Il ne
sera pas suffisant de proposer un algorithme et de se lamenter sur sa lenteur.
Après tout, cel algorithme peut être lent, et il se peut qu'il
existe des méthodes plus rapides.
L'inversion de matrices est facile. La méthode
courante d'élimination gaussienne inverse une matrice n * n
en un temps d'au plus c*n3 .
Un exemple intéressant de problème difficile
est le "problème du carrelage". Supposons que l'on
ait une infinité de carreaux identiques, de forme hexagonale. On
peut alors carreler le plan entier, c'est-à-dire recouvrir le plan
sans laisser aucun espace. Ceci peut également être fait avec
des carreaux rectangulaires, mais pas avec des pentagones réguliers.
La figure 1 représente un carrelage du plan par
des rectangles identiques, et la figure 2 un carrelage par des hexagones
réguliers.
Ceci pose un certain nombre de questions tbéoriques
et calculatoires. L'une d'entre elles est la suivante: soit un certain polygone,
pas nécessairement régulier
ni convexe, et supposons que
nous disposions d'une infinité de carreaux de cette forme. Pouvons-nous
alors carreler tout le plan?
Il a été démontré (R. Berger,
The undecidability of the domino problem, Memoirs Amer. Math. Soc.
Vol. 66 (1966)) que ce problème était insoluble par le calcul.
Non seulement on ne connait pas de moyen rapide de résoudre ce problème
sur ordinateur, mais il a été prouvé qu'il n'y avait
aucun moyen de le faire. Cela ne signifie pas que le problème soit
difficile pour tous les polygones.
Des problèmes difficiles peuvent avoir des
instances faciles. Ce qui a été prouvé est qu`il
n'existe pas de méthode simple qui garantisse de trouver une réponse
à cette question pour chaque polygone.
Le fait qu'un problème soit difficile ne veut
pas dire que toutes ces instances sont forcément difficiles. Le problème
est difficile car on ne peut pas trouver d'algorithme qui garantisse une
performance pour toutes les instances.
Remarquez que la somme de données d'entrée
est assez faible sur cette exemple. Il suffit d'entrer la forme du polygone
de base. Pourtant, non seulement il est impossible de trouver un algorithme
rapide pour ce problème, mais il a été prouvé
qu'il était impossible de trouver un algorithme qui garantisse une
réponse Oui/Non en un nombre fini d'étapes (problème
de décidabilité).
Le but ce module est de tenter de répondre à
des questions que l'on peut légitement se poser sur ce qu'il est
possible de faire faire par un ordinateur, indépendamment de l'état
d'avancement de la technologie.
Ces questions pourraient-être :
Qu'est-ce qui est calculable par une machine ?
Dans un tel contexte, la littérature propose plusieurs modèle théorique
de machine abstraite ( Turing, RAM). Un résultat important qui a été
démontré est qu'il existe des fonctions que l'on ne peut pas
calculer, des problèmes que l'on ne peut pas résoudre dans
ces modèles. Ces modèles étant pourtant un idéal
calculatoire, cela implique que les ordinateurs ne peuvent pas tout faire
et il est bon d'en connaître les limites théoriques.
En deça de ces limites théoriques, il existe
également des limites pratiques de temps et d'espace mémoire.
C'est la question de ce qui est calculable en pratique par une machine semble
être directement liée à la technologie du jour. Pourtant,
il est possible de distinguer dans l'absolu des problèmes qui ont
une solution faisaible (en anglais "tractable") et des
problèmes qui ont certes une solution, mais qui demandent des calculs
si couteux en temps qu'ils sont irréalisables.
Un exemple simple : le jeu d'echec est un jeu à deux joueurs à
information complète. On sait qu'il existe un algorithme de jeu optimal.
En pratique, l'explosion combinatoire fait que l'on ne peut pas calculer
l'ensemble, pourtant fini, de toutes les parties possibles.
Nous introduirons une mesure de la complexité
d'un algorithme en comptant le nombre d'opérations élémentaires
qu'il faut effectuer en fonction de la taille des données d'entrées.
Si cette fonction est au moins exponentielle, le problème cesse rapidement
d'être traitable. Par contre si cette fonction est au pire polynomiale,
on dira que le problème reste faisable. Notions déjà
abordées précédement, sous la terminologie problème
facile ou difficile.
Avant d'aborder l'aspect quantitatif d'un algorithme
en temps ou en mémoire (ie sa complexité), on introduira quelques
notions sur la preuve de propriétés, et la terminaison de
programmes itératifs et récursifs, ie l'aspect qualitatif.
Ces notions qualitatives (preuve de propriétés, de terminaison)
assureront que l'algorithme réalise bien se que l'on attendait de
lui. Aprés cette étape, l'on pourra rechercher la complexité
de l'algorithme, ie l'aspect quantitatif. Ces étapes constituent
de notre point de vue l'étude pratique des algorithmes. Notre étude
théorique des algorithmes, le dernier chapitre de ce module, se
limitera aux notions de calculabilité, décidabilté,
les classes P et NP que l'on peut définir par rapport aux machines
de Turing.