prvy termin:

1. Zadefinujte Postov koresp. problem a dokazte, ze
PKP nad 1-prvkovou abecedou je rozhodnutelny.

2. Napiste algoritmus, ktory pre vstupnu bezkontextovu
gramatiku G urci, ci jazyk nou generovany je
konecny/nekonecny/prazdny. Odovodnite korektnost
algoritmu.

3. Najdite a vysvetlite chybu v dokaze P nerovna sa
NP. Uvazujme nasledovny algoritmus pre problem KNF
splnitelnosti. Pre vstupnu formulu F preverime vsetky
mozne priradenia hodnot premennym. Ak niektore z nich
splna F, tak akceptujeme. Tento algoritmus ma zrejme
exponencialnu zlozitost. Problem KNF-slpnitelnosti
teda nepatri do triedy P. Kedze je problem
KNF-splnitelnosti NP-uplny, tak musi platit P nerovna
sa NP.

4. Popiste neformalne TS rozpoznavajuci jazyk
L={"1 na n"w | kde w je binarny zapis cisla n}
-aka je casova zlozitost vami navrhnuteho TS?
-aka by podla simulacie z prednasky bola casova a
pamatova zlozitost (pri jednotkovej i logaritmickej
cene) MRAMu simulujuceho vas TS? Vysvetlite.

5. jazyk L={#a(w)=#b(w) | n>0} sa na 1-paskovom TS
neda rozpoznat s dlzkou prechodovej postupnosti
ohranicenou konstantou. Dokazte. Vysvetlite co je
prechodova postupnost.

6. Vyslovte a dokazte Savitchovu vetu.

7. Nasledujuci problem patri do triedy NP. Dokazte.
L={kod(G)#k | kod(G) je matica susednosti grafu
G=(V,E) zapisana po riadkoch, k je prirodzene cislo a
graf G sa da rozlozit na k disjunktnych uplnych
podgrafov}


opravny termin:

1. Zadefinovat nerozhodnutelny problem,
-ukazat algoritmus, ako sa dokazuje, ze problem B je
nerozhodnutelny, ked mate problem A, o ktorom viete,
ze je nerozhodnutelny
-a ukazat to na probleme zastavenia TS

2. UTS dostal na vstup kod(T)#w, Casova zlozitost TS s
kodom kod(T) je T(n). Aka je casova zlozitost UTS pri
tomto vstupe?

3. Napiste MRAM priestorovej zlozitosti O(1) pri
jednotkovej cene pre nasledujuci problem
vstup n , a1, a2, ..., an
vystup = 1 ak a1a2..an=an...a1
-zadefinujte casovu zlozitost, jednotkovu,
logaritmicku,
-aku casovu zlozitost (jedn. / log.) ma vami navrhnuty
MRAM
- aku casovu zlozitost ma TS simulujuci tento MRAM

4. Co je to polynomialne redukovatelny model,
zadefinujte prvu pocitacovu triedu.

5. TS s jednosmernym vstupom. Ako sa robia dolne
odhady na priestor, a aplikujte to na dokaz toho, ze
na jazyk L={"a na n""b na n", n>0} nestaci priestor
konstantnej velkosti.

6. Nech f(n) je konstruovatelna funkcia. Pre aku g(n)
(najmensiu) plati NTIME(f(n)) je podmnozinou
DSPACE(g(n))?

7. Napiste definiciu NP, a dokazte, ze tento problem
patri do NP:
vstup: U={{u1, u2, ....un}, v(ui)>0, B>0, k patri N}
vystup: 1 prave vtedy ked, existuje take rozdelenie U
na K-disjunktnych podmnozin, U1, .. Uk, ze
pre vsetky i 1<=i<=k plati (Suma(cez vsetky uj
patriace Ui) v(uj) ) <=B .
(problem plnenie batoha - knapsack problem)

8. Vysvetlite, co je parametricka zlozitost na
priklade parametrickeho polynomialneho algoritmu pre
NPU problem vrcholoveho pokrytia.
(na vstupe je graf a k, chceme vediet, ci existuje
podmnozina S mnoziny vrcholov mohutnosti nanajvys k
taka, ze kazda hrana ma aspon jeden vrchol z S)