MountyHall - La Terre des Trõlls

	Ze Figurines
MountyHall

Référencé sur

Nous sommes le 19° jour de la Limace du 24° cycle après Ragnarok

Bienvenue Invité

Tous les Forums

Hors Jeux

Modérateurs de ce forum : Aghabeu, Dabihul, Grankausto, Loinvu, Madère, Mamoune, Modérateur 6, Modérateur1, Modérateur2, Modérateur3, Modérateur4, Modérateur5, Mr x, Rouletabille, Schtroumpf, TilK, VYS, Xaruth

Vous pouvez discuter ici de tout et de rien et surtout de tout ce qui ne se retrouve pas dans les autres forums Hors-jeux.

Il est cependant interdit d'utiliser ce forum pour un bénéfice personnel (vente, publicité, affiliation, ...).
Evitez aussi tout "sujet qui fache" et autre "trolls". Seuls des messages appelant à une discussion cordiale et pleine de tolérance seront acceptés.

petite énigme mathématique
Pages : 1, 2, [3], 4

#. Message de Rand Al Troll le 23-04-2006 à 15:58	21003 - Rand Al'Troll (Kastar 43) - Teubreu -
Pays: France Inscrit le : 14-11-2003 Messages: 236 (Golem Costaud)	Citer

Ah, ben yavait une erreur, je m'y remets alors

#. Message de TilK le 23-04-2006 à 16:44 [MH Team] [Maître Outilleur] [Ami de MountyHall]	36216 - mini TilK (Kastar 49) - Teubreu -
Pays: France Inscrit le : 06-12-2002 Messages: 8352 (Hydre Fumante)	Citer

Voila déja 4 bonnes réponses.

Néanmoins, personne ne m'a pour l'instant donné l'ensemble d'arrivé, ni une démonstration que c'est bien une bijection.

#. Message de Garffon le 23-04-2006 à 20:49	43658 - Garffon (Tomawak 39) - RELAIS&MAGO -
Pays: France Inscrit le : 07-08-2004 Messages: 424 (Golem Costaud)	Citer

L'ensemble d'arrivé ?
Tous les éléments de l'ensemble d'arrivé sont 0, 1 et des séquences (en faisant fi des espaces, qui sont décoratifs et compliqueraient tout) :
* délimitées par (...)
* possédant autant de "(" que de ")"
* ne possédant pas les motifs "0)" et "()"

Prouver que cette méthode fournit une bijection de N vers l'ensemble des valeurs bien formées est faisable relativement facilement, quitte, si l'on veut être rigoureux, à utiliser une bonne grosse récurrence. Je peux essayer d'en faire une démonstration ce soir.
Je conjecture que l'ensemble des valeurs bien formées est l'ensemble des séquences ayant les caractéristiques ci-dessus. Prouver qu'il est inclu dedans est assez simple, mais je ne vois pas comment démontrer l'autre inclusion, même si je ne trouve pas de contre-exemple a priori. Bah, il faudra peut-être se contenter d'une définition plus compliquées de l'ensemble d'arrivée...

#. Message de Gork le 23-04-2006 à 23:18	81052 - ( )
Pays: France Inscrit le : 17-12-2003 Messages: 646 (Shaï Epileptique)	Citer

Ca doit marcher comme ça :

E_0 = {0;1}
E_1 = E_0 U U_{n app N} ( + {0;1}^n + 1 + ) [ + : produit carthésien]

E_{k+1} = E_k U U_{n app N} ( + E_k^n + E_k\{0} + )

On construit ainsi une suite d'ensemble croissante au sens de l'inclusion et l'union de tous les E_k est l'ensemble d'arrivée.

En fait, la construction donne une bijection de P_k dans E_k où P_k est l'ensemble des entiers codés par E_k. C'est une bijection car on peut "décoder", c'est à dire "définir" l'application inverse. La construction de l'application inverse est simple : On la définit sur E_0 puis par récurence sur E_k (difficile d'en dire plus sans tout dévoiler)

Ensuite, c'est assez facile de voir que U P_k = N : Si E_k contient tous les entiers inférieurs à f(k), alors E_k+1 contient tous les entiers inférieurs à f(k)+1 (il contient même bien plus en fait, mais ça suffit : E_1 contient 0 et 1, donc E_k contient tous les entiers inférieurs ou égaux à k)

Donc on a finalement une bijection de N dans U E_k

La description que Garffon donne de l'ensemble d'arrivée semble correcte. Pour prouver l' "autre" inclusion, il suffit de "décoder" (probablement une récurence sur le nombre maxi de paires de parenthèses emboitées)

Voili voilo

#. Message de Rand Al Troll le 24-04-2006 à 16:59	21003 - Rand Al'Troll (Kastar 43) - Teubreu -
Pays: France Inscrit le : 14-11-2003 Messages: 236 (Golem Costaud)	Citer

Tilk: tu pourrais me marquer Rand au lieu de Fly ? Pasque ya surement des trolls qui s'appellent fly et puis c'est moi qui est trouvé et pas eux

#. Message de TilK le 24-04-2006 à 17:14 [MH Team] [Maître Outilleur] [Ami de MountyHall]	36216 - mini TilK (Kastar 49) - Teubreu -
Pays: France Inscrit le : 06-12-2002 Messages: 8352 (Hydre Fumante)	Citer

Voila c'est corrigé

et voila comment j'aurais exprimé l'ensemble d'arrivée récursivement :

Ea = {0} U {1} U {x \ Il existe n appretenant à N+ tel que x appartient Ea^n}

#. Message de Gork le 24-04-2006 à 23:57	81052 - ( )
Pays: France Inscrit le : 17-12-2003 Messages: 646 (Shaï Epileptique)	Citer

Ca sent la définition "informatique", ça

C'est une jolie définition, parce que synthétique, mais :

1) Où sont les parenthèses ? Celà dit, on peut les rajouter sans trop compliquer les choses...

2) Ea n'est pas défini de manière unique par ton égalité, Tilk. Par exemple, si on pose Ez = l'ensemble de TOUS les mots construits sur l'alphabet { 0 ; 1 ; ( ; ) } et commençant par ( et se terminant par ), auquel on rajoute les mots 0 et 1, eh bien Ez vérifie l'égalité par laquelle tu définis Ea, sans pour autant être égal à Ea. C'est un petit peu génant... Pour s'en "tirer", il suffit de préciser que Ea est le plus petit ensemble (au sens de l'inclusion) vérifiant cette égalité (ce qui doit être implicite dans les langages de programmation qui autorisent ce genre de définition) et ensuite vérifier qu'un tel plus petit ensemble existe (c'est facile, car l'intersection de deux ensembles vérifiant cette égalité la vérifie encore)

Celà dit, même avec ces "nuances", ça reste un joli moyen d'exprimer Ea

Edit : tiens tiens, Encore une petite amélioration de mountyzilla

(dans le profil... : Il restera XXX PXs)

#. Message de Garffon le 25-04-2006 à 00:35	43658 - Garffon (Tomawak 39) - RELAIS&MAGO -
Pays: France Inscrit le : 07-08-2004 Messages: 424 (Golem Costaud)	Citer

Sauf qu'avec cette définition, (0 0) appartient aussi à Ea, même avec tes restrictions... Ce qui va compliquer encore la définition si on cherche à régler ce problème. Au final, j'ai peur qu'elle ne soit plus aussi élégante.

#. Message de Gork le 25-04-2006 à 09:28	81052 - ( )
Pays: France Inscrit le : 17-12-2003 Messages: 646 (Shaï Epileptique)	Citer

Ah oui, bien vu, il y a aussi ce pb :/

Ea, le plus petit ensemble Z vérifiant :

Z = {0} U {1} U { x / il existe n>=0, x app "("+Z^n+Z\{0}+")" }

avec + qui désigne une sorte de produit carthésien-concaténation (E+F : l'ensemble des mots formés comme la concaténation d'un mot de E et d'un mot de F)

Comme ça, ça marche, non ? En tout cas, j'ai l'impression (corrigez moi si j'ai faux).

Par rapport au Ea que tu proposes, Garffon, ça ne marche pas : (1)(1) n'est pas dans Ea mais vérifie les contraintes que tu as données.

#. Message de knacki le 25-04-2006 à 14:40	53597 - ( )
Pays: France Inscrit le : 30-12-2004 Messages: 2778 (Djinn Tonique)	Citer

Comme dit un pote de taff, ce serait pas la célèbre suite du sapin de Noël ?

0 ->            0
1 ->            1
2 ->           (1)
3 ->          (0 1)
4 ->          ((1))
5 ->        (0 0 1)
6 ->          (1 1)
7 ->       (0 0 0 1)
8 ->        ((0 1))
9 ->      (0 0 0 0 1)
10->      ((0 1 1))
11->   (0 0 0 0 0 1)
                     I I
                   I__I

Nan je déconne, m'en fout j'ai trouvé, nananère.

knacki, mode maternelle pourtant

#. Message de TilK le 25-04-2006 à 15:01 [MH Team] [Maître Outilleur] [Ami de MountyHall]	36216 - mini TilK (Kastar 49) - Teubreu -
Pays: France Inscrit le : 06-12-2002 Messages: 8352 (Hydre Fumante)	Citer

Gork : les () ne représente ici qu'un n upplet. C'est vrai par contre qu'il peut y avoir des 0 en trop :
Ea = {0} U {1} U {x \ Il existe n appretenant à N+ tel que x appartient Ea^n ^ x_n != 0}

Il peuvent être tous nul sauf le dernier (sinon je n'ai plus la bijection).

Et sinon (0)(0) appartient à Ez et ne respecte pas la définition de Ea.

On doit pouvoir montrer que Ea est unique par récurence sur la taille des éléments de Ea.
Taille(0)=1
Taille(1)=1
Taille( (x1 ... xn) )=1+Somme( Taille(xi) )

La taille d'un élément est donc strictement plus grande que la taille des éléments qui le constitue.

#. Message de Gork le 26-04-2006 à 10:12	81052 - ( )
Pays: France Inscrit le : 17-12-2003 Messages: 646 (Shaï Epileptique)	Citer

Tilk : ((0 1) 1) \neq (0 (1 1)) donc les parenthèses "comptent" [\neq : n'est pas égal]

Et sinon (0)(0) appartient à Ez et ne respecte pas la définition de Ea.

Si (au passage, c'est Ez qui doit vérifier une définition, pas seulement un de ses éléments). Ton égalité définit Ea comme un "point fixe", c'est à dire comme un ensemble vérifiant une égalité du type "x=f(x)". Il n'y a en général pas qu'une seule solution à ce type d'équation. Et le Ez que je propose est bien une solution de cette équation. Pour t'en persuader, tu n'as qu'à regarder l'égalité "à l'envers" :
{0} U {1} U {x \ Il existe n appretenant à N+ tel que x appartient Ez^n} est-il bien égal à Ez ? La réponse est "oui"...

En regardant ton équation, Ea n'est donc pas unique... sauf si - implicitement - tu recherches le plus petit ensemble vérifiant cette égalité.

En fait, j'ai l'impression que tu confonds le "=" des mathématiques (pour lequel a=b est complètement équivalent à b=a) et le "=" de l'informatique, qui sert souvent (pas toujours) à faire des affectations.

Je vais essayer d'être plus clair en prenant un exemple :

Soit V <- {0} U V+V
V est l'ensemble des mots ne contenant que des 0.
Il est vrai que {0} U V+V est égal à V, donc V = {0} U V+V

Mais maintenant, si on définit Vz = l'ensemble de tous les mots sur l'alphabet {0;1}, il est vrai aussi que Vz = {0} U Vz+Vz

Donc l'ensemble V n'est pas défini par l'égalité V = {0} U V+V

C'est un peu la même chose (en plus complexe) avec Ea et Ez.

Cela dit, je trouve que c'est intéressant de voir comme l'informatique tend à "simplifier" les concepts mathématiques. C'est surtout une question de formalisme, en fait. Il y a une sorte de "symbiose" qui peut se faire (et qui se fera probablement) entre le formalisme informatique, souvent efficace mais pas toujours complètement rigoureux, et celui des mathématiques, rigoureux mais parfois aussi un peu "lourd".

Edit : juste un petit rajout, pour bien préciser que le formalisme mathématique n'est pas la panacée (d'ailleurs, il évolue régulièrement).

Quand on écrit "2(x+5)=14" ou quand on écrit "2(x+5)=2x+10", on utilise le même signe "=" (ce qui peut se justifier, j'en conviens) alors qu'il serait probablement plus judicieux d'utiliser un = d' "affectation" dans le premier cas.

#. Message de TilK le 26-04-2006 à 10:51 [MH Team] [Maître Outilleur] [Ami de MountyHall]	36216 - mini TilK (Kastar 49) - Teubreu -
Pays: France Inscrit le : 06-12-2002 Messages: 8352 (Hydre Fumante)	Citer

Gork : je n'ai pas dit que les paranthèse ne comptait pas, j'ai dit qu'elles étaient implicites. Par exemple on note habituellement un 2-upplet (x,y), un 3-upplet (x,y,z)...

Or ici ((0 1) 1) = (x1,y1) app Ea^2 donc app Ea avec x1=(0,1) app Ea^2 et y1 app Ea^1
(Oui Ea^1 peut etre vu comme une abération mais il est facile de modifier le produit cartésien pour permettre cela)

Donc ((0 1) 1) != (0 (1 1)) car (0 1) != 0

Petite apperté sur l'informatique. Le symbole '=' n'existe pas dans les langages avec une sémantique forte : Il y a le ':=' pour l'affectation et le '==' pour l'égalité.

Pour le point fixe, je suis tout à fait d'accord, il peut y avoir plusieurs solutions mais il est facile de prouver que la solution est unique.

Or (0)(0) n'a aucun sens mathématique. Ce n'est pas un n-upplet

Par contre pour ton affirmation sur l'informatique, je te conseille de regarder pluis en profondeur tout ce qui touche aux langages formels et/ou à la sémantique des langages, tu verras que tout est bien défini mathématiquement.

#. Message de troll ki roule le 26-04-2006 à 11:12	46450 - ( )
Pays: France Inscrit le : 22-09-2004 Messages: 2159 (Djinn Tonique)	Citer

snip

je dis pas n importe quoi c est comme ca que j ai trouvé :p

#. Message de knacki le 26-04-2006 à 11:16	53597 - ( )
Pays: France Inscrit le : 30-12-2004 Messages: 2778 (Djinn Tonique)	Citer

Paye ton SPOILER tkr

(en plus tu dis n'importe quoi)

knacki, m'en fout j'avais trouvé

#. Message de Gork le 26-04-2006 à 23:35	81052 - ( )
Pays: France Inscrit le : 17-12-2003 Messages: 646 (Shaï Epileptique)	Citer

3eme indice

la solution de contient que des '(', des ' ', des ')' et des 0 ou 1.

Dit comme ça, ça donne plutôt l'impression qu'on travaille avec des mots sur un alphabet avec 4 (5 ?) caractères que sur des n-uplets de n-uplets de n-uplets etc. C'est d'ailleurs la même impression qu'a eue Garffon (voir son premier post)... et ça complique légèrement la définition de l'ensemble d'arrivée.

Quant à mes cours de maitrise et de DEA, notament ceux de sémantique et de sémantique du parallélisme, je n'irai pas les relire : ça fait longtemps qu'ils sont à la poubelle, largement 10 ans en fait. Mais c'est vrai que le contenu y était tout ce qu'il y a de plus rigoureux. Maintenant, l'informatique est-elle toujours rigoureuse, j'en doute. Sinon, pourquoi tous ces bugs ? Enfin et pour conclure, je cherchais juste à faire avancer le sujet...

#. Message de TilK le 27-04-2006 à 08:31 [MH Team] [Maître Outilleur] [Ami de MountyHall]	36216 - mini TilK (Kastar 49) - Teubreu -
Pays: France Inscrit le : 06-12-2002 Messages: 8352 (Hydre Fumante)	Citer

Pas de pbm, c'est bien une petite discussion sur le sujet

Et sinon pour répondre à tes questions : Parce que dans la plupart des cas, ls problèmes rencontrés sont indécidables. Le code "prouvé" est encore très cher à faire et bien souvent ne peut etre que extremmement simple.

Un petit exemple : les organismes de certification demande à airbus de "prouver" le code critique embarqué dans leurs avions. Tout ce qu'ils ont pu obtenir comme résultat est que leur variable n'exploseront pas (qu'elles sont toujours bornées) et c'ets déja quelque chose...

#. Message de Gork le 27-04-2006 à 19:44	81052 - ( )
Pays: France Inscrit le : 17-12-2003 Messages: 646 (Shaï Epileptique)	Citer

OK dac

. Les variables qui n'explosent pas, ça permet aux fusées de ne pas exploser, après tout :/

Pour revenir à ce que je disais, il pourrait y avoir à mon avis interaction fructueuse entre les maths et l'info (cette interaction existe déjà, en fait et heureusement : ça prouve que les choses ne sont pas si cloisonnées). En particulier la double notation pour "=" que les matheux gagneraient à introduire dans leur formalisme. Dans l'autre sens, et pour les souvenirs que j'en ai, il arrive que les informaticiens ignorent des théorèmes de mathématiques qui pourraient leur être bien utiles.

#. Message de Solmyr le 29-04-2006 à 22:00	17704 - Solmyr (Durakuir 60) - Les Pilleurs des Ombres -
Pays: France (69 - Rhône) Inscrit le : 22-04-2004 Messages: 4715 (Djinn Tonique)	Citer

J'comprend rien.

Solmyr, qui va allé se coucher

#. Message de John-Baner le 29-04-2006 à 22:21	52220 - John-Baner (Tomawak 40) - Lés Trõlls Gnõns dé Põm' -
Pays: France (13 - Bouches-du-Rhône) Inscrit le : 09-07-2005 Messages: 1210 (Trõll de Compèt')	Citer

moi j'aimerai savoir si quelqu'un peut démontrer la chose suivante :

Cheval
_____ = 3.14 (3.14 = pie, en gros, mais les symboles grecs marchent pas là...)
Oiseau

Pages : 1, 2, [3], 4

Pour poster une réponse sur ce Forum, vous devez d'abord vous connecter

Si vous n'êtes pas encore enregistré, vous devez d'abord vous inscrire.

[ Contact : ] - [ Heure Serveur : 13:03:06 le 19/12/2025 ] - [ Page générée en 0.003 sec. ]