Search
Rozvrh na FEL Posluchači PAL Odevzdávací systém BRUTE Diskusní fórum
Na podzim 2020 probíhala cvičení PAL výhradně v distanční formě. Některé záznamy jsou k dispozici jako doplňkový studijní materiál. Paralelka 107, paralelka 102. Nezaručujeme, že probíraná témata a úlohy v záznamech plně pokryjí témata probíraná letos v prezenčních cvičeních.
Semestr zahrnuje domácí programovací úlohy, které je třeba postupně vyřešit, naprogramovat a odevzdat v termínu do odevzdávacího systému (poučení viz Upload System ). Úlohy představují algoritmicky mírně rozsáhlejší problémy, je v nich většinou zapotřebí vhodně propojit více algoritmů nebo datových struktur, čas na řešení každé z nich je cca 20 dní.
Správnost řešení je kontrolována automaticky pomocí testovacích datových souborů (řešitelům neznámých).
Sleduje se čas, který kód potřebuje na výpočet řešení. Typicky by mělo být studentské řešení nanejvýš dvakrát pomalejší než referenční autorské řešení, pomalejší řešení považujeme za neúspěšná.
(Ne)sdílení kódu a využití veřejných zdrojů
Každý řešitel v PAL píše svůj kód samostatně a svůj kód ani jeho části s nikým nesdílí, nezveřejňuje v síti a neposkytuje kód nikomu dalšímu, kromě učitelů PAL a případně jejich nadřízených, a to převážně prostřednictvím odevzdávacího systému brute. Sdílení kódu se spolužáky bývá považováno za spoluúčast v plagiarismu. Kód může obsahovat části převzaté z veřejně dostupných zdrojů, viz níže.
Poznámka: Úlohy PAL jsou úmyslně strukturovány tak, aby pro jejich řešení nestačilo mechanické nebo téměř mechanické spojení hotových veřejných implementací jednotlivých menších částí úlohy. V drtivé většině úloh PAL proto bývá rychlejší a snazší, po správném pochopení problému, napsat příslušný úsek kódu samostatně. Pokud chce přesto autor využít vnější zdroje, může, při zachování uvedených pravidel citace.
Odevzdávaný kód, převzetí kódu a citace
Záhlaví kódu obsahuje jméno autora nebo jeho e-mailovou adresu nebo domovskou stránku, či jiný kontaktní údaj.
Pokud kód obsahuje části doslova převzaté odjinud, musí být tyto části v kódu citovány, to jest označeny jako převzaté. V označení se uvede zdroj (url) a datum převzetí. Musí být jasné, o které části odevzdávaného kódu jde, s přesností na řádek.
Pokud kód obsahuje části převzaté odjinud ale autorem přizpůsobené, musí být tyto části v kódu také označeny, stejně jako při doslovném převzetí. Pouze se navíc uvede, že kód je přizpůsobený. Ve všech případech může být převzat nebo přizpůsoben pouze kód veřejně přístupný.
Termíny jednotlivých úloh: 1. zadání 2.10. - - odevzdání do 23.10. 2. zadání 9.10. - - odevzdání do 30.10. 3. zadání 23.10. - - odevzdání do 13.11. 4. zadání 6.11. - - odevzdání do 11.12. 5. zadání 13.11. - - odevzdání do 29.12. 6. zadání 28.11. - - odevzdání do 10.1.
Kromě účasti na cvičení je nutno odevzdat v termínu úspěšná řešení programovacích úloh. Pro zápočet je nutno získat alespoň 12 bodů, přitom nezáleží na tom, z kterých a jak úspěšně vyřešených úloh. Hodnocení úlohy podle počtu správně zpracovaných vstupních souborů:
.... 8 a méně ................. 0 bodů ............... Neúspěšné řešení :-( .... 9 ........................ 3 body ............... Úspěšné řešení :-) ... 10 ........................ 4 body ............... Úspěšné řešení :-D
Úloha odevzdaná po termínu nabývá penalizace 1 bod bezprostředně po termínu a pak také v každém dalším týdnu po termínu (penalizační body se sčítají), přitom hodnocení nemůže nabýt záporné hodnoty.
Bezdůvodně lze vynechat nejvýše 2 cvičení. Všechny odevzdané úlohy je nutno vypracovat samostatně a vyvarovat se plagiátů, viz plagiáty. Posluchač, který z doložitelných důvodů (nemoc, studijní cesta, apod) nemůže průběžně plnit požadavky PAL, se domluví co nejdříve s cvičícím nebo přednášejícím na individuální úpravě podmínek absolvování předmětu.
Video z 1. cvičení
* Seznámení s odevzdávacím systémem, neklasifikovaná 0. programovací úloha, její zadání je zde. Doma (ne ve cvičení) napište program, který úlohu řeší, odevzdejte ho a zkontrolujte, jak ho systém vyhodnotil. Postupujte zásadně podle pravidel uvedených v oddíle |Upload System.
Orientační zkoušková témata - převážně bakalářské opakování
Specifická zkoušková témata
Video z 3. cvičení
Zkoušková témata
Pro posluchače, kteří téma v bakalářské etapě absolvovali, to bude opakování. Zájemce upozorňujeme na bohatý seznam literatury v oddílu literatura_odkazy .
Orientační zkoušková témata
Video z 8. cvičení
Slovní úlohy na prvočíselnost a náhodná čísla jsou zde.
Manipulace s trie a patricia trie zde
Trie a patricia trie, jejich vlastnosti.
Opakování asymptotické složitosti. Náměty k procvičení zde a zde a zde. Grafy a jejich reprezentace. Náměty k procvičení neřešené zde a řešené zde. Zkouškové otázky z předchozích let zde.
Kostry a minimální kostry grafů. Náměty k procvičení zde. Řešené náměty cvičení koster : zde a zde.
Orientované grafy, eulerovské grafy, náměty k procvičení zde. a zde. Řešené náměty cvičení orientovaných grafů zde a zde.
Jednoduché určení binární haldy zde. Opakování binární haldy - kap. 6 z [CLRS], cvičení v oddílu 6.1, 6.2, 6.5. zde. D-ární haldy - tamtéž - úloha 6-2 v oddílu Problems, str.167. Fibonacciho halda - kap. 19 z [CLRS] zde. Binomiální halda - tamtéž - úloha 19-3 v oddílu Problems, str.527. Fibonacciho halda - Kevin Wayne: adaptované příklady podle [CLRS]: zde . Applet pro experimenty s Fibonacciho haldou: zde. Zkouškové otázky z předchozích let zde.
Pro opakování základů kombinatoriky lze s výhodou využít skripta doc. Habaly pro předmět Diskrétní matematika zde v podkapitolách 11a - 11c. Podkapitola 11d koresponduje s tématy PAL. Krátké opakování o grafovém izomorfizmu zde. Jednodušší kombinatorické úlohy zde, hodí se “kuchařková” věta 11a.5. ze skript doc. Habaly výše. Řešené náměty cvičení jednoduché kombinatoriky zde.
Menší ilustrativní pojednání o isomorfismu grafů s příklady zde. Izomorfizmus a certifikáty zde. Zkouškové otázky z předchozích let zde., pozor, letos je témat ke zkoušce o něco více.
Konečné automaty, regulární výrazy zde. Řešené náměty Konečné automaty: zde, zde. Zkouškové otázky z předchozích let zde.
Hledání v textu pomocí konečných automatů, lze využít předchozí cvičení a dále úlohy zde.
Hledání v textu 1. neřešené zde. (přeskočte BM algoritmus.) Hledání v textu 2. neřešené zde. Zdroj přednášky v literatuře zde. Řešené cvičení automatů zde.
Témata: Binární vyhledávací stromy, BVS, AVL, Splay, R-B, B. Řešené první cvičení na stromy zde. Řešené náměty opakování BVS/AVL zde. Splay a R-B: zde. Ještě jednou Splay a R-B, vč všeobecné rekurze v BVS zde Řešené náměty RB-strom zde. Řešené náměty splay tree zde. Připomenutí B-stromů a BVS vůbec (opakování z bak.) zde.
Opakování binárních vyhledávacích stromů různého druhu zde. Splay stromy zde. RB stromy zde,