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í: 2019/2020
• Typ práce: diplomová 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í: 10.04.2020
• Datum zadání: 17.04.2020
• Datum potvrzení stud. oddělením: 29.04.2020
• Datum a čas obhajoby: 08.07.2020 09:00
• Datum odevzdání elektronické podoby: 28.05.2020
• Datum odevzdání tištěné podoby: 28.05.2020
• Datum proběhlé obhajoby: 08.07.2020
• 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. Matej Lieskovský ve své předchozí bakalářské práci prozkoumal a opravil distriktovou vrstvu této struktury. Cílem této práce je prozkoumat zbývající kyblíkovou vrstvu uvedené struktury, napravit nedostatky v jejím fungování a posoudit praktickou použitelnost celé struktury.

Seznam odborné literatury

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

Gianni Franceschini and Roberto Grossi: Optimal implicit and cache-oblivious dictionaries over unbounded universes. Full version, 2003.

Gianni Franceschini, Roberto Grossi, J. Ian Munro, and Linda Pagli: Implicit B-trees: New results for the dictionary problem. In IEEE Symposium on Foundations of Computer Science (FOCS), 2002.