Během semestru obvykle každé úterý, 10:30–12:00

Náhodné grafy

Důležitou charakteristikou algoritmů je jejich průměrná složitost, kterou lze chápat jako odhad průměrné doby nutné k vyřešení úlohy předepsaného rozsahu při použití uvažovaného algoritmu. Exaktní stanovení této charakteristiky obvykle není možné, proto se používají empirické testy, které zjišťují chování algoritmů na náhodně vygenerovaných vstupních datech.

Cíl práce:

• Student se seznámí se základy teorie grafů a s vybranými grafovými algoritmy.
• Vytvoří software pro generování náhodných grafů (ne/orientovaných, hranově ne/ohodnocených), které slouží jako testovací data grafových algoritmů.

Empirické testování vybraných grafových algoritmů

Empirické testy se často využívají při analýze tzv. průměrného chování algoritmů.

Cíl práce:

• Seznámit se základy statistického zpracování dat (např. lineární regrese, metoda nejmenších čtverců apod.).
• Seznámit se s vybranými grafovými algoritmy (minimální kostra, maximální tok atd.).
• Vytvoření software implementující zvolené algoritmy na PC. Provedení empirických testů, analýza průměrného chování.

Turingovy stroje

Cíl práce:

• Vytvořit software pro názornou prezentaci Turingových strojů.