Katedra počítačů FEL

TIS 311

Katedra počítačů FEL

Ukázka úlohy ke zkoušce z předmětu:

Textové informační systémy FEL

1. Navrhněte KMP vyhledávací stroj pro vzorek v = kakadu, 2. Pro stejný vzorek navrhněte deterministický konečný automat. 3. Simulujte činnost obou strojů na textu T = dukakakaduka, porovnejte jejich činnost z hlediska paměťové a časové složitosti.

TIS 331




1. Navrhněte BM vyhledávací stroj pro vzorek v = kakao, pro výpočet fail funkce použijte jednu z metod Bad-character shift, first fit nebo best fit. Určete pravidla pro výpočet vámi zvolené fail funkce. 2. Pro stejný vzorek navrhněte suffixový automat. 3. Simulujte činnost obou strojů na textu T = pijtekakakao, porovnejte jejich činnost z hlediska paměťové a časové složitosti.

TIS 351




1. Navrhněte AC vyhledávací stroj pro množinu vzorků V = {kolo, loto, ol}, 2. Pro stejnou množinu vzorků navrhněte deterministický konečný automat. 3. Simulujte činnost obou strojů na textu T = kolotoce, porovnejte jejich činnost z hlediska paměťové a časové složitosti.

TIS 371




1. Navrhněte CW vyhledávací stroj pro množinu vzorků V = {kolo, loto}, 2. Popište pravidla výpočtu funkcí shift1 a shift2. 3. Simulujte činnost CW vyhledávacího stroje na textu T = kolotoce, zhodnoťte jeho činnost z hlediska paměťové a časové složitosti.

TIS 391




1. Vytvořte nedeterministický faktorový automat pro vzorek v = abbbabcb. 2. Vytvořte ekvivalentní deterministický automat. 3. Pomocí tohoto automatu nalezněte nejdelší opakující se podřetězec bez překryvu (s mezerou a bez mezery) a nejdelší opakující se podřetězec s překryvem. 4. Nalezněte všechny nejčatěji se opakující podřetězce. U bodů 3 a 4 vysvětlete vztah pozice nalezeného podřetězce a čísla stavu deterministického automatu.

TIS 611




1. Vytvořte nedeterministický automat přijímající všechny podřetězce vzorku v s maximálně jednou záměnou (Hammingova vzdálenost). v = abbbabcb 2. Vytvořte ekvivalentní deterministický automat. 3. Pomocí tohoto automatu nalezněte nejdelší opakující se podřetězec bez překryvu (s mezerou a bez mezery) a nejdelší opakující se podřetězec s překryvem(s kHamm = 1). 4. Nalezněte všechny nejčatěji se opakující podřetězce. U bodů 3 a 4 vysvětlete vztah pozice nalezeného podřetězce a čísla stavu deterministického automatu.

TIS 631




1. Vytvořte nedeterministický vyhledávací automat pro vzorek v s maximálně jednou záměnou (Hammingova vzdálenost). v = abba 2. Simulujte jeho činnost nad textem aabcabbaacba pomocí dynamického programování. 3. Definujte pravidla výpočtu ve Vámi použitém algoritmu.

TIS 651




1. Vytvořte nedeterministický vyhledávací automat pro vzorek v s maximálně jednou chybou v Levensteinově vzdálenosti. v = abca 2. Simulujte jeho činnost nad textem T = bacacbbca pomocí dynamického programování. 3. Definujte pravidla výpočtu ve Vámi použitém algoritmu.

TIS 671




1. Vytvořte nedeterministický vyhledávací automat pro vzorek v s maximálně jednou chybou v Levensteinově vzdálenosti. v = abca 2. Simulujte jeho činnost nad textem T = bacacba pomocí bitového paralelismu (použijte algoritmus SHIFT-AND nebo Shift-OR). 3. Definujte pravidla výpočtu ve Vámi použitém algoritmu.

TIS 691




1. Vytvořte nedeterministický vyhledávací automat pro vzorek v s maximálně jednou záměnou (Hammingova vzdálenost). v = abba 2. Simulujte jeho činnost nad textem T = aabccba pomocí bitového paralelismu (použijte algoritmus SHIFT-AND nebo Shift-OR). 3. Definujte pravidla výpočtu ve Vámi použitém algoritmu.

TIS 711




1. Vytvořte sufixový automat pro pro přibližné protisměrné vyhledávání v textu vzorku v s maximálně jednou záměnou (Hammingova vzdálenost). v = abba 2. Simulujte jeho činnost nad textem T = bacbacbbcacca.

TIS 731




Mějme uspořádanou abecedu Σ = {a(1), b(2), c(3), d(4), e(5), f (6)}, kde číslo v závorce určuje pořadí daného symbolu v našem uspořádání. Vzdálenost dvou symbolů je definována jako absolutní hodnota rozdílu jejich pořadí, např. d(a, c)= |1 − 3| = 2. 1. Vytvořte vyhledávací automat pro vzorek v s maximálně dvěma chybami v δ vzdálenosti nad abecedou Σ. v = abbab 2. Je tento automat deterministický? 3. Simulujte práci tohoto automatu pro text T = aabcabbaacba

TIS 751




Mějme uspořádanou abecedu Σ = {a(1), b(2), c(3), d(4), e(5), f (6)}, kde číslo v závorce určuje pořadí daného symbolu v našem uspořádání. Vzdálenost dvou symbolů je definována jako absolutní hodnota rozdílu jejich pořadí, např. d(a, c)= |1 − 3| = 2. 1. Vytvořte vyhledávací automat pro vzorek v s maximálně dvěma chybami v γ vzdálenosti nad abecedou Σ. v = abbab 2. Simulujte práci tohoto automatu pro text T = aabcabbaacba

TIS 791




Mějme uspořádanou abecedu Σ = {a(1), b(2), c(3), d(4), e(5), f (6)}, kde číslo v závorce určuje pořadí daného symbolu v našem uspořádání. Vzdálenost dvou symbolů je definována jako absolutní hodnota rozdílu jejich pořadí, např. d(a, c)= |1 − 3| = 2. 1. Vytvořte vyhledávací automat pro vzorek v s maximálně dvěma chybami v γ vzdálenosti a jednou chybou v δ nad abecedou Σ. v = abbab 2. Je tento automat deterministický? 3. Simulujte práci tohoto automatu pro text T = aabcabbaacba

Katedra počítačů FEL

Recommend Documents