navigation
hledat
Toto je starší verze dokumentu!
Obsah
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.
Studijní materiály
Příklady ze cvičení 2011
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.
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:
- Č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
2011/2012
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.
- 9.1.2012: Třetí zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=mastermind (Stejná jako 6. z loňska)
- 17.1.2012: 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: Šestá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=puzzle (Stejná jako 4. z loňska)
Termíny v letním semestru:
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: První zkoušková úloha
- 8.1.2014: Druhá zkoušková úloha
- 15.1.2014 Třetí zkoušková úloha
- 22.1.2014: Čtvrtá zkoušková úloha (…task=isomers2)
- 29.1.2014: Pátá zkoušková úloha
Teoretická část
- Máme dvě binomialní haldy s nějakými prvkami, 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)
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: První zkoušková úloha - komponenty
- 5.1.2015: Druhá zkoušková úloha - levenhstein
- 22.1.2015: Čtvrtá zkoušková úloha - stromy
- 26.1.2015 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?
Úlohy
2009/2010
se odevzdávají sem: https://cw.felk.cvut.cz/upload/secure/main.phtml?id=108
2010/2011
se odevzdávají sem: https://cw.felk.cvut.cz/upload/secure/main.phtml?id=191
- Úloha 4 - stejná jako loni
2011/2012
2012/2013
- Úloha 0 - „plot“
2013/2014
- Úloha 0 - „Length of fence“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=fence
- Úloha 4 - malá - „Building Binomial Heaps“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=binomialheaps2
- Úloha 5 - malá - „Counting spanning trees“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=counting_spanning_trees
- Úloha 6 - malá - „Small Graphs Isomorphism“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=isomorphism
- Úloha 7 - malá - „Language accepted by NFA“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=nfa_language
- Úloha 8 - malá - „Dictionary automaton“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=dictionarynfa
- Úloha A - velká - „Travelling circus“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=circus
2014/2015
- Úloha 0 - „Length of fence“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=fence
- Úloha 1 - „Marsh Causeway“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=marshcauseway
- Úloha 2 - „Increasing Training Load“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=increasingload
- Úloha 4 - „Historical Segmented Belts“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=segmentedbelts
- Úloha 5 - „Basic Committee Work Model“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=committee
2015/2016
- Úloha 0 - „Length of fence“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=fence
- Úloha 1 - „Backup Connection“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=backupconnection
- Úloha 2 - „Reverse an Edge“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=reverseedge
- Úloha 3 - „Tree isomorphism“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=treematch2
Tipy na zrychlení
Opakování PJP
Nahoru
