Pokročilá redukce studentů
-
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í
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.
2009/2010
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:
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.
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.
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)
-
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ý.
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.
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.
Teoretická část
Úlohy
2009/2010
2010/2011
2011/2012
Úloha 0 - „ohrada“ stejná jako loni
Úloha 1 - „internetove pripojeni“ stejná jako loni(jenom ji měli jako 2)
Úloha 2 - „tarzan“ stejná jako 2009/3
-
-
-
2012/2013
2013/2014
2014/2015
2015/2016
Tipy na zrychlení
Opakování PJP