Vsak naj po najboljših močeh dopolni seznam z vprašanji, ki jih je dobil na ustnem izpitu. Hvala! Vprašanja na dnu seznama, ki so označena z zvezdico, se na ustnem izpitu niso pojavila, ampak so koristna za razumevanje snovi.

Kaj je Turingov stroj?

Turingov stroj je standardna formalizacija intuitivnega pojma algoritma. Zamislil si ga je Alan Turing leta 1936, in sicer se opira na model človeka, ki rešuje problem - glava, svinčnik, papir.

Osnovni model TS: trak (neskončen v eno smer, razdeljen na celice, simboli iz končne abecede, le končno mnogo celic je nepraznih), nadzorna enota (se nahaja v enem od končno mnogo stanj, ima čitalno okno nad eno celico traku).

Churcheva teza: Ali je dokazljiva? Ali jo je mogoče ovreči? Kako?

Churcheva oziroma Church-Turingova teza pravi, da je Turingov stroj sposoben izračunati vse, kar se (intuitivno) izračunati da. Teza ni dokazljiva, v moč Turingovih strojev se lahko prepričamo le tako, da na njih "sprogramiramo" čim več čim težjih nalog. Ovrgli bi jo lahko, če bi z nekim drugim računskim modelom izračunali rezultat naloge, ki ga s Turingovim strojem nikakor ne bi mogli izračunati, vendar to ni še nikomur uspelo.

Definicija Turingovih jezikov in rekurzivnih jezikov.

Turingovi jeziki so jeziki, ki jih sprejemajo Turingovi stroji. Obstajati mora torej Turingov stroj M, da velja L(M) = L. S tujko smo tem jezikom rekli, da so recursively enumerable.

Jezik Turingovega stroja L(M) je množica besed, ki jih lahko postavimo stroju na vhod in bo pri procesiranju teh besed Turingov stroj prišel v končno stanje. Torej, ko bo besedo sprocesiral, se bo TS nahajal v končnem stanju.

Rekurzivne jezike definiramo tako: Obstaja Turingov stroj, ki nam za vsako besedo zna odgovoriti z DA ali NE na vprašanje, če se ta beseda nahaja v jeziku.

Trenutni opis, prehod med stanji.

Trenutni opis je v splošnem Γ* x Q x Γ*, torej niz iz tračne abecede, stanje Turingovega stroja, in spet niz iz tračne abecede. Trenutni opis je torej trojka (α₁, q, α₂). α₁ je niz tračnih simbolov, ki se nahaja levo od okna. Okno se nahaja na skrajno levem simbolu niza α₂, ki se v desno nadaljuje do prvega od neskončno mnogo Bjev.

Relacija x→_My nam pove, da trenutni opis y neposredno sledi iz trenutnega opisa x z enim korakom TS M.

Tranzitivno-refleksivna ovojnica x→^*_My nam pove, da obstaja zaporedje korakov stroja M, ki vodi iz TO x v TO y.

Prehod med stanji sicer določa funkcija prehodov δ - prehod v novo stanje, zapišemo simbol pod oknom, premaknemo okno levo / desno.

Tehnike programiranja. Naštej jih in jih na kratko razloži.

Turingov stroj je zaradi svoje enostavnosti zelo okoren za programiranje. Obstaja nekaj prijemov, s katerimi olajšamo programiranje:

Uporaba nadzorne enote za pomnjenje: Stanje stroja imamo sestavljeno iz dveh komponent, iz dejanskega stanja in iz shrambe za en tračni simbol.

Večsledni trak: Trak je zdaj sestavljen iz več sledi, tračna abeceda je po novem Γ = Γ₁ x Γ₂ x Γ₃ x ... x Γ_k, kjer je Γ_i tračna abeceda i-te sledi.

Prestavljanje vsebine traku: Za premik tračne vsebine v desno za dve mesti imamo stanja oblike Q = K x Γ². K je množica čistih stanj stroja. S posebnim tračnim simbolom X označimo sproščena mesta med prestavljanjem.

Podprogrami: Koncept je zelo podoben delovanju današnjih računalnikov. Del TS služi kot podprogram. Ko glavni program želi izvedbo podprograma, naredi sledeče: zapomni si tekoče stanje (lahko ga zapiše na posebno sled), preide v vhodno stanje podprograma, izvaja podprogram, ob koncu podprograma preide v izhodno stanje, iz izhodnega stanja preide v prejšnje tekoče stanje in nadaljuje glavni program. Parametre lahko prenašamo v podprogram in iz njega preko posebne sledi (ki je neomejena) ali preko pomnilnika v nadzorni enoti (ki je omejen).

Modeli računanja

Kot modele računanja smo omenjali predvsem Turingov stroj, Random Access Machine (RAM) in lambda račun. Osredotočili smo se na dokazovanje enakovrednosti teh modelov računanja.

Dokazovanje ekvivalence med modeli računanja

Kot model računanja lahko razumemo Turingove stroje, RAM (Random Access Machine), lambda račun itd. Ekvivalenco vedno dokazujemo tako, da pokažemo, da je reševanje problema z enim modelom računanja izvedljivo tudi ob uporabi drugega modela računanja. Natančneje rečeno, vedno pokažemo, da model računanja A zmore vsaj toliko kot model računanja B - nato pokažemo še, da model računanja B zmore vsaj toliko kot model računanja A. Tako sta si modela računanja ekvivalentna (enakovredna).

Naj bo M razred računskih modelov. Najti moramo sistematično proceduro S (simulacija), ki vsakemu M iz M priredi TS M' = S(M).

Različice TS. Kako smo dokazovali ekvivalenco?

Srečali smo več različic Turingovih strojev. Za vsako smo dokazovali ekvivalenco tako, da smo pokazali, da je novi TS kvečjemu enakovreden osnovnemu TS.

TS z dvosmernim trakom: Priredimo mu enosmerni dvosledni TS, kjer znak # označuje prehod na drugo sled.

Večtračni TS: neskončnih trakov. Priredimo mu 2k-sledni TS, vsaka druga sled nam označuje položaj čitalnega okna nad vsakim trakom. V splošnem pri tej prevedbi dosežemo kvadratno upočasnitev.

Nedeterministični TS: Generiramo zaporedje navodil po naraščajoči dolžini. Tako na determinističnem TS simuliramo delovanje nedeterminističnega TS, torej sta ekvivalentna.

Večdimenzionalni TS: Vse neprazne celice lahko vedno zapremo v k-dimenzionalno škatlo. Vsebino te k-dimenzionalne škatle lahko sedaj vrstico po vrstico zapišemo v eni dimenziji na trak.

TS z več okni: Simuliramo s TS, ki ima k + 1 sledi. Na k sledeh beležimo, kje so okna stroja M nad trakom.

Stroj z naslovljivim pomnilnikom (RAM): V bistvu gre za današnji računalnik, saj ima shranjena končno velika cela števila, ki predstavljajo bodisi podatke bodisi ukaze (ukazi so lahko aritmetični, logični ali razvejitveni).

Kaj so parcialno/totalno rekurzivne funkcije?

Turingov stroj si lahko predstavljamo kot računalnik funkcij. Če imamo na vhodu 0ⁱ¹10ⁱ²1...10^ik in nam stroj iz tega izračuna 0^m, potem je stroj izračunal funkcijo f: N^kN.

Funkcija f je v splošnem parcialna, kar pomeni, da ni nujno definirana za vse k-terke. Opozorimo, da isti TS M računa funkcije NN, N²N, N³N, ... Tem funkcijam, ki jih računajo TS, pravimo parcialno rekurzivne funkcije.

Če je funkcija definirana za vse k-terke, pravimo, da je totalna. Primer: seštevanje, množenje, fakulteta, potenciranje, logaritem, ...

Splošno rekurzivne funkcije: Kaj so, katere so, formule?

Splošno rekurzivne funkcije: kompozicija, primitivna rekurzija, ničelna funkcija, naslednik, projekcija.

Funkcija f je primitivno rekurzivna funkcija (PRF), če je ena od funkcij Z, N ali πⁿ_i; ali pa je dobljena iz PRF s končno-mnogokratno uporabo kompozicije in primitivne rekurzije. Razred PRF je zelo velik, ampak ne vsebuje vseh funkcij, ki jih smatramo za intuitivno izračunljive.

Dodajmo še minimizacijo. Funkcija f je splošno rekurzivna funkcija (SRF), če je ena od funkcij Z, N ali πⁿ_i; ali pa je dobljena iz SRF s končno-mnogokratno uporabo kompozicije, primitivne rekurzije in minimizacije.

Funkcija je splošno rekurzivna natanko takrat, ko je parcialno rekurzivna ko je izračunljiva s Turingovim strojem.

Turingov generator (Kako smo dokazali ekvivalenco?)

Jezik, ki ga generira TS M: G(M) = {w | wE^* in M izpiše w na izhodni trak}

Če M teče končno dolgo, je G(M) končen jezik regularen jezik.

Lema: Če TS generira nek jezik L, potem je ta jezik L Turingov jezik.

TS M' (sprejemnik) simulira M, vse generirane besede primerja z vhodom x, enake besede sprejme, torej velja xG(M) G(M) = L(M').

Še 3 leme: Če je L Turingov jezik, ga generira nek TS. Če je L rekurziven jezik, ga nek TS generira v kanonskem vrstnem redu. Če lahko jezik L generiramo v kanonskem vrstnem redu, je L rekurziven.

Kaj je pojem problem?

Problem je ustni izpit pri TOR 2.

Blef: Problem je neko vprašanje, na katerega z ustreznim postopkom lahko (ali pa tudi ne) poiščemo pravilen odgovor.

Jeziki in problemi

Naj bo P odločitveni problem, torej sta možna odgovora DA in NE. Primerek I (instance) problema dobimo, če formalne parametre v P nadomestimo z dejanskimi.

Z neko izbrano kodirno shemo lahko sedaj vsak I∈P zapišemo z neko besedo v Ε^*, torej z nizom vhodnih simbolov. Kode vseh primerkov problema tvorijo nek jezik v Ε^*.

Jezik Lp (množica kod pozitivnih primerkov problema P) je jezik, ki pripada problemu P.

Če je Lp rekurziven, obstaja algoritem, ki za vsak I∈P v končno mnogo korakih odloči I∈P_DA ali I∈P_NE.

Če je Lp Turingov, ampak ni rekurziven, obstaja beseda wLp, ob kateri se M nikoli ne ustavi. Torej, obstaja primerek, ki spada v P_NE, ampak tega nikoli ne dokažemo.

Če Lp ni niti Turingov, obstajata w in w' za I∈P_DA in J∈P_NE, pri katerih se M nikoli ne ustavi. Torej, obstajata primerka, ki spadata v P_DA in P_NE, ampak tega nikoli ne dokažemo.

Problem P je odločljiv, kadar je Lp rekurziven. Sicer problem P ni odločljiv.

Povezava jezika s problemom. Zakaj je dobro, da obstaja?

Naj bo P odločitveni problem, torej sta možna odgovora DA in NE. Primerek I (instance) problema dobimo, če formalne parametre v P nadomestimo z dejanskimi.

Z neko izbrano kodirno shemo lahko sedaj vsak I∈P zapišemo z neko besedo v Ε^*, torej z nizom vhodnih simbolov. Kode vseh primerkov problema tvorijo nek jezik v Ε^*.

Jezik Lp (množica kod pozitivnih primerkov problema P) je jezik, ki pripada problemu P.

Tako smo naš odločitveni problem prevedli na vprašanje, ali je beseda w element jezika L. Ta pristop je dober, ker nam glede na vrsto jezika pove veliko o odločljivosti samega problema.

Ali obstaja problem, ki ni algoritmično izračunljiv? Naštej par takšnih problemov.

Da, takšnim problemom rečemo neodločljivi problemi. Problem P je odločljiv, kadar je ustrezni jezik Lp rekurziven. Če jezik problema ni rekurziven, potem je problem neodločljiv.

Primeri takšnih problemov so: Postov korespondenčni problem (PKP), problem dvoumnosti kontekstno neodvisne gramatike (AMB), diofantske enačbe (D(k) je neodločljiv že pri k = 13 spremenljivkah), problem tlakovanja, problem domin (če lahko gre pot le po polovici Z² ali pa ne sme iti čez točko U, ki je različna od začetne in končne točke).

Splošno o prevedbah: Kaj so in kaj pomeni prevedba problema (jezika) A na problem (jezik) B.

Prevedba problema A na problem B je sestavljanje Turingovega stroja M_A za reševanje problema A z uporabo TS M_B. Če problem A prevedemo na problem B, smo dokazali, da je problem B vsaj toliko zahteven kot problem A.

M_A torej vsebuje hipotetični stroj M_B in izkorišča njegove odgovore. Odgovori so DA/NE, če je M_B algoritem, ali pa zgolj DA, če je M_B Turingov stroj.

M_A te odgovore izkorišča tako, da jih preoblikuje v svoj odgovor ali pa jih uporabi kot vhod v nek drug TS.

Kako smo skonstruirali jezik Ld, ki ni Turingov?

Besede w razvrstimo v kanonskem vrstnem redu in z njimi naredimo 2-D tabelo. Tabela je dobro definirana, in sicer za vsako polje velja f(i, j) = { 0; če w_iL(M_wj) ali 1; če w_iL(M_wj) }

Na podlagi teh vrednosti definiramo diagonalni jezik Ld = { w_k | w_kL(M_wk) }.

Ld ni Turingov jezik - dokažimo to s protislovjem. Če je Ld Turingov, potem po definiciji obstaja w_n, da velja: L_d = L(M_wn). Poglejmo, kako je s pripadnostjo točno te besede w_n jeziku Ld - v vsakem primeru pride do protislovja!

Riceov izrek

Riceov izrek: Jezikovna lastnost je rekurzivna natanko takrat, ko je trivialna.

S je jezikovna lastnost. Jezik L ima jezikovno lastnost S, če LS. S je trivialna, če je nima noben Turingov jezik ali pa če jo imajo vsi Turingovi jeziki.

Jezikovna lastnost S je rekurzivna / Turingova, če je L_S rekurziven / Turingov jezik.

Zakaj je važno vprašanje P = NP?

Odgovor nas zanima zato, ker ogromno praktičnih problemov sodi v razred NP. Gotovo njihove rešitve lahko preverimo v polinomskem času. Vendar, vsakega od njih gotovo lahko rešimo kvečjemu v eksponentnem času, kar je v praksi prepočasi.

Kako lahko iščemo odgovor na to vprašanje? Iščemo najtežje probleme v NP in skušamo vsaj za enega dokazati, da ni v P. S tem bi dokazali, da P NP in da ne velja.

Kaj je NP-težek problem?

Jezik (problem) L₀ je NP-težek, če za vsak jezik L∈NP velja, da je polinomsko časovno prevedljiv (^p) na jezik L₀ ali pa je logaritemsko prostorsko prevedljiv (^log) na jezik L₀.

Kaj je NP-poln jezik? Kaj je pretvornik R pri prevedbi jezika L na L0 s pretvornikom R?

Jezik (problem) L₀ je NP-poln, če je L₀ NP-težek in istočasno L₀NP.

Pretvornik (transducer) R z logaritemsko prostorsko omejitvijo je deterministični TS, ki ima en vhodni trak (le bere), en izhodni trak (le piše), en delovni trak (z logaritemsko prostorsko omejitvijo) in se ustavi za vsak vhod.

Jezik L je R-prevedljiv na jezik L₀, če obstaja deterministični TS M z lastnostjo R, ki za vsak vhod x vrne izhod M(x), za katerega velja: M(x)L₀ xL.

Preprosteje rečeno, s pomočjo stroja M vprašanje "ali je beseda x element jezika L?" prevedemo na vprašanje "ali je M(x) beseda jezika L₀?".

Savitchev izrek? Odnos med P, NP, PSPACE in NSPACE? Kako smo dokazali PSPACE = NSPACE?

Savitchev izrek pravi, da za vsako funkcijo f(n) log n in f(n) popolnoma prostorsko predstavljiva velja: NSPACE(f(n)) DSPACE(f²(n))

Če funkcija ni popolnoma prostorsko predstavljiva (je pa prostorsko predstavljiva), mora veljati f(n) n.

Odnos: P NP PSPACE = NSPACE

P NP: To je trivialno.

NP PSPACE:

1. Za velja

2. Zaradi Savitchevega izreka velja tudi (za isti k) in zaradi tega velja

PSPACE = NSPACE: Z gotovostjo lahko trdimo PSPACE NSPACE. Poglejmo na situacijo še v nasprotni smeri:

1. NSPACE je po definiciji enakovreden _i>=1 NSPACE(nⁱ).

2. To je z uporabo Savitchevega izreka vsebovano v _i>=1 DSPACE(n²ⁱ).

3. To je definitivno vsebovano v PSPACE.

PSPACE in NSPACE torej morata biti enakovredna.

* Kaj je prostorska zahtevnost? Kaj je časovna zahtevnost?

M je TS s prostorsko omejitvijo S(n), če za vsak vhod dolžine n stroj obišče S(n) celic na vsakem delovnem traku. Takrat pravimo, da ima jezik L(M) prostorsko zahtevnost S(n).

M je TS s časovno omejitvijo T(n), če za vsak vhod dolžine n stroj naredi T(n) korakov. Takrat ima jezik L(M) časovno zahtevnost T(n).

* Katere razrede zahtevnosti poznamo?

Poznamo DSPACE(S(n)) (L ima deterministično prostorsko zahtevnost S(n)), NSPACE(S(n)) (nedeterministično), DTIME(T(n)) (časovno) in NTIME(T(n)) (nedeterministično časovno).

* Linearno stiskanje, linearna pospešitev?

Pri k-tračnih TS lahko vedno dosežemo prostorsko zahtevnost c•S(n) za vsak c > 0. Vedno lahko tudi dosežemo časovno omejitev c•T(n) za vsak c > 0 pod pogojem, da imamo več kot 1 trak in da je infimuum(T(n)/n) neskončen, kar nam pove, da je linearna pospešitev smiselna.

* Kdaj je funkcija prostorsko predstavljiva? Kdaj je popolnoma prostorsko predstavljiva?

Funkcija S(n) je prostorsko predstavljiva, če obstaja tak TS M s prostorsko omejitvijo S(n), za katerega za obstaja vhod dolžine n, na katerem M porabi natanko S(n) celic. Popolnoma prostorsko predstavljiva - za vsi vhodi dolžine n porabijo natanko S(n) celic. Analogno velja tudi za časovno predstavljivost.

* Kakšne so relacije med časovno in prostorsko zahtevnostjo?

OPOMBA: tole tudi sprašuje na usntem zato ga js neb lih z zvezdico označu

Kar lahko izračunamo:

a) v času O(f(n)), lahko tudi na prostoru O(f(n)).

b) na prostoru O(f(n)), lahko tudi v času O(c^f(n)).

c) v nedeterminističnem času O(f(n)), lahko tudi v determinističnem času O(c^f(n)).

d) na nedeterminističnem prostoru O(f(n)), lahko tudi na determinističnem prostoru O(f²(n)), če f(n)log n. Savitchev izrek!

* Kaj so pravzaprav P, NP, PSPACE, NSPACE?

P = _i>=1 DTIME(nⁱ) jeziki, ki jih TS deterministično sprejemajo v polinomsko omejenem času

Analogno še za NP (nedeterministično sprejemanje), PSPACE (polinomsko omejen prostor), NSPACE (nedeterministično sprejemanje, polinomsko omejen prostor).

Ostali uporabni "bits and pieces"

Tole so vtisi s Fri-Info.net foruma glede ustnih izpitov pri Robiču:

• ... Je pa Robič zelo kul in prijazen, ni blo treba izpeljevat kakšnih grdih dokazov, dovolj je da mu stvar opišeš.

• Nič posebnega, potem vpiše oceno in kramlja o drugih stvareh :) Ful je prjazn, res, pa čist izi stvari je sprašval, tud tiste k so pisal 6.

• Treba je predvsem razumet stvari (zanima ga intuitivna razlaga, bolj kot formalna). Zadnjo snov se je treba naučit, ker je povdarek na njej (vse je spraševal to).

• Če predelaš zapiske, bi moralo zadostovati, poleg tega pa mu je baje bolj važna sama ideja odgovora in ne tako zelo do pike natančna definicija... skratka da razumeš zadevo. So rekli, da je bil čisto prijazen in korekten.

• No, da za "zanamce" opisem ustni izpit... Noter sem sel prvi in pricakoval, da me bo dalj casa spraseval, kar je bilo tudi res (25 minut). Sla sva cez cel prvi del snovi in malo cez kompleksnost, ker ni bilo casa za vec. Profesor je res izjemno prijazen, pomaga pravilno formulirati stvari in sproti preverja, ce zadevo res razumes s prakticnimi podvprasanji (npr. ce sta L in Lcrtica rekurzivna, kaj to prakticno pomeni za algoritme v "realnem svetu"). V splosnem je ustni zelo lahek, ce pokazes razumevanje vseh izrekov, dokazov (razen ideje pri trivialnih) pa sploh ne sprasuje.

• Pri dokazih je praviloma treba poznali le glavno idejo, podrobnosti Robiča ne zanimajo kaj preveč. Btw, junija sploh ni spraševal dokazov.

• Na splošno pa ni zajeban ustni, detajlov niti ne sprašuje, je pa +, če mu jih sam od sebe poveš.

• Jaz sem bil proti koncu. 5 min, samo nekaj o prevedljivosti pa sem sel. Mislim da nas je vseh 10 (tam nekje nas je naredilo izpit) naredilo ustnega.it

• Pri razširitvah turingovih strojev me je vprašal še pretvorbe v osnovni TS (moraš bit kr natančen)