Sylabus prenášky

• Složitost algoritmu -- v nejhorším případě, očekávaná složitost, amortizovaná složitost. Dolní a horní odhady složitosti.
• Metody analýzy složitosti algoritmů --- shluková technika, technika účtů, potenciálová metoda.
• Datové struktury --- binomiální a Fibonacciho halda, datové struktury pro reprezentaci disjunktních množin. Příklady použití.
• Techniky návrhu efektivních algoritmu --- divide et impera, dynamické programování, hladové algoritmy. Obecná formulace, aplikace, teoretické základy.
• Grafové algoritmy --- kostry v grafech, problém nejkratších cest, toky v sítích, párování.
• Algoritmy pro práci s řetezci --- přímý algoritmus, Rabin-Karpův algoritmus, užití konečných automatů.
• Algoritmy pro NP-těžké problémy.

---

Prerekvizity a vstupní test
Podmínkou pro zapsání předmětu  je absolvování kursu IB002 Algoritmy a datové struktury I. 

Zápis je možný i pro studenty, kteří  bakalářský studijní program neabsolvovali na FI a mají znalosti v rozsahu kursu IB002 (požádejte si, prosím, o výjimku v ISu). 

V průběhu prvních dvou týdnů výuky (do 6.3.2016) je Vám k dispozici v ISu odpovědník s názvem Vstupní test. Vyplnění odpovědníku je povinné, výsledky ale nejsou nijak hodnoceny. Odpovědník slouží k ověření, že Vaše znalosti skutečně odpovídají vstupním předpokladům předmětu. Jestliže je Vaše úspěšnost v testu nízká, zvažte zda pro Vás není lepší si nejdříve zapsat kurz IB002, resp. počítejte s tím, že si budete muset individuálně doplnit a prohloubit svoje znalosti.

---

 

Podmínky absolvování předmětu

K úspěšnému absolvování předmetu zkouškou je potřeba řešit sady problémů a absolvovat písemný test na konci semestru.

• Sady problémů

V průběhu semestru budou zveřejněny 3 sady problémů k řešení.
Maximální počet bodů, které lze získat za jejich řešení je 340.
Pro absolvování predmětu zkouškou je nutné získat z těchto 340 bodů alespoň 170 bodů.

Za každou sadu je dále možné získat 20 bonusových bodů za plně funkční a korektní implementaci určeného algoritmu. 

• Písemný test

Termíny pro písemný test budou zveřejněny cca třetí týden výuky.
Maximální počet bodů, které lze za test získat je 160.
Pro absolvování předmetu zkouškou je nutné získat z těchto 160 bodů alespoň 80 bodů.

• Výsledné hodnocení

Výsledné hodnocení je závislé od počtu bodů, které student získá za vyřešené problémy, implementaci a  písemný test; a to následujícím způsobem:

>= 450 bodů  --- hodnocení A

>= 400 bodů  --- hodnocení B

>= 350 bodů  --- hodnocení C

>= 300 bodů  --- hodnocení D

>= 250 bodů  --- hodnocení E

<= 249 bodů  --- hodnocení F

---

 

Konzultace
K dotazům využívejte, prosím, diskusní fórum předmětu.

Individuální konzultace je potřebné dohodnout  mailem.