Pokročilá redukce studentů

  • There is something in between love, god and 4-dimensional directed graphs.
  • 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

  • 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):

  1. 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.
  2. 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.
    • (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.

Teoretická část

Úlohy

2009/2010

2010/2011

2011/2012

2012/2013

2013/2014

2014/2015

2015/2016

Tipy na zrychlení

Opakování PJP

courses/a4m33pal.txt · Poslední úprava: 2019/01/10 18:36 (upraveno mimo DokuWiki)
Nahoru
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0