Utilisateur:TomT0m/intro à la Complexité et à P=NP

Complexité des algorithmes, classes P et NP

Un algorithme est une méthode de résolution systématique d'un problème donné. Il existe souvent plusieurs méthodes pour résoudre un problème donné. La théorie de la complexité des algorithme est un outil mathématique pour comparer ces méthodes entre elles, savoir lesquelles sont efficaces, et mesurer leur efficacité, et lesquelles ne le sont pas, et peut nous aider à choisir une méthode pour résoudre un problème donné.

Nous verrons ensuite comment, en plus de comparer les méthodes, cette théorie tente d'établir la difficulté des problèmes eux mêmes, de les comparer, et nous verrons comment on peut diviser les problèmes en plusieurs grandes familles de difficulté, dont deux qui nous intéressent particulièrement dans le cadre de cet article, la classe $P$ et la classe $NP$.

Dans la suite de cette section, nous ne chercherons pas à définir formellement et précisément ces notions mais plutôt d'essayer d'en donner au lecteur une intuition, d'abord la notion d'algorithme au travers d'exemple de méthodes et de complexité en essayant de comparer l'efficacité de ses méthodes.

les algorithmes et leur complexité.

On prendra pour exemple de problème illustratif la recherche d'un mot dans un dictionnaire alphabétique, en considérant qu'il n'y a qu'un seul mot par page. Nous allons présenter deux méthodes de résolutions de ce problème, puis nous allons les comparer entre elles.

Méthodes de résolutions

Une première méthode systématique pourrait être de commencer par regarder une par une toutes les pages du dictionnaire, dans l'ordre des pages, pour voir si le mot s'y trouve.

Une meilleure méthode, communément employée est la recherche dichotomique, qui utilise le fait que les mots du dictionnaire sont triés par ordre alphabétique. On pourrait décrire informellement cette méthode de la manière suivante :

1. on mémorise une page inférieure et une page supérieure, en sachant que le mot ne sera jamais sur une page précédent la page inférieure et jamais après la page supérieure. Au début on choisit respectivement la première et la dernière page du dictionnaire;
2. on ouvre le dictionnaire au milieu de la page inférieure et la page supérieure;
3. on regarde si notre mot doit être par ordre alphabétique avant, après, ou si il est sur la page.
   1. si le mot est celui de la page, on a terminé, et on peut répondre "oui" à notre question;
   2. si le mot n'est pas sur la page mais qu'on ne peut plus couper, on a terminé, et on peut réponde "non";
   3. si le mot n'est pas sur la page, mais il est alphabétiquement avant : on change notre page supérieure pour la page de coupure et on recommence à l'étape 2;
   4. si le mot n'est pas sur la page, mais il est alphabétiquement après : on change notre page inférieure la page de coupure et on recommence à l'étape 2;

Ces deux méthodes sont utilisables pour être exécutées automatiquement par une machine de calcul suffisamment puissante, comme par exemple la machine de Turing, machine abstraite, ou par n'importe quel ordinateur de salon. On parle dans ce cas algorithme de résolution du problème de la recherche dans un dictionnaire.

Comparaison, laquelle est meilleure ?

Nous allons maintenant essayer de comparer ces méthodes. Dans ce but nous allons compter le nombre de page du dictionnaire que nous devront regarder pour arriver au résultat. Ce nombre de page n'est pas fixe et varie en fonction de la taille du dictionnaire et du mot recherché.

1. Pour la première méthode, dans le pire cas le mot n'est pas dans le dictionnaire, et nous devront regarder une à une toutes les pages du dictionnaires avant de conclure que le mot n'y est pas.
2. Pour la deuxième méthode, nous n'avons pas à parcourir toutes les pages. Chaque coupure nous permet de déterminer que notre mot n'est pas dans la moitié des pages que nous considérions encore, ce qui signifie que nous ne les observeront pas.

Le tableau suivant nous permettra de comparer les deux méthodes du point de vue du nombre de page que l'on doit regarder avant que la méthode ne termine:

Nombre d'étapes avant la fin de chaque méthodes

Taille du dictionnaire	Nombre de pages regardées (méthode 1)	Nombre de pages regardées (méthode 2)
1	1	1
2	2	2
3	3	2
4	4	2
5	5	3
6	6	3
…	…	…
32	32	5
…	…	…
256	256	8
…	…	…
$n$	$n$	$log_{2}(n)$

La méthode 2 est clairement sur ce tableau meilleure que la première. Pour la première le nombre de page regardé est proportionnel au nombre de page du dictionnaire, elle fait partie des méthode de complexité linéaire. Pour la deuxième le nombre de page regardé est proportionnel au logarithme de la taille du dictionnaire, elle fait partie des méthodes de complexité logarithmique. Un logarithme grandit de manière bien moins rapide qu'une fonction linéaire, la méthode 2 est donc plus efficace.

Complexité et classe de complexité de problèmes

Intro : la complexité d'un problème est la complexité de la meilleure méthode de résolution, la méthode dichotomique pour l'exemple.

Classes différentes : log et pb linéaire, classe P, exponentielles (dur à priori)

Classe P

Exemple du plus court chemin, complexité en n*n

Classe NP

Exemple du voyageur de commerce (?), tableau pour comparer n^2 à 2^n

Relation P=NP

Relation classe P=NP : rendre explicite le "facile à vérifier", trouver problème approprié (SAT est bien pour ça mais pénible à expliquer)