Applications of Gray codes in cache-oblivious algorithms

• Název práce v češtině: Aplikace Grayových kódů v cache-oblivious algoritmech
• Název v anglickém jazyce: Applications of Gray codes in cache-oblivious algorithms
• Klíčová slova: Grayovy kódy, cache-oblivious algoritmy
• Klíčová slova anglicky: Gray codes, cache-oblivious algorithms
• Akademický rok vypsání: 2017/2018
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: RNDr. Jiří Fink, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 04.04.2018
• Datum zadání: 04.04.2018
• Datum potvrzení stud. oddělením: 09.04.2018
• Datum a čas obhajoby: 16.09.2019 09:00
• Datum odevzdání elektronické podoby: 17.07.2019
• Datum odevzdání tištěné podoby: 17.07.2019
• Datum proběhlé obhajoby: 16.09.2019
• Oponenti: doc. Mgr. Petr Gregor, Ph.D.

Zásady pro vypracování

Cílem této práce je prozkoumat aplikace Grayových kódů v cache-oblivious algoritmech. Kombinatorický Grayův kód je libovolná posloupnost kombinatorických
objektů taková, že se po sobě jdoucí objekty liší jen velmi málo, například klasický reflektovaný Grayův kód pro n-bitové řetězce, v němž se po sousední
řetezce liší v právě jednom bitu. Algortimus pro generování kombinatorického Grayova kódu je loopless, pokud vygenerování následujícího prvku trvá konstatní
čas.

Student se bude zabývat návrhem a analýzou cache-oblivious algoritmů bez rekurze, založených na použití loopless algoritmů pro generování kombinatorických
Grayových kódů. Student se zaměří na maticové a algebraické algoritmy jako je transpozice, násobení matic a velkéch čísel a FFT. Student se může zabývat například následujícímí otázkami:
* Je možné pomocí Grayových kódů zlepšit multiplikativní konstanty pro počet cache-missů oproti existujícím algoritmům?
* Budou takové algoritmy lepší i na reálných počítačích?
* Je možné eliminovat rekurzi ze Strassenova algoritmu na násobení matic (při zachování počtu cache-missů)?
* Další podobné otázky související s cache-oblivious a loopless algoritmy.

Práce bude napsána v anglickém jazyce.

Seznam odborné literatury

Erik D Demaine. Cache-oblivious algorithms and data structures. Lecture Notes from the EEF Summer School on Massive Data Sets, 8(4):1–249, 2002.

Matteo Frigo, Charles E Leiserson, Harald Prokop, and Sridhar Ramachandran. Cache-oblivious algorithms. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 285–297. IEEE, 1999.

Donald E Knuth. The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations. Addison-Wesley Professional Boston, MA, 2005. ISBN 0-201-85393-0.

Carla Savage. A survey of combinatorial gray codes. SIAM review, 39(4):605–629, 1997