Projet de théorie de l'information (M1 Informatique)

Implantation de Sardinas-Patterson

Marie-Pierre Béal et Samuele Giraudo

Modalités

Le projet sera écrit dans le langage de votre choix et réalisé par binômes. Une archive ZIP devra être envoyée avant le lundi 21 janvier 2013 (date à confirmer) à beal@univ-mlv.fr et giraudo@univ-mlv.fr. L'archive doit être nommée Nom1Nom2.zip où Nom1 et Nom2 sont les noms des deux membres du binôme. Celle-ci devra contenir, outre les sources, un document user.pdf au format PDF contenant une notice d'utilisation et un document dev.pdf au format PDF décrivant l'architecture du projet ainsi que des tests éventuels. Ces documents ne seront pas nécessairement très longs.

Description du mini projet

L'objectif du projet est de programmer l'algorithme de Sardinas-Patterson étudié en TD qui teste si un ensemble fini de mots est un code. Le programme prendra en entrée un fichier qui aura le format décrit par l'exemple suivant :

{0, 01, 10}
{aba, bb}
{baa, 0ab, 010}

Chaque ligne du fichier contient donc un ensemble de mots sur lequel on applique le test de Sardinas-Patterson. Le programme traite les ensembles spécifiés par chacune des lignes du fichier et affiche pour chacun s'il est un code ou non. Sur l'exemple, on obient donc :

non
oui
oui

En outre, si l'exécutable se nomme SardinasPatterson et le fichier Ensembles, ce résultat doit être obtenu par la commande

./SardinasPatterson Ensembles

Amélioration facultative

En option, lorsque l'ensemble de mots n'est pas un code, on affichera un découpage multiple d'un mot. Par exemple, avec l'exemple précédent, on aura l'affichage :

non : (0)(10) = (01)(0)
oui
oui