Applications of Gray codes in cache-oblivious algorithms
Thesis title in Czech: | Aplikace Grayových kódů v cache-oblivious algoritmech |
---|---|
Thesis title in English: | Applications of Gray codes in cache-oblivious algorithms |
Key words: | Grayovy kódy, cache-oblivious algoritmy |
English key words: | Gray codes, cache-oblivious algorithms |
Academic year of topic announcement: | 2017/2018 |
Thesis type: | diploma thesis |
Thesis language: | angličtina |
Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
Supervisor: | RNDr. Jiří Fink, Ph.D. |
Author: | hidden - assigned and confirmed by the Study Dept. |
Date of registration: | 04.04.2018 |
Date of assignment: | 04.04.2018 |
Confirmed by Study dept. on: | 09.04.2018 |
Date and time of defence: | 16.09.2019 09:00 |
Date of electronic submission: | 17.07.2019 |
Date of submission of printed version: | 17.07.2019 |
Date of proceeded defence: | 16.09.2019 |
Opponents: | doc. Mgr. Petr Gregor, Ph.D. |
Guidelines |
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. |
References |
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 |