====== Pokročilá redukce studentů ====== * There is something in between love, god and 4-dimensional directed graphs. * Stránky předmětu: [[http://cw.felk.cvut.cz/doku.php/courses/a4m33pal/start]] * Přednášející: RNDr. Marko Genyk-Berezovskyj * Cvičící: RNDr. Marko Genyk-Berezovskyj , Ing. Štěpán Obdržálek, Ph.D., Mgr. Ondřej Chum, Ph.D., Mgr. Viliam Lisý, MSc., Ing. Michal Perďoch, Ing. Martin Grill, RNDr. Michal Jančošek ===== Cvičení ===== * Odevzdat 4 programovací úlohy a získat alespoň 5 bodů * Za 10 testů jsou 2 body, za 9 testů 1 bod. * více: http://cw.felk.cvut.cz/doku.php/courses/a4m33pal/cviceni/start ==== Studijní materiály ==== [[http://service.felk.cvut.cz/courses/36TI/TIN-Pred-PPT.html|Skripta profesora Koláře, Teoretická informatika(Grafy,poslední kapitola Gramatiky a automaty), nutné heslo na service.felk.cvut.cz]] [[http://www.algoritmy.net/article/1369/Graf|Grafy a grafové algoritmy na Algoritmy.net]] [[http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAnimation.html|Příklad fungování Fibonačiho haldy]] [[http://www.stringology.org/DataCompression/fgk/index_cs.html| Adaptivní Huffmanovo kódování]] [[http://stm-wiki.cz/index.php/X36TIN_-_pojmy| Grafové pojmy na STM-WIKI ]] [[http://www.ece.uc.edu/~franco/C321/html/RedBlack/redblack.html| RB trees demo ]] ==== Příklady ze cvičení 2011 ==== * [[courses/a4m33pal/cviceni2011_4| 4. AVL, BST, Splay trees, RB trees]] * [[courses/a4m33pal/cviceni2011_13| 13. Izomorfismus]] ===== Zkouška ===== ==== Materiály ke zkoušce ==== Materiály můžeme mít na flashce u praktické části. * Offline verze stránek Algoritmy.net zde: http://www.uloz.to/7473930/algoritmy-net-zip * Offline verze sekce PAL na OI-WIKI: http://www.uloz.to/12199370/oi-wiki-zip (ze dne 3.1.2012) * Offline verze C++ reference: http://www.uloz.to/12442584/cplusplus-zip * Jak stáhnout offline verzi Wikipedie: http://www.kiwix.org/wiki/Main_Page ==== 2009/2010 ==== * písemná a ústní * U zkoušky se neprogramuje elektronicky, adept však může být požádán, aby napsal nebo analyzoval krátký kód nebo pseudokód. * [[courses/a4m33pal/zkouska| Zkouška]] ==== 2010/2011 ==== 1.termin (13.1.2011): - **prakticka cast** (programovaci uloha) : orientovany multigraf reprezentujici jednosmerne silnice (hrany) a krizovatky (uzly). Nalezt takovou cestu grafem, pri niz projdeme kazdou silnici pouze jednou a zaroven je projdeme vsechny. - **teoreticka cast** - 14 otazek s jednou nebo vice spravnymi odpovedmi. Nektere otazky za 1 bod, nektere za 2 (celkem 20 bodu). Typove totozne s ukazkovymi priklady na ofiko webu predmetu. Všechny zkoušky z PALů jsou na courseware: * [[courses/a4m33pal/zkouska2010_1| První zkoušková úloha]] (euler) : http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=udrzba * [[courses/a4m33pal/zkouska2010_2| Druhá zkoušková úloha]] (výrazy) : http://cw.felk.cvut.cz/courses/a4m33pal/getdata.php?task=vyrazy&item=zadani.pdf * [[courses/a4m33pal/zkouska2010_3| Třetí zkoušková úloha]] (polymino) : http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=polymino * [[courses/a4m33pal/zkouska2010_4| Čtvrtá zkoušková úloha]] (automat) : http://cw.felk.cvut.cz/courses/a4m33pal/getdata.php?task=automat&item=zadani.pdf a data k zásobníkovému automatu : http://cw.felk.cvut.cz/courses/a4m33pal/getdata.php?task=automat&item=ukazky.txt * [[courses/a4m33pal/zkouska2010_5| Pátá zkoušková úloha]] (silnice) : http://cw.felk.cvut.cz/courses/a4m33pal/getdata.php?task=silnice&item=zadani1.pdf ==== 2011/2012 ==== ** Praktická část ** * 4.1.2012: [[courses/a4m33pal/zkouska2012_1| První zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=makefile_refactoring * 11.1.2012: [[courses/a4m33pal/uloha6-2013| Druhá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=izomorfizmus * 18.1.2012: [[courses/a4m33pal/zkouska2012_3| Třetí zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=prumergrafu * 25.1.2012: [[courses/a4m33pal/zkouska2012_4| Čtvrtá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=hlavolam * 1.2.2012: [[courses/a4m33pal/zkouska2012_5| Pátá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=pripojeni * 8.2.2012: [[courses/a4m33pal/zkouska2012_6| Šestá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=mastermind ** Teoretická část ** * 4.1.2012: [[http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/zk1test.pdf|Zadání]], [[http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/zk1testreseny.pdf|Zadání řešené]] {{:courses:pal12_zk1testreseny.pdf|Zadání řešení (na wiki)}} *[[courses/a4m33pal/zkouska2012_1test| Diskuze k řešení]] * 11.1.2012 [[http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/zk2.zip|Zadání + řešení, řešení - praktická]] {{:courses:pal12_zk2.zip|Link na totéž na wiki}} * 18.1.2012: [[courses/a4m33pal/zkouska2012_3teorie| Zadání a řešení + diskuze]] [[courses/a4m33pal/diskuze_berezovsyk| Korespondence s Berezovským]] ==== 2012/2013 ==== ** Praktická část ** Limit byl 4 hodiny, ale většinou dávali ještě nějaký čas (15 - 60 min, jak kdy) navíc. * 19.12.2012: [[courses/a4m33pal/zkouska2013_1| První zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=bintree_automorphism * 3.1.2012: [[courses/a4m33pal/zkouska2013_2| Druhá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=nfa_language * 9.1.2012: [[courses/a4m33pal/zkouska2013_3| Třetí zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=mastermind (Stejná jako 6. z loňska) * 16.1.2012: [[courses/a4m33pal/zkouska2013_4| Čtvrtá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=binomialheaps * 17.1.2012: [[courses/a4m33pal/zkouska2013_5| Pátá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=makefile_refactoring (Stejná jako 1. z loňska) * 23.1.2012: [[courses/a4m33pal/zkouska2013_6| Šestá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=puzzle (Stejná jako 4. z loňska) * 24.1.2012: [[courses/a4m33pal/zkouska2013_7| Sedmá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=cascade * 30.1.2012: [[courses/a4m33pal/zkouska2013_8| Osmá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=dictionarynfa * 31.1.2012: [[courses/a4m33pal/zkouska2013_9| Devátá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=isomers * 6.2.2013: [[courses/a4m33pal/zkouska2013_10| Desátá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=paldistance Termíny v letním semestru: * 14.5.2013: [[courses/a4m33pal/zkouska2013_11| Jedenáctá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=maxpath * 26.8.2013: [[courses/a4m33pal/zkouska2013_12| Dvanáctá zkoušková úloha]] - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=counting_spanning_trees ** Teoretická část ** Každý dostal 5 otázek, každá byla z jiného oddílu (A - F, tudíž z jednoho oddílu jste otázku nedostali). Otázky jste si samostatně vypracovávali, pak jste si zavolali zkoušejícího a řekli mu odpověď. Klidně jste si mohli vypracovávat otázky dopředu. Je lepší nevolat si k sobě Vyskočila. Pro splnění bylo potřeba mít z každé otázky alespoň 50%. ==== 2013/2014 ==== ** Praktická část ** Limit byl 5 hodin, první hodinu byl vyhrazený čas na přemýšlení a analýzu, programovat se nesmělo. * 17.12.2013: [[courses/a4m33pal/zkouska2014_1| První zkoušková úloha]] * 8.1.2014: [[courses/a4m33pal/zkouska2014_2| Druhá zkoušková úloha]] * 15.1.2014 [[courses/a4m33pal/zkouska2014_3| Třetí zkoušková úloha]] * 22.1.2014: [[courses/a4m33pal/zkouska2014_4| Čtvrtá zkoušková úloha]] (...task=isomers2) * 29.1.2014: [[courses/a4m33pal/zkouska2014_5| Pátá zkoušková úloha]] ** Teoretická část ** * Máme dvě binomialní haldy s nějakými prvky, co se stane když se slouče. Chtěl hlavně vysvětlení jak se přesně mergují haldy stejne velikostí * Máme nějaký pattern, potřeba napsat NFA bez epsilon-přechodu tak, aby editovaná (jenom rewrite a delete) Levenshteinová vzdálenost byla přesně 2. * Počítáme permutace podle lexikografického uspořádaní. Napsat funkce která vrací permutace s rankem n!/2. * Jaká je složitost počítání kondenzace grafu, pokud je graf reprezentovaní jako neuspořádání seznam dvojic. (Tarjan, ale pří každém uzlu musíme projít celý ten seznam --> O(V*E) * Popsat všechný možný reprezentace grafu (adj list, adj matrix, Laplac matrix, incidence matrix) a jak přepsat jednou na druhou. * Algoritm který najde a vypíše všechný cesty delky 3 v acyklickém grafu. * Napište pseudokód metody INSERT pro d-nální haldu a vyslvětlete jení vlastnosti. * Kolik musí obsahovat graf s N uzly orientovaných hran, aby byl silně souvislý? (1 KSS) * [[https://docs.google.com/document/d/1G-pSpSXk0FUVInr9HSoJHrXrcrWesRgD5o4-soeDK2I/edit?usp=sharing|Příklady teoretické části]] ==== 2014/2015 ==== ** Praktická část ** Limit byly 4h. První půl hodina byla jen k přemýšlení, bez programování. Odevzdávání do upload systému. Ke konci bývá dost zpomalený. * 15.12.2014: [[courses/a4m33pal/zkouska2015_1| První zkoušková úloha - komponenty]] * 5.1.2015: [[courses/a4m33pal/zkouska2015_2| Druhá zkoušková úloha - levenhstein]] * * 22.1.2015: [[courses/a4m33pal/zkouska2015_4| Čtvrtá zkoušková úloha - stromy]] * 26.1.2015 [[courses/a4m33pal/zkouska_2015_5 | Pata zkoušková úloha - automaty]] ** Teoretická část ** 4 otázky, času dostatek, pokud aspoň tušíte - na přípravu je "oficiálně" kolem půlhodiny, v praxi asi kolik potřebujete (já přemýšlel něco přes hodinu). * Máme certifikát stromu. Jak určíme maximální stupeň uzlu, aniž bychom strom z certifikátu rekonstruovali. * Mějme binární vyhledávací strom. V kořenu stromu je uložen prvek s nejmenší hodnotou klíče. Napište pseudo-kod, který seřadí prvky ve stromu tak, aby prvek s největší hodnotou klíče byl v kořenu a v listech byly prvky s nejnižší hodnotou. * Rozhodněte, zda následující dva regulární výrazy generují stejný jazyk. * (01+0)*0 a 0(10+0)* * Máme binomiální haldu. Kořeny stromů tvoří prvky s nejnižší hodnotou klíče. Určite asymptotickou složitost odebrání prvku s nejvyšší hodnotou klíče. * Máme 2 grafy, oba n uzlů, oba mají stejné skóre n-1, n-2, ..., n/2+1, n/2+1 apod. (je to příklad, který je v těch dokumentech na cvičení), tj. všechny uzly mají rozdílný stupeň, kromě 2 uzlů, které mají stejný stupeň. Za jak dlouho stihneme ověřit izormorfismus těchto grafů v závislosti na n? * Nejvyšší stupeň uzlu v binominální haldě o s n klíči. * Nalézt pomocí DP všechny podřetězce textu, které mají od patternu Levenshteinovu vzdálenost nejvýše 3. * Graf máme zadaný pomocí váhové matice, přístup k jednomu prvku je logaritmický vzhledem k počtu uzlů grafu. Jaká bude složitost Kruskalova algoritmu? ==== 2015/2016 ==== ** Praktická část ** Limit byl 4.5 h. První půl hodina byla jen k přemýšlení, bez programování. Odevzdávání do upload systému. Berezovsky akceptoval drobne zmeny v kodu i po uplynuti casu zkousky. * 18.01.2015: [[https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=networks| První zkoušková úloha - site]] * 25.01.2015 [[courses/a4m33pal/zkouska_2016_2 | Druhá zkoušková úloha - automaty]] * 01.02.2015 [[courses/a4m33pal/zkouska_2016_3| Třetí zkoušková úloha - lineární kongruentní generátory]] ** Teoretická část ** ===== Úlohy ===== ==== 2009/2010 ==== se odevzdávají sem: [[https://cw.felk.cvut.cz/upload/secure/main.phtml?id=108]] * [[courses/a4m33pal/uloha0| Úloha 0]] * [[courses/a4m33pal/uloha1| Úloha 1]] * [[courses/a4m33pal/uloha2| Úloha 2]] * [[courses/a4m33pal/uloha3| Úloha 3]] * [[courses/a4m33pal/uloha4| Úloha 4]] ==== 2010/2011 ==== se odevzdávají sem: [[https://cw.felk.cvut.cz/upload/secure/main.phtml?id=191]] * [[courses/a4m33pal/uloha0-2010| Úloha 0]] * [[courses/a4m33pal/uloha1-2010| Úloha 1]] * [[courses/a4m33pal/uloha2-2010| Úloha 2]] * [[courses/a4m33pal/uloha3-2010| Úloha 3]] * [[courses/a4m33pal/uloha4| Úloha 4]] - stejná jako loni ==== 2011/2012 ==== * [[courses/a4m33pal/uloha0-2010| Úloha 0]] - "ohrada" stejná jako loni * [[courses/a4m33pal/uloha2-2010| Úloha 1]] - "internetove pripojeni" stejná jako loni(jenom ji měli jako 2) * [[courses/a4m33pal/uloha3| Úloha 2]] - "tarzan" stejná jako 2009/3 * [[courses/a4m33pal/uloha3-2011 | Úloha 3]] - "sklady" * [[courses/a4m33pal/uloha4-2011] | Úloha 4]] - "dna" * [[courses/a4m33pal/uloha5-2011] | Úloha 5]] - "shoda stromů" ==== 2012/2013 ==== * [[courses/a4m33pal/uloha0-2012| Úloha 0]] - "plot" * [[courses/a4m33pal/uloha1-2012| Úloha 1]] - "kampus" http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=campus * [[courses/a4m33pal/uloha2-2012| Úloha 2]] - "lyžování" http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=ski * [[courses/a4m33pal/uloha3-2012| Úloha 3]] - "jeskyně" http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=cave * [[courses/a4m33pal/uloha4-2012| Úloha 4]] - "counter" http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=word_counter * [[courses/a4m33pal/uloha5-2012| Úloha 5]] - "cable tv" http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=cable_TV ==== 2013/2014 ==== * [[courses/a4m33pal/uloha0-2012| Úloha 0]] - "Length of fence" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=fence * [[courses/a4m33pal/uloha1-2013| Úloha 1 - malá]] - "Make" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=makefile_refactoring * [[courses/a4m33pal/uloha2-2013| Úloha 2 - malá]] - "hedgehogMST" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=hedgehogMST * [[courses/a4m33pal/uloha3-2013| Úloha 3 - malá]] - "Maintenance" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=maintenance * [[courses/a4m33pal/uloha4-2013| Úloha 4 - malá]] - "Building Binomial Heaps" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=binomialheaps2 * [[courses/a4m33pal/uloha5-2013| Úloha 5 - malá]] - "Counting spanning trees" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=counting_spanning_trees * [[courses/a4m33pal/uloha6-2013| Úloha 6 - malá]] - "Small Graphs Isomorphism" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=isomorphism * [[courses/a4m33pal/uloha7-2013| Úloha 7 - malá]] - "Language accepted by NFA" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=nfa_language * [[courses/a4m33pal/uloha8-2013| Úloha 8 - malá]] - "Dictionary automaton" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=dictionarynfa * [[courses/a4m33pal/ulohaA-2013| Úloha A - velká]] - "Travelling circus" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=circus * [[courses/a4m33pal/ulohaB-2013| Úloha B - velká]] - "Cyclic Isomers" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=cyclic_isomers ==== 2014/2015 ==== * [[courses/a4m33pal/uloha0-2014| Úloha 0]] - "Length of fence" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=fence * [[courses/a4m33pal/uloha1-2014| Úloha 1]] - "Marsh Causeway" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=marshcauseway * [[courses/a4m33pal/uloha2-2014| Úloha 2]] - "Increasing Training Load" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=increasingload * [[courses/a4m33pal/uloha3-2014| Úloha 3]] - "Road Trip" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=roadtrip * [[courses/a4m33pal/uloha4-2014| Úloha 4]] - "Historical Segmented Belts" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=segmentedbelts * [[courses/a4m33pal/uloha5-2014| Úloha 5]] - "Basic Committee Work Model" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=committee * [[courses/a4m33pal/uloha6-2014| Úloha 6]] - "Word Game" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=wordgame ==== 2015/2016 ==== * [[courses/a4m33pal/uloha0-2014| Úloha 0]] - "Length of fence" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=fence * [[courses/a4m33pal/uloha1-2015| Úloha 1]] - "Backup Connection" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=backupconnection * [[courses/a4m33pal/uloha2-2015| Úloha 2]] - "Reverse an Edge" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=reverseedge * [[courses/a4m33pal/uloha3-2015| Úloha 3]] - "Tree isomorphism" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=treematch2 * [[courses/a4m33pal/uloha4-2015| Úloha 4]] - "Linear congruential generator" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=generator * [[courses/a4m33pal/uloha5-2015| Úloha 5]] - "Incomplete Automaton" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=incomplete_automaton * [[courses/a4m33pal/uloha6-2015| Úloha 6]] - "Text Search" https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=textsearch2 ==== Tipy na zrychlení ==== * [[courses/a4m33pal/zrychleni-javy|Zrychlení Javy]] * [[http://www.odi.ch/prog/design/newbies.php|Java antipatterns a reseni]] ===== Opakování PJP ===== [[courses/a4m33pal/opakovani_pjp|Opakování pojmů z PJP]] ~~DISCUSSION~~