P = NP : problème ou illusion ? (partie 2)

Dans la première partie nous avons calculé la complexité de l'addition scolaire, dans le cas d'une addition à N chiffres, on a vu que l'addition scolaire était un calcul à temps linéaire, c'est à dire que le temps de calcul est proportionnel à N.

Calculons maintenant la complexité de la multiplication scolaire à N chiffres. Pour cela, nous allons prendre comme unité de temps, l'opération AxB, où A et B sont des nombres à un seul chiffre, donc :

T(AxB) = 1

Si on note A(N) et B(N) des nombres à N chiffres, calculer T(A(N)xB(N)) revient à calculer combien de multiplications "unitaires" (chiffre à chiffre) il faut réaliser pour calculer A(N)xB(N) avec la méthode scolaire.

Pour N = 2, par exemple, avec A(2) = 12 et B(2) = 34

12 * 34 = 2*4 + 10*(4*1) + 10*( 3*2 + 10*(3*1) )

Comme nous sommes en base 10, l'opération X + 10*Y revient à accoler les chiffres X et Y, en écrivant le nombre "YX", cette opération ne sera pas comptabilisé dans le calcul de la ocmplexité, on a donc :

T(A(2)xB(2)) = 4

De manière générale, pour multiplier deux nombres à N chiffres, il faudra multiplier deux à deux chaque chiffre de l'un avec ceux de l'autre, on obtient donc :

T(A(N)xB(N)) = N²

On en déduit que la multiplication scolaire est un calcul à temps quadratique : Le temps de calcul nécéssaire dépend du carré du nombre de chiffres.

De la même manière, on peut calculer le temps de calcul de n'importe quelle opération ou algorithme.

Les calculs comme l'addition ou la multiplication sont dits à temps "polynomial", car le temps dépend d'une fonction polynomiale de N (le nombre de données), c'est à dire :

T(calcul polynomial) = somme (a(k)*N^k) pour k entier

On peut donc classer l'addition et la multiplication (et un grand nombre d'autres calculs) dans l'ensemble des calculs à temps polynomiaux, on appelle cet ensemble P. (le fameux P de P = NP)

Plus précisément, l'ensemble P est appellé "Ensemble des calculs déterministes à temps polynomial", c'est à dire l'ensemble des calculs qui ne font pas appel à des fonctions aléatoires (comme l'addition ou la multiplication)

On devine donc que l'ensemble NP est tout simplement "L'Ensemble des calculs non déterministes à temps polynomial" (et non comme on le croit parfois, "L'ensemble des calculs à temps non polynomial)

Voilà pour la base... Dans la prochaine partie, nous verrons un troisième ensemble et je tenterai de donner une explication concrète du problème P = NP.

A suivre...

Comment faire rire un ordinateur ?

QUand je n'ai rien à faire, j'aime me ballader sur le site de l'université de Cornell www.arxiv.org qui publie une nombre incroyable d'articles scientifiques dans tous les domaines.

L'autre jour, je suis tombé sur un vieil article (1994) écrit par un chercheur russe I.M. Suslov,, l'article était intitulé "Can a computer laugh ?" suivi d'une deuxième article "How to realize a sense of humour in computers ?"

J'ai d'abord pensé à un gros canular, mais après avoir lu quelques paragraphes, je me suis très vite rendu compte du sérieux de cet article et surtout de sa pertinence : il semble bien que l'humour ait une explication tout à fait rationnelle, l'humour serait de plus indispensable au développement de l'intelligence, y compris chez les ordinateurs !

Pour ceux qui sont intéressés, voici le lien vers ces différents articles : http://arxiv.org/find/all/1/all:+humour/0/1/0/all/0/1

Pour les plus fainéants - ou les moins anglophiles - je vais tenter de résumer l'idée de départ de Monsieur Suslov. (J'avoue que je n'ai pas eu le courage de lire l'article en entier, car la suite devient plus technique...)

Soit une phrase, composée de n mots que l'on notera A(1),A(2),...,A(n).

Chaque mot est associé à un tableau de m images (ou sens) que l'on notera B(n,1), ...,B(n,m).

On dira que le mot n de la phrase possède m(n) sens possibles, B(i,j) représente le j-ème sens du i-ème mot.

Comprendre une phrase "correctement" reviens à trouver la bonne "trajectoire", c'est à dire la suite k(n) telle que la suite B(n,k(n)) représente la suite d'images qui a le "plus de sens".

Lorsque nous essayons de comprendre une phrase, notre inconscient analyse différentes trajectoires possibles et détermine la trajectoire qui semble avoir le plus de sens.

Pour cela, notre cerveau procède par étape, Suslov nous suggère l'algorithme suivant :

1. Notre conscience lit le premier mot A(1)
2. Notre inconscient fait la liste des images B(1)
3. Notre conscience lit le mot suivant A(i)
4. Notre inconscient fait la liste des B(i) images de ce mot
5. Notre inconscient met en mémoire les combinaisons d'images entre B(i-1) et B(i) les plus probables (en réalité ce choix est fait en observant toutes les combinaisons précédentes)
   
6. La combinaison la plus probable est renvoyée à notre conscience
7. Retour à l'étape 3
   

L'étape cruciale dans ce processus est l'étape 5. C'est elle qui va permettre de choisir quel sens donner à tel ou tel mot.

Suslov interprète l'humour comme le dysfonctionnement qui arrive, lorsque l'esprit arrive dans une impasse au niveau du choix des images (le sens de la phrase nous apparaît alors comme absurde)

Plus précisément, on peut avoir sélectionné au i-ème mot l'image qui nous a semble la plus "sensée" et se rendre compte au i+1-ème mot qu'on ne peut pas choisir une image sensée en rapport avec les images précédemment choisies.

Dans ce cas, le rire permettrait de remettre à zéro le processus de compréhension et permettrait à l'esprit de revenir en arrière pour choisir une autre image du ou des mots précédents.

Je pense qu'il s'agit là d'une très bonne interprétation du rire. Cette approche a en plus le mérite de fournir un modèle simple de compréhension du langage.

Pour terminer, voici une petite blague pour illustrer ce principe :

Au restaurant, le garçon demande au client:
- Comment avez-vous trouvé le beefsteak?
- Tout à fait par hasard, en soulevant une frite!

Je vous laisse le soin d'analyser cette blague pour y déceler le mécanisme suggéré par Suslov.

Une dernière chose : j'ai écrit cet article car j'ai été très intéressé par l'idée de Monsieur Suslov, j'ai tenté ici de résumer une partie de son article telle que je l'ai compris, mais le raisonnement de ce chercheur est bien sûr plus profond et plus détaillé. Il identifie par exemple plusieurs types d'humours. J'ai décrit ici uniquement l'humour basé sur un double sens mais il y a bien d'autres variantes qui permettent de couvrir l'ensemble du "sens de l'humour".

Il semble également que Suslov étende son raisonnement à d'autres sentiments humains, mais je n'ai pas trouvé d'articles sur le sujet.

En attendant, riez bien, c'est important pour la santé !