|
|
New Bounds for Combinatorial Problems and Quasi-Gray Codes
Das, Debarati ; Koucký, Michal (vedoucí práce) ; Vassilevska Williams, Virginia (oponent) ; Porat, Ely (oponent)
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í...
|
host ::
RSS.