Domácí programovací úlohy

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

Termíny jednotlivých úloh: 
 
 1. zadání   4.10. -       - odevzdání do 24.10.  
 2. zadání  18.10. -       - odevzdání do  7.11. 
 3. zadání   1.11. -       - odevzdání do 21.11. 
 4. zadání  15.11. -       - odevzdání do  5.12. 
 5. zadání  29.11. -       - odevzdání do 19.12. 
 6. zadání  13.12. -       - odevzdání do   2.1.

Podmínky zápočtu

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.

1. týden - Asymptotická složitost. Reprezentace grafů. Minimální kostra grafu. Union-Find problém

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

První domácí úloha
Zadání od 4.10. ( New advances in gravitational waves observations )

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

2. týden - Eulerův tah. Algoritmy pro orientované grafy. Hamiltonova cesta

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

3. týden - Haldy binární, d-ární, binomiální, Fibonacciho

Druhá domácí úloha
Zadání od 18.10. ( Wayfarers )

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

4. týden - Izomorfismus obecných grafů a stromů

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

5. týden - Generování kombinatorických objektů. Grayovy kódy

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

Třetí domácí úloha
Zadání od 1.11. (Molecules)

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.

6. týden - Číselně teoretické algoritmy

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

7. týden - Konečné automaty, nedeterminizmus. Regulární výrazy

Čtvrtá domácí úloha

  Zadání od 15.11.

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.