Algorithme des chaînes de Markov

L'algorithme des chaînes de Markov permet de traiter ce type de problèmes. L'entrée est vue comme une séquence de phrases se recouvrant. Une phrase est composée de deux parties : un préfixe de plusieurs mots et un suffixe, le mot unique qui suit le préfixe. L'algorithme produit un texte en choisissant aléatoirement un suffixe parmi ceux associés au préfixe dans le texte original.

Dans notre cas, un préfixe de deux mots produit un résultat correct [Réduire la taille du préfixe tend à produire des textes moins cohérents, augmenter cette taille tend à reproduire plus/trop exactement le texte d'entrée.]. L'algorithme peut être décrit de la manière suivante :

soient w_1 et w_2 les deux premiers mots du texte ;
afficher w_1 et w_2 ; 
forever do
    choisir aléatoirement w_3 parmi les successeurs du préfixe w_1 w_2 ; 
    afficher w_3 ;
    remplacer w_1 et w_2 par w_2 et w_3 ;
done

On définit un mot de la manière suivante. Un mot est une suite de caractères alphabétiques. Les mots sont séparés par des espaces. On laisse la ponctuation attachée aux mots : « mot » et « mot. » sont des mots différents [Ainsi le texte généré sera ponctué. Cependant, cette approche peut produire des textes mal ponctués : parenthèse non concordante, guillemets incorrects, etc.].

Exemples

Soit le « texte » suivant :

aa bb cc dd ee aa bb dd ee cc dd aa bb ee (fin)

Les phrases de ce texte sont les suivantes (étudiez par exemple les apparitions du préfixe aa bb dont les suffixes sont soulignés dans le texte) :

Préfixe :	Suffixes possibles :
`aa bb`	`cc`, `dd`, `ee`
`bb cc`	`dd`
`cc dd`	`ee`, `aa`
`dd ee`	`aa`, `cc`
`ee aa`	`bb`
`bb dd`	`ee`
`ee cc`	`dd`
`bb ee`	(fin)

Le texte généré débutera par aa bb, l'algorithme choisira ensuite un des suffixes parmi cc, dd, et ee. Si dd est choisi, le préfixe courant devient bb dd et on choisira ensuite nécessairement ee. Le préfixe courant est alors dd ee et on pourra choisir aa ou cc. La génération se poursuit ainsi jusqu'à ce que le texte produit soit assez long ou que le marqueur de fin ait été généré.

Le texte suivant a été généré à partir d'anciens sujets d'examen :

La commande Bourne-shell entry qui affiche le nom est passé en paramètre sous la forme du code Bourne-shell qui, à partir d'une arborescence originelle et d'un fichier non défini comme une nouvelle version. Les options -C et -D spécifient d'utiliser les commandes précédentes ont été positionnées en conséquence. Donnez le code Bourne Shell de l'algorithme proposé à la question ont été appliquées. Vous ferez figurer les partitions. Donnez une liste de variables d'environnement de modifier la configuration de MC. Il définit entre autres la variable PATH est gênante. Expliquer en quoi il est intéressant que les répertoires.

Le texte suivant a été généré à partir de Bouvard et Pécuchet de Gustave Flaubert.

De temps à autre, il lâchait un juron puis, sur un tabouret. Pendant dix minutes, ils demeurèrent dans cette intolérable odeur, une odeur féroce et comme ils parlaient des menhirs et des bandes traînaient sur la manière d'une lanterne magique. Ses personnages, alertes comme des pains de sucre, tenus en l'air -- pas davantage ! Celle de Victorine était généralement unie, marque de décadence.

Architecture de nos développements... donc de l'examen

Nous allons développer une commande ecrivain en C. Afin de tester cette commande, nous développerons en Bourne-shell une commande test-ecrivain.