TI2 - Pardubská - Zadania 10.06.2005 - opravny termin

Rieste styri ulohy podla vlastneho uvazenia, tie sa Vam budu hodnotit.
1. (10b)
   Vysvetlite, ako pomocou pumpovacej lemy pre regularne jazyky rozhodneme, ci je dany regularny jazyk prazdny//konecny/nekonecny.
2. (10b)
   Univerzálny TS dostal na vstupe - kod(T)#w. Co vieme povedat o casovej zlozitosti UTS (pri vypocte podla prednasky) na tomto vstupe, ak vieme, ze pre zakodovany DTS T plati
   • jeho priestorova zlozitost je O(n²)
   • jeho casova zlozitost je O(n⁴log(n))
   Vysvetlite.
3. (10b)
   MRAM sme simulovali na TS simulaciou z prednasky. Co plati o casovej a piestorovej zlozitosti TS, ak vieme, ze casova zlozitost MRAM bola
   1. O(n²) pri jednotkovej cene
   2. T(n) pri logaritmickej cene
   Vysvelite. To su dva rozne MRAMy.
4. (10b)
   PSPACE = NPSPACE. Dokazte.
5. (10b)
   Dokazte, ze nasledujuci problem patri NP.
   Vstup: BF(x₁, ..., x_n) v KNF, k patri N
   Vystup:
   • 1 ak existuje priradenie hodnot α premennym x₁, ..., x_n tak, ze v BF(α) je presne k elemnentarnych disjunkcii splnenych
   • 0 inak
   Predpokladajte, ze indexy premennych aj hodnoty su priane v dvojkovej sustave, napr.:
   (x101 or x11 or x100) and (x1 or notxx101 or x11) and (not x10 or x101 or x100), 10
6. (10b)
   Napiste definiciu pojmu pseudopolynomialny algoritmus a navrhnite pseudopolynomialny algoritmus pre problem KnapSack (plnenie batoha).