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

Druhá domácí úloha

Zkoušková témata

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

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

Třetí domácí úloha

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.

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

Čtvrtá domácí úloha

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

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.

Pátá domácí úloha

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.

Šestá domácí úloha

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.

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

(V přípravě)

Orientační zkoušková témata

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.
Applet pro R-B stromy 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,

Setkáváme se občas s přáním, abychom učinili naše předměty pro studenty snazší. Jestli máte jako student toto přání také, ozvěte se, vyjdeme vám vstříc. Uděláme to jednoduše tak, že Vám dáme něco zajímavého k nastudování. Čím více toho nastudujete, tím snazší pro Vás naše předměty budou.
[Karl Taylor Compton, prezident Massachusettského technologického institutu, v osobní komunikaci v r. 1935 ]