|
| |
|
|
The Online Labeling Problem
Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Brodal, Gerth (oponent) ; Iacono, John (oponent)
Setříděné pole je zásadní algoritmický koncept, jehož online varianta je základem pro problém online labelingu. Problém online labelingu je definován následovně. Vstupem je pole velikosti m a posloupnost celých čísel z universa {1,...,r} v libovolném pořadí délky n. Naším úkolem je udržovat všechna přijatá čísla setříděná v poli. Mezi vloženými čísly mohou být mezery. Protože závěrečné pořadí čísel nelze určit, dokud nejsou vložena všechna, je povoleno čísla v poli přesouvat. Cílem je minimalizovat počet přesunů. Ukážeme dva algoritmy, které společně poskytují optimální řešení pro téměř všechny hodnoty m coby funkce n. Dokážeme těsné dolní odhady pro téměř všechny hodnoty m. Zavedeme notaci omezeného universa vstupní množiny čísel a dokážeme dolní odhady i pro tuto variantu. Dokážeme dolní odhady i pro případ randomizovaných algoritmů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Datové struktury pro setříděné ukládání dat
Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Kráľ, Daniel (oponent)
V předložené práci studujeme dvě varianty přihrádkovací hry. Tato hra je použita v důkazu spodniho odhadu časové složitosti vkládání prvků do setříděného pole. Ukážeme, že tyto varianty přihrádkovací hramy jí až na konstantní faktor ekvivalentní časovou složitost. Dále ukážeme výhody použití setříděných polí z hlediska vyrovnávacích pamětí. Na závěr ukážeme jednu možnou implementaci vyhledávání datové struktury s použití velikosti n1+e.
|
|
|
Data structures for file maintenance problem
Bulánek, Jan
V předložené práci studujeme dvě varianty přihrádkovací hry. Tato hra je použita v důkazu spodniho odhadu časové složitosti vkládání prvků do setříděného pole. Ukážeme, že tyto varianty přihrádkovací hramy jí až na konstantní faktor ekvivalentní časovou složitost. Dále ukážeme výhody použití setříděných polí z hlediska vyrovnávacích pamětí. Na závěr ukážeme jednu možnou implementaci vyhledávání datové struktury s použití velikosti n1+e.
|
|
|
Data structures for file maintenance problem
Bulánek, Jan
V předložené práci studujeme dvě varianty přihrádkovací hry. Tato hra je použita v důkazu spodniho odhadu časové složitosti vkládání prvků do setříděného pole. Ukážeme, že tyto varianty přihrádkovací hramy jí až na konstantní faktor ekvivalentní časovou složitost. Dále ukážeme výhody použití setříděných polí z hlediska vyrovnávacích pamětí. Na závěr ukážeme jednu možnou implementaci vyhledávání datové struktury s použití velikosti n1+e.
|
|
|
The Online Labeling Problem
Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Brodal, Gerth (oponent) ; Iacono, John (oponent)
Setříděné pole je zásadní algoritmický koncept, jehož online varianta je základem pro problém online labelingu. Problém online labelingu je definován následovně. Vstupem je pole velikosti m a posloupnost celých čísel z universa {1,...,r} v libovolném pořadí délky n. Naším úkolem je udržovat všechna přijatá čísla setříděná v poli. Mezi vloženými čísly mohou být mezery. Protože závěrečné pořadí čísel nelze určit, dokud nejsou vložena všechna, je povoleno čísla v poli přesouvat. Cílem je minimalizovat počet přesunů. Ukážeme dva algoritmy, které společně poskytují optimální řešení pro téměř všechny hodnoty m coby funkce n. Dokážeme těsné dolní odhady pro téměř všechny hodnoty m. Zavedeme notaci omezeného universa vstupní množiny čísel a dokážeme dolní odhady i pro tuto variantu. Dokážeme dolní odhady i pro případ randomizovaných algoritmů. Powered by TCPDF (www.tcpdf.org)
|
|
|
Automatic assembly of jigsaw puzzles from digital images
Ondrúška, Peter ; Sedlář, Jiří (vedoucí práce) ; Bulánek, Jan (oponent)
V tejto práci popíšeme nový algoritmus na automatické skladanie klasických obrázkových puzzle pomocou počítača. Automatické skladanie zahŕňa spracovávanie obrázkov s naskenovanými dielcami, výpočet riešenia na základe vzájomnej kompatibility dielcov a vyprodukovania obrázku s výsledným riešením. Predchádzajúce metódy na riešenie tejto úlohy využívali len informáciu o tvare dielcov. Popísaný algoritmus využíva informáciu o tvare ale aj farbe dielcov a tiež prináša niekoľko zlepšení v rôznych aspektoch celého procesu. Testovanie nakoniec poukázalo, že táto metóda dosahuje lepšie výsledky ako všetky doterajšie algoritmy keď dokázala zložiť puzzle o veľkosti viac ako 1000 dielcov.
|
|
|
Datové struktury pro setříděné ukládání dat
Bulánek, Jan ; Koucký, Michal (vedoucí práce) ; Kráľ, Daniel (oponent)
V předložené práci studujeme dvě varianty přihrádkovací hry. Tato hra je použita v důkazu spodniho odhadu časové složitosti vkládání prvků do setříděného pole. Ukážeme, že tyto varianty přihrádkovací hramy jí až na konstantní faktor ekvivalentní časovou složitost. Dále ukážeme výhody použití setříděných polí z hlediska vyrovnávacích pamětí. Na závěr ukážeme jednu možnou implementaci vyhledávání datové struktury s použití velikosti n1+e.
|
|
| |
host ::
RSS.