školitel: |
Ing. Ľubomíra Dvořáková, Ph.D. |
e-mail: |
zobrazit e-mail
|
typ práce: |
bakalářská práce, diplomová práce
|
zaměření: |
MI_MM, MI_AMSM |
klíčová slova: |
maticové násobení, součin matic, verifikace, korekce |
popis: |
Maticové násobení hraje klíčovou roli v lineární algebře a v numerické matematice. Proto je mu v informatice věnovana velká pozornost z hlediska návrhu efektivních algoritmů. S naším prohlubujícím se poznáním a s vývojem výpočetní techniky trvá snaha o nalezení stále efektivnějších algoritmů násobení matic. Asymptotická složitost násobení matic postupně klesá, je rovna O(n^t) aritmetických operací, kde 2 < t < 3 a t se stále více blíží dvěma. Bohužel, odpovídající algoritmy jsou z technického hlediska stále náročnější a v praxi zatím nepoužitelné kvůli velké konstantě ukryté v notaci O.
Problémy maticového násobení se studují z různých úhlů pohledu:
- Lze uvažovat matice reálné, celočíselné, v modulární aritmetice, booleovské a jiné.
- Je možné zkoumat deterministické a nedeterministické algoritmy, pravděpodobnostní atd.
- Rozlišuje se mezi různými výpočetními modely: aritmetické obvody, real RAM, unit-cost RAM, log-cost RAM, p-RAM, BSS atd.
- Dále se může úloha zúžit na verifikaci maticového součinu či korekci maticového součinu.
Tato práce bude zaměřena právě na složitost verifikace maticového součinu.
Rešeršní část práce
- Nastudování prací týkajících se historie verifikace maticového součinu -- postupná eliminace náhodných kroků ve Freivaldsově algoritmu.
- Nastudování různých výpočetních modelů a výsledků pro složitost verifikace odpovídající takovým modelům.
Výzkumná část práce
- Porovnání známých výsledků v závislosti na použitém modelu a na třídě matic, s níž se pracuje (reálné, celočíselné, v modulární aritmetice, booleovské atd.)
- Identifikace nových problémů.
|
literatura: |
-
Aho, A., Hopcroft, J. E., Ullman, J. D.: The Design and Analysis of Computer Algorithms, Addison--Wesley (1974), 470 p.
-
Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation, Springer (1998), 452 p.
-
Korec, I., Wiedermann, J.: Deterministic Verification of Integer Matrix Multiplication in Quadratic Time, V. Geffert at al. (Eds.): SOFSEM 2014, LNCS 8327, Springer International Publishing Switzerland (2014), 375--382
-
Wiedermann, J.: Fast Nondeterministic Matrix Multiplication via Derandomization of Freivalds Algorithm, preprint (2014)
|
poznámka: |
Na tématu pracuje Jan Legerský. |
naposledy změněno: |
26.04.2018 22:50:04 |