Podmínky absolvování předmětů PALG/KALG/CALG

Zakončení předmětu

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 76 a více bodů
výborně mínus za 70 až 75 bodů
velmi dobře za 64 až 69 bodů
velmi dobře mínus za 58 až 63 bodů
dobře za 52 až 57 bodů

Za co získáte body

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.

Vyzkoušení z témat probraných na přednášce.
Vyřešení a obhájení úloh z Korespondenčního semináře programování (KSP, soutěž pro studenty středních škol).
Vytvoření výukového materiálu s použitím velkých jazykových modelů (LLM).
Dva eseje/úvahy, jeden na začátku semestru, druhý v průběhu semestru.

Vyzkoušení.

Témata.

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. Implementace zásobníku listem a nevhodnost implementace fronty listem. Balík collections a funkce deque v pythonu.
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.
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.
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.

Bodové hodnocení.

Ke zkoušce si můžete připravit jen některá z témat. Maximální počet bodů, které můžete získat, je desetinásobek počtu vámi vybraných témat (například 40 bodů, pokud se připravíte na všechna čtyři témata, ze kterých pak zkoušenjící jedno vybere; nebo 10 bodů při výběru jednoho tématu).

Možnosti vyzkoušení:

Během semestru se můžete přihlásit o výklad jednoho tématu při výuce. Při výkladu budete mít povoleno používat písemnou přípravu, kterou si přinesete na hodinu. Kromě faktických znalostí ocením i vaše didaktické kompetence. Při volbě této možnosti vám zůstává možnost nechat se vyzkoušet i z dalších témat později.
Na 13. týden semestru budou vypsány termíny na vyzkoušení v is stag.

Úlohy z KSP.

Ú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ů.
Předpokládám, že si budete vybírat ze začátečnické kategorie. Pokud jste zkušení a chtěli byste si vybrat z hlavní kategorie, je to možné. V tom případě se se mnou dopředu dohodněte, zda vám úlohu schválím (pravděpodobně ano) a kolik bodů za ni můžete získat (zpravidla o pět bodů více, než je u úlohy určeno).

Jednu úlohu si vyberete z praktických úloh, vypracujete ji 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. Za úlohu obdržíte tolik bodů, kolik jste získali na cvičišti za předpokladu, že budete umět vysvětlit všechny řádky vašeho kódu a jak kód pracuje. Někdy si se studenty při rozhovoru nad kódem nerozumíme a takové situace řeším tak, že vám k části vašeho kódu na mnou vybraný řádek přidám tisk proměnné a měli byste být schopni vysvětlit, co bude spuštěný kód tisknout. Úloha je určená k ověření, že chápete základní konstrukce jako cyklus, podmínka a že nepoužíváte funkce, kterým nerozumíte.

Druhou úlohu vyberete z předvybraných teoretických úloh. Tuto úlohu můžete, ale nemusíte programovat. Měli byste umět popsat a vysvětlit algoritmus, kterým úlohu řešíte (například napíšete jeho pseudokód), umět dokázat, že algoritmus doběhne v konečném čase a na závěr vydá požadovaný výsledek. Dále byste měli vysvětlit, jakou časovou a případně paměťovou složitost váš algoritmus má. Za splnění všech požadavků obdržíte tolik bodů, kolik je za ni na KSP.

Třetí úlohu si můžete vybrat buď jako další úlohu z výše uvedeného balíku teoretických úloh, nebo vybírejte z předvybraných praktických úloh (seznam není kompletní, budu úlohy přidávat). Požadavky jsou stejné jako výše na praktickou/teoretickou úlohu.

Není možné odevzdat a obhájit úlohu, která byla předtím vysvětlena na cvičení či přednášce.
Úlohy můžete obhajovat v pořadí, které si zvolíte. Nemusíte respektovat výše uvedené pořadí.

Termíny odevzdání:
Pro studenty prezenčního studia jsou neděle (vyberte tři z následujících šesti): 22. února, 1. března, 15. března, 29. března, 12. dubna, 26. dubna.
V týdnu následujícím po odevzdání proběhne obhajoba vašich prací v termínech vypsaných v is stag.
Se studenty kombinovaného studia dohodneme termíny na výuce. Prezentace budou probíhat na hodinách, na hromadných online setkáních, na individuálních prezenčních setkáních.

Způsob odevzdání: do odevzdávátka na elearningu. V případě praktické úlohy odevzdejte textový soubor s kódem programu, který bude v hlavičce obsahovat kód úlohy (ve tvaru uvedeném v zadání, např. 34-Z2-3), dále odevzdejte snímek obrazovky cvičištěr. V případě teoretické úlohy odevzdejte kód úlohy (například 34-Z2-4) a svoji přípravu na obhajobu, která může být v bodech (podstatné bude, co budete říkat při obhajobě).

Vytvoření výukového materiálu s použitím velkých jazykových modelů (LLM).

Tato možnost je v letošním akademickém roce zařazena poprvé. Cílem je dodat vám kuráž v používání LLM a zahájit diskusi o dobrém a špatném způsobu používání. Jako téma pro výukový materiál můžete zvolit buď jedno z témat na vyzkoušení, nebo některou výše zmíněnou předvybranou úlohu z KSP, a to jak teoretickou, tak praktickou. Podmínkou je, že svůj materiál budete prezentovat na výuce svým spolužákům. Získat můžete (kromě bodů za vyzkoušení, prezentaci úlohy zmíněné výše) až deset bodů navíc.

Esej/úvaha.

Během semestru můžete odevzdat až dvě eseje. Za každou můžete získat až 3 body. Přitom za dodání po termínu vám strhnu za každých načatých 24 hodin jeden bod. Před udělením bodů si vyhrazuji právo s vámi vaši práci prodiskutovat.

Témata.

Proč jsem si vybral/-la studium učitelství informatiky, Jakou mám představu o náplni a metodice práce v hodinách informatiky na základní/střední škole.
Zamyslete se nad výukou informatiky a nad výukou obecně v horizontu deseti a více let. Téma je široké, vyberte, co vás osobně zajímá. Mě osobně zajímají přínosy a rizika používání sociálních sítí a LLM. Při psaní eseje čerpejte ze své zkušenosti a ze svých zájmů. Vyhněte se prosím frázím, které nebudete umět vysvětlit.

Termín a způsob odevzdání.

Svoji práci vložte do odevzdátátka na elearning.tul.cz ve formátu pdf. Rozsah práce by měl být zhruba jedna 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 práce i delší. Pište prosím upřímně své názory. V rámci svých časových možností bych chtěla vaše práce s vámi probrat. Buďte tedy na diskusi připraveni.

Poznámka k výběru úloh a poskládání bodů.

Nejlehčí úlohy v KSP jsou za 8 bodů a jsou na úrovni UDP. Standardní praktické úlohy jsou za 10 bodů. Teoretické úlohy jsou zpravidla za 12 až 14 bodů.

Body na nejnižší hranici pro absolvování předmětu můžete získat například takto: 3x9bodů za úlohy, 6 bodů za eseje a 19 bodů za vyzkoušení.
K lepšímu hodnocení je třeba lépe skórovat u úloh, případně u zkoušení, případně vytvořit a didakticky prezentovat výukový materiál.