velikost textu

New Bounds for Combinatorial Problems and Quasi-Gray Codes

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
New Bounds for Combinatorial Problems and Quasi-Gray Codes
Název v češtině:
Nové Odhady pro Kombinatorických Problémů a Kvazi-Grayových Kódů
Typ:
Disertační práce
Autor:
Debarati Das, Ph.D.
Školitel:
doc. Mgr. Michal Koucký, Ph.D.
Oponenti:
Virginia Vassilevska Williams
Ely Porat
Id práce:
85391
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Informatický ústav Univerzity Karlovy (32-IUUK)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
6. 6. 2019
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova v angličtině:
Boolean matrix multiplication, Combinatorial lower bounds, Edit distance, Pattern matching, Graph algorithm, Quasi-Gray code
Abstrakt:
ABSTRAKTNÍ: Tato práce má dvě části. V první části studujeme řadu kombinatorických problémů souvisejících s řetězci, Booleovskými maticemi a grafy. Pro dané dva řetězce x a y je jejich editační vzdálenost nejmenší počet operací vložení znaku, smazání znaku a náhrada znaku, které jsou potřeba na přeměnu řetězce x na y. V této práci předkládáme algoritmus, který spočítá konstantní aproximaci editační vzdálenosti vpravdě sub-kvadratickém čase. S využitím těchto myšlenek zkonstruujeme další sub-kvadratický algoritmus, který umí nalézt výskyty vzoru P v zadaném textu T , když hledáme i výskyty s malou editační odchylkou. Dále studujeme problém násobení Booleovských matic (BMM) nad Booleovským polo-okruhem. Pro tento problém zavedeme dva kombinatorické výpočetní modely√a ukážeme, že v těchto √ modelech BMM vyžaduje Ω(n3/2O( log n)) a Ω(n7/3/2O( log n)) práce. Dále též představíme konstrukci řídkého pod-grafu, který zachovává vzdálenost určitého vrcholu od všech ostatních, ikdyž dojde k celkovému navýšení cen hran o kon- stantu. V druhé části práce studujeme efektivní konstrukci Grayových kódů. Ukážeme konstrukci prostorově optimálních kódů nad abecedou liché velikosti se složitostí čtení 4 logm n. Navíc sestrojíme kvazi-Grayovy kódy délky 2n − 20n nad binární abecedou se složitostí čtení 6 + logn. 1
Abstract v angličtině:
ABSTRACT: This thesis consists of two parts. In part I, a group of combinatorial problems pertaining to strings, boolean matrices and graphs is studied. For given two strings x and y, their edit distance is the minimum number of character insertions, deletions and substitutions required to convert x into y. In this thesis we provide an algorithm that computes a constant approximation of edit distance in truly sub-quadratic time. Based on the provided ideas, we construct a separate sub- quadratic time algorithm that can find an occurrence of a pattern P in a given text T while allowing a few edit errors. Afterwards we study the boolean matrix multiplication (BMM) problem where given two boolean matrices, the aim is to find their product over boolean semi-ring. For this problem, we present two√ combinatorial models and show in these models BMM requires Ω(n3/2O( log n)) √ and Ω(n7/3/2O( log n)) work respectively. Furthermore, we also give a construction of a sparse sub-graph that preserves the distance between a designated source and any other vertex as long as the total weight increment of all the edges is bounded by some constant. In part II, we study the efficient construction of quasi-Gray codes. We give a construction of space optimal quasi-Gray codes over odd sized alphabets with read complexity 4 logm n. Moreover, this part also presents a construction of quasi- Gray codes of length 2n − 20n over binary alphabet set with read complexity 6 + log n. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Debarati Das, Ph.D. 1.55 MB
Stáhnout Abstrakt v českém jazyce Debarati Das, Ph.D. 107 kB
Stáhnout Abstrakt anglicky Debarati Das, Ph.D. 105 kB
Stáhnout Posudek vedoucího doc. Mgr. Michal Koucký, Ph.D. 137 kB
Stáhnout Posudek oponenta Virginia Vassilevska Williams 92 kB
Stáhnout Posudek oponenta Ely Porat 474 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Jaroslav Nešetřil, DrSc. 153 kB