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 |