Název:
Časová složitost dynamických datových struktur
Překlad názvu:
Complexity of dynamic data structures
Autoři:
Král, Karel ; Koucký, Michal (vedoucí práce) ; Drucker, Andrew (oponent) ; Ishai, Yuval (oponent) Typ dokumentu: Disertační práce
Rok:
2021
Jazyk:
eng
Abstrakt: [eng][cze] Sorting is one of the fundamental problems in computer science. In this thesis we present three individual results. Asymptotically optimal sorting networks have been created by Ajtai et al. [1983]. But Asharov et al. [2021] have observed that boolean circuits based on sorting networks are not optimal for sorting short integers. We present a construction of even smaller boolean circuits for sorting short integers. Lower bounds for offline Oblivious RAM have been connected to lower bounds for sorting circuits by Boyle and Naor [2016]. Larsen and Nielsen [2018] have shown a lower bound for online Oblivious RAM. We provide a lower bound for online Oblivious RAM in a more general model. Finally we provide an algorithm with expected running time O(n log log(n)) for sort- ing integers on random access machine with word length between log(n) and log(n) cubed. This algorithm does not match the expected running time of the algorithm of Han and Thorup [2002], but our algorithm is much easier to implement and analyse. 1Třídění je jedním z fundamentálních problémů informatiky. V této práci prezentujeme tři výsledky. Asymptoticky optimální třídící sítě byly popsány v článku Ajtai a kol. [1983]. Ale Asharov a kol. [2021] ukázali, že booleovské obvody vytvořené z třídících sítí nejsou optimální pro třídění krátkých celých čísel. My ukazujeme konstrukci ještě menších obvodů pro třídění krátkých celých čísel. Dolní odhady pro offline Oblivious RAM byly spojeny s dolními odhady pro třídící booleovské obvody v článku Boyle a Naor [2016]. Larsen a Nielsen [2018] ukázali dolní odhad pro online Oblivious RAM. My ukazujeme dolní odhad pro online Oblivious RAM v obecnějším modelu. Nakonec ukazujeme algoritmus se střední dobou běhu O(n log log(n)) pro třídění celých čísel na RAM s délkou slov mezi log(n) a log(n) na třetí. Tento algoritmus ne- dosahuje střední doby běhu algoritmu z článku Han a Thorup [2002], ale náš algoritmus je mnohem jednodušší na implementaci i analýzu. 1
Klíčová slova:
Třídění|Booleovské obvody|online Oblivious RAM; Sorting|Boolean Circuit|online Oblivious RAM