Experimentální analýza algoritmů

Upozornění

Úmluva na výběrovou přednášku proběhne e-mailem. Prosím zájemce, aby mě kontaktovali nejpozději do pátku 17. února 2023

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. 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.

Slidy k přednášce

Úvod

• Cíle a prostředky
• Experimentální algoritmika
• Algoritmové inženýrství
• Příklady experimentální analýzy algoritmů

Statistické metody

• Popisná statistika
• Základy matematické statistiky (opakování pojmů z přednášky pro bakalářské studium)
• Určení potřebného počtu experimentů
• Testování hypotéz
  1. Testy hypotéz o parametrech normálního rozdělení
  2. Silofunkce a síla testu
  3. Sekvenční metody
  4. Porovnání 2 výběrů
  5. Příklad – Quicksort

Regrese

• Lineární regresní model
• Příklad – Tranzitivní uzávěr grafu
• Příklad – Shellsort
• Příklad – Tranzitivní uzávěr

Porovnání více výběrů – analýza rozptylu

• Jednoduché třídění
• Dvojné třídění

Neparametrické a robustní metody

• Robustní odhady a testy hypotéz
• Testy nezávislosti
• Jednoduché třídění

Pořizování dat pro experimenty

• Náhodné generování - historie a teorie
• Současnost - přehledový článek
• Mersenne Twister
• Výběry z reálných dat

Měření času

• Úvod do problematiky

Cvičení

Obsahem cvičení bude samostatné vypracování experimentální studie chování konkrétního algoritmu, zadaného podle vlastního zájmu studenta. Cvičení v klasické formě se nekoná.

Zkouška a zápočet

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. Předmět nemá zkoušku v klasické podobě. Známka je odvozena od úrovně odevzdané semestrální práce.