velikost textu

The Online Labeling Problem

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:
The Online Labeling Problem
Název v češtině:
Problém Online Labelingu
Typ:
Disertační práce
Autor:
Mgr. Jan Bulánek
Školitel:
doc. Mgr. Michal Koucký, Ph.D.
Oponenti:
Prof. Gerth Brodal
John Iacono
Id práce:
85225
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Matematický ústav AV ČR, v.v.i. (32-MUAV)
Program studia:
Informatika (P1801)
Obor studia:
Teoretická informatika (4I1)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
18. 9. 2014
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
problém online labelingu, problém file maintenance, dolní odhady, horní odhady
Klíčová slova v angličtině:
online labeling problem, file maintenance problem, lower bounds, upper bounds
Abstrakt:
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)
Abstract v angličtině:
A sorted array is a fundamental algorithmic concept. Its on-line variant gives rise to the online labeling problem. In the online labeling problem we are given an array of size m and a stream of n integers from the universe {1, ..., r} coming in an arbitrary order. Our task is to maintain all received items in the array in sorted order. The inserted items do not have to be stored consecutively in the array. Since the final order of the items is not known until we see all the items, moves of already inserted items are allowed but should be minimized. We present two algorithms which together provide an optimal solution for almost all values of m as a function of n. We provide tight lower bounds for almost all ranges of m. We introduce a notion of the limited universe and prove lower bounds also in that setting. Some of our lower bounds also apply to randomized algorithms. Powered by TCPDF (www.tcpdf.org)
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Jan Bulánek 1.15 MB
Stáhnout Abstrakt v českém jazyce Mgr. Jan Bulánek 84 kB
Stáhnout Abstrakt anglicky Mgr. Jan Bulánek 83 kB
Stáhnout Posudek vedoucího doc. Mgr. Michal Koucký, Ph.D. 2.98 MB
Stáhnout Posudek oponenta Prof. Gerth Brodal 177 kB
Stáhnout Posudek oponenta John Iacono 49 kB
Stáhnout Záznam o průběhu obhajoby 79 kB