Algorithms for code decipherability verification

Celem pracy magisterskiej jest porównanie algorytmów Sardinasa - Pattersona i algorytmu zaprezentowanego w pracy „Directected figure codes are decidable” autorstwa mgr M. Kolarza oraz dr W.Moczurada. Algorytm Sardinasa-Pattersona to klasyczny algorytm, który pracuje w czasie wielomianowym, i sprawdza czy dany kod na słowach o zmiennej długości jest jednoznacznie dekodowany. Algorytm "poliominowy" dotyczy pewnych struktur, zwanych figurami skierowanymi. Figury skierowane są uogólnieniem słów.Rozdział drugi tej pracy jest o kodach zmiennej długości. On zawiera definicji oraz twierdzenia, które służą do zdefiniowania algorytmu Sardinasa - Pattersona. W rozdziale trzecim przedstawiono wstęp do figur skierowanych. Oraz został opisany warunek, przy którym skierowana figura jest kodem. I podany algorytm, który sprawdza czy wejściowy zbiór figur skierowanych jest kodem. Oraz został podany pseudokod algorytmu. W rozdziale czwartym opisana złożoność czasowa algorytmu Sardianasa – Pattersona i algorytmu „poliominowego” oraz przedstawione przykłady, które pokazują podobieństwo algorytmów. Rozdział piąty zawiera krótkie podsumowanie tej pracy.

The aim of the thesis is compare the algorithm Sardinas - Patterson and the algorithm presented in the work "Directed figure codes are decidable" by M. Kolarz and W.Moczuradad. Sardinas-Patterson algorithm is a classic algorithm that checks whether the code on the words of variable length is unambiguously decoded. Algorithm for directed figure refers to certain structures, called directed figures. Directed figures are generalization of words.The second chapter of this work is an introduction to the theory of variable length codes. It contains definitions and theorems, which are used to define the algorithm Sardinas - Patterson. The third section gives an introduction to the directed figures. And was described conditions, when the directed figure is code. And given algorithm, which checks whether an input set of directed figures is code. And was given a pseudo code of the algorithm. In the fourth chapter described time complexity of the algorithm Sardianas - Patterson and algorithm for directed figures and presented examples that show similarity of this algorithms.The fifth chapter provides a brief summary of the work.