Bonjour, si on considère deux événements : a et b, et qu'on essaye de former des "épisodes" de taille 3 avec a et b, par exemple :

- aba (qui signifie il y a eu "a", puis "b", puis "a"), mais aussi par exemple :

- a{ab} = a{ba} (qui signifie il y a eu "a" puis "a et b en même temps")

De combien de façons différentes peut on former d'épisodes de taille n avec k événements ?

(Dans notre exemple la solution entière serait :
-aaa
-aab
-aba
-baa
-abb
-bab
-bba
-bbb
-{ab}a
-a{ab}
-{ab}b
-b{ab}
mais dans le cas général ?..)

C'est juste une question que je me demandais donc pas super important mais si quelqu'un sait

Ah oui, et imaginons qu'on veuille l'ensemble des épisodes de taille n tels que l'épisode A de taille n-1 n'est le sous-épisode d'aucun de ces épisodes.
(a{ab}c est sous épisode de ad{abd}dcd pour exemple, ça devrait suffire à comprendre l'idée sinon je donne un truc formel)

Comment générer de tels épisodes de taille n (avec un algorithme et prouver que l'algorithme marche) ?

C'est pas exactement ça mais ça me fait penser au dénombrement des parenthésages avec les nombres de Catalan.

La séquence a{ab{ab}a}b est elle valide?
Si oui il y a Cn*k^n épisodes de taille n contenant au maximum k caractères différents, avec Cn le nième nombre de Catalan (Cn=1/(n+1)*(n parmis 2n))
Sinon c'est moins classique, là comme ça j'ai pas d'idée, ça me semble audacieux de faire du dénombrement pur

Moi aussi j'ai pensé aux nombres de Catalan

La séquence a{ab{ab}a}b est elle valide?

Eh non

Ca vient d'un truc "concret" (temporal pattern mining) donc voilà, faut que le truc ait du sens "réel"

Considérons une liste de n éléments et dénombrons le nombre de concaténation différente possibles
Il y a n-1 endroits ou l'on peut "couper" la liste
Il y a donc 2^(n-1) concaténation différente possible
Maintenant il ne reste plus qu'à choisir les caractères de la liste, si on a le choix entre k caractères il y a k^n listes différentes

Il y a donc 2^(n-1)*k^n épisodes différents, si je me trompe pas

Ah mince, a et a ne peuvent pas se produire ne même temps, c'est faux ce que je raconte

T'en as moins que ça parce que par exemple {aa}b ça existe pas, si j'ai bien compris.

Voilà

Le 17 mars 2018 à 19:32:19 PTSI-PT a écrit :
Ah mince, a et a ne peuvent pas se produire ne même temps, c'est faux ce que je raconte

Exact, on peut pas

Pas évident du coup

Il faut peut-être partir dans l'autre sens. Compter le nombre de mots de n lettres qu'on peut faire avec k lettres, puis voir quelles sont les parenthèses qu'on peut ajouter. T'as essayé de voir ce que ça donne si on passe de n à n+1 (pour voir si y'a une récurrence sympa) ?

Le 17 mars 2018 à 19:38:58 Prauron a écrit :
Il faut peut-être partir dans l'autre sens. Compter le nombre de mots de n lettres qu'on peut faire avec k lettres, puis voir quelles sont les parenthèses qu'on peut ajouter. T'as essayé de voir ce que ça donne si on passe de n à n+1 (pour voir si y'a une récurrence sympa) ?

En fait c'est même mon véritable but de comprendre comment passer des épisodes de taille n à n+1 !
Disons qu'on enlève des épisodes de taille n (on veut pas qu'ils soient sous-épisode de taille n+1), on obtient alors une liste d'épisodes de taille n et tout ce que je sais c'est que si on a par exemple :

1{23}4 et {23}{45}, on pourra former 1{23}{45}
Si on a 1{23}4 et {23}45, on pourra former 1{23}45 ..

En d'autres termes il faut : vérifier que le mot1 (sans les parenthèses donc, et donc on peut former plusieurs mots à partir d'un épisode) élaguée de sa première lettre soit le préfixe du mot 2

Je sais ni pourquoi ça marche ni en quoi ça formerait l'ensemble des épisodes de taille n+1 ça me fout le tournis, enfin bon c'est pas si important si la réponse n'est pas that simple abandonnons

Étant donné un mot donné de taille n, avec k lettres tu peux:

• rajouter une lettre, il y a k possibilités, t'obtiens un mot de taille n+1
• rajouter deux lettres simultanées, il y a (2 parmi k) possibilités, t'obtiens un mot de taille n+2
• ...
• rajouter k lettres simultanées, il y a (k parmi k) possibilités, t'obtiens un mot de taille n+k

Ça fait Un = somme des (i parmi k) * U(n-i), je sais pas si ça t'avance.

C'est marrant j'ai des trucs assez similaires dans mon travail, pour parler de programmes concurrents où des processus (=les lettres) peuvent s'exécuter séquentiellement ou simultanément. {aa} n'a pas de sens puisque ça représenterait le processus 'a' en parallèle avec lui-même. Par contre j'ai des chevauchements plus complqués, genre « a commence, b commence, b termine, c commence, c termine, a termine », où a est en parallèle avec b et avec c, mais b est avant c. Si jamais ce genre de considération est pertinente pour toi, des structures utiles sont celle de pomset (ordre partiel avec labels), ou encore d'interval order.

Il y a plus de cas que ça, si on ajoute b à aaa on peut construire l'épisode aa{ab} qui n'est pas pris en compte par ton dénombrement

Il est obtenu en ajoutant {ab} à aa