Choux romanesco, Vache qui rit et intégrales curvilignes

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 pour vendre de chouettes encyclopédies !... 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 pourrais 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.

commerce

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. Fonctionnent 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 ?

hamilton1
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 ?"

Sudoku
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)

Kalingrad_carte

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 :

Konigsberg

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)

graphe_konis

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...

maison

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)

Posté par El Jj à 10:00 - Commentaires [2]
Tags :

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 :

Marche_du_cavalier_selon_al_Adli_ar_Rumi

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).

graphe_cavalier



Sources :
Cet excellent article de procrastin
Et un peu wikipedia

Posté par El Jj à 16:14 - Commentaires [6]
Tags : ,

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) :

cocci
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.

croixCroix
Laçage en croix (alias, laçage américain, pour les amateurs de country)

demon
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.

neupapneupap

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.

zigzsag
A ne pas confondre...

serpentserpent
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 :

formgenerale
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)

Posté par El Jj à 10:14 - Commentaires [10]
Tags :


31 mars 2007

[#] De la nécéssité de ne plus inventer la pièce de 62 cts mais celles de 3 et 4 cts

Vous avez raté le début ?

Quatrième question : Comment je fais pour payer 2,98€ avec mon jeu de 1c, 6cts, 14cts, 62 cts, 99cts, et 1,40€ ?
Et voilà le gros problème de notre nouveau système : il ne suffit pas d'être doué en calcul mental, il faut aussi être un ordinateur capable de tester toutes les combinaisons donnant la somme voulue.
Comment feriez-vous pour payer cette somme de 2,98€ ? Et bien, vous utiliseriez l'algorithme glouton, c'est à dire, prendre la plus grande pièce possible, puis faire la soustraction :
298 = 140+140+14+1+1+1+1 : 7 pièces
Pourtant, on peut faire cette même somme avec 4 pièces :
298 = 99+99+99+1

Un exemple plus simple : payer 18€ avec des pièces de 1, 6 et 14€
L'algorithme glouton donne 5 pièces : 18=14+1+1+1+1
Alors qu'une simple réflexion donne 3 pièces : 18=6+6+6

Le jeu de pièce optimal calculé plus tôt est malheureusement basé sur le principe que les usagers doivent posséder un ordinateur interne pour rendre la monnaie avec le minimum de pièces...

Cinquième question : Quel est le meilleur jeu de pièces, alors ?
Pour celà, on va appeler effmoy_gl(298,[1,6,14,62,99,140]) le nombre de pièces à donner pour payer 298 cts avec le jeu de pièces [1,6,14,62,99,140], et effmoy_gl(500,[1,6,14,62,99,140]) le nombre moyen de pièces à payer pour payer une somme entre 1cts et 500cts avec le jeu de pièces  [1,6,14,62,99,140].
Bref, après un temps de calcul moins long, on trouve :
effmoygl(500,[1,6,14,62,99,140])=5,992 (Ce qui est quand même moins bon que les 4,67 pièces quand on cherche la décomposition optimale)

Le palmarès des meilleurs jeux de pièce, en considérant l'algorithme glouton, est donc celui-ci :
Pour les sommes entre 1 et 499 centimes :
* 4 pièces, les gagnants sont...
[1,5,23,109]* et [1,5,23,110]* (7,1 pièces en moyenne)
* 5 pièces, les gagnants sont...
[1,4,13,44,147], [1,4,13,44,150]*, [1,4,14,47,160]* et [1,4,14,48,160]* (5,8 pièces en moyenne)
* 6 pièces, les gagnants sont...
[1,3,8,26,64,202], [1,3,8,26,64,203], [1,3,8,26,64,204], [1,3,10,25,79,195], [1,3,10,25,79,196] et [1,3,10,25,79,197] (5,4 pièces en moyenne)

Notre actuel jeu de pièces [1,2,5,10,20,50,100,200]* donne 4,6 pièces en moyenne

(A noter que pour les jeux de pièces avec un *, l'algorithme glouton donne toujours la meilleure décomposition)

Sixième question : C'est quoi cette fonction effmoy_gl de $£¤µ% ?????
Je vous l'accord, cette fonction se base sur un très mauvais principe : celui que toutes les sommes payables sont réparties équitablement, ce qui n'est pas tout à fait vrai (pas du tout vrai, en fait)
Les gens suivant activement ce blog se rappelle très bien la loi de Benford, qui régit également les prix affichés dans les magasins (A une certaine échelle). Autre chose à prendre également en compte : l'euro a étrangement fait monter les prix, puisqu'ils terminent très souvent par des 0 ou des 5...
Beaucoup de choses à prendre en compte finalement... Et ma flemme m'empêche de le programmer...

Septième question : Ouais, mais bon...
Malgré toute la bonne volonté du monde, il y a peu de chances de voir un jour adapté en pièces ces jeux de pièces mathématiquement parfaits... Pourquoi ? Parce que le monde n'est pas prêt à faire tous les jours des calculs avec des soustractions à retenues...
Il y a un seul moyen de résoudre ce problème : que les calculs de rendus se fassent en procdédant chiffres par chiffre. D'abord les unités, puis les dizaines, puis les centaines...
Le problème se ramène donc à chercher le jeu de pièce le plus performant sur les sommes de 1 à 9 centimes, on prendra ensuite les pièces de dizaines et centaines correspondantes.
Avec une répartition équilibrée des sommes de 1 à 9 centimes, on trouve, pour notre jeu actuel :
effmoy(10,[1,2,5])=1.7 pièces par chiffres
Notre système est donc plutôt correct, mais le meilleur est le système [1,3,4], avec effmoy(10,[1,3,4])=1.6 pièces par chiffres.

(A noter que le système [1,2,5] est à égalité avec les sytsèmes [1,4,6], [1,4,5], [1,2,7], [1,2,6], [1,2,4], [1,3,8], [1,3,7], [1,3,6] et [1,3,5]. Le pire est évidemment [1,8,9])

S'il y a une réforme faisable, ça serait de changer notre jeu de pièces actuel contre [1,3,4,30,40,300,400,...] ! C'est la banque centrale qui serait contente, puisque cela voudrait dire moins de pièces à imprimer...

Et si on considère notre amie la loi de Benford, on découvre que le système [1,3,4] est meilleur que [1,2,5]...

Il y a évidemment une mise en garde, puisque notre faux-amis l'algorithme glouton n'aime pas trop ce système, à cause de 6.
Avec l'algorithme glouton, on a 6=4+1+1 (3 pièces)
Sans cet algorithme, on a 6=3+3 (2 pièces)
Mais pour un seul contre exemple plutôt facile à contourner, on ne va quand même pas cracher sur cette révolution monétaire, non !?

Huitième question : Ben alors, on change quand de monnaie ?
Je proposerai bien maintenant, mais il semble que Roland Yéléhada ait une petite réserve à émettre :
"C'est bien joli, tout ça, mais la loi de Benford, elle s'applique beaucoup plus aux phénomènes naturels qu'aux phénomènes humains ! En Europe, on aime bien les prix ronds, avec plein de 0 et de 5 !..."
Et ben en fait, il a part tord, l'ami Roland... [1,3,4] est meilleur pour les répartitions équiprobables et selon la loi de Benford des chiffres, mais se fait dépasser en efficacité quand on considère une grande probabilité de présence de 5 et de 0. Par "grande probabilité", on entend "que la présence de 5 ou de 0 ait une fréquence de plus de 33,33%".

Seulement, et juste pour contredire Roland, parlons de nos non-amis les publicitaires, qui se font un plaisir de vendre des choses à 9,99€. Et bien, le jeu de pièces [1,3,4,10,30,40,100,300,400, ...] serait quand même plus efficace...

Et pour ceux qui disent qu'il vaut mieux payer avec un billet de 10€ une somme de 9,99€, ils seront heureux d'apprendre qu'ils pourront toujours le faire facilement !

Pour moi, il n'y a qu'une seule chose à faire pour rendre l'Europe meilleure : votons les pièces de 3, 4, 30 et 40 centimes !

(Et pour ceux qui douteraient de la nécessité de tous ces calculs, il faut quand même savoir qu'ils ont une vraie utilité pour les banques émetrices, celle de décider le nombre pièces de chaque types à imprimer, selon leur fréquences relatives...)


Sources :
Toujours Pour la science, n°335, septembre 2005
et toujours mes petits programmes en Isetl

Posté par El Jj à 16:35 - Commentaires [3]
Tags :

24 mars 2007

[#] De la nécéssité d'inventer la pièce de 62 centimes

1, 2, 5, 10, 20 ou 50 centimes d'euros, un euro ou 2 euros... De belles pièces bien rondes...

Ceausescu, célèbre dictateur communiste, avait bien comprit que le système était quelque chose de bien trop capitaliste. C'est pour cela qu'il inventa la pièce de 3 lei... Notre ami dictateur n'a cependant pas été le seul à changer la formule des [1,2,5,10,20,50,100,200] unités, puisque les États-Unis ont fait leur pièce de 3 cents dans les années 1850 et les russes ont fait leur pièce de 3 kopecks...

3lei

Une pièce de 3 unités, c'est bien, mais pourquoi ne pas réformer tout le système ?...

Première question à se poser : pourquoi a-t-on plusieurs pièces différentes ?
Question un brin stupide (pas qu'un brin, d'ailleurs), je sais, mais imaginons un monde pas bien merveilleux où seule la pièce de un centime existerait... Certes, on aurait plus à chercher les bonnes pièces dans notre poche, mais pour payer les 87 centimes du carambar... Pour chaque somme à payer entre 1 et 100 unités, il va donc falloir en moyenne 50 pièces.

En face de ce monde pas bien merveilleux, un autre monde pas bein merveilleux où les gens ne savent pas compter. Ils ont donc autant de pièces que de sommes payables. Pour le caramabr à 89 centimes, pas de problème, la pièce de 89 centimes existe... C'est pour celà que les habitants de ce monde sont aussi baraqués, à force de porter toujours sur soi des porte-monnaies de 9 kilos... Pour chaque somme à payer entre 1 et 100 unités, il va donc falloir en moyenne 1 pièce.

Un jeu de pièce sera donc efficace si, en moyenne, le nombre de pièces nécessaires pour payer une somme est minimal, tout en limitant le nombre de pièces différentes.

Deuxième question : quel est maintenant le meilleur jeu de pièces ?
Le meilleur moyen de le savoir, finalement, c'est de faire des tests. Comme j'aime bien l'informatique aussi, je me suis permit de programmer toutes les fonctions  dont je vais vous parler. Si vous voulez faire vos propres tests, téléchargez vite ce petit logiciel (même pas besoin d'installation, il marche tout de suite).

Pour les besoins de compréhensions, et au lieu de faire des phrases trop longues, je vais appeler le nombre minimum de pièces pour payer 49 centimes avec des pièces de [1,2,5,10,20] centimes eff(49,[1,2,5,10,20])

Comment fait-on pour payer 49 centimes en faisant l'appoint avec notre actuel jeu de pièces ? Et bien, il faut 5 pièces : 49=20+20+5+2+2
Et avec d'autres systèmes, alors ?...
eff(49,[1,2,5,10,20]) = 5
eff(49,[1,3,6,10,20]) = 4
eff(49,[1,4,5,15,30]) = 3
eff(49,[1,2,3,4,49]) = 1

Évidemment, et ça se voit bien sur le dernier exemple, un seul exemple ne donne pas l'efficacité d'un jeu de pièce. Ce qui serait intéressant à connaitre, c'est le nombre moyen de pièces nécessaires pour payer des sommes entre 0 et 99 centimes, par exemple. Avec notre actuel jeu de pièces, notons effmoy(100,[1,2,5,10,20,50]) le nombre moyen de pièces nécessaires pour payer une somme entre 1 et 99 centimes. (effmoy(100,[1,2,5,10,20,50]) = (eff(0,[1,2,5,10,20,50]) + eff(1,[1,2,5,10,20,50]) + ... + eff(99,[1,2,5,10,20,50])) /100 )

La question que tout le monde attend à présent... Combien faut-il en moyenne de pièces pour payer une somme entre 0 et 99 centimes (en considérant que tous les prix son équiprobables) avec notre jeu d'euros basique ?

Et bien..........(temps de calcul long, c'est un problème NP, quand même)...........
effmoy(100,[1,2,5,10,20,50]) = 3,4
Et avec d'autres systèmes, alors ?...
effmoy(100,[1,3,4,10,30,40]) = 3,2 (Waw, c'est mieux, dites donc !)
effmoy(100,[1,4,6,21,30,37]) = 2,92

En fait, avec 6 pièces et X=100, le système [1,4,6,21,30,37] est le plus efficace (ex aequo avec [1,5,8,20,31,33])

Troisième question : et si on ajoute les pièces de 1 euro et 2 euros ?
Et bien, il y a juste à faire d'autres petits calculs :

effmoy(500,[1,2,5,10,20,50,100,200]) = 4,6
Une moyenne de 4,6 pièces aves un jeu de 8 pièces, c'est pas vraiment la panade...

Mais quels sont donc les meilleurs jeux de pièce, alors ?...
Ouvrez vos esgourdes, l'heure est grave...
Pour les sommes entre 1 et 99 centimes :
* 5 pièces, le gagnant est...
effmoy(100,[1,5,16,23,33]) = 3,92
* 6 pièces, les deux gagnants ex-aequo sont...
effmoy(100,[1,4,6,21,30,37]) = effmoy(100,[1,5,8,20,31,33]) = 2,92
* 7 pièces, le gagnant est...
effmoy(100,[1,4,9,11,26,38,44]) = 2,65

Pour les sommes entre 1 et 499 centimes :
* 4 pièces, le gagnant est...
effmoy(500,[1,7,57,80]) = 6,804
* 5 pièces, le gagnant est...
effmoy(500,[1,6,20,85,121]) = 5,44
* 6 pièces, les gagnants ex-aequo sont...
effmoy(500,[1,6,14,62,99,140]) = effmoy(500,[1,8,13,69,110,160]) = 4,67

La question sur le jeu de 7 et 8 pièces optimal est ouvert, si vous avez une idée...

Bref, avec seulement 6 pièces, on atteint le même nombre moyen de pièces qu'avec notre bon vieux système européens de pièces... Moins de pièces différentes, moins de pièces en moyenne... J'appelle tout de suite la banque centrale européenne, il y a une réforme à faire là !

Bref...
Votez pour les pièces de 62 centimes, 99 centimes et 1€40 !

Et dans la prochaine note, la suite...


Sources :
Pour la science, n°335, septembre 2005
Et puis, je remets là mes petits programmes

Posté par El Jj à 16:32 - Commentaires [10]
Tags : ,

18 mars 2007

[#] Avec des si, on couperait du bois...

"Si Paris était un liquide, alors, on pourrait le mettre en bouteille." Simple raisonnement, et pourtant, totalement juste. Pourtant, tout le monde s'accorde à dire que Paris n'est pas un liquide, mais bel et bien une ville. Pourtant, si c'était un liquide, on pourrait facilement la mettre en bouteille. La prémisse du raisonnement est fausse, mais le raisonnement est juste.

La logique formelle au premier abord peut paraitre au premier abord tout à fait étrange, car tout ce qui est faux implique tout et n'importe quoi. Pour montrer que l'implication est fausse, il faudrait réussir à trouver un contre exemple par l'expérience.
Par exemple, la phrase "Tous les basketteurs de plus de 9 mètres sont multimilliardaires" est une phrase vraie. Si vous n'êtes pas d'accord, trouvez-moi un contre exemple, comme par exemple un basketteur de plus de 9 mètres et pauvre... S'il n'y a pas de contre exemples, c'est que la phrase est vraie ! (En admettant l'axiome du tiers exclus...)


Un autre exemple est la démonstration par Bertrand Russel que "si 2+2=5, alors je suis le Pape"
* Supposons que 2 + 2 = 5
* Soustrayons 2 de chaque membre de l’identité, nous obtenons 2 = 3
* Par symétrie, 3 = 2
* Soustrayant 1 de chaque côté, il vient 2 = 1
* Maintenant, le pape et moi sommes deux. Puisque 2 = 1, le pape et moi sommes un. Par suite, je suis le pape.

Petite application pratique à présent, pour redorer le blason de nos amis les sondages électoraux, qui finalement, sont tout à fait vrais du point de vue de la logique formelle.
Jour J-1: le sondage du jour pose la question "si les élections avaient lieu aujourd'hui, pour qui voteriez-vous ?". Les réponses sont plus qu'étonnantes, puisque le sondage annonce la victoire à 80% d'une tourte géante.
Jour J, les élections ont lieu, et contre toute attente, Ségolène Royal est élue présidente de la République avec 53% des voix.
Le sondage s'est il trompé ? Du point de vue de la logique formelle, absolument pas ! Ne me faites pas dire que Ségolène Royal est une tourte géante (bien qu'il s'agisse d'une conséquence logique).
Le sondage demandait aux électeurs pour qui ils voteraient SI l'élection avait lieu au jour J-1. Les élections, quant à elles, ont eu lieu au jour J. Pour montrer que le sondage était erroné, il aurait fallut constater que effectivement au jour J-1, aucune tourte géante n'était élue avec 80% des voix. Mais à moins de déplacer le jour des élections, c'est impossible de montrer que le raisonnement est faux... Il est donc vrai !

 

Bref, avec des si, on mettrait Paris en bouteille, mais seulement si ce que l'on trouve après le "si" est quelque chose d'irréalisable, et Ségolène Royale est une tourte géante si les élections avaient lieu un jour plus tôt que prévu...


Sources :
2+2=5, sur Wikipedia (Avec la réflexion philosophico-politique de Orwell)
Chronique de Didier Nordon, Pour la Science, mars 2007 (pour l'exemple des sondages pré electoraux)

Posté par El Jj à 15:33 - Commentaires [5]
Tags :

14 mars 2007

[#] Journée de π

Bien que j'arrive un peu tard, il est nécessaire tout de même de fêter aujourd'hui dignement la journée mondiale de π (pi, pour ceux qui lisent mal le grec ancien).

En effet, nous sommes le 14 mars, soit, au format américain, 3/14. Il est donc d'usage de fêter en cette belle journée ensoleillée du 14 mars à 1h59 (car π = 3,14159...) tous les bienfaits du nombre π, et d'imaginer dans quel cauchemar nous vivrions si π n'existait pas...

Bref, bonne journée de π à tout le monde !

A noter qu'il existe également une journée de π approximatif le 22 juillet (car 22/7=3,14286...), ou le 26 avril, jour où la la longueur totale de l'orbite terrestre, divisée par la distance déjà parcourue, est égale à π...

Posté par El Jj à 20:03 - Commentaires [3]
Tags : ,

11 mars 2007

[#] Histoire de dénombrabilité

Combien avons nous de doigts par mains ?
Je vous le donne en mille : nous en avons (pour la majorité d'entre nous) 5. L'ensemble doigts de la main {pouce, index, majeur, annulaire, l'auriculaire} possède bien 5 éléments. On dit qu'il a pour cardinal (nombre d'éléments) 5. Bon, là, c'est facile de compter, puisque ce nombre est fini. (Pour la suite, quand je vais dire "il y a autant", ça veut dire que les ensembles ont le même cardinal)

Combien y a t'il de nombre premiers, de carrés parfait, d'entiers pairs ou de puissances de 2 ?

En voilà une bonne question que tout le monde s'est un jour posé (Peut-être avec beaucoup d'alcool dans le sang, mais tout le monde se l'est un jour posé). La réponse est simple, finalement : il y en a une infinité (quoiqu'il faut quand même passer par la démonstration pour les nombres premiers, mais là n'est pas le propos)

Une autre question alors :
Y a t'il plus de nombre premiers, de carrés parfait, d'entiers pairs ou de puissances de 2 ?
Mais là, la réponse est moins évidente : il y en a autant ! En fait, il y en a autant qu'il y a d'entiers dans N (l'ensemble des entiers naturels {1,2,3,...}). Tous les ensembles que je viens de citer sont des ensembles appelés ensembles dénombrables.
Un ensemble est dit dénombrable lorsqu'il existe une bijection entre cet ensemble et N. (C'est à dire que pour chaque élément de N, on peut associer un unique élément de cet ensemble, et inversement)
En gros, ça veut dire qu'il y a autant d'entiers que d'entiers pairs, puisque, pour chaque entier, on peut faire correspondre un nombre pair en le multipliant par 2, et inversement.
A partir de là, on peut voir que l'ensemble des zentiers relatifs Z ( ...,-2,-1,0,1,2,...} est également dénombrable, il suffit d'associer au côté positif de Z les entiers pairs de N et au côté négatif de Z les entiers impairs : (0 avec 0, -1 avec 1, 1 avec 2, -2 avec 3, 2 avec 4, et ainsi de suite).
Pour ceux qui ont du courage, on peut aussi montrer que N×N (l'ensemble des couples d'entiers) est également dénombrable, en associant à un couple (n,m) l'entier 2n(2m+1) (Si vous avez eu le courage d'avoir lu jusqu'à ici, je vous laisse réfléchir à la question)

Et pourquoi je parle de ça ? Juste histoire de donner tord à Euclide qui nous disait que le tout est plus grand que la partie...


Bon, mais ça amène à une réflexion : Si il y a des ensembles dénombrables, c'est qu'il y en a des indénombrables, alors ! Exactement ! Par exemple, l'ensemble des réels R (qui contient tous les nombres à infinité de décimales), ou l'ensemble des points dans un cercle. J'ai la flemme de vous faire la démonstration la plus célèbre (l'argument de la diagonale de Cantor, je vous laisse chercher sur google)

En gros, ça veut dire qu'il y a autant de nombres dans l'ensemble [0,1] (tous les nombres entre 0 et 1)que dans R tout entier, mais qu'il y beaucoup plus de points dans l'ensemble [0,1] que dans N.

Tout ça pour dire qu'il y a plusieurs infinis, plus ou moins grands. Celui de N (que nous appellerons aleph0 (aleph 0)) et celui de R (aleph1). Désormais, quand vous voudrez dire à propos de quelque chose qu'il y en a une inifinité, soyez précis dans vos terme, et employez aleph0 ou aleph1 ! (Ou même aleph 2, mais c'est rare, dans la nature)

Une autre question que vous allez sans doute (pas) vous poser : Ya aleph 0, ya aleph 1... Y a t'il un aleph 0.5 ou quelque chose entre les deux ?... Un ensemble infini qui soit plus grand que N et plus petit que R ?...

Et bien la réponse est : oui ! Ou bien, non ! En fait, c'est comme vous voulez... On s'accorde plutôt sur le fait que la réponse est non (hypothèse du continu) mais on ne pourra jamais le démontrer. Non pas que les mathématiciens soient trop nuls pour le démontrer, mais parce qu'un petit malin a sû démontrer que c'était quelque chose d'impossible à démontrer (C'est ce qu'on appelle un problème indécidable, j'en reparlerai peut-être un jour)

Bref, que retenir de cette note, si ce n'est qu'elle est trop longue et trop technique, et que vous pourrez ressortir demain midi pour paraitre intelligent à table ?
- Il y a autant d'entiers pairs que d'entiers tout courts.
- Il y a plus d'éléments dans R que dans N.
- Il y a des infinis plus grands que d'autres.
- Ca ne sert à rien de se poser la question sur ce qu'il y a entre aleph0 et aleph1.

Et voilà. Je remercie chaleureusement tout ceux qui ont tout lu !

Posté par El Jj à 21:29 - Commentaires [6]
Tags :


« Début   23  24  25  26  27  28  29  30  31    Fin »
Licence Creative Commons
Ce(tte) œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 3.0 France.