Historie: • a4m33pal

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í

Studijní materiály

Skripta profesora Koláře, Teoretická informatika(Grafy,poslední kapitola Gramatiky a automaty), nutné heslo na service.felk.cvut.cz

Grafy a grafové algoritmy na Algoritmy.net

Příklad fungování Fibonačiho haldy

Adaptivní Huffmanovo kódování

Grafové pojmy na STM-WIKI

RB trees demo

Příklady ze cvičení 2011

Zkouška

2020/2021

Teoretická

Praktická

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.
  • Zkouška

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

Praktická část

Teoretická část

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.

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)
  • 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ý.

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

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

2011/2012

2012/2013

2013/2014

2014/2015

2015/2016

Tipy na zrychlení

Opakování PJP

Opakování pojmů z PJP

courses/a4m33pal.txt · Poslední úprava: 2022/01/15 21:37 autor: pan_sveta
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