An implicit representation of sets

• Název práce v češtině: Implicitní reprezentace množin
• Název v anglickém jazyce: An implicit representation of sets
• Klíčová slova: optimální worst-case implicitní cache-oblivious vyhledávací strom
• Klíčová slova anglicky: optimal worst-case implicit cache-oblivious search tree
• Akademický rok vypsání: 2017/2018
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: Mgr. Martin Mareš, Ph.D.
• Řešitel: Mgr. Matej Lieskovský - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 14.02.2018
• Datum zadání: 14.02.2018
• Datum potvrzení stud. oddělením: 21.02.2018
• Datum a čas obhajoby: 22.06.2018 10:00
• Datum odevzdání elektronické podoby: 18.05.2018
• Datum odevzdání tištěné podoby: 18.05.2018
• Datum proběhlé obhajoby: 22.06.2018
• Oponenti: Mgr. Vladan Majerech, Dr.

Zásady pro vypracování

Francheschini a Grossi publikovali v roce 2003 návrh datové struktury pro reprezentaci uspořádaných množin, která je současně implicitní, časově optimální a I/O-optimální v cache-oblivious modelu. Jejich článek ovšem pomíjí mnoho důležitých detailů a obsahuje četné drobné chyby. Cílem této práce je prozkoumat uvedenou strukturu (zejména její distriktovou vrstvu), napravit nedostatky v jejím fungování a posoudit praktickou použitelnost.

Seznam odborné literatury

Francheschini, Gianni, and Grossi, Roberto: Optimal worst-case operations for implicit cache-oblivious search trees. Workshop on Algorithms and Data Structures 2003.

Bender, Michael et al.: Cache-oblivious B-trees. Proceedings of FOCS 2000.