PředmětyPředměty(verze: 821)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Experimentální analýza algoritmů - NTIN033
Anglický název: Experimental Analysis of Algorithms
Zajišťuje: Katedra distribuovaných a spolehlivých systémů (32-KDSS)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2014
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Další informace: http://d3s.mff.cuni.cz/teaching/ntin033
Garant: RNDr. Alena Koubková, CSc.
Třída: Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: Tajemník Katedry (22.04.2010)

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.
Podmínky zakončení předmětu
Poslední úprava: RNDr. Alena Koubková, CSc. (10.10.2017)

Zápočet se uděluje za vypracování semestrální práce, účast na cvičení se nevyžaduje. Charakter zápočtu umožňuje jeho opakování. Zápočet je nutnou podmínkou pro zkoušku.

Literatura
Poslední úprava: RNDr. Alena Koubková, CSc. (04.04.2014)

Antoch, J., Vorlíčková, D.: Vybrané metody statistické analýzy dat. Academia, Praha, 1992.

Demetrescu, C., Italiano, G. F.: What do we learn from experimental algorithmics? Proc. MFCS´00, Lecture Notes in Comp. Sci. 1893, 36-51, Springer-Verlag 2000

Komárková, L., Komárek, A., Bína, V.: Základy analýzy dat a statistického úsudku s příklady v R. Oeconomia, Praha, 2007.

Požadavky ke zkoušce
Poslední úprava: RNDr. Alena Koubková, CSc. (10.10.2017)

Předmět nemá zkoušku v klasické podobě. Známka je odvozena od úrovně odevzdané semestrální práce.

Sylabus -
Poslední úprava: RNDr. Alena Koubková, CSc. (04.04.2014)

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.

 
Univerzita Karlova | Informační systém UK