Nos algorithmes pourraient-ils être BEAUCOUP plus rapides ? (P=NP ?)

Bonjour à tous !

Aujourd'hui on va parler d'une énigme à un million de dollars.

Vous savez, un de ces sept problèmes de mathématiques

pour lesquels l'institut Clay a décidé d'offrir une récompense

à celui ou celle qui en trouverait une solution.

Le problème d'aujourd'hui est intéressant

car il est à la frontière entre les mathématiques et l'informatique

et il est parfois considéré comme le plus simple des sept.

Alors, le plus simple, pas forcément à résoudre mais du moins à expliquer,

car il concerne en quelque sorte la rapidité des algorithmes

qui sont utilisés par nos ordinateurs.

Commençons par un problème très simple,

imaginons que je vous donne une liste de nombres

et que je vous demande de trouver

le plus petit nombre de cette liste, son minimum.

Pas très compliqué, vous prenez un bout de papier

vous parcourez la liste et sur le papier vous gardez trace

du plus petit nombre que vous avez croisé pour l'instant,

vous mettez à jour si vous en trouvez un plus petit

et une fois arrivé à la fin de la liste,

eh bien vous avez la certitude d'avoir

sur votre bout de papier le minimum de cette liste.

Alors, l'air de rien, quand on fait ça on applique un algorithme

c'est à dire une procédure bien définie qui résout un problème donné

en prenant en entrée, ici : la liste de nombre,

et en fournissant une sortie : le plus petit nombre de cette liste.

Quand on met au point un algorithme pour effectuer une certaine tâche,

on va souvent s'intéresser à sa rapidité,

combien de temps va-t-il lui falloir pour réaliser le job ?

On pourrait la mesurer de différentes façons, par exemple avec un chronomètre,

mais ça va évidemment dépendre

de la puissance de la machine sur laquelle on le fait tourner.

Alors une autre façon de quantifier la rapidité d'un algorithme,

c'est de compter combien d'opérations élémentaires il doit effectuer.

Dans notre cas, on voit que pour chaque nombre de la liste,

il faut le lire pour le comparer au plus petit qu'on ait trouvé jusqu'ici,

on va dire que faire cette comparaison c'est une opération.

Alors évidemment s'il y a 10 nombres dans ma liste

je vais devoir faire 10 opérations,

100 nombres : 100 opérations

1000 nombres : 1000 opérations etc.

De façon générale, avec cet algorithme s'il y a N nombre dans la liste

il me faudra faire N opérations élémentaires pour l'appliquer.

Considérons maintenant un problème un peu différent,

il ne s'agit plus de trouver le plus petit nombre de la liste

mais de la classer par ordre croissant.

C'est plus compliqué mais on peut facilement imaginer un algorithme qui le fait.

Puisqu'on sait trouver le minimum d'une liste grâce à l'algorithme précédent,

on n'a qu'à le chercher et le sortir de la liste.

Et puis ensuite recommencer sur la liste restante,

trouver son minimum, le sortir, puis à nouveau etc.

C'est juste un peu plus long puisqu'il va falloir appliquer plein de fois

l'algorithme de recherche du plus petit nombre d'une liste.

On peut calculer que pour faire ça avec 10 nombres dans la liste

il me faudra au total une cinquantaine d'opérations élémentaires,

avec 100 nombres il faudra 5 000 opérations

et avec 1 000 nombres, environ 500 000.

Vous voyez que la situation de cet algorithme de tri

est assez différente de celle de l'algorithme de recherche d'un minimum,

le nombre d'opérations nécessaires

augmente beaucoup plus quand la taille de la liste augmente.

Si N est la taille de la liste, le nombre d'opérations nécessaires pour la trier

avec cet algorithme est en gros (N au carré) /2 et ça change beaucoup de choses,

vous voyez que si je multiplie la taille de la liste par 10,

trouver le minimum prendra 10 fois plus de temps,

mais en faire le tri prendra 100 fois plus de temps.

Quand on veut traiter beaucoup de données avec un ordinateur,

cette différence va se faire sentir.

Cette question du nombre d'opérations nécessaire

on se la pose évidemment chaque fois que l'on imagine

un nouvel algorithme pour résoudre un problème donné.

On essaye d'estimer comment le nombre d'opérations

va croître quand on augmente la taille du problème

c'est-à-dire la taille des données en entrée.

On note toujours traditionnellement N cette taille,

pour la recherche de minimum, le nombre d'opérations est proportionnelle à N,

pour la méthode de tri que je vous ai présentée, il est proportionnel à N au carré .

Cette notion là c'est ce qu'on appelle la "complexité" de l'algorithme.

Alors attention hein, car ce terme de complexité peut être un peu trompeur.

La complexité ça ne mesure pas

à quel point l'algorithme est difficile à comprendre ou à programmer

mais de quelle façon le temps de calcul

va augmenter quand on augmente la taille du problème.

Pour ma recherche de minimum, la complexité est proportionnelle à N, la taille de la liste,

on dit que la complexité est linéaire.

Pour mon algorithme de tri elle est proportionnelle à N²,

on parle de complexité quadratique,

Comme vous pouvez vous en douter, ces questions de complexité

sont très importantes pour toutes les applications pratiques

où on a besoin d'algorithmes, que l'on parle de gestion de données,

de graphisme, de calcul scientifique, de jeux vidéo.

Heureusement grâce à l'inventivité des chercheurs,

on découvre régulièrement des algorithmes

de plus en plus rapides pour résoudre un problème donné.

Reprenons le problème du tri d'une liste de nombres,

la méthode que je vous ai présentée, qu'on peut appeler l'algorithme naïf,

vous sentez peut-être qu'elle n'est pas forcément hyper maligne,

on parcourt la liste pour trouver le plus petit élément,

puis ont la re-parcourt pour trouver le 2ème plus petit, puis à nouveau etc,

On est amené à refaire plusieurs fois quasiment la même chose.

Intuitivement on se dit qu'il doit y avoir moyen de gagner du temps

en exploitant mieux l'information.

Eh bien oui, c'est possible, on connaît aujourd'hui

plusieurs algorithmes de tri dont la complexité n'est pas proportionnelle à N²

mais à N fois logarithme de N : N x log (N)