Informace o kurzu (sylaby, vstupní test, podmínky absolvování)
Sylabus přednášky
- Složitost algoritmů a problémů
- Metody analýzy složitosti algoritmů, amortizovaná složitost
- Datové struktury: Fibonacciho halda, datové struktury pro reprezentaci disjunktních množin
- Rozděl a panuj (rekurze): problém maximálních prvků, problém nejbližších bodů
- Dynamické programování: problém rozvrhů, editační vzdálenost, nejkratší cesty, problém batohu a součtů
- Hladové algoritmy: problém rozvrhů, nejkratší cesty, nejlevnější kostry
- Toky v sítích, aplikace
- Algoritmy pro práci s řetezci
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ího týdne výuky (do neděle 25. 2. 2018) je Vám k dispozici v ISu odpovědník s názvem Vstupní test. Vyplnění odpovědníku je povinné. Výsledky 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. V případě, že odpovědník nevyplníte, získáváte -20 bodů k hodnocení písemného testu.
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ů.
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 případě, že nevyplníte vstupní test, je nutné získat alespoň 100 bodů.
Výsledné hodnocení
Výsledné hodnocení je závislé na počtu bodů, které student získá za vyřešené problémy 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