navigation
hledat
Toto je starší verze dokumentu!
Obsah
Řešení příkladů ze zkoušek TAL
Disclaimer: Nejlíp se vždy na učím na příkladech. Takže místo biflování skript řeším příklady ze zkoušky jako přípravu na státnice. Odpovědi nejsou matematicky přesné, ale psané tak abych si je zapamatoval. — David Vávra (Destil) 2012/05/20 15:00
Složitosti
Co to znamená f(n) = O(g(n))
Existuje kladná konstanta c, kde platí že f(n) ≤ c g(n) od nějakého přirozeného čísla n.
Definice Ω(g(n)).
Existuje kladná konstanta c, kde platí že f(n) ≥ c g(n) od nějakého přirozeného čísla n.
Co platí pro f(n) = Θ(g(n))?
Existují kladné konstanty c1 a c2, kde platí že c1 g(n) ≤ f(n) ≤ c2 g(n) od nějakého přirozeného čísla n.
Mame f(n) = 2n^(log n) + (log n)^n + 10n + 5, najdete nejmensi nejjednodussi a nejkrasnejsi g(n) takove, ze f(n) = O(g(n))
g(n) = n^n
Je dána fce f(n) = n log^3 n + n^2 + ...., najdi nejjednodušší g(n) tak, aby platilo f(n) = Θ(g(n))
g(n) = n^2
Prozkoumej T(n) = 2 T(n/2) + 1. Příklad na Master Theorem.
- n^(log_2(2)) = n
- 1 = O(n)
- prvni pripad ⇒ T(n)=Θ(n)
T(n) = 3T(n/4) + n^2
- n^2 = Ω(n^(log_4(3))
- treti pripad ⇒ T(n) = Θ(n^2)
Zjisti složitost, co to dělá a dokaž správnost:
Give(m,n,s)
s = 0; i = 1;
while i <= n
j = 1;
while j <= m
s = s + j*n;
j = j + 1;
end;
i = i + 1;
end;
Output s
O(n^2) Nevím co alg. dělá
Turingův stroj
Co je to Turingův stroj a co to znamená, když přijímá jazyk L?
Turingův stroj je teoretický model počítače. Obsahuje:
- Množinu stavů, počáteční stav a koncové stavy
- Abecedu vstupních symbolů, výstupních symbolů a prázdný symbol (na pásce)
- Přechodovou funkci, která mapuje stav a vstup na změnu stavu, výstup a posun pásky doleva nebo doprava
TS přijímá jazyk L, pokus se úspěšně zastaví na každém slově z jazyka.
Nadefinujte nedeterministicky Turinguv stroj.
Stejná definice jako v minulé otázce ale přechodová funkce může obsahovat více přechodů pro daný vstup a stav.
Rozdíl mezi tím, když TM nějaký jazyk přijímá a když jej rozhoduje.
- Když TM jazyk přijímá tak každé slovo musí schválit.
- Když TM jazyk rozhoduje tak každé slovo musí schválit nebo zamítnout, ale nezacyklit se.
Jaky je vztah mezi tridami jazyku rozpoznavanymi deterministickym a nedeterministickym Turingovym strojem?
Nedeterministický TS lze vždy převést na deterministický. Proto jazyk rozpoznávaný DTS je podmnožinout jazyka rozpoznávaného NTS.
Je dán jazyk L, jehož slova mají tvar: {0|1}* - libovolná posloupnost 0 a 1, kde ale musí být víc jedniček. Napiš TM, který rozhoduje tento jazyk. Stačí slovní popis nebo klidně i přechody. Napiš jeden netriviální stav jako přechodovou funkci.
- Hledám 1
- Když najdu přepíšu na x, vracím se na začátek pásky a hledám 0
- Když nenajdu reject
- Hledám 0
- Když najdu přepíšu na x, vrátím se na začátek pásky a hledám 1
- Když nenajdu accept
Přechodová funkce pro úplně první stav q1 (hledání jedničky):
- q1, 0 → q1, 0, R
- q1, 1 → q2, x, R
- q1, x → q1, x, R
- q1, blank → reject
Vytvorte nedeterministicky Turinguv stroj, ktery prijima slova {w#w|w je {0,1}^*} (dve slova za sebou oddelene #).
NP
Co je to třída NP a napiš jeden rozhodovací problém, který do ní nepatří.
Rozhodovací problém leží v NP pokud existuje nedeterministický Turingův stroj, který jí vyřeší a pracuje v polynomiálním čase.
Nepatří např. Existuje minimální kostra grafu menší než k?
Jaký je vztah mezi jazyky ROZHODOVANÝMI deterministickým TM a jazyky rozhodovanými nedeterministikým TM.
Rozhodování těchto jazyků je ve třídě P resp. NP.
Definovat třídu NPC
Popiš postup pro důkaz toho, že je něco NP úplné. Popiš redukci atd. Můžeš buďto všeobecně a nebo na příkladu nějakého převodu.
Co jsou to rekurzivní a rekurzivně spočetné jazyky.
Vztah mezi NP, rekurzivnými a rekurzivně spočtenými.
U <| V (redukce) a vite, ze V je rekurzivne spocetny, co muzete rict o U (nadefinujte i redukci (trojuhelnicek))
Definujte PSPACE a NPSPACE
Reknete priklad jazyka patriciho do NPSPACE
Vztah mezi P, NP, PSPACE, NPSPACE
Vztah mezi rekurzivne spocetnymi jazyky a NPSPACE
Definujte tridu jazyku RP a ZPP
Reknete priklad jazyka patriciho do RP
Vyjmenovat dvě úlohy patřící do NPC, dvě úlohy patřící no NP
Třída EXP je třída všech jazyků přijímaných TS v exponenciálním čase (nebo něco v tom smyslu), určit vztah mezi EXP, NPSPACE, NP, co-NP
Třída co-RE je doplněk jazyka RE. Co platí pro třídy R, RE, co-RE a třídu úplně všech jazyků VS. Napiš všechny inkluze, které platí. Pokud jsou některé tyto inkluze ostré, uveď příklad jazyka
