navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:zkouska [2009/12/16 21:18] mrlicker |
courses:a4m33pal:zkouska [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 4: | Řádek 4: | ||
| vzorový test: http://cw.felk.cvut.cz/lib/exe/fetch.php/courses/a4m33pal/zk01mb_uk_pub.pdf?id=courses%3Aa4m33pal%3Azkouska&cache=cache | 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~~ | ~~DISCUSSION~~ | ||
| ===== Vzorový test řešení ===== | ===== Vzorový test řešení ===== | ||
| - | * 1) c) d) e) (je to bubble sort s inplace swapem a zarazkou) | + | * 1) c) d) e) f) g) (je to bubble sort s inplace swapem a zarazkou) |
| - | * 3) c) -- pouzijte [[http://www.algoritmy.net/article/1417/Kruskaluv-algoritmus|Kruskaluv algoritmus]] | + | * 2) b) c) d) e) |
| - | * 4) b) -- strom == pocet vrholu - 1, 4 komponenty == -3 hrany | + | * 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 | * 5) c) -- [[http://www.algoritmy.net/article/1531/Binomialni-halda|Binomialni halda]] nebo scitani binarnich cisel | ||
| - | * 12) a) b) e) | + | * 12) a) b) e) (myslím, že správně je i c => ABS -> BS -> BS -> BBS --- //[[[email protected]|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]] | * 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 | * 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ý. | * 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). | * nejsem si jist, zda i d) by porušilo LL(1). | ||
| - | * ta gramatika neni LL1 ze zadani...(jinak co jsem to zkousel rpojet Vagner toolem, tak vsechno udela nejakou dalsi kolizi...) | + | * ta gramatika neni LL1 ze zadani...(jinak co jsem to zkousel projet Vagner toolem, tak vsechno udela nejakou dalsi kolizi...) |
| - | * 18) e) | + | * 18) e) [[http://www.beluga.ch/code/applets/huffman/|Huffman Applet]] |
| - | * 19) zkontrolovat! | + | * 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 | * a) BCS je pro a=1, zbytek má 5 | ||
| - | * b) BCS je pro b=1, zbytek má 4 | + | * b) BCS je pro b=1, zbytek má 4 |
| * c) BCS je pro c=1, zbytek má 3 | * c) BCS je pro c=1, zbytek má 3 | ||
| * d) BCS je pro b=1, d=2, zbytek má 6 | * d) BCS je pro b=1, d=2, zbytek má 6 | ||
| - | * e) BCS je pro d=6, a=1, c=7,b=8,a=9 | + | * e) BCS je pro a=1, d=6, c=7, b=8 |
| * 20) podle mě všechny platí, ale nevím | * 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://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]] | ||
