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í tří úloh z Korespondenčního semináře programování (KSP, soutěž pro studenty středních škol).
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, zmiňte se stručně o hodinách informatiky, které jste absolvovali jako student/-tka základní a střední školy. Zda náplň této výuky odpovídá oboru informatika a co vlastně obor informatika zahrnuje. Případně, co víte o nové informatice a zda jsou na její výuku české školy připraveny.
Svoji práci pošlete do neděle 23. února 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 z programování (http://ksp.mff.cuni.cz) z letošního i z proběhlých ročníků.
Dvě ú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. Teoretické úlohy poznáte podle ikony u zadání a dále podle toho, že nemají vstupy na cvičišti.
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: 2. března, 16. března, 30. března, náhradní termíny 13. dubna, 27. dubna. 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, vysvětlení proč váš kód 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 na všech vstupech. 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ýstup 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. Pokud to dovolí č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 řadících algoritmů a jejich časové složitosti. Rozbor časové složitosti binárního vyhledávání. Pseudokód binárního vyhledávání, slévání, řazení vkládáním a řazení výběrem.
2. Vysvětlení základních pojmů teorie grafů (vrchol, hrana, cyklus, cesta, tah, sled, souvislost, strom, list, rovinný graf, klika, podgraf, komponenta). Maximální a minimální počet hran v grafu o n vrcholech pro případ kliky, stromu, rovinného grafu. 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. Pseudokód 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ě. Pseudokód Dijkstrova a Bellmann-Fordova algoritmu.
4. Kostra grafu, minimální kostra grafu s ohodnocenými hranami. Řezové lemma a jeho důkaz (na tuto část si můžete vzít ke zkoušce tahák). 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. Pseudokód Jarníkova algoritmu.
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 10 násobený počtem vámi vybraných témat (například 40 bodů, pokud budu vybírat ze všech čtyř témat, nebo 10 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í dvou praktických úloh za 10 bodů, 10 bodů za teoretickou úlohu (kde plný počet je zpravidla 14 bodů), 20 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í.