Succinct encodings of trees

• Název práce v češtině: Stručná kódování stromů
• Název v anglickém jazyce: Succinct encodings of trees
• Klíčová slova: stromy, stručné datové struktury, korektní uzávorkování, stromové pokrytí
• Klíčová slova anglicky: trees, succinct data structures, blanaced parentheses, tree covering
• Akademický rok vypsání: 2015/2016
• 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: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 19.11.2015
• Datum zadání: 20.11.2015
• Datum potvrzení stud. oddělením: 01.12.2015
• Datum a čas obhajoby: 12.09.2016 09:00
• Datum odevzdání elektronické podoby: 28.07.2016
• Datum odevzdání tištěné podoby: 28.07.2016
• Datum proběhlé obhajoby: 12.09.2016
• Oponenti: Mgr. Vladan Majerech, Dr.

Zásady pro vypracování

Stručné (succinct) říkáme těm datovým strukturám, kterým stačí prostor blízký k informačně-teoretickému optimu, a přitom stále mají příznivou časovou složitost vhodné množiny operací.

Cílem práce je prozkoumat existující stručné datové struktury pro reprezentaci stromů, porovnat jejich chování a případně je vylepšit.

Seznam odborné literatury

Sadakane, Kunihiko, and Navarro: Fully-functional succinct trees. In: Proceedings of the 21st annual ACM-SIAM symposium on Discrete Algorithms, 2010.

Pătraşcu: Succincter. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008.

Dodis, Pătraşcu, Thorup: Changing base without losing space. In: Proceedings of the 42th ACM Symposium on Theory of Computing, 2010.