Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Algorithme de Sardinas-Patterson
Résumé
En théorie des codes, l'algorithme de Sardinas-Patterson permet de déterminer si une partie d'un monoïde libre est un code en temps polynomial. Il est nommé d'après August Sardinas et George Patterson, qui le publièrent dans un article de 1953.
On considère un monoïde libre . On appelle code à longueur variable ou code une partie de telle que le sous-monoïde engendré est libre. L'algorithme de Sardinas-Patterson prend en entrée un alphabet et une partie finie de et détermine si est un code.
L'objectif est de pouvoir transcrire un mot dans un alphabet en un mot dans l'alphabet en associant à chaque lettre de un nombre variable de lettres de , étant alors l'ensemble des codages des lettres de . On cherche alors à ce que ce code ne soit pas ambiguë. Par exemple, en code Morse, A est codé par .-, E par . et F par ..-.. Mais alors, ..-. peut être interprété comme EAE ou comme F. Le code Morse nécessite ainsi l'usage d'un autre caractère séparant les lettres.
Si et sont deux parties de , on pose . On note le mot vide. L'algorithme calcule les éléments de la suite d'ensembles définie par récurrence :
et
pour .
Si lors du calcul, on obtient un égal à un des précédents, alors est un code. Si l'un des contient , alors n'est pas un code.
Chacun des est une partie de l'ensemble des facteurs des éléments de . Or est fini, donc l'ensemble des facteurs de ses éléments est fini (dans un monoïde libre, chaque élément ayant un nombre fini de facteurs), donc l'ensemble des parties de cet ensemble est fini. Par conséquent, des termes de la suite se répètent. L'algorithme s'arrête donc nécessairement.
La correction de l'algorithme s'énonce comme suit.
Théorème. n'est pas un code si, et seulement si l'un des contient .
Démonstration.
(⇒) Supposons que n'est pas un code. Si , alors . Sinon, on dispose de et égaux avec et deux suites d'éléments de telles que . On peut voir ce mot comme un segment, par exemple :
A0B0-----------------A1--------B1---------B2-----A2-----------------B3---------A3B4
Les lettres en majuscules notent des positions dans le mot, de manière que , et ainsi de suite et de même pour les , avec les crochets notant le facteur délimité par les deux positions.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.