Dans la deuxième partie , nous avons calculé la complexité de la multiplication scolaire à N chiffres : il s'agit d'un calcul à temps quadratique, nous avions vu que l'addition scolaire est un calcul à temps linéaire dans la première partie
Nous avions conclut que ces deux opérations appartiennent à l'ensemble P, qui représente l'ensemble des calculs déterministes à temps polynomial.
Dans la conjecture P = NP, l'ensemble NP représente les calculs non déterministes à temps polynomial. Mais avant de revenir sur cet ensemble plus en détail, il nous faut voir une dernière notion.
Avant, je dois préciser que certains passages peuvent contenir des erreurs pour deux raisons : d'une part, je ne suis pas un spécialiste de la théorie de la complexité et encore moins du problème P = NP. D'autre part, je présenterai à certains endroits mon point de vue, qui là encore peut contenir des erreurs ou même sembler simpliste aux spécialistes, vous voilà prévenus...
Les calculs à temps exponentiel
Imaginons que l'on souhaite connaître le nombre d'ancêtres A que nous avons, pour une génération N, par exemple :
A(1) = 2 (parents)
A(2) = 4 (grands parents)
A(3) = 8 (arrière grands parents)
...
A(N) = 2^N
Pour calculer A(N), il nous faut multiplier le résultat précédent A(N-1) par deux. En prenant comme opération unitaire la multiplication, on a donc un calcul à temps exponentiel, c'est à dire du type :
T(calcul exponentiel) = K^N
Où K est un nombre fixé (2 dans le cas du calcul des ancêtres) et N le nombre de données (dans notre exemple, le nombre de générations)
Un point fréquent dans les calculs à temps exponentiels est qu'ils sont récursifs : pour calculer A(N), on doit calculer A(N-1). Le résultat final n'est possible qu'en faisant tous les calculs
Mon point de vue : On peut se représenter le calcul à temps polynomial ou exponentiel comme une série de calculs à effectuer dans l'ordre : les calculs sont "branchés" en série, un peu comme des composants d'un circuit électrique. Tous les "circuits sont nécéssaires pour alimenter" le résultat. Les problèmes P ou E (voir plus bas) sont des "calculs en ET".
Nous pouvons maintenant définir l'ensemble E, comme étant l'ensemble des calculs à temps exponentiel. Mais quel rapport avec P = NP ? En quoi cela peut-il nous aider à définir l'ensemble NP ?
Calculs non déterministes à temps polynomial
Que signifie un calcul "non déterministe" ? En gros, que l'algorithme doit effectuer un certain nombre de calculs indépendants les uns des autres et qu'en fonction du "choix" qu'il fera, il pourra mettre moins de temps que nécéssaire, s'il avait dû tous les calculer, ou s'il les avait calculé dans un "ordre déterministe".
Pour cette raison, on dit souvent que les problèmes de la classe NP sont des problèmes de "décision".
On observe plusieurs propriétés importantes des problèmes de la classe NP :
- On peut calculer un problème NP avec un algorithme à temps exponentiel
- On peut vérifier le calcul d'un problème NP avec un algorithme à temps polynomial
On voit qu'en terme d'efficacité, les problèmes NP semblent se situer "entre" les problèmes P et E.
Autre point important : un problème P fait également partie de la classe NP. En termes ensembliste, on dira que l'ensemble P est inclus dans l'ensemble NP.
En mathématique, pour que deux ensembles (P et NP) soient égaux, il faut (et il suffit) qu'ils soient inclus l'un dans l'autre. Nous savons déjà que P est inclus dans NP. Toute la question de l'hypothèse P = NP est en fait de savoir si la réciproque est vraie : En fait la question n'est pas "P est-il égal à NP ?", mais plus précisément "NP est-il inclus dans P ?", autrement dit :
Pour chaque problème NP, existe-il un algorithme déterministe à temps polynomial capable de le résoudre ?
Généralement, les problèmes mathématiques commençant par "Pour chaque...existe t'il..." sont les plus difficiles à résoudre , car il faut démontrer l'existence d'un tel algorithme pour chaque problème, mais comment peut-on étudier en même temps TOUS les problèmes de type NP ? (Une blague de mathématicien serait de dire qu'on se trouve en face d'un problème à temps exponentiel...)
En fait, dans les années 60, un mathématicien américain du nom de Stephen Cook a découvert qu'on pouvait étudier tous les problèmes d'une classe, en étudiant uniquement "les plus difficiles" de cette classe : En résumé, "qui peut le plus, peut le moins". On appelle ces problèmes des problèmes complets.
Un problème NP-Complet : le problème du voyageur
Imaginons qu'un touriste veuille visiter N villes. Il souhaite effectuer le trajet le plus court possible, ou plus précisément, plus court qu'une certaine distance autorisée, qu'on appelera D, tout en passant par toutes les villes.
Pour résoudre ce calcul il faudrait à priori calculer toutes les combinaisons possibles de trajets, soit (N-1)! et sélectionner uniquement celles inférieures à D, par exemple :
Pour deux villes (N=2), il y a 1 seul trajet possible (T=1), donc une seule distance à calculer.
N = 3, T = 2
N = 4, T = 6
N = 5, T = 24
...
N = k, T = (k-1)! = (k-1) * (k-2) * ... * 1
On retrouve un peu le même schéma que pour le calcul des ancêtres (à temps exponentiel) : une série de multiplications, on peut donc à priori classer cet algorithme dans l'ensemble E.
Cependant, on peut vérifier si notre solution est correcte en beaucoup moins de temps : en faisant la somme des distances des trajets parcourus, on obtient une distance qui doit nécéssairement être inférieure à D. L'algorithme de vérification appartient à la classe P, car le temps de calcul est proportionnel au nombre de villes.
Ces deux éléments (calcul dans E et vérification dans P) suffisent à classer notre problème dans la catégorie NP.
En plus de cela (la démonstration m'est inconnue) ce problème est un problème "NP difficile", un problème NP-Complet. On peut reformuler la conjecture P = NP comme cela :
Si on parvient à trouver un algorithme déterministe à temps polynomial pour résoudre le problème du voyageur, alors on pourra le faire pour n'importe quel problème NP. La classe NP sera alors réduite à la classe P.
Le problème, c'est que personne n'a encore trouvé d'algorithme déterministe à temps polynomial pour aucun problème NP-Complet, donc pour l'instant, force est de constater que P n'est pas égal à NP !
Mon point de vue : P n'est pas égal à NP
Comme je l'ai dit dans la première partie de cet article, je ne suis pas un spécialiste, pourtant, en lisant divers articles sur le problème P = NP, dont l'excellent livre "les énigmes mathématiques du 3ème millénaire", je me suis mis à rêver d'une légitimité pour donner ma conception de ce problème... Voici mon idée, peut-être naïve ou stupide, mais c'est une idée...
Les problèmes NP consistent à effectuer plusieurs calculs, qui sont à priori pas tous nécéssaires, pour les résoudre : Dans le problème du voyageur, "si on a de la chance", on peut tomber sur le plus court trajet du premier coup, pas besoin de tous les calculer.
On peut se représenter les problèmes NP comme des calculs "en parallèle" (comme dans un circuit électrique), nous n'avons pas besoin "d'alimenter tous les circuits" pour arriver au résultat. Les problème NP sont des "calculs en OU".
J'ai dit plus haut que les problèmes P ou E sont des "calculs en ET". D'où la nécéssité d'effectuer TOUS les calculs pour arriver au résultat.
Les mathématiciens, car il existe de nombreuses méthodes (appelées heuristiques) pour trouver les meilleurs chemins, ont conjecturé qu'un problème NP ("calcul en OU") n'est pas aussi complexe qu'un problème E ("calcul en ET"). ET que donc, on pouvait réduire les problèmes NP à des problèmes P ("calculs en ET") beaucoup plus simples que le problème E ("calcul en ET") équivalent.
Mon idée est que pour un algorithme donné, il existe un seul "calcul en ET" et que celui-ci est nécéssairement le problème E d'origine. Je dirais donc que NP n'est pas inclus dans P mais qu'au contraire, NP est inclus dans E.
Je pense que le meilleur moyen de résoudre un problème NP est donc d'utiliser ces heuristiques ou des algorithmes non déterministes comme par exemple les algorithmes génétiques.
Car il est vrai qu'un problème NP se distingue d'un problème E, par la possibilité de "sauter" des étapes du calcul, mais je suis convaincu qu'il n'existe pas de "formule magique" pour effectuer ce choix, on peut simplement éviter de faire de "mauvais choix" (heuristiques), ou expérimenter des échantillons prometteurs de choix (algo génétique).
J'ai bien conscience qu'il s'agit d'un avis tranché, sans aucun vrai argument scientifique ou mathématique. J'essayerai d'étayer cette idée plus tard avec, si je peux, des arguments plus rigoureux ou à défaut, par d'autres images peut-être plus convaincantes.
Une dernière précision sur P = NP : on peut se poser la question de savoir si cette conjecture est démontrable (ou réfutable). Autrement dit, il y a trois réponses possibles à la question P = NP ?
1- Vrai
2- Faux
3- Indémontrable
J'ai dis que je pensais que la réponse était Faux, mais je dois avouer que la troisième solution est tentante : Cela pourrait signifier soit une limite dans les outils mathématiques à notre portée (3A), soit que la question n'a pas de sens dans l'absolu (3B).
En résumé, je pencherais pour la solution 2 ou - dans une moindre mesure - la solution 3B.
Et vous, qu'en pensez-vous ? Quelle solution vous semble la plus plausible ?
PS : Si j'ai commis des erreurs dans cet article, je vous prie de m'en excuser, je n'aime pas trop me documenter pour écrire, mon but n'était pas de faire une "leçon" sur la théorie de la complexité. N'hésitez pas à apporter des corrections si nécéssaire.
Affichage des articles dont le libellé est informatique. Afficher tous les articles
Affichage des articles dont le libellé est informatique. Afficher tous les articles
lundi 11 février 2008
vendredi 25 janvier 2008
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.
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...
dimanche 13 janvier 2008
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 :
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é !
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 :
- Notre conscience lit le premier mot A(1)
- Notre inconscient fait la liste des images B(1)
- Notre conscience lit le mot suivant A(i)
- Notre inconscient fait la liste des B(i) images de ce mot
- 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)
- La combinaison la plus probable est renvoyée à notre conscience
- Retour à l'étape 3
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é !
vendredi 7 décembre 2007
P = NP : problème ou illusion ?
D'après le livre "Les énigmes mathématiques du 3ème millénaire" (Keith Devlin), le problème P = NP serait, parmi les sept, le problème le plus accessible au commun des mortels, voire, pourquoi pas, le seul problème qu'un non spécialiste pourrait éventuellement résoudre.
Etant moi-même un éminent non-spécialiste, voici ma conception de ce problème et, si on peut dire, la réponse que je pense pouvoir y apporter. Mais avant, je vais tenter de planter le décor, que signifie P = NP ?
Théorie de la complexité
La théorie de la complexité est une méthode qui permet, quel que soit le problème que l'on ait à résoudre, de calculer le temps qu'il faudra pour trouver la ou les réponses.
Plus précisément, on ne calcule pas le temps (en secondes), car cela dépend bien-sûr de la vitesse du calculateur (ordinateur ou humain), mais plutôt le nombre d'opérations simples nécéssaires pour effectuer un calcul.
Qu'est-ce qu'une opération "simple" : en fait, cela n'a pas d'importance, on pourrait prendre n'importe quelle opération comme étant "l'unité". Prenons par exemple une des opérations les plus simples qui existe : l'addition entre deux chiffres décimaux. (nombres compris entre 0 et 9)
Soient A et B deux chiffres compris entre 0 et 9, le calcul de A+B, sans retenue, nécéssite une seule opération, donc le temps T de ce problème est de 1 : T(A+B) = 1
Si l'on souhaite maintenant calculer la somme avec la retenue, il nous faut une opération supplémentaire : T(A+B+R) = 2
Combien de temps faut-il pour calculer la somme de deux nombres décimaux composés chacuns de N chiffres ?
Soient A et B deux nombres décimaux, on note A(n) le n-ième chiffre de A et B(n) celui de B (on prendra n entre 1 et n pour simplifier les formules).
Additionner A et B revient à additionner leurs chiffres respectifs, en ajoutant la retenue précédente, on notera R(n), la retenue de l'opération A(n)+B(n)+R(n-1)
A+B = (A(1)+B(1))*10^0 + (R(1)+A(2)+B(2))*10^1 + ... + (R(n-1)+A(n)+B(n))*10^(n-1) + R(n)*10^n
Autrement dit :
A+B = Somme ((A(k+1)+B(k+1)+R(k))*10^k), pour k allant de 0 à n, avec R(0)=A(n+1)=B(n+1)=0
Comme nous sommes en base 10, l'opération 10^k revient simplement à écrire les chiffres à différents emplacements (unités, dizaines, centaines...), cette partie n'entre donc pas dans le calcul de compexité de A+B.
Pour calculer T(An+Bn), il suffit de compter le nombre d'additions entre deux chiffres, dans la formule ci-dessus : chaque étape comporte 2 additions et il y a (n+1) étapes. La première et la dernière étape, ne comptent qu'une opération, on pourra donc enlever 2 au résultat final, en résumé :
T(An+Bn) = 2*(n+1) - 2 = 2*n
Cette formule signifie que le temps de calcul de l'addition de deux nombres composés de n chiffres est proportionnel à 2 fois le nombre de chiffres.
On dira que l'addition est un calcul à temps (ou à complexité) linéaire : le temps nécéssaire au calcul est proportionnel à la quantité de données en entrée, à un facteur k près. Pour l'addition de deux nombres, nous avons k = 2.
Cet indice k, représente tout simplement le nombre d'opérations nécéssaires à ajouter, à chaque fois que l'on rajoutera une donnée en entrée dans notre calcul (ici, un chiffre de plus à A et B).
Nous allons maintenant calculer la complexité de la multiplication entre deux nombres A et B composés chacuns de n chiffres décimaux : T(An*Bn)
Calculons d'abord la complexité de l'opération T(A*B), soit le cas n = 1 :
A * B = A + A + ... + A
Nous avons ici (B-1) additions, on aurait tout aussi bien pu dire (A-1). D'où :
T(A*B) = k * T(A+B), où k est une valeur qui dépend des données A et B.
Etant moi-même un éminent non-spécialiste, voici ma conception de ce problème et, si on peut dire, la réponse que je pense pouvoir y apporter. Mais avant, je vais tenter de planter le décor, que signifie P = NP ?
Théorie de la complexité
La théorie de la complexité est une méthode qui permet, quel que soit le problème que l'on ait à résoudre, de calculer le temps qu'il faudra pour trouver la ou les réponses.
Plus précisément, on ne calcule pas le temps (en secondes), car cela dépend bien-sûr de la vitesse du calculateur (ordinateur ou humain), mais plutôt le nombre d'opérations simples nécéssaires pour effectuer un calcul.
Qu'est-ce qu'une opération "simple" : en fait, cela n'a pas d'importance, on pourrait prendre n'importe quelle opération comme étant "l'unité". Prenons par exemple une des opérations les plus simples qui existe : l'addition entre deux chiffres décimaux. (nombres compris entre 0 et 9)
Soient A et B deux chiffres compris entre 0 et 9, le calcul de A+B, sans retenue, nécéssite une seule opération, donc le temps T de ce problème est de 1 : T(A+B) = 1
Si l'on souhaite maintenant calculer la somme avec la retenue, il nous faut une opération supplémentaire : T(A+B+R) = 2
Combien de temps faut-il pour calculer la somme de deux nombres décimaux composés chacuns de N chiffres ?
Soient A et B deux nombres décimaux, on note A(n) le n-ième chiffre de A et B(n) celui de B (on prendra n entre 1 et n pour simplifier les formules).
Additionner A et B revient à additionner leurs chiffres respectifs, en ajoutant la retenue précédente, on notera R(n), la retenue de l'opération A(n)+B(n)+R(n-1)
A+B = (A(1)+B(1))*10^0 + (R(1)+A(2)+B(2))*10^1 + ... + (R(n-1)+A(n)+B(n))*10^(n-1) + R(n)*10^n
Autrement dit :
A+B = Somme ((A(k+1)+B(k+1)+R(k))*10^k), pour k allant de 0 à n, avec R(0)=A(n+1)=B(n+1)=0
Comme nous sommes en base 10, l'opération 10^k revient simplement à écrire les chiffres à différents emplacements (unités, dizaines, centaines...), cette partie n'entre donc pas dans le calcul de compexité de A+B.
Pour calculer T(An+Bn), il suffit de compter le nombre d'additions entre deux chiffres, dans la formule ci-dessus : chaque étape comporte 2 additions et il y a (n+1) étapes. La première et la dernière étape, ne comptent qu'une opération, on pourra donc enlever 2 au résultat final, en résumé :
T(An+Bn) = 2*(n+1) - 2 = 2*n
Cette formule signifie que le temps de calcul de l'addition de deux nombres composés de n chiffres est proportionnel à 2 fois le nombre de chiffres.
On dira que l'addition est un calcul à temps (ou à complexité) linéaire : le temps nécéssaire au calcul est proportionnel à la quantité de données en entrée, à un facteur k près. Pour l'addition de deux nombres, nous avons k = 2.
Cet indice k, représente tout simplement le nombre d'opérations nécéssaires à ajouter, à chaque fois que l'on rajoutera une donnée en entrée dans notre calcul (ici, un chiffre de plus à A et B).
Nous allons maintenant calculer la complexité de la multiplication entre deux nombres A et B composés chacuns de n chiffres décimaux : T(An*Bn)
Calculons d'abord la complexité de l'opération T(A*B), soit le cas n = 1 :
A * B = A + A + ... + A
Nous avons ici (B-1) additions, on aurait tout aussi bien pu dire (A-1). D'où :
T(A*B) = k * T(A+B), où k est une valeur qui dépend des données A et B.
A suivre ...
mercredi 28 novembre 2007
Tout est dans le NON !
Aujourd'hui, j'ai décidé de vous présenter le pouvoir du NON. Pour être plus précis, je vais tenter d'expliquer comment créer l'algèbre de Boole, à partir du chiffre 0 et du seul opérateur logique NON.
Cette propriété connue est utilisée chaque jour pour créer les circuits logiques des puces de nos ordinateurs. Mais au delà de çà, ce principe me fascine car il permet de penser que "tout existe à partir du zéro et du NON".
Définissons tout d'abord quelques notions.
Opérateur : loi de transformation d'un ou plusieurs éléments d'un ensemble, vers un ou plusieurs éléments d'un autre ensemble (éventuellement le même).
Soit O un opérateur quelconque, on écrira :
O : E^a -> F^b
Ce qui signifie que l'opérateur O prend en entrée a éléments de l'ensemble E et génère en sortie b éléments de l'ensemble F.
Construire l'algèbre de Boole revient à exprimer tous les opérateurs logiques unaires et binaires, à partir de l'opérateur NON.
A partir de la définition d'un opérateur, on se place dans le cas suivant :
E = F = {0, 1}
b = 1
a = 1 (pour les opérateurs unaires)
a = 2 (pour les opérateurs binaires)
Autrement dit : les opérateurs logiques
unaires sont les transformations d'un élément 0 ou 1 en un autre élément valant 0 ou 1. Les opérateurs logiques binaires sont les transformations d'un couple d'éléments (0,0) , (0,1) , (1,0) ou (1,1) en un seul élément valant 0 ou 1.
Tables de vérité
La table de vérité d'un opérateur est le tableau qui donne pour chaque élément en entrée, l'élément correspondant en sortie. Voici quelques exemples :
Table de vérité de l'opérateur unaire identité :
Table de vérité de l'opérateur unaire négation :
Pour les opérateurs binaires, on peut représenter la table de vérité sous la forme d'un tableau à deux dimensions :
Table de vérité de l'opérateur binaire OU :
Table de vérité de l'opérateur binaire ET :
Les nombres en gras représentent les éléments en entrée, les autres les éléments en sortie. Pour connaître le résultat, il suffit de choisir une ligne et une colonne et de lire le résultat. Par exemple : 1 ET 1 = 1
Ici l'ordre des éléments en entrée n'a pas d'importance, mais lorsque ce sera le cas, on lira en premier la ligne, puis la colonne.
Codage des opérateurs logiques
Comment connaître tous les opérateurs logiques ? Pour cela, nous allons utiliser une méthode de codage qui va nous permettre de les compter et de n'en oublier aucun. Pour coder un opérateur, nous allons d'abord réécrire sa table de vérité de manière "compacte".
Par exemple, pour les opérateurs unaires, on constate que la première colonne est inutile : le 0 et le 1 seront toujours à la même place. On va donc accoler les chiffres restants, c'est à dire :
Codage de l'opérateur unaire identité : 10
Codage de l'opérateur unaire négation : 01
Vous constaterez qu'on a inversé les nombres, afin que le résultat de l'élément 0 soit situé à droite et celui de l'élément 1 à gauche. Ce choix est plus logique, car on lit les nombres de droite à gauche.
On peut en déduire qu'il existe seulement 4 opérateurs logiques unaires :
De même, le deuxième opérateur (le fameux NON) est la négation du troisième (l'identité).
Donc seul la moitié de ces opérateurs semble utile (0 et NON) puisque les deux autres peuvent s'obtenir en rajoutant l'opérateur NON.
Nous pouvons donc exprimer tous les opérateurs unaires en utilisant le 0 et le NON (que nous noterons "!") :
On note A l'élément de départ, appliqué à chaque opérateur unaire (souvenez-vous que A peut prendre la valeur 0 ou 1) :
Nous allons maintenant appliquer cette méthode pour d'abord coder, puis pour exprimer tous les opérateurs logiques binaires en fonction de l'opérateur NON.
En reprenant les tables de vérité, on va supprimer les éléments en entrée, comme on l'a fait pour les opérateurs unaires, puis on va accoler les 4 éléments en sortie. De maniuère générale, la table suivante :
Deviendra le code : DCBA
Par exemple, les codes des opérateurs OU et ET sont respectivement 1110 et 1000.
A nouveau, on voit qu'il ne peut y avoir que 16 opérateurs logiques binaires distincts (il y a quatres chiffres binaires, soit 2^4 = 16 possibilités).
Comme nous l'avons fait pour les opérateurs unaires, il nous suffira de calculer les 8 premiers opérateurs, les 8 suivants étant symétriques (à l'opérateur NON près)
Avant de pouvoir coder les opérateurs, il nous faut cependant étendre le domaine de validité de l'opérateur logique unaire NON aux opérateurs logiques binaires, en mathématiques, on noterait :
NON : E -> F
NON(A) = !A
NON ET : E^2 -> F
NON ET(A,B) = A!B = NON(A) ET NON(B)
Je dois reconnaître ici que j'ai un peu triché en annonçant que l'on n'aurait besoin que du NON et du 0. En effet, pour étendre l'opérateur NON aux opérateurs binaires, nous devons le combiner avec un opérateur binaire quelconque , ici on a choisi ET.
Mais ce qui est important, c'est que l'on aurait pu prendre n'importe quel opérateur non trivial (comme 0 ou 1) : l'opérateur ET est donc uniquement là pour faire la figuration, bien qu'il nous permette d'accéder au monde merveilleux des opérateurs binaires.
Donc muni de notre opérateur étendu "!" (à la fois unaire et binaire), tentons d'exprimer les opérateurs binaires logiques en utilisant toujours uniquement les symboles 0 et "!" avec un peu de calcul, on obtient :
Remarque : Pour exprimer une opération quelconque en fonction de A, B 0 et "!", il suffit de la décomposer en des opérateurs dont on connait le code, d'effectuer l'opération sur le code des opérateurs, puis de lire l'expression correspndante dans le tableau ci-dessus, par exemple :
A correspond à l'opérateur 1100, B, à l'opérateur 1010, donc l'expression A OU B correspond à l'opérateur (1100 OU 1010) = 1110, soit l'expression !A!!B
On peut ensuite réaliser le circuit de portes logiques en utilisant uniquement la porte NON ET : c'est la dernière étape dans la conception d'un circuit électronique.
Ci dessous, un circuit logique simple qui réalise l'opération OU (opérateur 1110 dans notre liste), avec les entrées E1 et E2, la sortie S et trois portes logiques NON ET. Les entrées sont d'abord reliées chacune à une porte NON, puis les sorties respectives sont reliées entre elles à une même porte NON ET, qui donne le résultat final S.
En lisant ce schéma, on peut tout à fait vérifier la formule 1110(E1,E2) = !E1!!E2 ou si vous préférez 1110(E1,E2) = (!E1)!(!E2).
Cliquez-ici pour voir les circuits d'autres opérateurs logiques, réalisés avec la porte NON ET (également appelé NAND).
Enfin, on peut bien sûr étendre cette méthode pour manipuler autant d'entrées qu'on le souhaite et ainsi réaliser des circuits plus élaborés (sommateurs, compteurs, multiplexeurs...) comme on en trouve au coeur des puces électroniques...
Voilà, cet article est terminé. J'espère que cela vous aura intéressé. J'aimerais avoir votre avis ou vos réflexions sur ce sujet ou sur l'algèbre de Boole en général... Que pensez-vous également de cette méthode de codage (on pourrait presque parler de classification) des opérateurs logiques ? Que changeriez-vous dans le codage pour obtenir une classification des opérateurs plus élégante ?
Pour terminer sur une note plus spirituelle, je pense sincèrement que derrière l'opérateur NON se profile toute la puissance génératrice du zéro. Une sorte de preuve que tout ce qui existe peut-être généré à partir de ce qui n'existe pas (à partir de rien en fait)... mais il s'agit bien sûr d'un sentiment personnel.
Pour plus d'informations sur l'opérateur NON et sur l'histoire du zéro, je vous recommande le livre "A propos de rien, une histoire du zéro" (Robert Kaplan).
A très bientôt.
Cette propriété connue est utilisée chaque jour pour créer les circuits logiques des puces de nos ordinateurs. Mais au delà de çà, ce principe me fascine car il permet de penser que "tout existe à partir du zéro et du NON".
Définissons tout d'abord quelques notions.
Opérateur : loi de transformation d'un ou plusieurs éléments d'un ensemble, vers un ou plusieurs éléments d'un autre ensemble (éventuellement le même).
Soit O un opérateur quelconque, on écrira :
O : E^a -> F^b
Ce qui signifie que l'opérateur O prend en entrée a éléments de l'ensemble E et génère en sortie b éléments de l'ensemble F.
Construire l'algèbre de Boole revient à exprimer tous les opérateurs logiques unaires et binaires, à partir de l'opérateur NON.
A partir de la définition d'un opérateur, on se place dans le cas suivant :
E = F = {0, 1}
b = 1
a = 1 (pour les opérateurs unaires)
a = 2 (pour les opérateurs binaires)
Autrement dit : les opérateurs logiques
unaires sont les transformations d'un élément 0 ou 1 en un autre élément valant 0 ou 1. Les opérateurs logiques binaires sont les transformations d'un couple d'éléments (0,0) , (0,1) , (1,0) ou (1,1) en un seul élément valant 0 ou 1.
Tables de vérité
La table de vérité d'un opérateur est le tableau qui donne pour chaque élément en entrée, l'élément correspondant en sortie. Voici quelques exemples :
Table de vérité de l'opérateur unaire identité :
| 0 | 0 |
|---|---|
| 1 | 1 |
Table de vérité de l'opérateur unaire négation :
| 0 | 1 |
|---|---|
| 1 | 0 |
Pour les opérateurs binaires, on peut représenter la table de vérité sous la forme d'un tableau à deux dimensions :
Table de vérité de l'opérateur binaire OU :
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 1 |
Table de vérité de l'opérateur binaire ET :
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Les nombres en gras représentent les éléments en entrée, les autres les éléments en sortie. Pour connaître le résultat, il suffit de choisir une ligne et une colonne et de lire le résultat. Par exemple : 1 ET 1 = 1
Ici l'ordre des éléments en entrée n'a pas d'importance, mais lorsque ce sera le cas, on lira en premier la ligne, puis la colonne.
Codage des opérateurs logiques
Comment connaître tous les opérateurs logiques ? Pour cela, nous allons utiliser une méthode de codage qui va nous permettre de les compter et de n'en oublier aucun. Pour coder un opérateur, nous allons d'abord réécrire sa table de vérité de manière "compacte".
Par exemple, pour les opérateurs unaires, on constate que la première colonne est inutile : le 0 et le 1 seront toujours à la même place. On va donc accoler les chiffres restants, c'est à dire :
Codage de l'opérateur unaire identité : 10
Codage de l'opérateur unaire négation : 01
Vous constaterez qu'on a inversé les nombres, afin que le résultat de l'élément 0 soit situé à droite et celui de l'élément 1 à gauche. Ce choix est plus logique, car on lit les nombres de droite à gauche.
On peut en déduire qu'il existe seulement 4 opérateurs logiques unaires :
- 00 : L'opérateur zéro
- 01 : L'opérateur négation
- 10 : L'opérateur identité
- 11 : l'opérateur un
De même, le deuxième opérateur (le fameux NON) est la négation du troisième (l'identité).
Donc seul la moitié de ces opérateurs semble utile (0 et NON) puisque les deux autres peuvent s'obtenir en rajoutant l'opérateur NON.
Nous pouvons donc exprimer tous les opérateurs unaires en utilisant le 0 et le NON (que nous noterons "!") :
On note A l'élément de départ, appliqué à chaque opérateur unaire (souvenez-vous que A peut prendre la valeur 0 ou 1) :
- 00(A) = 0
- 01(A) = !A
- 10(A) = A
- 11(A) = !0 (non, je n'utiliserai pas le 1 !)
Nous allons maintenant appliquer cette méthode pour d'abord coder, puis pour exprimer tous les opérateurs logiques binaires en fonction de l'opérateur NON.
En reprenant les tables de vérité, on va supprimer les éléments en entrée, comme on l'a fait pour les opérateurs unaires, puis on va accoler les 4 éléments en sortie. De maniuère générale, la table suivante :
| 0 | 1 | |
|---|---|---|
| 0 | A | B |
| 1 | C | D |
Deviendra le code : DCBA
Par exemple, les codes des opérateurs OU et ET sont respectivement 1110 et 1000.
A nouveau, on voit qu'il ne peut y avoir que 16 opérateurs logiques binaires distincts (il y a quatres chiffres binaires, soit 2^4 = 16 possibilités).
Comme nous l'avons fait pour les opérateurs unaires, il nous suffira de calculer les 8 premiers opérateurs, les 8 suivants étant symétriques (à l'opérateur NON près)
Avant de pouvoir coder les opérateurs, il nous faut cependant étendre le domaine de validité de l'opérateur logique unaire NON aux opérateurs logiques binaires, en mathématiques, on noterait :
NON : E -> F
NON(A) = !A
NON ET : E^2 -> F
NON ET(A,B) = A!B = NON(A) ET NON(B)
Je dois reconnaître ici que j'ai un peu triché en annonçant que l'on n'aurait besoin que du NON et du 0. En effet, pour étendre l'opérateur NON aux opérateurs binaires, nous devons le combiner avec un opérateur binaire quelconque , ici on a choisi ET.
Mais ce qui est important, c'est que l'on aurait pu prendre n'importe quel opérateur non trivial (comme 0 ou 1) : l'opérateur ET est donc uniquement là pour faire la figuration, bien qu'il nous permette d'accéder au monde merveilleux des opérateurs binaires.
Donc muni de notre opérateur étendu "!" (à la fois unaire et binaire), tentons d'exprimer les opérateurs binaires logiques en utilisant toujours uniquement les symboles 0 et "!" avec un peu de calcul, on obtient :
- 0000(A,B) = 0
- 0001(A,B) = !(!A!!B)
- 0010(A,B) = !(!A!B)
- 0011(A,B) = !A
- 0100(A,B) = !(A!!B)
- 0101(A,B) = !B
- 0110(A,B) = (!A!B)!(A!!B)
- 0111(A,B) = A!B
- 1000(A,B) = !(A!B)
- 1001(A,B) = (A!B)!(!A!!B)
- 1010(A,B) = B
- 1011(A,B) = A!!B
- 1100(A,B) = A
- 1101(A,B) = !A!B
- 1110(A,B) = !A!!B
- 1111(A,B) = !0 (on n'a toujours pas besoin du 1...)
Remarque : Pour exprimer une opération quelconque en fonction de A, B 0 et "!", il suffit de la décomposer en des opérateurs dont on connait le code, d'effectuer l'opération sur le code des opérateurs, puis de lire l'expression correspndante dans le tableau ci-dessus, par exemple :
A correspond à l'opérateur 1100, B, à l'opérateur 1010, donc l'expression A OU B correspond à l'opérateur (1100 OU 1010) = 1110, soit l'expression !A!!B
On peut ensuite réaliser le circuit de portes logiques en utilisant uniquement la porte NON ET : c'est la dernière étape dans la conception d'un circuit électronique.
Ci dessous, un circuit logique simple qui réalise l'opération OU (opérateur 1110 dans notre liste), avec les entrées E1 et E2, la sortie S et trois portes logiques NON ET. Les entrées sont d'abord reliées chacune à une porte NON, puis les sorties respectives sont reliées entre elles à une même porte NON ET, qui donne le résultat final S.
En lisant ce schéma, on peut tout à fait vérifier la formule 1110(E1,E2) = !E1!!E2 ou si vous préférez 1110(E1,E2) = (!E1)!(!E2).
Cliquez-ici pour voir les circuits d'autres opérateurs logiques, réalisés avec la porte NON ET (également appelé NAND).
Enfin, on peut bien sûr étendre cette méthode pour manipuler autant d'entrées qu'on le souhaite et ainsi réaliser des circuits plus élaborés (sommateurs, compteurs, multiplexeurs...) comme on en trouve au coeur des puces électroniques...
Voilà, cet article est terminé. J'espère que cela vous aura intéressé. J'aimerais avoir votre avis ou vos réflexions sur ce sujet ou sur l'algèbre de Boole en général... Que pensez-vous également de cette méthode de codage (on pourrait presque parler de classification) des opérateurs logiques ? Que changeriez-vous dans le codage pour obtenir une classification des opérateurs plus élégante ?
Pour terminer sur une note plus spirituelle, je pense sincèrement que derrière l'opérateur NON se profile toute la puissance génératrice du zéro. Une sorte de preuve que tout ce qui existe peut-être généré à partir de ce qui n'existe pas (à partir de rien en fait)... mais il s'agit bien sûr d'un sentiment personnel.
Pour plus d'informations sur l'opérateur NON et sur l'histoire du zéro, je vous recommande le livre "A propos de rien, une histoire du zéro" (Robert Kaplan).
A très bientôt.
Inscription à :
Articles (Atom)