Langage de programmation

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: lapras

Bonsoir,
je cherche un langage de programmation permettant de manier les listes et les tableaux tres tres facilement, tout en étant rapide (aussi rapide que le C au moins).
je travaille sur un probleme de maths (ouvert) et je dois explorer des listes contenant des chaines de caracteres.
En gros, (tres tres gros), je veux faire un "tableau" qui serait organisé comme ceci :
Nombre de caracteres : i
caractere possible [1] : ABCAB[....]
caractere possible [2] : ....
etc...
Vous voyez ce que je veux dire ?
Malheureusement, c'est difficile en C de faire ca... Quelqun pourrait me donner un langage qui serait adapté pour ce genre de manipulation ?
Et si possible, un langage qui a des tutos en français sur le net (ca c'est mon véritable probleme !)

Merci d'avance !
lapras


Posted by: gol_di_grosso

Citation:
Posté par lapras
Nombre de caracteres : i
caractere possible [1] : ABCAB[....]
caractere possible [2] : ....
etc...
Vous voyez ce que je veux dire ?

lapras

pas compris



Posted by: lapras

Désolé, je n'ai pas été assez clair.
En fait j'ai mots de longueurs i=1 jusqu'a i=n
par exemple un mot de longueur 1 : 'A'
Un mot de longueur 3 : 'ABC'
etcc...
Mais pour une longueur de mot i , j'ai plusieurs mots possibles
par exemple plusieurs mots possibles à i = 3 caracteres :
1. 'ABC'
2. 'ACB'
3. 'BCA'
etc...
(c'est pas un probleme tout bête de listage de combinaisons, je simplifie)
donc par exemple si je demande le mot de longueur i numéro 3 j'aurai :
'BCA'

C'est avec ce genre de manipes que je souhaite travailler


Posted by: gol_di_grosso

et le C c parfait
pourquoi ca va pas ?


Posted by: abcd22

Bonsoir,
En C on doit pouvoir faire ça avec un tableau de taille n dont chaque cellule contient un pointeur vers une liste chaînée, chaque cellule de la liste chaînée contenant une chaîne de caractère (un des mots de longueur i possible). Je ne sais pas s'il y a des langages qui permettent de faire ça plus simplement ni si c'est une bonne solution pour ce que tu veux faire (s'il y a i! mots de longueur i et que i peut être grand le temps d'accès aux derniers mots de la liste va vite augmenter...).


Posted by: lapras

Tu êux gérer en C des tableaux tels que
Tableau[i][n] = "CHAINE DE CARACTERE"
?
Je pense que ca n'est pas tres simple !
Apres je dois aussi explorer les caracteres de Tableau[i][n]
par exemple :
Tableau[i][5] = "ABC"
Je veux pouvoir sortir facilement (et surtout tres rapidement) la 2eme lettre de tableau[i][5] c'est à dire B


Posted by: gol_di_grosso

Citation:
Posté par lapras
Tableau[i][5] = "ABC"
Je veux pouvoir sortir facilement (et surtout tres rapidement) la 2eme lettre de tableau[i][5] c'est à dire B

tableau[i][5][2]='B' en caractère ou en code ascii je sais plus
Sinon :
ADA -> non (c'est une sorte de c un peu chiant)
C++ -> ba c pareil que le c
ocaml -> pas la peine
arf j'en connait pas d'autre je peux plus t'aider dsl


Posted by: abcd22

Quand on fait un tableau à plusieurs dimensions en C la deuxième dimension (et suivantes) doit être fixe, donc je ne pense pas que ça te convienne, il faut passer par des tableaux de pointeurs pour avoir des longueurs variables. Voir par exemple http://clips.imag.fr/commun/bernard...I_C/node63.html et pages suivantes. Peut-être qu'il y a des bibliothèques où les structures qu'il faut sont déjà décrites.
En fait si on fait un tableau de pointeurs vers des tableaux de pointeurs (vers les chaînes de caractères) on n'a pas le problème de temps d'accès dont j'ai parlé plus haut avec les listes.


Posted by: gol_di_grosso

ouai mais si la dernière dimension c'est un caractère on peut le caser entre 1 et 256 voir moins si on prend que des lettres non ?
le problème c'est que c'est la troisième dimension ici
sinon t'a pas moyen de connaitre la dimension de ton tableau avant ?
parce que tu peux le déclaré après avoir trouvé sa taille


Posted by: bruce.ml

Nan mais utilise O'caml :P c'est le meilleur langage du monde pour faire ce genre de choses. C c'est un langage voué à disparaitre, du moins dans sa forme actuelle ...


Posted by: gol_di_grosso

arf un fan
ce qui est bien avec caml c'est que les fonctions sont pas très compliquée en général mais bon y en a plein (pour ce que j'en ait fait => pas beaucoup)
puis y a la compilation "instantané" eee fonctionnel c'est ça ?


Posted by: abcd22

gol_di_grosso : Si on fait un tableau à taille fixe en prenant les plus grandes tailles nécessaires pour les 2e et 3e dimension ça risque de faire beaucoup de gaspillage de mémoire... et les tableaux de pointeurs ne sont pas beaucoup plus compliqués si on se donne un peu de mal pour apprendre à manipuler des pointeurs (je ne pense pas qu'on puisse faire grand chose en C si on ne connaît pas les pointeurs).


Posted by: bruce.ml

L'informatique c'est pas la science de faire des trucs super compliqués alors qu'on peut faire très simple, bien au contraire. 90% du temps que passe un informaticien devant son ordinateur, c'est pour débuger le code qu'il ne met que 10% de son temps à écire !!! alors autant faire du code simple dans un langage simple comme l'est ocaml.


Posted by: Joker62

Salut Emmanuel ;)
Tu pourrais rappeler ton problème de maths ouvert au passage !
J'me rapelle plus :(


Posted by: lapras

Salut David
Le dernier probleme ouvert dont je t'ai parlé samedi, on l'a résolu grace a l'informatique !
celui la c'est un nouveau :
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

Voila ne gros.
Bruce.ml : mon programme va donc prendre rapidement beaucoup beaucoup de place ?


Posted by: gol_di_grosso

et tu veux sauvegarder tout ça ou juste y afficher (là t'aurai pas besoin de sauvegarder dans un tableau)


Posted by: Joker62

On ne peut pas faire de répétition de mots ? ou de syllabes ?
Entre chaque mot on met un espace ?


Posted by: lapras

En fait je garderai en mémoire le tableau des mots de longueurs i-1
Les autres je les effacerai : aucune utilité vu que je veux les mots de longueur i.
non aucune répétition de mot, de syllabe, et pas d'espace entre les mots.
par exemple si on veut un mot de longueur 4, on prend un mot de longueur 3 et on voit si on peut lui ajouter un C, un A ou un B (on a trouvé qu'un exemple de mot où l'on ne peut rien rajouter)



Posted by: Joker62

Si on a par exemple ABCAB
On ne peut pas rajouter de C ?


Posted by: lapras

Non, mais tu peux rajouter un A


Posted by: abcd22

Citation:
Posté par lapras
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...000000000 0000000000000000 (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é.


Posted by: lapras

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


Posted by: emdro

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?


Posted by: abcd22

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é !


Posted by: lapras

c'est exactement ca emdro !


Posted by: lapras

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.


Posted by: gol_di_grosso

ca rappelle les automates d'état fini ton truc


Posted by: Patastronch

Citation:
Posté par lapras
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.


Posted by: lapras

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


Posted by: Patastronch

Citation:
Posté par lapras
AA est une répétition !
Donc ce mot ne marche pas.


Et ABCABCAC ?


Posted by: abcd22

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 a_1...a_n, il ne doit pas exister de k entre 1 et n et de p entier strictement positif tels que a_k = a_{k+p},\ \cdots,\ a_{k+p-1} = a_{k+2p-1} 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).


Posted by: bruce.ml

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 ?


Posted by: lapras

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 !


Posted by: Patastronch


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 i-1 premieres lettres forment un mot valide,
- si i\equiv 0[2] (resp. i\equiv 1[2]) alors \forall j&lt;i, j\equiv 1[2] (resp. j\equiv 0[2]) le mot allant de la lettre j à la lettre \frac{i+j-1}{2} est différent du mot allant de la lettre \frac{i+j-1}{2}+1 à i.

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 i a partir de mot de longueur i-1 déjà valide.

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


Posted by: lapras

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 !


Posted by: Patastronch

Citation:
Posté par lapras
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.


Posted by: lapras

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


Posted by: Patastronch

Citation:
Posté par lapras
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 ...


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.


Posted by: lapras

mais qu'entends tu par "file" ?


Posted by: abcd22

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


Posted by: lapras

Dommage
je vais essayer de regarder Ocaml quand même


Posted by: Patastronch

oups j'ai rien dit










-