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

• 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

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

• 4. AVL, BST, Splay trees, RB trees
• 13. Izomorfismus

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

• 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

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:

• První zkoušková úloha (euler) : http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=udrzba
• Druhá zkoušková úloha (výrazy) : http://cw.felk.cvut.cz/courses/a4m33pal/getdata.php?task=vyrazy&item=zadani.pdf
• Třetí zkoušková úloha (polymino) : http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=polymino
• Č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
• Pátá zkoušková úloha (silnice) : http://cw.felk.cvut.cz/courses/a4m33pal/getdata.php?task=silnice&item=zadani1.pdf

Praktická část

• 4.1.2012: První zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=makefile_refactoring
• 11.1.2012: Druhá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=izomorfizmus
• 18.1.2012: Třetí zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=prumergrafu
• 25.1.2012: Čtvrtá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=hlavolam
• 1.2.2012: Pátá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=pripojeni
• 8.2.2012: Šestá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=mastermind

Teoretická část

• 4.1.2012: Zadání, Zadání řešené Zadání řešení (na wiki)
• Diskuze k řešení
• 11.1.2012 Zadání + řešení, řešení - praktická Link na totéž na wiki
• 18.1.2012: Zadání a řešení + diskuze

Korespondence s Berezovským

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: První zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=bintree_automorphism
• 3.1.2012: Druhá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=nfa_language
• 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)
• 16.1.2012: Čtvrtá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=binomialheaps
• 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)
• 24.1.2012: Sedmá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=cascade
• 30.1.2012: Osmá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=dictionarynfa
• 31.1.2012: Devátá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=isomers
• 6.2.2013: 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: Jedenáctá zkoušková úloha - http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=maxpath
• 26.8.2013: 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%.

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)
• Příklady teoretické části

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?

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: První zkoušková úloha - site

Teoretická část

se odevzdávají sem: https://cw.felk.cvut.cz/upload/secure/main.phtml?id=108

• Úloha 0
• Úloha 1
• Úloha 2
• Úloha 3
• Úloha 4

se odevzdávají sem: https://cw.felk.cvut.cz/upload/secure/main.phtml?id=191

• Úloha 0
• Úloha 1
• Úloha 2
• Úloha 3
• Úloha 4 - stejná jako loni

• Ú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
• Úloha 3 - „sklady“
• Úloha 4 - „dna“
• Úloha 5 - „shoda stromů“

• Úloha 0 - „plot“
• Úloha 1 - „kampus“ http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=campus
• Úloha 2 - „lyžování“ http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=ski
• Úloha 3 - „jeskyně“ http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=cave
• Úloha 4 - „counter“ http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=word_counter
• Úloha 5 - „cable tv“ http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=cable_TV

• Úloha 0 - „Length of fence“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=fence
• Úloha 1 - malá - „Make“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=makefile_refactoring
• Úloha 2 - malá - „hedgehogMST“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=hedgehogMST
• Úloha 3 - malá - „Maintenance“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=maintenance
• Ú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
• Úloha B - velká - „Cyclic Isomers“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=cyclic_isomers

• Ú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 3 - „Road Trip“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=roadtrip
• Ú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
• Úloha 6 - „Word Game“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=wordgame

• Ú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
• Úloha 4 - „Linear congruential generator“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=generator
• Úloha 5 - „Incomplete Automaton“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=incomplete_automaton
• Úloha 6 - „Text Search“ https://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=textsearch2

• Zrychlení Javy
• Java antipatterns a reseni

Opakování pojmů z PJP