Search
This is an old revision of the document!
Rozvrh na FEL Posluchači PAL Odevzdávací systém BRUTE Diskusní fórum
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í.
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í .
Orientační zkoušková témata - převážně bakalářské opakování
Specifická zkoušková témata
Zkoušková témata
Druhá domácí úloha Zadání od 17.10. text zadání .
Třetí domácí úloha Zadání od 31.10. text zadá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 .
Orientační zkoušková témata
Čtvrtá domácí úloha Zadání od 14.11. text zadání .
Slovní úlohy na prvočíselnost a náhodná čísla jsou zde.
Pátá domácí úloha
Zadání od 28.11. (...)
Šestá domácí úloha
Zadání od 12.12. (...)
Manipulace s trie a patricia trie zde
Trie a patricia trie, jejich vlastnosti.
(V přípravě)
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 ]