Hyperkrychle Qn řádu n je graf, jehož vrcholy jsou všechny n-bitové řetězce, přičemž hrany vedou mezi řetězci, které se liší v jediném bitu. Ivan Havel v roce 1984 publikoval hypotézu [2], podle níž je strom maximálního stupně tři kostrou Qn právě tehdy, když se dá obarvit dvěma barvami tak, že sousední vrcholy jsou obarveny různě a každá barva je použita 2n-1 krát. Uběhly více než tři desetiletí a problém je stále otevřený, platnost tvrzení se dosud podařilo ověřit jen ve speciálních případech (viz čerstvý výsledek [4]).
V 90. letech minulého století byla hypotéza ověřena na počítači pro všechny stromy na nejvýše 16 vrcholech [3]. Od té doby ovšem výpočetní síla dostupného hardware významně pokročila, mělo by tedy být možné, experimentálně prozkoumat i instance většího rozsahu.
Cílem práce je tedy ověřit platnost hypotézy pro malé n experimentálně na počítači. Dosažitelná by měla být alespoň dimeze n=5. Protože problém existence vnoření obecného stromu do hyperkrychle je NP-úplný [5], v literatuře nenajdeme lepší návod nežli pokusit se každý vygenerovaný strom vnořit hrubou silou (prohledáváním stavového prostoru). Tento postup lze výrazně urychlit použitím vhodných heuristik či využitím paralelismu, zde se nabízí široké možnosti pro vlastní invenci řešitele.
Na projekt lze navázat podobně zaměřenou bakalářskou prací.
Literatura
[1] T. Dvořák, Dense sets and embedding binary trees into hypercubes. Discrete Appl. Math. 155 (2007), 506-514. [doi]
[2] I. Havel, On hamiltonian circuits and spanning trees of hypercubes, Čas. Pěst. Mat. 109 (1984), 135-152 [html]
[3] J-M. Laborde, Le plongements des arbres à au plus 16 sommets dans l'hypercube, Rapport de Recherche 7551, LSD IMAG Grenoble.
[4] B. Monien, G. Wechsung. Balanced caterpillars of maximum degree 3 and with hairs of arbitrary length are subgraphs of their optimal hypercube. J. Graph Theory 87 (2018), 561-580 [doi]
[5] A. Wagner, D.G. Corneil, Embedding trees in a hypercube is NP-complete. SIAM J. Comput. 7 (1990), 570-590 [doi]
Grayův kód řádu n je posloupnost všech n-bitových řetězců taková, že sousední se liší v jediném bitu [4]. Je dobře známo, že mezi řetězci u a v existuje Grayův kód právě tehdy, když se u a v liší v lichém počtu bitů (viz např. [3]). V práci [2] je tato známá konstrukce rozšířena na n-1 dvojic n-bitových navzájem různých řetězců, kde se každá dvojice liší v lichém počtu bitů, a to pro každé n >1 s jednou výjimkou v případě n=4. Jde o optimální výsledek v tom smyslu, že pro každé n >2 existuje n takových n-bitových dvojic řetězců uvedeného typu, pro něž tvrzení neplatí.
Zesnulý prof. Václav Koubek, který vynikal skvělou intuicí, se domníval, že tvrzení půjde rozšířit na libovolné dvojice různých řetězců, které splňují nutnou paritní podmínku, a to pro všechna n >1 s konečným počtem výjimek [5]. Zatím byl objeveny pouze dvě výjimečné konfigurace pro n=3 [1].
Cílem projektu je počítačové ověření Koubkovy hypotézy pro malé instance problému, nejlépe pro n ≤ 6. Téma nabízí dostatečný prostor pro navázání bakalářskou či diplomovou prací, v níž by se využily výsledky počítačových experimentů pro (alespoň částečný) pokrok v teoretickém řešení.
Literatura
[1] T. Dvořák, V. Koubek, Generalized Gray codes with prescribed ends of small dimensions, CoRR abs/1701.06705 (2017)
[2] T. Dvořák, P. Gregor, V. Koubek, Generalized Gray codes with prescribed ends, Theor. Comput. Sci. 668 (2017), 70-94 [doi]
[3] I. Havel, On hamiltonian circuits and spanning trees of hypercubes, Čas. Pěst. Mat. 109 (1984), 135-152 [html]
[4] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations, Addison-Wesley Professional, 2005
[5] V. Koubek, osobní komunikace, 2015
Hyperkrychle řádu n je graf, jehož vrcholy jsou všechny n-bitové řetězce, přičemž hrany vedou mezi řetězci, které se liší v jediném bitu. Kreweras v roce 1996 publikoval hypotézu, podle níž lze každé perfektní párování v hyperkrychli rozšířit na Grayův kód. Tento problém, který též popularizoval Knuth v monografii [3], vyřešil o deset let později nebyčejně elegantním způsobem Fink [1]. Práce [2] popisuje alternativní řešení, kde se požadovaný cyklus sestrojí metodou rozděl a panuj.
Cílem práce je rozšířit Finkův výsledek na cesty s předepsanými koncovými vrcholy. Rozšíření induktivní konstrukce popsané v [2] by nemělo být obtížné, větším problémem bude ověření báze indukce, které bude zřejmě třeba provést na počítači.
[1] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Comb. Theory Ser. B 97 (2007), 1074–1076 [doi]
[2] J. Fink, Matching graphs of hypercubes and complete bipartite graphs, Eur. J. Comb. 30 (2009), 1624–1629 [doi]
[3] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations, Addison-Wesley Professional, 2005
[4] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996), 87–91
Grayův kód řádu n je posloupnost všech n-bitových řetězců taková, že sousední se liší v jediném bitu [2]. Hyperkrychle řádu n je graf, jehož vrcholy jsou všechny n-bitové řetězce, přičemž hrany vedou mezi řetězci, které se liší v jediném bitu. Ruskey a Savageová v roce 1993 publikovali otázku, zdali lze každé párování v hyperkrychli rozšířit na Grayův kód [4]. Kreweras v roce 1996 navázal hypotézou, podle níž je odpověď pozitivní pro každé perfektní párování [3]. Hypotézu, kterou též popularizoval Knuth v monografii [2], vyřešil o deset let později mimořádně elegantním způsobem doktorand MFF UK Jiří Fink [1]. Původní problém Ruskeyho a Savageové pro libovolné párování však zůstává stále otevřený.
Cílem projektu je počítačové ověření malých instancí problému. Kvůli exponenciální explozi počtu rozšiřovaných párování je třeba, důsledně omezovat počet instancí využíváním automorfismů hyperkychle. Další možností pro vlastní invenci je pokus o návrh heuristik, které by rychleji našly řešení, pokud existuje.
Téma nabízí dostatečný prostor pro navázání bakalářskou či diplomovou prací, v níž by se využily výsledky počítačových experimentů pro (alespoň částečný) pokrok v teoretickém řešení.
Literatura
[1] J. Fink, Perfect matchings extend to Hamilton cycles in hypercubes, J. Comb. Theory Ser. B 97 (2007), 1074–1076 [doi]
[2] D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations, Addison-Wesley Professional, 2005
[3] G. Kreweras, Matchings and Hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996), 87–91
[4] F. Ruskey, C. Savage, Hamilton cycles which extend transposition matchings in Cayley graphs of Sn, SIAM J. Discrete Math. 6 (1993), 152–166 [doi]
Klasická konstrukce Grayova kódu (GK) má tradiční využití v oblasti komprese obrazu [5, kapitola 4.2.1]. V posledních letech se objevily experimentální studie [2-3], které zkoumají využití GK při kompresi bitových map, indexujících velké databáze [6]. Některé experimenty na reálných datech však ukazují, že prosté lexikografické uspořádání může vést k účinnější kompresi nežli uspořádání dle GK [2].
Cílem práce je nahradit v uvedeném postupu [3] klasický GK novou konstrukcí [1], která generuje komprimovaný GK, a experimentálně ověřit účinnost dosažené komprese na vhodně zvolené množině reálných dat. V rámci práce bude též nutné implementovat třídění dle GK, které je pro klasickou konstrukci uspokojivě vyřešeno [4], pro komprimovaný kód [1] je však tato otázka zatím otevřena.
[1] D. Dimitrov, T. Dvořák, P. Gregor, R. Škrekovski, Gray code compression, Lect. Notes Comput. Sci. 5874 (2009), 183-193, [doi]
[2] H. H. Malik, J. R. Kender, Optimizing Frequency Queries for Data Mining Applications, Proc. 7th Int. Conf. Data Mining (ICDM 2007), IEEE Computer Society, 2007, 595-600, [doi]
[3] A. Pínar, T. Tao, H. Ferhatosmanoglu, Compressing Bitmap Indices by Data Reorganization, 21st International Conference on Data Engineering (ICDE'05), IEEE Computer Society, 2005, 310-321, [doi]
[4] D. S. Richards, Data Compression and Gray-Code Sorting, Inf. Process. Lett. 22 (1986), 201-205, [doi]
[5] D. Salomon, Data Compression: The Complete Reference, 3rd ed., Springer-Verlag, New York, 2004
[6] K. Wu, E. J. Otoo, A. Shoshani, Optimizing bitmap indices with efficient compression, ACM Trans. Database Syst. 31 (2006), 1-38, [doi]
Kompaktni sufixový automat (CDAWG) je sufixová datové struktura, kterou lze obdržet ztotožněním izomorfních podstromů sufixového stromu [1]. Ve srovnání se sufixovým stromem je tedy prostorově úspornější, postrádá však některé jeho užitečné vlastnosti. Pro aplikace v oblasti komprese dat je užitečná reprezentace textu v posuvném okně, které lze v případě sufixového stromu aktualizovat v amortizovaně konstantním čase [2], CDAWG však vyžaduje čas úměrný velikosti okna [3].
Cílem projektu je implementace algoritmu, popsaného v [3], udržujícího CDAWG pro text v posuvném okně, a experimentální ověření jeho časové náročnosti. Přes nepříznivou časovou složitost v nejhorším případě by totiž mohlo být chování algoritmu v průměrném případě příznivější; podobný výsledek je znám pro přibuznou datovou strukturu DAWG [4]. Na projekt může navázat bakalářská práce, která by porovnala časovou i prostorovou efektivitu implementovaného řešení s přibuznými strukturami (DAWG, sufixový strom).
[1] M. Crochemore, C. Hancart, T. Lecroq, Algorithms on Strings, Cambridge University Press, 2007.
[2] M. Senft, Suffix Tree for a Sliding Window: An Overview, In: Šafránková, J. (ed.) WDS 2005, pp. 41–46, Matfyzpress, Praha 2005.
[3] M. Senft, T. Dvořák, Sliding CDAWG Perfection, Proceedings of the 15th International Symposium on String Processing and Information Retrieval, LNCS 5280 (2008), 109-120 [doi]
[4] J. Blumer, How much is that DAWG in the window? Journal of Algorithms 8 (1987), 451–469 [doi]
Fraktální komprese je dnes již klasická metoda ztrátové komprese obrazu, která počátkem 90. let minulého století vzbudila velkou pozornost zejména účinností dosahovaného kompresního poměru, jejímu praktickému využití však zabránila příliš vysoká časová náročnost. V poslední době se objevila řada nových prací, zaměřených na různé aspekty této metody: kromě zrychlení kompresní fáze [3-4], které je pro praktické využití kritické, je zkoumáno i další zlepšení kompresního poměru [5] či zpracování barev [6].
Cílem projektu je navrhnout modulárně koncipovaný systém pro fraktální kompresi obrazu, v jehož rámci by bylo možné otestovat nově navržená vylepšení a porovnat je s klasickým řešením [1-2]. Součástí práce by mělo být i experimentální vyhodnocení implementovaných metod na vhodně zvolené množině testovacích dat a pokus o interpretaci dosažených výsledků.
Autor by měl nejprve nastudovat existující algoritmy bezztrátové komprese, experimentálně je vyhodnotit na vhodně zvoleném souboru krátkých zpráv a na základě výsledků se pokusit navrhnout a implementovat vlastní řešení. Výsledná aplikace by měla být nezávislá na operačním systému; doporučuji zvážit využití platformy Java ME (MIDP).
G. Korodi, J. Rissanen, I. Tabus, Lossless data compression using Optimal Tree Machines, Proceedings of the 2005 Data Compression Conference (DCC'05), pp. 1-10, IEEE Computer Society Press, Los Alamitos, CA, 2005.
S. Rein, C. Guhmann, F. H.P. Fitzek, Low-Complexity Compression of Short Messages, Proceedings of the 2006 Data Compression Conference (DCC'06), pp. 123-132, IEEE Computer Society Press, Los Alamitos, CA, 2006.
L. Stuiver, A. Moffat, Piecewise integer mapping for arithmetic coding, Proceedings of the 1998 Data Compression Conference (DCC'98), pp. 3-12, IEEE Computer Society Press, Los Alamitos, CA, 1998.
Qusay H. Mahmoud, Naučte se Java 2 Micro Edition, Grada, Praha 2002.
S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, G. Mauri, G. Pavesi: On-Line Construction of Compact Directed Acyclic Word Graphs, Discrete Applied Mathematics 146(2005), 156-179 [html]
S. Inenaga, A. Shinohara, M. Takeda, S. Arikawa: Compact Directed Acyclic Word Graphs for a Sliding Window, Journal of Discrete Algorithms 2(2004), 33-51 [pdf]