===== Zkouška =====

podmínky: https://cw.felk.cvut.cz/doku.php/courses/a4m33pal/zkouska

vzorový test: http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/zk01mb_uk_pub.pdf?id=courses%3Aa4m33pal%3Azkouska&cache=cache

test z předtermínu je spolu s řešením na stránkách PALů: http://cw.felk.cvut.cz/doku.php/courses/a4m33pal/zkouska

~~DISCUSSION~~

===== Vzorový test řešení =====
    * 1) c) d) e) f) g) (je to bubble sort s inplace swapem a zarazkou)
    * 2) b) c) d) e)
    * 3) c) -- pouzijte [[http://www.algoritmy.net/article/1417/Kruskaluv-algoritmus|Kruskaluv algoritmus]] [[http://www.kasan.net/fel/pjw/|Applet algoritmu Borůvky a Jarníka]]
    * 4) b) -- strom == pocet vrcholu - 1, 4 komponenty == -3 hrany
    * 5) c) -- [[http://www.algoritmy.net/article/1531/Binomialni-halda|Binomialni halda]] nebo scitani binarnich cisel
    * 12) a) b) e) (myslím, že správně je i c => ABS -> BS -> BS -> BBS  --- //[[lukas.rychtecky@gmail.com|Lukáš Rychtecký]] 2012/01/16 18:01//)
    * 13) zřejmě platí všechny možnosti, generované slovo je u obou aa(aa)*b(b)*cd
    * 15) a) b) c) d) e) -- [[http://www.algoritmy.net/article/55/Prevod-NKA-na-DKA|Prevod NKA na DKA]]
    * 16) a) (pismena+startovni) d) e) (musi se precist minimalne d) -- je cyklicky, protoze hvezdicka
    * 17) e) protože FIRST(A) již obsahuje a z neterminálu D, pokud bychom přidali A->aA, tak přidáme a a průnik není prázdný.
      * nejsem si jist, zda i d) by porušilo LL(1).
      * ta gramatika neni LL1 ze zadani...(jinak co jsem to zkousel projet Vagner toolem, tak vsechno udela nejakou dalsi kolizi...)
    * 18) e) [[http://www.beluga.ch/code/applets/huffman/|Huffman Applet]]
    * 19) teď je to snad dobře, omlouvám se za matení
      * Applet BM [[http://www-igm.univ-mlv.fr/~lecroq/string/node14.html|Boyer-Moore]]
      *  a) BCS je pro a=1, zbytek má 5
      *  b) BCS je pro b=1, zbytek má 4
      *  c) BCS je pro c=1, zbytek má 3
      *  d) BCS je pro b=1, d=2, zbytek má 6
      *  e) BCS je pro a=1, d=6, c=7, b=8
    * 20) podle mě všechny platí, ale nevím

[[http://www.scribd.com/doc/24139618/PAL-Zapisky|Zápisky z posledního cvika s Markem]] - jakousi shodou šťastných okolností se to více či méně shoduje se vzorovým testem ;) (upozornění: mohla jsem si něco špatně napsat, takže "důvěřujte, ale prověřujte" :) )

[[http://stuff.shy.cz/parsingtbl.php|Vagneruv tool na LL1 gramatiky]]