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 2024
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• 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
• Je neslučitelnost pro: NTIX033
• Je záměnnost pro: NTIX033

Anotace

čeština

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.

Poslední úprava: Katedry Tajemník (22.04.2010)

angličtina

Major goals, basic methods and software tools of experimental algorithmics. An illustration of using statistical methods in experimental studies of algorithm behavior. Sampling methods and simulation of data sets for experiments with algorithms. Individual students' project: the experimental study of some algorithm. Basic knowledge of statistics is required.

Poslední úprava: Katedry Tajemník (22.04.2010)

Podmínky zakončení předmětu

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.

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

Literatura

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.

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

Požadavky ke zkoušce

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

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

Sylabus

čeština

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.

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

angličtina

Experimental algorithmics and its relation to the theoretical analysis of algorithms.

Software systems for the experimental analysis of algorithms: libraries of efficient implementations, test sets (generators), tools for vizualization and animation.

A survey of statistical methods for working with experimental data: A random sample from normal distribution, parameter estimates and tests of hypotheses about parameters, methods for determination of the necessary sample size. Sequential analysis. Tests of normality, influence of non-normality on the results, robust methods. Tests of independence.

Obtaining data for experiments with algorithms, random generators, methods for sampling from existing collections.

Software systems for statistical data analysis.

Examples of experimental analysis of the time complexity of algorithms (sorting, graph algorithms, hashing and others), interpretation of results and comparison with theoretical results.

Individual elaboration of an experimental study of behavior of some algorithm (depending on the student's own choice).

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