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í.

1. Správnost řešení je kontrolována automaticky pomocí testovacích datových souborů (řešitelům neznámých).
2. 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á.

Termíny jednotlivých úloh: 
 
 1. zadání   29.9. -       - odevzdání do 20.10.  
 2. zadání   6.10. -       - odevzdání do 27.10. 
 3. zadání  20.10. -       - odevzdání do 10.11. 
 4. zadání   3.11. -       - odevzdání do 24.11. 
 5. zadání  17.11. -       - odevzdání do  8.12. 
 6. zadání   1.12. -       - odevzdání do  5.1.
 

Kromě účasti na cvičení je nutno odevzdat v termínu úspěšná řešení programovací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.

Upozornění: Při pozdním odevzdání se v BRUTE zobrazí jednotná penalizace -100. Má však pouze informativní charakter. Přepočet na body se vždy provede podle výše uvedeného pravidla, typicky až na zkoušce při sčítání všech bodů pro určení výsledné známky.

Pro zápočet je nutno získat alespoň 13 bodů, přitom nezáleží na tom, z kterých a jak úspěšně vyřešených úloh.
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.

* 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.

• Opakování asymptotické složitosti, grafy a jejich reprezentace, DFS, BFS: příklady zde.
• Slovní úlohy na hledání minimálních i jiných koster jsou zde.
• S častečným návodem na postup řešení ukázky zde .
• Další doplňující příklady otázek z předchozích semestrů a zkoušek najdete na konci této stránky.
  

Orientační zkoušková témata - převážně bakalářské opakování

• Řád růstu funkcí, definice, porovnání řádu růstu dvou nebo více funkcí, definice množin O(f), Θ(f), Ω(f) pro rostoucí reálnou funkci f. Definice asymptotické složitosti algoritmu pomocí řádu růstu funkce. Určení asymptotické složitosti jednoduchého algoritmu. Asymptotické složitosti jednotlivých algortimů PAL, jejich zdůvodnění.
• Reprezentace grafu: Matice, seznamy sousedů uzlů, seznam hran. Vhodnost/nevhodnost jednotlivých reprezentací pro základní grafové algoritmy (DFS, BFS, MST), pro různě velké nebo různě husté grafy. Jak výběr reprezentace ovlivní složitost toho kterého grafového algoritmu.

Specifická zkoušková témata

• Borůvkův, Kruskalův, Primův-Jarníkův algoritmus, jejich implementace a datové struktury v nich použité, tj. prioritní fronty a Union-Find.
• Primův-Jarníkův algoritmus bez použití fronty.
• Implementační varianty Union-Find operací.

• Slovní úlohy na analýzu a zpracování orientovaných i jiných grafů jsou zde.

Zkoušková témata

• Eulerův graf (orientovaný i neorientovaný), Eulerova cesta/cyklus, metody jejich nalezení.
• Slabá a silná souvislost, slabé a silné komponenty, kondenzace grafu. Algoritmy nalezení silných komponent a kondenzace.
• Topologické uspořádání grafu pomocí DFS nebo postupné likvidace kořenů.

• Slovní úlohy na různé druhy hald jsou zde.
• Ukázka činnosti Fibonacciho haldy (Frank Stajano). Dále viz také odkazy dole na stránce.
  
• Složitost operací ve Fibonacciho haldě (Cormen et al. Ch 21).

Zkoušková témata

• Pravidlo haldy. Typické operace s haldou. Binární halda, d-ární halda, binomiální halda.
• Implementace binární a d-ární haldy v poli.
• Fibonacciho halda a amortizovaná složitost operací v ní.
  

• Slovní úlohy hlavně na izomorfizmus grafů a certifikáty stromů jsou zde.

Zkoušková témata

• Grafový izomorfizmus, definice, pojem invariantu, algoritmus nalezení všech izomorfizmů.
• Izomorfizmus a výpočet certifikátů neorientovaných stromů.

• Úlohy hlavně na permutace a k-prvkové podmnožiny jsou zde.

Zkoušková témata

• Kombinace, variace, permutace s opakováním nebo bez něj, definice, vzorce pro výpočet. Binomické koeficienty, vztahy mezi nimi, Pascalův trojůhelník.
• Operace (funkce) Rank a UnRank pro uspořádané k-prvkové podmnožiny dané množiny (variace bez opakování) a permutace.
• Gray code - definice, vlastnosti, operace Rank a UnRank.

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 .

• Slovní úlohy hlavně na jednoduché konečné automaty a regulární výrazy jsou zde.

Orientační zkoušková témata

• Definice konečného automatu, deterministického (DKA) a nedeterministického (NKA). Jazyky rozpoznávané konečnými automaty.
• Algoritmus převodu NKA na DKA, simulace činnosti NKA bez převodu na DKA. Epsilon-přechody, jejich odstranění z automatu.
• Definice regulárního výrazu, převod regulárního výrazu na NKA.

• Slovní úlohy hlavně na přibližné hledání a operace s jazyky jsou zde.

Orientační zkoušková témata

• Konstrukce NKA pro vyhledávání v textu. Implementace automatu tabulkou nebo kódem.
• Hammingova a Levenshteinova vzdálenost, NKA pro vyhledávání v textu podřetězců/podposloupností s určitou vzdáleností od daného vzorku.

• Slovní úlohy hlavně na přibližné hledání vzorků v textu pomocí DP a úpravy probraných metod jsou zde.

Orientační zkoušková témata

• Vyhledávání v textu libovolného z dané množiny slov pomocí slovníkového automatu.
• Počet stavů slovníkového NKA a DKA.
• Přibližné hledání v textu kombinací předchozích metod.

Přednáška odpadá kvůli státnímu svátku 17.11.

Ve cvičeních, která neodpadnou, doporučujeme jednak dokončit nedodělané úlohy z konečných automatů a také podle uvážení udělat opakování, zejména méně “zažitých” témat, bývá to kombinatorické generování, izomorfizmus obecných grafů, haldy.

Slovní úlohy na prvočíselnost a náhodná čísla jsou zde.

Zkoušková témata

• Prvočísla – definice, generování, testování prvočíselnosti, prvočíselný rozklad.
• Generátory náhodných čísel
• Rychlé umocnňování, rychlé modulární umocňování.

• Slovní úlohy hlavně na Skip list a vyhledávací stromy: B, B+ jsou zde.

Orientační zkoušková témata

• Skip List
• Vyhledávací stromy, B a B+, operace v nich a jejich asymptotická složitost.

• Slovní úlohy na BVS, AVL a Splay stromy jsou zde.
• Slovní úlohy hlavně na vyhledávací stromy, B+, Splay, RB jsou zde.
• Menší mechanické procvičení je zde.

Orientační zkoušková témata

• Binární vyhledávací stromy, BVS, AVL, Splay, R-B, operace ve stromech a jejich asymptotická složitost, amortizovaná složitost operací ve splay tree.

• Další vyhledávací stromy různého druhu zde.
  

Orientační zkoušková témata

• Vícedimenzionální hledání, K-D stromy, hledání nejbližšího souseda ve 2D.

Manipulace s trie a patricia trie zde

Orientační zkoušková témata

Trie a patricia trie, jejich vlastnosti.

• Binary search tree
• AVL tree
• B tree
• B+ tree
• Red-black tree
• Splay tree
• 2-3-4 tree

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,