[[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B181/public/html/predmety/46/84/p4684006.html|Rozvrh na FEL]] [[https://www.fel.cvut.cz/cz/education/rozvrhy-ng.B181/public/html/paralelky/P46/84/par4684006.1.html|Posluchači PAL]] [[https://cw.felk.cvut.cz/brute/|Odevzdávací systém BRUTE]] [[https://cw.felk.cvut.cz/forum/forum-1525.html|Diskusní fórum]] --------------- ===== Cvičení ===== odkaz na [[ https://cw.fel.cvut.cz/wiki/be5b33alg|ealg]] ===== 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 [[courses:b4m33pal:cviceni:upload_system|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í 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. ===== 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 [[courses:b4m33pal:cviceni:plagiaty| 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 [[https://cw.felk.cvut.cz/brute/data/ae/release/2018z_b4m33pal/b4m33pal_2018z/evaluation/input.php?task=fence|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 [[https://cw.fel.cvut.cz/wiki/courses/b4m33pal/cviceni/upload_system|Evaluation system and submissions]].\\ **První domácí úloha**\\ Zadání od 3.10. [[https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=MSTpath| text zadání ]]. * Opakování asymptotické složitosti, grafy a jejich reprezentace, DFS, BFS: {{:courses:a4m33pal:cviceni:cv01.docx| příklady zde}}. * Slovní úlohy na hledání **minimálních i jiných koster** {{:courses:a4m33pal:cviceni:kostry.doc| 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ů** {{:courses:a4m33pal:cviceni:cvorigfy.doc| 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 17.10. [[https://cw.felk.cvut.cz/brute/data/ae/release/2018z_b4m33pal/b4m33pal_2018z/evaluation/input.php?task=bluepromenades| text zadání ]]. * Slovní úlohy na **různé druhy hald** {{:courses:a4m33pal:cviceni:haldy.docx| jsou zde}}. * Ukázka činnosti [[http://www.cl.cam.ac.uk/teaching/1213/AlgorithII/fibonacci.pdf| 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ů** {{:courses:b4m33pal:cviso-1.doc| 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** {{:courses:a4m33pal:cviceni:kombi1.docx|jsou zde}}. **Třetí domácí úloha**\\ Zadání od 31.10. [[https://cw.felk.cvut.cz/brute/data/ae/release/2018z_b4m33pal/b4m33pal_2018z/evaluation/input.php?task=treecycle| 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. ===== 6. týden - Konečné automaty, nedeterminizmus. Regulární výrazy ===== 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 [[courses:a4m33pal:literatura_odkazy|literatura_odkazy ]]. * Slovní úlohy hlavně na **jednoduché konečné automaty a regulární výrazy** {{:courses:a4m33pal:cviceni:ata1.docx|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. ===== 7. týden - Operace nad jazyky. Přibližné vyhledávání v textu pomocí konečných automatů ===== * Slovní úlohy hlavně na **přibližné hledání a operace s jazyky** {{:courses:a4m33pal:cviceni:ata2.docx | jsou zde}}. **Čtvrtá domácí úloha**\\ Zadání od 14.11. [[https://cw.felk.cvut.cz/brute/data/ae/release/2018z_b4m33pal/b4m33pal_2018z/evaluation/input.php?task=interword| 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. ===== 8. týden - Slovníkové automaty. Implementace automatů ===== * Slovní úlohy hlavně na **přibližné hledání vzorků v textu pomocí DP a úpravy probraných metod ** {{:courses:a4m33pal:cviceni:ata3.docx| 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. ===== 9. týden - Číselně teoretické algoritmy ===== Slovní úlohy na prvočíselnost a náhodná čísla {{:courses:a4m33pal:cviceni:cvrndprimes.docx|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í. ===== 10. týden - Skip list, Vyhledávací stromy: B, B+ ===== * Slovní úlohy hlavně na **Skip list a vyhledávací stromy: B, B+ ** {{:courses:a4m33pal:cviceni:cv11_2015.docx| jsou zde. }} **Orientační zkoušková témata**\\ * Skip List * Vyhledávací stromy, B a B+, operace v nich a jejich asymptotická složitost. ===== 11. týden - Vyhledávací stromy: B+ a 2-3-4 ===== **Šestá domácí úloha**\\ Zadání od 12.12. (...) * Slovní úlohy na BVS, AVL a Splay stromy {{:courses:a4m33pal:cviceni:cvbvsetsplay.docx| jsou zde. }} * Slovní úlohy hlavně na vyhledávací stromy, B+, Splay, RB {{:courses:a4m33pal:cviceni:cv13nyni.docx|jsou zde.}} * Menší mechanické procvičení {{:courses:a4m33pal:cviceni:stromy0.docx| 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. ===== 12. týden - Hledání ve více dimenzích, K-D stromy ===== * Další vyhledávací stromy různého druhu {{:courses:a4m33pal:cviceni:cv13mb.docx| zde}}. \\ **Orientační zkoušková témata**\\ * Vícedimenzionální hledání, K-D stromy, hledání nejbližšího souseda ve 2D. ===== 13. týden - Trie, suffix trie, binary trie ===== Manipulace s trie a patricia trie {{:courses:b4m33pal:cv14_2017.docx| zde}} **Orientační zkoušková témata**\\ Trie a patricia trie, jejich vlastnosti. ===== 14. týden - Radix trie, segment tree ===== (V přípravě) **Orientační zkoušková témata**\\ ====== Materiály k samostatnému procvičování pro přípravu na zkoušku ====== Opakování asymptotické složitosti. Náměty k procvičení {{:courses:a4m33pal:cviceni:01complexitybare.pdf| zde}} a {{:courses:a4m33pal:cviceni:cv0.docx| zde}} a {{:courses:a4m33pal:cviceni:asymp.pdf| zde.}}\\ Grafy a jejich reprezentace. Náměty k procvičení neřešené {{:courses:a4m33pal:cviceni:cvgrafy01.pdf| zde}} a řešené {{:courses:a4m33pal:cviceni:cvgrafy01sol.pdf| zde.}} \\ **Zkouškové otázky z předchozích let** {{:courses:a4m33pal:cviceni:starezkousky01.pdf| zde.}} Kostry a minimální kostry grafů. Náměty k procvičení {{:courses:a4m33pal:cviceni:cvkostry.pdf| zde.}}\\ Řešené náměty cvičení koster : {{:courses:a4m33pal:cviceni:cvkostry.pdf| zde}} a {{:courses:a4m33pal:cviceni:cvkostrysol.doc| zde}}. Orientované grafy, eulerovské grafy, náměty k procvičení {{:courses:a4m33pal:cviceni:cvorigfy.pdf| zde.}} a {{:courses:a4m33pal:cviceni:cvsicoetal.pdf| zde.}}\\ Řešené náměty cvičení orientovaných grafů {{:courses:a4m33pal:cviceni:cvorigfysol2.doc| zde}} a {{:courses:a4m33pal:cviceni:cvsicoetalsol.doc| zde}}.\\ Jednoduché určení binární haldy {{:courses:a4m33pal:cviceni:cvbinahalda.pdf| zde}}. \\ Opakování binární haldy - kap. 6 z [CLRS], cvičení v oddílu 6.1, 6.2, 6.5. {{:courses:a4m33pal:cviceni:clrs_heaps.pdf| zde.}} \\ D-ární haldy - tamtéž - úloha 6-2 v oddílu Problems, str.167.\\ Fibonacciho halda - kap. 19 z [CLRS] {{:courses:a4m33pal:cviceni:clrs_fibheaps.pdf| zde}}. \\ Binomiální halda - tamtéž - úloha 19-3 v oddílu Problems, str.527. \\ Fibonacciho halda - Kevin Wayne: adaptované příklady podle [CLRS]: [[http://www.cs.princeton.edu/~wayne/cs423/lectures/fibonacci-4up.pdf| zde ]]. \\ Applet pro experimenty s Fibonacciho haldou: [[http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAnimation.html| zde]].\\ **Zkouškové otázky z předchozích let** {{:courses:a4m33pal:cviceni:zkhaldy.pdf| zde.}} Pro opakování základů kombinatoriky lze s výhodou využít skripta doc. Habaly pro předmět Diskrétní matematika [[http://math.feld.cvut.cz/habala/teaching/dma/dmknih11.pdf|zde]] v podkapitolách 11a - 11c. Podkapitola 11d koresponduje s tématy PAL.\\ Krátké opakování o grafovém izomorfizmu {{:courses:a4m33pal:cviceni:isiceopak.pdf| zde.}}\\ Jednodušší kombinatorické úlohy {{:courses:a4m33pal:cviceni:cvkombi1.pdf| zde}}, hodí se "kuchařková" věta 11a.5. ze skript doc. Habaly výše.\\ Řešené náměty cvičení jednoduché kombinatoriky {{:courses:a4m33pal:cviceni:cvkombi1sol.doc| zde.}}\\ Menší ilustrativní pojednání o isomorfismu grafů s příklady {{:courses:a4m33pal:cviceni:isice.pdf| zde.}}\\ Izomorfizmus a certifikáty {{:courses:a4m33pal:cviceni:cvkombiiso.pdf| zde.}}\\ **Zkouškové otázky z předchozích let ** {{:courses:a4m33pal:cviceni:zkcombiold.pdf| zde.}}, pozor, letos je témat ke zkoušce o něco více. Konečné automaty, regulární výrazy {{:courses:a4m33pal:cviceni:cvautomaty1.pdf| zde.}}\\ Řešené náměty Konečné automaty: {{:courses:a4m33pal:cviceni:cvaty08sol.pdf| zde}}, {{:courses:a4m33pal:cviceni:cvautomaty1.docx| zde}}.\\ **Zkouškové otázky z předchozích let ** {{:courses:a4m33pal:cviceni:zkaty1.pdf| zde.}}\\ Hledání v textu pomocí konečných automatů, lze využít předchozí cvičení a dále úlohy {{:courses:a4m33pal:cviceni:cvautomaty2.pdf| zde.}} \\ Hledání v textu 1. neřešené {{:courses:a4m33pal:cviceni:cvhlevtextu1.pdf| zde.}} (přeskočte BM algoritmus.) \\ Hledání v textu 2. neřešené {{:courses:a4m33pal:cviceni:cvautomaty3.pdf| zde.}}\\ Zdroj přednášky v literatuře {{:courses:a4m33pal:cviceni:pal09_zdroje.pdf| zde.}}\\ Řešené cvičení automatů {{:courses:a4m33pal:cviceni:cvautomaty3sol.docx| zde.}}\\ Témata: Binární vyhledávací stromy, BVS, AVL, Splay, R-B, B.\\ Řešené první cvičení na stromy {{:courses:a4m33pal:cviceni:cvtrees1sol.docx| zde. }}\\ Řešené náměty opakování BVS/AVL {{:courses:a4m33pal:cviceni:cvbst_avl.pdf| zde.}}\\ Splay a R-B: {{:courses:a4m33pal:cviceni:cvtrees1unsol.pdf| zde.}} \\ Ještě jednou Splay a R-B, vč všeobecné rekurze v BVS {{:courses:a4m33pal:cviceni:cv11mb.docx| zde}} \\ Řešené náměty RB-strom {{:courses:a4m33pal:cviceni:cvrbtree.pdf| zde. }}\\ Řešené náměty splay tree {{:courses:a4m33pal:cviceni:cvsplay.pdf| zde. }} \\ Applet pro R-B stromy[[http://www.cse.yorku.ca/~aaw/Sotirios/RedBlackTree.html | zde.]]\\ Připomenutí B-stromů a BVS vůbec (opakování z bak.) {{:courses:a4m33pal:cviceni:cv07_2011.pdf| zde. }}\\ Opakování binárních vyhledávacích stromů různého druhu\\ {{:courses:a4m33pal:cviceni:cvbst_avlunsol.pdf| zde.}} \\ Splay stromy {{:courses:a4m33pal:cviceni:cvsplayunsol.pdf| zde.}} \\ RB stromy {{:courses:a4m33pal:cviceni:cvrbtreeunsol.pdf| 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// ]