Sylabus
Experimentální algoritmika a její vztah k teoretické analýze algoritmů.
Softwarové systémy pro experimentální analýzu algoritmů: knihovny efektivních implementací, soubory (generátory) testovacích dat, nástroje pro vizualizaci a animaci.
Přehled statistických metod pro zpracování experimentálních dat: Náhodný výběr z normálního rozdělení, odhady parametrů a testy hypotéz o parametrech, metody stanovení potřebného rozsahu výběru. Sekvenční analýza. Porovnání dvou a více výběrů. Regresní analýza. Ověřování normality, vliv porušení předpokladu normality na výsledky, robustní metody. Testy nezávislosti.
Pořizování dat pro experimenty s algoritmy, náhodné generování, metody výběru z existujících souborů dat.
Softwarové systémy pro statistickou analýzu dat.
Příklady experimentální analýzy složitosti algoritmů (třídicí algoritmy, grafové algoritmy, hašování apod.), interpretace výsledků a porovnání s teoretickými výsledky.
Obsahem cvičení bude samostatné vypracování experimentální studie chování konkrétního algoritmu, zadaného podle vlastního zájmu studenta.
Anotace
Hlavní cíle, základní metody a programové prostředky experimentální algoritmiky. Ukázky použití metod matematické statistiky při zpracování experimentálních studíí o chování algoritmů.
Metody výběru a simulace dat pro experimenty s algoritmy. V rámci cvičení vypracování samostatné experimentální studie konkrétního algoritmu (podle vlastního zájmu studentů).
Předpokládají se základní znalosti pravděpodobnosti a matematické statistiky.