odkaz na ealg

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í   3.10. -       - odevzdání do 31.10.  
 2. zadání  17.10. -       - odevzdání do  7.11. 
 3. zadání  31.10. -       - odevzdání do 21.11. 
 4. zadání  14.11. -       - odevzdání do  5.12. 
 5. zadání  28.11. -       - odevzdání do 19.12. 
 6. zadání  12.12. -       - odevzdání do   2.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

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 Evaluation system and submissions.

První domácí úloha
Zadání od 3.10. text zadání .

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

Druhá domácí úloha
Zadání od 17.10. text zadání .

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

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

Třetí domácí úloha
Zadání od 31.10. text zadání .

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.

Čtvrtá domácí úloha
Zadání od 14.11. text zadání .

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.

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

Pátá domácí úloha

  Zadání od 28.11. (...)

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.

Šestá domácí úloha

  Zadání od 12.12. (...)

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

(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ší. Máte-li jako student toto přání také, 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 ]