03 juin 2007
Zéro divisé par zéro égalent ?...
Combien ça fait, zéro divisé par zéro ?
En voilà une bonne question qui revient souvent après la remarque "Jj, tu fais bien des études de maths ?..." pendant les dîners familiaux. (Déjà deux fois en une semaine)
Menons donc l'enquête ! Pour celà, rien de plus simple, on prend une calculette qui traîne, par exemple, une TI-30Xa, simple calculette de collégien des années 2000 et on tape "0/0"... "Error"... Testons alors une calculatrice plus évoluée, style lycéen des années 2002, une TI-82. "0/0"... "ERR: DIVIDE BY 0"...Tout porte à croire qu'il ne faut surtout pas diviser par 0...
Quelques règles élémentaires nous donne quelques informations sur "0 divisé par 0" :
* Zéro divisé par n'importe quel nombre, ça donne zéro. (Mais il faudrait que cet autre nombre ne soit pas 0)
* Quand on divise un nombre par lui-même, on obtient un. (Tant que ce nombre n'est pas zéro)
* Quand on divise un nombre par quelque chose de très proche de zéro, on trouve quelque chose de très grand. (Histoire de ne pas encore rentrer dans les histoires de calcul infinitésimal)
Donc, les trois ensembles, ça devrait donner quelque chose comme 0/0=0 ou 1 ou autre chose.
On est pas plus avancés...
Plutôt que de voir 0 comme le néant, le vide absolu, voyons plutôt 0 comme un nombre extrêmement petit, tellement petit qu'on ne le voit pas. On va l'appeler x.
Dans ces cas là, puisque x≠0, on aura toujours x/x=1 (Ce qui donnerait 0/0=1)
Mais si x est proche de 0, x² sera encore plus proche de zéro...
Et le problème, c'est que x²/x=x (Et en conséquence, on trouverait 0/0=0)
Inversement, x/x²=1/x (Et en conséquence, on a 0/0=+∞)
Et je ne parle pas du cas où l'un des zéro est 42 fois plus petit que l'autre, bien que ça plairait à Adams.
En fait, pour répondre à la question "combien font zéro divisé par zéro" avec des considération analytiques, il faudrait savoir quel est le plus petit des deux zéros, ce qui, en soit, a autant de sens que la question "combien font zéro divisé par zéro" (Tant que la fonction f(x,y)=x/y ne sera pas continue au point (0,0)).
La grande hantise du lycéen lors d'un calcul de limite reste toujours le stress de la forme indéterminée 0/0. Surtout avec des résultats stupides de ce genre :
Bref :
- Ca fait combien, zéro divisé par zéro ?
- Ca fait zéro puissance zéro...
27 mai 2007
J'aimerais tant revoir Syracuse
"Prenez un entier supérieur à 1.
S'il est pair, divisez le par 2.
S'il est impair, multipliez-le par 3 et ajoutez 1.
Réitérez ensuite les deux précédentes étapes"
Ce qui est surprenant dans cette histoire, c'est que la suite obtenue tombera toujours sur 1, peut importe l'entier choisit au départ.
Et ce qui est encore plus surprenant, c'est que personne ne sait pourquoi !
Ce problème est couramment appelé Conjecture de Syracuse. (mais aussi problème de Syracuse, algorithme de Hasse, problème de Ulam, problème de Kakutani, conjecture de Collatz, conjecture du 3n+1 ou plus poétiquement la suite de grêlons)
On a encore beaucoup de mal à en décider la paternité, les tests ADN n'ont pas encore été faits...
En fait, tout commence avec Lothar Collatz, dans les années 1930, qui s'amuse à faire des transformations itératives d'entiers et regarde ce que ça donne.
Dans les années 50, Helmut Hasse se rend à l'Université de Syracuse (près de New York, pas du tout en Sicile) et remporte un grand succès en diffusant son problème.
Pendant la seconde guerre mondiale, le polonais Stanislas Ulam reprend le problème à son nom, et, dix ans plus tard, S. Kakutani reprend le problème pour le diffuser à son tour sous son nom.
Et, dans l'histoire, personne n'a réussit à le résoudre.
A l'époque de la guerre froide, on parlait de ce problème comme d'un complot soviétique pour ralentir les recherches aux États-Unis...
Dans ces années là, un mathématicien hongrois, Paul Erdõs, proposait 500$ à qui arriverait à résoudre le problème (ça vaut pas le millions offert à qui résolverait P=NP...).
Bref, toute cette fabuleuse histoire pour dire que le problème a déjà bien vécu, si bien qu'un joli vocabulaire s'est créé autour du problème.
La trajectoire (ou le vol) d'en entier donné est la suite donnée plus haut.
Le temps de vol, c'est le nombre de terme avant l'apparition du premier 1.
L'altitude maximale est simplement le plus grand terme de la suite.
Le temps de vol en altitude, c'est le nombre de termes nécessaires pour qu'un terme de la suite soit inférieur au premier terme (les plus matheux d'entre vous remarqueront qu'il suffit de démontrer que le temps de vol en altitude est fini pour démontrer la conjecture)
Le facteur d'expansion, c'est simplement l'altitude maximale divisée par le premier terme.
Et pour faire des choses jolies, on peut mettre ça sous forme graphique :
Avec tout ça, vous devriez pouvoir comprendre ce petit script :
En 2004, la conjecture a été vérifiée pour tous les nombres inférieurs à 264 (1,8 × 1019)
Les seules démonstrations que l'on a réussi a réussi à donner pour l'instant sont heuristiques (statistiques) : en considérant que les nombres impairs, on trouve qu'en moyenne, le prochain nombre impair vaut 3/4 du nombre précédent, ce qui a tendance à décroitre.
En 2006, Alain Slakmon et Luc Macot, mathématiciens québécois se basent la dessus pour donner une démonstration probabiliste de la question, démonstration vraie, mais, comme le signale leur auteurs, "Comme il s’agit d’une approche probabiliste, nous ne pouvons affirmer
qu’il s’agit d’une preuve absolument irréfutable de la véracité de la
conjecture. Il reste une toute petite possibilité que certains nombres
y résistent". Cette possibilité est cependant petite... Mais pas impossible...
Sources :
Un site perso et un site moins perso
Article sur la démonstration probabiliste sur CyberSciences
20 mai 2007
Si c'est rond, c'est Poincaré
Rappelez-vous, c'était il y a une semaine...
Vous appreniez (sans doute avec effroi) que l'on pouvait concevoir que par un point extérieur à une droite ne passe aucune droite parallèle (géométrie elliptique) ou alors, une infinité (géométrie hyperbolique).
A propos de la géométrie hyperbolique, j'en était resté à un simple "Il y en a tout un tas, et n'en comprenant aucune d'entre elle, je ne peux pas en dire tellement plus".
Et bien, votre humble serviteur s'est renseigné sur le sujet (en fait, il est tombé sur l'article par hasard), et finalement, un monde dans lequel les carrés n'ont pas d'angles droits mérite pleinement sa place dans ce blog... Petite visite guidée au pays de la géométrie hyperbolique selon Poincaré.
Imaginons un disque. Un simple disque. Pour compliquer, appelons le "plan hyperbolique de Poincaré".
Pour avoir une bonne géométrie, il faut des droites et des points. Un "point" sera simplement un point appartenant au plan de Poincaré. Pour la notion de "droite", on prendra les diamètres du cercle et les arcs de cercle orthogonaux au pourtour du disque.
Les choses ressembleront alors à quelque chose comme ça :
H est le plan hyperbolique de Poincaré
Plusieurs droites y sont représentées. On peut voir que les 4 premiers axiomes d'Euclide sont bien conservés, notamment celui selon lequel il n'existe qu'une unique droite passant par deux points distincts.
Et l'axiome des parallèles ? On voit qu'il n'est pas respecté : il existe plusieurs droites passant par le point M qui ne coupent pas la droite D (T1, T2).
Maintenant, faisons attention à ne pas tout mélanger, surtout en matière de mesure des longueurs ! Le schéma ci-dessus n'est qu'une représentation. Plus on s'approche du bord du cercle, plus deux points proches en apparence seront éloignés. Un être vivant qui se déplacerait sur le plan de Poincaré ne pourrait jamais en atteindre les bords. Et nous, simple observateurs de cet être, le verrions rapetisser au fur et à mesure qu'il avance. Les angles, cependant, restent identiques pour tout le monde.
Ceci est un carré... Si si ! Les quatre angles sont égaux, les quatre côtés aussi
Dans le monde hyperbolique de Poincaré, la somme des angles d'un triangle est toujours inférieure à 180° (pi radians). Et ce qui est épatant la dedans, c'est que la différence avec pi donne la mesure de l'aire de ce triangle ! C'est peut-être un détail pour vous, mais quand même, c'est fou !
Et en conséquence, il n'existe pas de carrés à proprement parler, la somme des angles d'un quadrilatère étant toujours inférieure 360° (2pi radians). Il existe bien des "carrés", mais ils ne possèdent pas d'angles droits.
Autant il n'y a pas de quadrilatère avec quatre angles droits, autant il existe des pentagones droits avec 5 angles droits, des hexagones droits, et ainsi de suite... (heptagone, octogone, nonagone, triacontakaiheptagone...)
Un magnifique pavage du pan hyperbolique par des pentagones réguliers droits (en blanc)
Et encore plus fort : il existe un infinigone régulier ! C'est un polygone régulier, avec tous ses côtés égaux et tous ses angles égaux (à 120°). Et le plus fort, c'est que l'on peut paver le plan avec !
(Plan pavé d'infinigones réguliers)
Mais tout n'est pas si compliqué dans cette vision de la géométrie, puisqu'on peut y faire beaucoup de choses impossibles à faire dans le plan euclidien. On peut, par exemple, y réaliser la quadrature du cercle. Et, encore plus fort, la conjecture P=NP est vérifiée ! (Mais pour le millions de dollars, c'est dans le plan euclidien qu'il faut le démontrer).
Bon, les choses deviennent plus difficiles quand on commence à s'intéresser à un espace hyperbolique de dimension 5 ou supérieures, mais je crois que dans l'état actuel du blog, ce n'est pas très intéressant...
Limite Circulaire I (M.C. Escher)
Sources :
Pour la science, n°316 février 2004 (que l'on peut lire ici)
De jolies illustrations provenant de ici
Ici, un applet java sympathique
18 mai 2007
Le mystère du pentagone et du ruban...
Parce que ce blog aussi peut tomber à 9,81 m/s² dans l'inutilité, répondons aujourd'hui à cette question e-mail posée par Kaki (vous aussi, envoyez vos questions, peut-être elles seront tirées au sort pour y répondre) :
Pourquoi, quand on fait un nœud simple avec un ruban, on obtient un pentagone ?
En voilà une merveilleuse question qui nécessite que l'on s'y intéresse vraiment ! Pour comprendre ce phénomène, il faut remonter à l'origine du nœud, à la manière dont on le forme. Puisque un long discours vaut mieux que quelques images, et que j'ai pas le temps de discourir, voici quelques images :
Etape un : ...
Etape deux : ...
Etape trois : ...
Etape quatre : on tire des deux côtés. Les différents pliages vont alors s'agencer entre eux pour former un magnifique pentagone régulier.
Pour comprendre d'où il vient, il suffit simplement de s'intéresser aux pliages aboutissant au nœud terminé :
Etape un : On plie selon quelque chose qui ressemble à [ab]
Etape deux : On plie selon quelque chose qui ressemble à [cd]
Etape trois : On plie selon quelque chose qui ressemble à [ef]
Et à l'étape quatre, on tire des deux côtés, de manière à ce que toutes les longueurs soient minimales. Cela revient à avoir effectué les pliages de manière à ce que [ac] et [df] correspondent exactement à la largeur du ruban (donnant ainsi les points a', b', d' et f' : ac=a'c', df=d'f').
Les pliages donnent tout un tas d'égalités entre les différentes longueurs, identifiées par leur couleurs dans le schéma ci-dessous.
Et c'est là que cet exposé devient impossible à suivre !
soit x la mesure de l'angle ecd
(cd) étant la bissectrice de ecd, on a ecd=bcd
ecd et cdb sont alterne-interne : ecd=cdb
On a donc bcd=cdb, cbd est donc isocèle : cb=bd=de=ec=bd'=ec'
On peut alors trouver tout un tas de triangles semblables et d'angles alternes-internes, donc, plein d'angles égaux.
On a alors (ec')//(cf)//(da)//(bd')
On se retrouve avec ec'fc et adbd' étant des losanges, et acfd un parallélogramme.
De quoi conclure que ef=cd=ab et ac=fd. De la à conclure que tout est égal, il n'y a qu'un pas, que je n'hésite pas à franchir (il suffit d'ajouter le segment [a'f] pour voir apparaitre tout un tas de triangles semblables isocèles).
On a alors ac=cd=de=eb=ba : abcde est un pentagone régulier !
(Il y a peut être (et très sûrement) plus rapide, mais j'ai jamais été très fan de ce type de géométrie...)
Message personnel : Maintenant, Kaki, c'est à toi de jouer !
12 mai 2007
Puisque le Petit Prince l'a dit
C'est bien joli de parler de maths, mais pourquoi ne pas parler un peu de littérature ?!...
Je me sent d'humeur à parler d'Antoine de Saint Exupéry, du Petit Prince... Pourquoi ne pas faire une petite analyse de la portée philosophique de l'œuvre ? En effet, ça... Nan, parlons plutôt de math, je suis là pour ça !
On prête à Antoine de Saint Exupéry un dialogue entre lui et le Petit Prince, conversation durant laquelle le Petit Prince affirme sans sourciller son théorème (Le théorème du Petit Prince) : "Si un triangle a trois angles droits, alors il est équilatéral".
Ce a quoi vous aimeriez aimeriez bien lui répondre : "Et la marmotte, elle met le chocolat dans le papier d'alu. C'est pas possible d'avoir trois angle droits dans un triangle ! Rho le nul !".
Ce à quoi le Petit Prince vous répondrait, surement avec dédain, que vous avez tord, et commencerait à vous faire la morale. Et pour vous enfoncer encore plus, il vous dessinerait ce fameux triangle :
Le triangle ABC est bien un triangle équilatéral qui possède trois angle droits...
Et toutes ces histoires comme quoi la somme des angles d'un triangle font toujours 180° ?... Et oui, on vous a toujours menti, mais rassurez-vous, c'était pour votre bien...
-------
Il est donc l'heure de découvrir la vérité : tout ce que l'on apprend en géométrie depuis la maternelle, ce n'est qu'une vision euclidienne du domaine... Petit cours approximatif de l'histoire des mathématiques.
Avant Euclide, on faisait de l'arithmétique et de la géométrie, sans trop se poser de questions philosophiques comme "qu'est ce qu'un point ?" ou "qu'est ce qu'une droite". Vers 300 avant JC, Euclide en avait marre de tout ça, mis les pieds dans le plat et donna tout un tas de définition sur ces concepts (Ndlr : totalement indigestes).
A partir de toutes ces définitions, il donna 5 postulats (des propriétés que l'on décide vraies et sur lesquelles on fonde toute une théorie mathématiques - au contraire d'un axiome, on ne s'interdit pas de chercher la démonstration d'un postulat) :
1 - Un segment de droite peut être tracé en joignant deux points quelconques.
2 - Un segment de droite peut être prolongé indéfiniment en une ligne droite.
3 - Étant donné un segment de droite quelconque, un cercle peut être tracé
en prenant ce segment comme rayon et l'une de ses extrémités comme
centre.
4 - Tous les angles droits sont congruents (Celle là, je la comprend pas bien...)
5 - Par un point extérieur à une droite, on peut mener une et une seule parallèle à cette droite.
(A noter que Hilbert passe derrière en 1899, et propose 21 postulats comme base de la géométrie euclidienne... En fait, il y en avait un en trop dedans, mais c'est un détail)
Et pendant de très nombreuses années, les mathématiciens se sont toujours accordés à accepter les quatre premiers postulats (devenant, de fait, un axiome), mais pour le cinquième, ça bloquait... Ils étaient intimement persuadés qu'il était démontrable à partir des quatre premiers.
Et lors de nombreuses recherches infructueuses, ils tentèrent de voir ce que cela donnerait si ce cinquième postulat était faux.
Et si, par un point extérieur à une droite donnée, ne passait aucune droite parallèle ?
Créé par Riemann, cela donne une géométrie elliptique. Un lieu du plan, on évolue sur une sphère, et les droites, ce sont les cercles possédant le même centre que celui de la sphere. La dedans, les triangles peuvent (entre autre) avoir trois angles droits...
Par M ne passe aucune droite parallèle à D.
Et si, par un point extérieur à une droite donnée, passent une infinité de parallèles ?
On se retrouve avec une géométrie hyperbolique, crées par Lobatchevsky, Klein ou Poincaré (à des époques différentes). Il y en a tout un tas, et n'en comprenant aucune d'entre elle, je ne peux pas en dire tellement plus. En gros, ça donne quelque chose comme ça :
Géométrie hyperbolique de Lobatchevsky : par M passent une infinité de parallèles à D.
Maintenant, vous savez... Ne nous laissons pas dicter la géométrie par Euclide ! Il ne faut pas se laisser faire!
(Surtout que aujourd'hui, avec tout les concepts que l'on a inventé depuis, la géométrie euclidienne a laissé sa place à des choses encore plus alambiquées : dimensions infinies, distances négatives ou géométrie fractale)
Vous pouvez lire ce passage du Petit Prince ici. A noter que la discussion entre Antoine et Le Petit Prince n'est en réalité pas dans le bouquin du même nom, c'est simplement un hommage par un mathématicien au petit prince.
Et pour les sources, c'est encore Wikipedia, d'où proviennent les deux dernières images)
05 mai 2007
Un millions de dollars pour un sudoku
(Je ne cherche pas à rentrer dans tous les rouages de la question, juste une visite guidée de détails plus ou moins intéressants)
Rappelez-vous, c'était il y a une semaine : vous avez découvert ce qu'était un problème NP-complet, comme celui de la faisabilité du sudoku (et plein d'autres, j'ai donné plein d'exemples), et ce qu'était un problème de classe P...
Le grand problème du problème NP-complet, c'est que dans l'état actuel des choses, un ordinateur met généralement beaucoup de temps pour en venir à bout. Savoir si un sudoku de 10 000 cases est faisable est pour un ordinateur quelque chose d'inenvisageable (avec le manque de chance, la réponse nécessiterait dans les 10^20000 calculs... )...
Inenviseageable ?... Là est la véritable question... Cette question porte un nom : "A t'on P=NP ?"
Peut-être il existe quelque part, bien caché, un algorithme capable de déterminer si ce sudoku est faisable en un temps admissible, polynomial...
Pendant ce temps là, les mathématiciens cherchent...
Et pour cause : un millions de dollars est prévu pour la personne qui arrivera à démontrer que P=NP, ou arrivera à démontrer son contraire.
Et pourtant, c'est facile de le démontrer : il suffit simplement de trouver un algorithme polynomial qui résolve un problème Np-complet (Ou alors montrer que pour un problème NP-complet précis, il est impossible de trouver un algorithme polynomiale qui réponde à la question).
Ce qui est bien avec les problèmes NP-complets, c'est qu'il sont tous plus ou moins pareils : en résoudre un, c'est la même chose que tous les résoudre. Montrer que un seul est polynomial, c'est montrer qu'ils le sont tous... Idem pour l'inverse.
Bon, c'est pas forcément évident, à vrai dire, mais c'est faisable, avis aux amateurs...
(Enfin, c'est en théorie à la portée des amateurs en cherchant une démonstration du type évoqué ci-dessus, mais tout porte à croire que si la démonstration existe, elle porterait plutôt sur les définitions précises des diverses classes)
Et en attendant d'avoir une démonstrations, qu'en pensent les mathématiciens ?... Un sondage (encore un...) a été réalisé en 2002 sur la question :
45 % pensent que la question sera résolue avant 2050
27 % pensent qu'elle sera résolue après
5% pensent qu'on ne trouvera jamais, que ça sert à rien de chercher et qu'il vaudrait mieux chercher autre chose
(Et les autres ne pensent rien sur la question)
Mais ce qui est encore plus intéressant, c'est la deuxième question posée dans le sondage : "Est-ce que P=NP ?". A ça, on a :
61% pensent que P≠NP
9% pensent que P=NP
Et les 30% qui restent... pensent que c'est ni l'un, ni l'autre...
Et si la véritable réponse était là... Et si la question P=NP était indémontrable ?...
C'est tout à fait possible, Gödel a démontré 1931 qu'en mathématiques, tout n'est pas démontrable. Un théorème indémontrable (dans un système de démonstration donné) est appelé "indécidable".
Heureusement, c'est possible de démontrer que quelque chose n'est pas démontrable (c'est ça qu'est beau, en mathématiques !)...
Et que se passe t'il si on montre que "P=NP ?" est indécidable ?... Et bien, on ne sera pas plus avancés : les ordinateurs rameront toujours autant pour trouver la réponse d'un problème compliqué, mais on pourra admettre que P≠NP, et démontrer de nouvelles choses à partir de ça...
Et pour résoudre le sudoku, on gardera le papier et le crayon. Ou alors, on peut lire un bon bouquin, les sudoku, en fait, c'est nul...
Sources :
Pour la science - n°334, août 2005
26 avril 2007
Norbert Petiot, voyageur de commerce
(En lisant entièrement cette note, vous pourrez peut-être gagner un millions de dollars)
Voyageur de commerce, quel beau métier ! Se balader de maisons en maisons et refourguer sa camelote... Mais comment peut on aujourd'hui songer à faire ce métier quand on sait qu'il va falloir passer son temps à marcher entre toutes les maisons...
"Et si, avec mes compétences d'informatiques, j'écrivais un algorithme qui me chercherait le moyen le plus court de relier toute les maisons ! Avec ça, je pourrai minimiser mon temps à marcher, et passer plus de temps à vendre ma camelote !". Après cette réflexion, Norbert Petiot se mit à programmer, il trouva se qu'il chercha : un algorithme qui trouve le plus court chemin entre n points. Il fait un petit test simple, avec 4 points. Le programme teste alors les 12 chemins possible et retourne en un centième de seconde le meilleur chemin.
Parfait, se dit-il, devant ce jeu d'essai. Il décide alors de rentrer ses données, les 15 maisons qu'il veut visiter et les 105 distances qui séparent chaque maison 2 à 2... Cette histoire a plus de 17 ans... On dit qu'il attend encore la réponse à son problème... (Plus que 96 jours à attendre, finalement)
Mais que s'est-il donc passé ? Pourquoi ce malheureux voyageurs de commerce est mort de faim devant son écran en se disant "plus que quelques secondes à attendre" ? A t-il mal réalisé son programme ?
Eh bien, il se trouve que Herbert s'est frotté à un problème NP-complet...
NP-complet ? Qu'est ce que c'est que cette bête là ?!
(Les histoires de théorie de la complexité étant plus compliquée qu'il n'y parait, il y aura un certain nombre de simplifications fort peu précises)
Pour résoudre un problème en informatique, on a tendance à utiliser des algorithmes. En théorie, on peut calculer n'importe quoi. En théorie seulement, puisque dans la pratique, on est toujours limités par la puissance des ordinateurs que l'on utilise. C'est pour cela que l'on peut catégoriser les différents problèmes par leur facilité à être résolus par des ordinateurs. Parmi ces différentes catégories, on parle surtout des classes P et des classes NP.
La classe P (polynomial)
"Voici une boîte d'allumettes avec n allumettes. Fonctionne t-elles toutes ?". Pour le savoir, il va falloir essayer toutes les allumettes en les allumant. Si elles fonctionne toutes, on pourra répondre oui à la question. Le temps dont on aura besoin pour le savoir sera donc proportionnel au nombre d'allumettes.
"Y a t'il un couple qui s'est formé pendant cette soirée comportant n personnes ?". Sachant que personne ne voudra vous répondre, il va donc falloir vérifier pour chaque couple s'il correspondent à l'idée qu'on se fait d'un couple. Le temps qui va falloir pour trouver la réponse sera donc proportionnel au nombre de couples que l'on peut former, et donc, proportionnel (à quelque chose près) à n².
On dit qu'on problème de décision (auquel on peut répondre oui ou non) est de classe P si on peut trouver un algorithme qui donnera une réponse certaine en un temps polynomial.
La classe NP (non-déterministe polynomial)
"Étant donné n villes, existe t'il un chemin passant par tous ces villes de longueur inférieure à N ?". Avec un peu de chance, on va pouvoir répondre oui très rapidement, sinon, le temps d'attente sera proportionnel à n!
Pour simplifier de manière atroce, les problèmes NP sont les problèmes dont le temps d'exécution, si on manque de chance, ne sera pas polynomial.
Et les problèmes NP-complet (ou NP-difficile en simplifiant) dans cette histoire ? Et bien, c'est l'ensemble des problèmes qui ressemblent à notre problème du voyageur de commerce (qui est NP-complet), c'est à dire, les problèmes dont l'algorithme de résolution ressemble (même de loin) à celui du problème du voyageur de commerce.
Quelques exemples de problèmes NP-complets :
Problème du circuit hamiltonien
"Étant donné un graphe, y existe t-il un cycle hamiltonien ?"
Alias, étant donné un graphe, existe t-il un chemin passant une et unique fois par tous les points ?
Peut-on trouver un cycle hamiltonien dans ce graphe ?... Réponse...
Problème de la séparation équitable
"Étant donné une suite d'entiers données, y a t-il moyen de la séparer en deux paquets de même somme ?"
Exemple : 1, 2, 2, 3, 3, 4, 5...
Réponse : Oui : 2+2+3+3=1+4+5
Problème du sudoku
"Ce sudoku n²×n² cases est-il faisable ?"
Exemple : ce sudoku est-il faisable ?... Réponse...
Problème des équations quadratiques diophantiennes
"L'équation ax²+by=c, avec a,b,c entiers donnés, admet-elle des solutions ?..."
Problème de Laurent Romejko
"Quel est le mot le plus long existant parmi ces n lettres" et "Avec des additions, soustractions, multiplications et divisions, peut-on obtenir une certaines sommes avec n chiffres donnés"...
Bref
Il existe énormément de problèmes NP-complet, et en résoudre un seul de manière déterministe (avec un algorithme polynomial) suffirait à empocher la somme de un millions de dollars...
Plus d'informations dans le prochaine article, parce cet article-là est déjà trop long.
22 avril 2007
Königsberg et les parcours eulériens
Dans cette intéressante excursion au milieu de la théorie des graphes, nous allons aujourd'hui rejoindre la belle ville de Königsberg, aujourd'hui Kaliningrad, située dans l'enclave de Kaliningrad (le bout de la Russie perdu entre la Pologne et Lituanie)
Cette belle ville de Könisberg est une sorte de Mecque pour tous les mathématiciens, puisqu'elle a donné naissance au célèbre problème de la théorie des graphes, celui des "sept ponts de Könisberg".
Comme le nom du problème semble l'indiquer, Könisberg possède sept ponts. Une photographie de l'époque le montre bien :
Le problème dans cette ville est celui de la visite touristique : comment passer par tous les ponts de la ville sans passer deux fois par le même (ou revenir en arrière sur un pont) et revenir au point de départ. Autant le dire tout de suite, ce n'est pas possible...
En termes plus mathématiques, il faut trouver un cycle eulérien dans le graphe représentant la ville. Le graphe de la ville est ci-dessous : les arrêtes (lignes) représentent les ponts et les sommets (les cercles) représentent les îlots ou le continent. Un cycle eulérien, c'est un chemin qui passe une unique fois par toutes les arrêtes et qui revient à son point de départ. (Une chaîne eulérienne, c'est comme un cycle, mais il n'y a pas besoin de retourner au point de départ)
Tout le monde (j'espère) connait ce célèbre jeu qui consiste à tracer une sorte de maison (ou n'importe quel autre dessin) "sans lever le crayon". Il s'agit ni plus ni moins que de retrouver une chaîne eulérienne dans le graphe suivant...
Et comme ce blog a une volonté tout à fait pédagogique, même sur des problèmes de "tracé de figures sans lever le crayon", il faut savoir qu'il y a un truc à connaitre : pour qu'un tracé soit faisable sans lever le crayon (pour qu'il existe une chaîne eulérienne dans un graphe), il faut que le nombre de sommets possédant un nombre impair d'arêtes soit de zéro ou de deux. Il faut également savoir que l'on commence toujours et termine toujours en ces sommets.
Si on veut trouver un cycle, il faut qu'il n'y ait que des sommets avec un nombre pair d'arêtes...
A ne pas confondre avec les chaînes hamiltoniens (cf dernière note) dans lesquels il s'agit de trouver un chemin passant par tous les sommets de manière unique.
Et tant qu'on parle des graphes, on va continuer la prochaine fois avec le métier qui terrifie les mathématiciens et informaticiens : les voyageurs de commerce.
Sources :
Un peu de wikipédia (pour les jolies illustrations, les moins jolies sont de mon cru)
15 avril 2007
Le cavalier d'Euler
En ce 300e anniversaire de la naissance d'Euler, le mathématicien qui a tout fait en mathématiques, j'aimerais jouer à un jeu... Ce jeu, c'est celui du cavalier d'Euler (alias "le problème du cavalier", "le cavalier polygraphe" ou "la polygraphie du cavalier"), étudié par Euler en 1759 (car, je le rappelle, il a tout étudié)
Pour jouer, il suffit d'un échiquier de 64 cases et d'un cavalier (vendu avec l'échiquier). Le principe est simple : avec le mouvement en L spécifique du cavalier, il faut parvenir à passer sur toutes les cases de l'échiquier de manière unique. Vous pouvez le tester derrière ce lien.
Vous avez trouvé une solution ?! Félicitations ! Mais ce n'est pas tout d'en avoir une seule, ça serait quand même plus rigolo de toutes les avoir, non... On peut donc légitimement se poser la question du nombrede parcours possibles.
En 1995, deux chercheurs allemands, Martin Löbbing et Ingo Wegener, font tourner 20 puissants ordinateurs pendant 4 mois, et arrivent au chiffre de 33 439 123 484 294 parcours possibles... Mais après une petite réflexion, ils remarquent qu'une erreur s'était glissée dans leur raisonnement, et que finalement, les quatre mois de calculs n'ont servi à rien du tout...
En 1997, Brendan McKay, chercheur australien de son état, fait un travail un peu plus sérieux, et trouve le chiffre de 13 267 364 410 532 circuits.
Mais ces chiffres, ce n'est que pour les circuits fermés, c'est à dire, ceux qui reviennent à la case départ...
Alors, combien de circuits possibles ?!
En 2001, le chiffre tombe : 1,22 millions de milliards de possibilités, c'est à dire 1 220 000 000 000 000 possibilités. Pour se donner une idée, si un ordinateur donnait un millions de solutions par secondes, il faudrait dans les 40 ans pour avoir toutes les solutions. Évidemment, ce chiffre ne tient pas compte des possibilités de symétries...
Après, on peut s'amuser à changer la taille ou la forme de l'échiquier, et c'est parti pour de nombreuses heures de fun en perspectives. Par contre, si vous voulez vraiment trouver des solutions excluez les échiquiers de moins de 6×6 cases. Si vous cherchez des solutions qui reviennent à la case départ, il faut un nombre pair de cases.
La première solution de ce sympathique jeu nous est donné par al-Adli ar-Rumi en l'année 840 :
Et reste la question : pourquoi je vous parle de tout ça ? Et bien, tout simplement pour commencer une série de notes sur la théorie des graphes, qui va peut-être nous amener à résoudre le problème P=NP (ou pas)...
En fait, ce problème revient à chercher un parcours hamiltonien au sein de ce graphe : (mais j'y reviendrais lors de prochaines notes, histoire d'expliquer ce que veut dire parcours hamiltonien).
Sources :
Cet excellent article de procrastin
Et un peu wikipedia
07 avril 2007
Lacets coulants
S'il y a un domaine dans lequel les maths s'appliquent à un niveau énorme, c'est bien dans celui des chaussures... Si si, je vous assure ! Bon, peut-être pas à un point énorme, mais tout de même...
Le laçage des lacets ! Je ne parle pas des nœuds (qui est un véritable pan des mathématiques), mais le laçage des lacets sur la chaussure, qui donne de chouettes motifs le long de la chaussure. Si vous portez des chaussures à scratch, il est encore temps d'arrêter de lire cet article, puisqu'il ne va traiter que des chaussures à lacets... A noter que tout ce qui est contenu dans cette note se base sur de véritable travaux de recherches mathématiques commencés en 11992 par John Halton. Depuis, de nombreux progrès ont été effectués dans le domaine, mais je n'en dit pas plus...
Avant de commencer, définissons ce qu'est une chaussure mathématiques (d'ordre n). Il s'agit d'un ensemble de 2n points ressemblant à quelque chose comme ça (Avec h la hauteur entre deux points, et 1 la distance entre les deux côtés) :
Coccinelle Belle chaussure d'ordre n
Maintenant, on peut définir ce qu'est un laçage, et ou sera prêts à commencer l'étude. Un laçage, c'est un chemin composé de 2n segments qui passe une unique fois par tous les œillets de la chaussure, et qui revient à son point de départ. Comme un laçage est fait pour attacher sa chaussure, il faut que chaque œillet soit au moins relié à un œillet en face.
Maintenant que tous est clair, il faut savoir qu'il existe plusieurs types de laçages. Vous ne le saviez pas, mais vous portez peut-être aux pieds des laçages denses, simples, voire droits ou même super-droits (mais ils sont rares)
Les laçages denses
Un laçage dense est un laçage dans lequel chaque œillet est relié à deux œillets dans la série d'en face. Citons par exemple le laçage en croix, ou le laçage démoniaque.
Laçage en croix (alias, laçage américain, pour les amateurs de country)
Laçage diabolique (Mais très joli)
Les laçages simples
Quand on suit le chemin parcouru par le lacet d'un laçage simple, on descendra la chaussure dans un premier temps, et on le remontera dans un second temps. Le laçage en crois est un laçage simple, tout comme le laçage en nœud papillon.
Laçage en nœud papillon
Les laçages droits et super-droits
Un laçage est droit quand toutes les lignes horizontales sont présentes. Il est super-droit quand il n'y a plus un seul segment oblique. Citons par exemple le laçage zigzag, le laçage en zigsag ou celui en serpent.
A ne pas confondre...
Laçage en serpent (super droit)
Phase un : définir les choses (ça, c'est fait)
Phase deux : se poser des questions, et si possible, y répondre...
Le laçage le plus court...
Quelle est la chose que l'on redoute le plus dans la vie ? Oui, vous l'avez deviné, il s'agit de cette question horrible : "vais-je avoir suffisamment de lacets pour pouvoir boucler mon laçage ?"
Oui, un lacet qui se casse, et c'est l'angoisse, la chaussure ne tient pas, il faut réagir en faisant un laçage plus court. oui, mais lequel ? Après 12 pages de démonstration, on aboutit à ce résultat stupéfiant : le laçage le plus court est le laçage en nœud papillon !
Oui, mais si je veux un joli laçage droit ? Pas de problème, on a aussi la réponse : le laçage droit le plus court est le laçage en serpent (si n est pair) et le laçage en zigsag (si n est impair).
Et si vous voulez des chaussures bien serrées avec un laçage dense ? Et bien, le plus court sera le laçage en croix !
Le laçage le plus long...
Autre hantise de l'européen moyen aujourd'hui : que doit-on faire quand, après avoir acheté un joli lacet doré dans une grande surface, on se retrouve avec un lacet long d'un mètre... Non, n'utilisez surtout pas vos ciseaux ! Il suffit simplement de connaitre le laçage le plus long !
Une chose à savoir : le laçage le plus long est le laçage diabolique ! (Si h<1. Avec h>1, il faut le laçage angélique, mais je n'ai pas trouvé d'illustration... Et en plus, c'est une conjecture...)
Si n'avez pas que ça à faire, de lacer vos chaussures, il vous faudra un laçage simple. Le laçage simple le plus long est le laçage en zigzag, mais vous y perdrez énormément en longueur de lacet...
Combien de laçages ?...
Autre grande hantise du monde moderne, tous autant que l'on est nous sommes déjà posé cette question "Mon Dieu, avec quel laçage vais-je sortir ?". Et vous en êtes arrivés à essayer tous les laçages possibles pour voir le meilleur... Malheureusement, vous n'avez pas pris la peine de vous renseigner sur leur nombre, grand mal vous y a pris !... Heureusement, les mathématiciens se sont posé sur la question, et en ont tiré des résultats à prendre en compte !...
Combien de laçages en tout ?
C'est donné par cette formule toute simple :
Ce qui donne :
n=4 : 1080
n=5 : 51840
n=6 : 3 758 400
n=7 : 382 838 400
En fait, ces résultats sont intéressant sur un certain point : il ne faut jamais essayer tous les laçages possibles avant de partir au boulot...
(Bon, évidemment, tout ça, ce ne sont que des résultats, je vous ai passé les étapes de réflexion... De toutes façons, vous auriez sauté les paragraphes...)
Toutes les questions n'ont pas encore été éludées, puisque l'on se base sur des chaussures simples : les trous sont également espacée, et les deux lignes de points sont bien verticales... Que se passe t'il si l'on permet à un lacet de passer plusieurs fois par un même trou ? Que se passe t'il si les trous ne sont pas également espacés ? Que se passe t'il si on place nos trous suivant une courbe plus amusante qu'une simple droite ? Nombre de questions qui n'ont pas encore leur réponses... Il ne faut pas croire, il y a encore beaucoup de thèmes de recherche en mathématiques...
Sources :
Pour la sciences (j'adore ce magazine) n°352 février 2007 (Sur lequel j'ai également pris quelques images)
Le reste des images sur ce site russe (Avec plein d'autres très jolies photos pour donner des idées de laçage)
