Podmínky absolvování předmětu KGD/ALG

Předmět končí klasifikovaným zápočtem. Známku získáte podle bodů získaných za práci během semestru:
výborně za 75 a více bodů
výborně mínus za 70 až 74 bodů
velmi dobře za 65 až 69 bodů
velmi dobře mínus za 60 až 64 bodů
dobře za 55 až 59 bodů

Body získáte za následující tři aktivity, přitom žádná z nich není povinná, záleží jen na celkovém bodovém zisku. Ke všem aktivitám najdete podrobnosti níže. Aktivity jsou:
Esej/úvaha na začátku semestru.
Vyřešení a obhájení čtyř úloh z KSP.
Vyzkoušení ze čtyř témat probraných na přednášce.

Esej/úvaha: na téma Proč jsem si vybral/-la studium učitelství informatiky, stručně o hodinách informatiky, které jste absolvovali jako student/-tka, zda náplň této výuky odpovídá oboru informatika a co vlastně obor informatika zahrnuje pošlete do neděle 3. března emailem ze své @tul.cz adresy ve formátu pdf v rozsahu zhruba jedné necelé strany A4 (záleží víc na obsahu než na délce, neprodlužujte "slovním balastem" a pokud byste se naopak rozepsali, může být i delší). Nebudu hodnotit obsah, pište prosím upřímně své názory. Získáte 5 bodů, před jejich udělením si vyhrazuji právo s vámi vaši práci prodiskutovat.

Úlohy si vyberete z korespondenčního semináře v programování (http://ksp.mff.cuni.cz) z letošního i z proběhlých ročníků:
Tři úlohy vyberete z praktických úloh, vypracujete je v Pythonu, otestuje na cvičišti (pozor, nespleťte si ho s odevzdávátkem, které je určeno pro soutěžící středoškolské studenty), kde si zřídíte účet.
Jednu úlohu vyberete z teoretických úloh.
Není možné odevzdat a obhájit úlohu, která byla předtím vysvětlena na cvičení či přednášce.
Termíny odevzdání jsou neděle: 17. března, 31. března, 14. dubna, 28. dubna, náhradní termín 12. května. Odevzdané řešení nemusí obsahovat zadání úlohy, ale musí obsahovat odkaz na ročník, sérii a číslo úlohy (ve tvaru kódu uvedeného u zadání, např. 34-Z2-3). Svoji práci pošlete v příloze emailu, přílohu pojmenujte svým příjmením. Kód k praktickým úlohám můžete uložit na https://replit.com/, pak stačí v těle emailu poslat odkaz.
V týdnu následujícím po odevzdání proběhne obhajoba vašich prací v termínech vypsaných v is stag.
Bodové hodnocení: Body za úlohy kategorie KSP-Z jsou dle zadání, body za úlohy kategorie KSP-H o pět bodů více, než je v zadání uvedeno. Plný počet získáte u praktické úlohy za vysvětlení vašeho kódu, proč dává požadovaný výsledek a vysvětlení všech programovacích konstrukcí v kódu uvedených a dále je třeba úspěšně kód otestovat na cvičišti. Můžete obhajovat vzorové řešení zveřejněné na webu ksp (musíte v tom případě prokázat, že mu rozumíte). Pokud se vaše řešení bude od vzorového lišit (případně odevzdáte úlohu, která dosud vzorové řešení nemá zveřejněné), můžete dostat až o 50% bodů více.
U teoretické úlohy získáte plný počet za splnění úlohy, zpravidla to bude vysvětlení algoritmu, důkaz, že výsledek algoritmu řeší zadanou úlohu a rozbor časové složitosti algoritmu.
Jednu z úloh (výběr bude na vyučující) předvedete na cvičení.

Vyzkoušení proběhne ve 13. týdnu semestru v termínech vypsaných v is stag. Dovolí-li to časové možnosti, bude studentům dána možnost býti vyzkoušeni během výuky.
Témata jsou:
1. Binární vyhledávání v seřazeném souboru dat. Základní metody řazení: vkládáním (InsertSort), výběrem (SelectSort), QuickSort (první z rychlejších algoritmů), sléváním (MergeSort). Časová složitost algoritmu, symbol O. Rozbor řadicích algoritmů a jejich časové složitosti. Rozbor časové složitosti binárního vyhledávání.
2. Vysvětlení základních pojmů teorie grafů (vrchol, hrana, cyklus, cesta, souvislost, strom). Vysvětlení algoritmů na prohledávání grafu (prohledávání do hloubky, DFS, prohledávání do šířky, BFS), datové struktury zásobník (LIFO), fronta (FIFO) a jejich role při algoritmech DFS, BFS. Časová složitost algoritmů DFS, BFS.
3. Graf s ohodnocenými hranami, algoritmy na hledání nejkratší cesty v grafu (Bellmann-Ford, Dijkstra), nejen jak fungují, ale i proč vydají správný výsledek a jejich časová složitost. Vysvětlení datových struktur fronta, halda. Rozbor časové složitosti operací insert, extract, increase na haldě.
4. Kostra grafu, minimální kostra grafu s ohodnocenými hranami, řezové lemma a jeho důkaz. Co je hladový algoritmus a že při hledání minimální kostry dobře funguje, ale je to spíše výjimka. Jarníkův algoritmus na hledání minimální kostry, jeho časová složitost. Datová struktura halda, rozbor časové složitosti operací insert, extract, increase. Stručně o Kruskalově a Borůvkově algoritmu, velmi stručně o algoritmu union-find.
Z těchto čtyř témat si můžete vybrat pouze některá, a z nich vám pak vyberu jedno já. Maximální možný počet bodů je 5 násobený počtem vybraných témat (například 20 bodů, pokud budu vybírat ze všech čtyř témat, nebo 5 bodů při výběru jednoho tématu). Pokud nebudete spokojeni s udělenými body, budete mít možnost provést opravu během zkouškového období. Při této opravě budu brát v úvahu váš původní výběr témat, přičemž maximální počet bodů se při každé opravě sníží o pět bodů.

Poznámka k výběru úloh:
nejlehčí úlohy jsou za 8 bodů a jsou na úrovni UDP. K absolvování předmětu stačí získat plný počet bodů za nastudování, pochopení a obhájení vzorových řešení tří praktických úloh za 10 bodů, 10 bodů za teoretickou úlohu (kde plný počet je zpravidla 14 bodů), 10 bodů za vyzkoušení z teorie a za úvahu ze začátku semestru.
Pro lepší hodnocení vybírejte náročnější úlohy, případně vytvořte svoje řešení, ideálně pro úlohy, které nemají dosud publikovaná řešení.