Langage de programmation

Discutez d'informatique ici !
abcd22
Membre Complexe
Messages: 2426
Enregistré le: 13 Jan 2006, 16:36

par abcd22 » 20 Oct 2007, 19:28

lapras a écrit:On a des personnes qui ne peuvent parler que avec trois syllabes (qu'on note 'A', 'B' et 'C').
mais ils ne peuvent pas faire de répétition.
Par exemple
ABAB
est interdit
ou bien
ABCABC
est interdit
AA est interdit

etc..
je dois démontrer qu'il y'a une infinité de mots.

Mais c'est trop dur mathématiquement, on doit donc le faire avec un algo qui te sort les mots possibles pour la longueur que tu veux.
Mais cet algo a besoin des mots de la longueurs (i-1) pour faire un mot de la longueur i

Dans ce cas ce n'est pas la peine de continuer à chercher dans cette voie car même si ton programme trouve des mots de longueur 10000000000000000000000000000000000000...0000000000000000000000000 (ce qui m'étonnerait car ça demandera effectivement beaucoup d'espace disque pour stocker tous les mots de longueur i donnée, et beaucoup de temps de calcul pour vérifier qu'il n'y a pas de répétition en calculant ceux de longueur i+1, l'ordinateur risque de saturer avant), ça ne suffira pas à prouver qu'il existe une infinité de mots, l'ordinateur ne calculera toujours qu'un nombre fini de mots. Si la solution est effectivement à trouver en faisant un programme informatique, ce n'est pas le calcul systématique de tous les mots de longueur i qu'il faut faire.
À mon avis si on veut une vraie démonstration (et pas juste « il y a des mots de longueur i pour i < 100000000 donc il doit y avoir une infinité de mots » qui est le résultat que tu obtiendrais avec ton programme) il faut la faire mathématiquement, soit en montrant que s'il existe des mots de longueur i alors il y en a de longueur i+1 (ce qui revient à montrer que le programme que tu veux faire tournerait indéfiniment), soit par l'absurde, mais je n'ai pas cherché.



lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 14:00

par lapras » 20 Oct 2007, 19:35

la démonstration mathématique est tres(trop) poussée
(le probleme est ouvert)
On va donc se contenter de lister des mots pour n'importe quelle longueur !
Montrer que le programme n'a pas de raisons de s'arreter ca revient à faire une démo de maths, c'est trop compliquée pour nous :triste:
Et puis même , je veux observer le comportement du programme : comment sont les mots, remarquer des trrucs, faire des conjectures.
Si le programme me sort des mots de longueur 100 ca sera déja vraiment bien ! :happy2:

emdro
Membre Complexe
Messages: 2351
Enregistré le: 11 Avr 2007, 18:37

par emdro » 20 Oct 2007, 19:58

Bonjour,

Je n'arrive pas bien à saisir ce que tu appelles "sans répétition".
Si tu as ABACA, tu peux ajouter un B bien que la séquence AB figure au début? Elle est en quelque sorte annulée par le AC intermédaire?

Et dans ce cas, on peut mettre ABACAB, et là je pourrai mettre un A car ABA sera isolé du premir ABA par un C?
Et j'aurai ABACABA, mais là je ne pourrai pas mettre de C (à cause de ABAC), ni ce B (à cause de AB) ni de A évidemment.

C'est cela?

abcd22
Membre Complexe
Messages: 2426
Enregistré le: 13 Jan 2006, 16:36

par abcd22 » 20 Oct 2007, 20:01

Donc tu ne dois pas « démontrer qu'il y a une infinité de mots » comme tu l'as écrit plus haut (au passage cette formulation implique qu'on sait qu'il y en a une infinité et que ce n'est donc pas un problème ouvert au sens utilisé dans l'enseignement supérieur (i.e. dont on ne connait pas la réponse), dans le secondaire problème ouvert est parfois utilisé pour parler d'un problème où les élèves ne sont pas tenus par la main, en lisant tes messages j'ai du mal à savoir dans quel sens tu utilises ce mot), mais seulement lister les mots d'une longueur donnée qui vérifient cette propriété, ça change beaucoup l'énoncé !

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 14:00

par lapras » 20 Oct 2007, 20:01

c'est exactement ca emdro ! :++:

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 14:00

par lapras » 20 Oct 2007, 20:05

abcd :
Il existe une démonstration, mais elle est tres tres compliquée (en tout cas les profs de Maths.en.jeans ont dit que c'était monstrueusement complexe)
Donc c'est pas un probleme ouvert, désolé,mais c'est notre probleme au club Maths.en.jeans du lycée.

gol_di_grosso
Membre Irrationnel
Messages: 1402
Enregistré le: 22 Sep 2007, 13:28

par gol_di_grosso » 20 Oct 2007, 20:06

ca rappelle les automates d'état fini ton truc

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 20 Oct 2007, 21:06

lapras a écrit:Non, mais tu peux rajouter un A :++:

ABCABC est interdit mais ABCABCAA l'est il ? L'enoncé est un peu flou a mon gout :)

Si ABCABCAA n'est pas interdit alors tu peux pas déduire les mots de longueurs i a partir des mots de longueur i-1. Et comme dit juste au dessus, regarde du coté des automates finis.

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 14:00

par lapras » 20 Oct 2007, 21:07

AA est une répétition !
Donc ce mot ne marche pas.

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 20 Oct 2007, 21:11

lapras a écrit:AA est une répétition !
Donc ce mot ne marche pas.


Et ABCABCAC ?

abcd22
Membre Complexe
Messages: 2426
Enregistré le: 13 Jan 2006, 16:36

par abcd22 » 20 Oct 2007, 21:27

Ah oui et sinon si tu veux juste garder la liste des mots de longueur i pour un seul i je pense qu'il vaut mieux les stocker sous forme de liste chaînée, chaque cellule contenant un mot et un pointeur vers la cellule suivante. Pour trouver les mots de longueur i+1 on commence par initialiser la liste des mots de longueur i+1 à null, puis on prend le premier mot de la liste des mots de longueurs i, on regarde ce qu'on peut lui ajouter comme caractère, on ajoute le ou les nouveaux mots à la liste des mots de longueur i+1, on supprime le mot traité de la liste des mots de longueur i et on continue avec le suivant. Tu n'as pas besoin d'avoir accès rapidement à tous les mots d'une longueur donnée mais seulement à 1 à la fois donc pas la peine de faire ça sous forme de tableau, les listes ont l'avantage d'être plus flexibles (pas besoin de déclarer une taille au départ), mais si on doit accéder aux derniers éléments ce n'est pas pratique.
Pour stocker les mots de toutes les longueurs inférieures à un n donné de façon plus compacte je verrais bien un arbre ternaire, je ne sais pas si ça apporte quelque chose au niveau du calcul des mots qu'on peut ajouter de voir l'ensemble des mots sous forme d'arbre.
Moi j'ai compris que si on note les lettres , il ne doit pas exister de k entre 1 et n et de p entier strictement positif tels que donc un mot ne peut pas être valide si un de ses sous-mots n'est pas valide (si ce n'est pas ça mon idée de stockage par arbre ne marche pas).

bruce.ml
Membre Rationnel
Messages: 630
Enregistré le: 19 Juin 2007, 01:54

par bruce.ml » 21 Oct 2007, 00:30

Il faudrait une définition exacte de ton ensemble de mots parce que là je ne comprends pas trop. ABC est incontinuable car tu ajoutes forcément une lettre qui est déjà dans le mot et donc tu la répêtes. L'ensemble dont tu parles est-il l'ensemble de tous les mots privé des mots du type : m.m.n où m et n sont des mots et . représente la concaténation des mots ?

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 14:00

par lapras » 21 Oct 2007, 10:10

Salut abcd, ton idée est bonne, un mot ne peut pas marcher si les mots de longueurs inférieur sont faux.
bruce :
Une syllabe est sybolisée par une lettre 'A', 'B' ou 'C'
je n'ai pas de définition exacte (j'ai pas la feuille du probleme), mais les répétitions sont comptées comme des répétitions si les deux groupes de syllabes répétés se "touchent"
ex :
ABCABC
les des 'ABC' se touchent
par contre :
ABCBABC
Il n'y a pas de répétition : les ABC sont séparés par un B, et les AB sont séparés par un 'BC'
de même les 'BC' sont séparés par un 'BA'
Donc ce mot est valide
pour avoir un mot d'une lettre de plus, on prend par exemple
ABCBABC
on ne peut ajouter que un A ou un B (pour ne pas faire une répétition de 'C')
en l'occurence si on ajoute un A et un B il n'y a pas de répétition
a part de ce mot on forme donc deux mots de longueur +1 :
ABCBABCB
ABCBABCA

On m'a parler du langage Haskell, je vais essayer de l'apprendre !
C'est un langage fonctionel pur ! :++:

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 21 Oct 2007, 12:40

[quote="lapras"][/quote]
J'avais cru comprendre mais si ABCBABCB est accepté je comprends plus.

Voila ce que j'ai compris :
Un mot de longueur i est un mot valide si et seulement si :
- Les premieres lettres forment un mot valide,
- si (resp. ) alors (resp. ) le mot allant de la lettre à la lettre est différent du mot allant de la lettre à .

Si c'est le cas alors :
ABCBABCB n'est pas valide comme tu le prétends.
La validation d'un mot se code tres facilement et en combinaison avec ce que dit abcd22 y a plus rien a faire et la premiere condition pour la validation d'un mot sera deja vérifiée puisque tu généres tes mots de longueur a partir de mot de longueur déjà valide.

Si c'est pour le faire en haskell, moi je dit fait le en O'Caml !

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 14:00

par lapras » 21 Oct 2007, 12:58

Désolé ABCBABCB n'est pas valide je n'avais pas vu la répétition des "ABCB"
Oui, pour ton interprétation mathématique, c'est comme ca que je le vois !
Oui pour valider un mot c'est simple, si on a des outils pour utiliser des listes, en C ca me semble tres dur !

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 21 Oct 2007, 13:04

lapras a écrit:Désolé ABCBABCB n'est pas valide je n'avais pas vu la répétition des "ABCB"
Oui, pour ton interprétation mathématique, c'est comme ca que je le vois !
Oui pour valider un mot c'est simple, si on a des outils pour utiliser des listes, en C ca me semble tres dur !


En C les listes c'est pas dur ... au pire fait le en C++ tu trouveras ton bonheur. Mais ce genre de truc je le ferais plutot en o'caml.
Et la validation d'un mot se fait sans les listes !!! Une chaine de charactere c'est deja un tableau de charactere !!! Pas besoin de stocker tes lettres dans une nouvelle structure tu peux deja acceder à la lettre ou au sous-mot de ton choix tres facilement.

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 14:00

par lapras » 21 Oct 2007, 13:05

En C tu as des listes ?
j'utilise que des tableaux pour stocker des caracteres, ca a l'air assez compliqué pour avoir des mot pour une certaine longueur ... :triste:

Patastronch
Membre Irrationnel
Messages: 1345
Enregistré le: 23 Aoû 2005, 01:53

par Patastronch » 21 Oct 2007, 13:06

lapras a écrit:En C tu as des listes ?
j'utilise que des tableaux pour stocker des caracteres, ca a l'air assez compliqué pour avoir des mot pour une certaine longueur ... :triste:


Voir ce que j'ai dit au dessus. Une chaine de charactere c'est du type char*, plus vulgairement ca veut dire que c'est un tableau de char.

Donc ce que je ferais si je devais programmer ca : une file pour le stockage des mots (et non une liste), t'enfile chaque nouveau mot valide dans cette file et tu désenfile un mot pour générer les mots d'une lettre deplus a partir de ce mot, et ces mots tu les réenfile etc. Faut juste initialiser la file avec tous les mots d'une lettre possible.

Et pour la validation d'un mot une petite boucle avec les contraintes que je t'ai filé (pas besoin de vérifier la premiere pusique tes mots sont généré apartir de mot deja valide) sur ton mot et voila c'est torché. T'as juste a prévoir une bonne condition d'arret si tu veux avoir dans ta file que les mots d'une certaine longueur. Par exemple tu veux les mots de longueur 4, alors au moment ou tu désenfile un mot de longueur 4 tu le réenfile et t'arretes l'algorithme. Et dans ta file tu auras tous les mots de longueur 4.

Si à un moment ta file est vide, c 'est qu'il existe une certaine longueur pour laquelle il n'existe aucun mot et donc le nombre de mots possible n'est pas infini.

lapras
Membre Transcendant
Messages: 3664
Enregistré le: 01 Jan 2007, 14:00

par lapras » 21 Oct 2007, 15:03

mais qu'entends tu par "file" ?

abcd22
Membre Complexe
Messages: 2426
Enregistré le: 13 Jan 2006, 16:36

par abcd22 » 21 Oct 2007, 15:46

C'est une structure de données où le premier arrivé est le premier à sortir, par opposition aux piles où le dernier arrivé est le premier servi, les deux sont souvent implémentés en utilisant des listes, plus haut quand je parlais de listes c'étaient des listes utilisées comme des piles. Il y a des articles là-dessus sur wikipedia mais pas très détaillés, pour comprendre ce que c'est je pense qu'il vaut mieux regarder un vrai cours d'algorithmique avec plein de dessins de piles et de files, mais je n'en connais pas de disponible sur internet...

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 7 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite