• Show simple item record
• Show full item record
• PBN data

select style... apa harvard chicago-fullnote-bibliography ISO-690

Bibliographic description



title:	Izomorficzne podstruktury w słowach i permutacjach
alternative title:	Isomorphic substructures in words and permutations
author:	Gawron Maciej
reviewer:	Grytczuk Jarosław , Bosek Bartłomiej
advisor:	Grytczuk Jarosław
date of submittion :	2014-10-16
language:	Polish
abstract in Polish:	Tematem pracy są izomorficzne podstruktury w strukturach kombinatorycznych, które w skrócie nazywać będziemybliźniakami. Interesuje nas problem znajdowania maksymalnych dwóch rozłącznych podstruktur w danej strukturze, które są izomorficzne. Problem ten był szeroko omawiany dla grafów. Praca skupia się na rozważaniu analogicznego problemu dla słów oraz permutacji. Rozdział pierwszy dotyczy problemu bliźniaków w słowach, zarówno z teoretycznego jak i algorytmicznego punktu widzenia. Główne wyniki tego rozdziału pochodzą z pracy Axenovich, Persona i Puzyniny . Pokazano między innymi zaskakującetwierdzenie , że w słowie długości $n$ znajdziemy bliźniaki długości n/2-o(n). Dowód twierdzenia zapewnia algorytm znajdujący bliźniaki tej długości, w rozdziale załączono implementację tego algorytmu. Rozdział drugi poświęcony jest problemowi bliźniaków w permutacjach. Podano dolne i górne ograniczenia na długość bliźniakóww dowolnej permutacji zbioru n-elementowego. Głównymi narzędziami w dowodzie są twierdzenie Erdosa-Szekeresa, lemat lokalnyLovasza oraz metoda probabilistyczna. Zaimplementowane zostały również algorytmy wyszukujące bliźniaki w permutacjach.
abstract in English:	The main topic of the thesis are isomorphic substructures in words and permutations. We call them twins. We are interested infinding two maximal disjoint substructures in given structure. This problem has a long history for graphs. We investigate thisproblem for words and permutations.In Chapter one we consider twins in words form both theoretical and algorithmic point of view. The main results of this chapterare theorems of Axenovich, Person and Puzynina. They showed surprising theorem about maximal twins in word of lenth n. Moreprecisely they showed that in each word of lenth n there are twins of length at least n/2-o(n). Proof of this theorem gives an algorithm for finding such twins. We have implemented this algorithm.In Second Chapter we consider twins in permutations. We give lower and upper bound on length of twins in permutations of theset 1,2,...,n. The main tools which we used are Erdos-Szekeres theorem, Lovasz local lemma and probabilistic method. We alsoimplemented some algorithms which finds twins in permutations.
keywords in Polish:	słowo, permutacja, bliźniaki w słowach, bliźniaki w permutacjach
keywords in English:	word, permutations, twins in words, twins in permutations
affiliation:	Wydział Matematyki i Informatyki
type:	master work

This item appears in the following Collection(s)

• Prace magisterskie
  
• ROD UJ