IRZ - Izpit Flashcards
Definiraj prehodno funkcijo turingove mašine δ
δ: Q x Γ –> Q x Γ x {L, R, S}
Predstavi turingovo mašino t = (Q, Σ, Γ, δ, q0, B, F)
Q je množica stanj kontrolne enote. Σ je vhodna abeceda. Γ je abeceda traku. δ : funkcija prehodov q0 je začetno stanje Turingovega stroja. B je poseben simbol delovnega traku. F je množica končnih stanj Turingovega stroja.
Definiraj kdaj je jezik generiran s T
G(T) = {w | w ∈ Σ* ∧ T sčasoma zapiše w na trak}
Definiraj prehodno funkcijo turingove mašine δ za mašino z več trakovi
δ: Q x Γ^n –> Q x (Γ x {L, R, S})^n
n je število trakov
Naj bo S ⊆ 𝛴* jezik (množica). Kdaj je jezik odločljiv, pol odločljiv in neodločljiv?
- S je odločljiv če ∃TM, ki lahko odgovori z DA/NE na ``Je x ∈ S?’, za vsak x ∈ 𝛴*.
- S je polodločljiv če ∃TM, ki lahko odgovori z DA na ``Je x ∈ S?’’, kadarkoli x ∈ S.
- S je neodločljiv če ne obstaja nobenega TM, ki bi lahko odgovoril z DA/NE na ``Je x ∈ S?’’, za vsak x ∈ S.
Kako je definiran jezik odločitvenega problema
Jezik odločitvenega problema D je množica L(D), ki je definirana z L(D) = {〈d〉∈ 𝛴* | d je pozitivni primer D - ja}.
Naj bo D odločitveni problem. Kdaj je problem odločljiv, pol odločljiv in neodločljiv?
- D je odločljiv (izračunljiv) če je L(D) odločljiva množica;
- D je polodločljiv če je L(D) polodločljiva množica;
- D je neodločljiv (neizračunljiv) če je L(D) neodločljiva množica.
definiraj univerzalni jezik K0
K0 = L (DHalt) = { ⟨T, w⟩ | T se ustavi na w }
definiraj diagonalni jezik K
K = { ⟨T, T⟩ | T se ustavi na ⟨T⟩ }.
Definiraj DTIME(T(n)) formalno in z besedami.
- DTIME(T(n)) = {L | L je jezik ∧ L ima deterministično časovno zahtevnost T(n)}
- DTIME(T(n)) vsebuje vse L-je za katere je problem w ∈? L lahko deterministično rešljiv v ⩽ T(|w|) času.
- DTIME(T(n)) = {D | D je odločitveni problem ∧ D ima deterministično časovno zahtevnost T(n)}
- DTIME(T(n)) ima vse D - je čigar primeri d so lahko deterministično rešljivi v ⩽ T(|⟨d⟩|) času.
Definiraj NTIME(T(n)) formalno in z besedami.
- NTIME(T(n)) = {L | L je jezik ∧ L ima nedeterministično časovno zahtevnost T(n)}
- NTIME(T(n)) vsebuje vse L - je za katere je lahko problem w ∈? L nedeterministično rešljiv v ⩽ T(|w|) času.
- NTIME(T(n)) = {D | D je odločitveni problem ∧ D je nedeterministične časovne zahtevnosti T(n)}
- NTIME(T(n)) ima vse D - je čigar primeri d so lahko nedeterministično rešljivi v ⩽ T (|⟨d⟩|) času.
Definiraj DSPACE(S(n)) formalno in z besedami.
- DSPACE(S(n)) = {L | L je jezik ∧ L ima deterministično prostorsko zahtevnost S (n)}
- DSPACE(S(n)) vsebuje vse L-je za katere je lahko problem w ∈? L deterministično rešljiv na ⩽ S(|w|) prostoru.
- DSPACE(S(n)) = {D | D je odločitveni problem ∧ D je deterministične prostorske zahtevnosti S(n)}
- DSPACE(S(n)) ima vse D čigar primeri d so lahko deterministično rešljivi na ⩽ S (|⟨d⟩|) prostoru.
Definiraj NSPACE(S(n)) formalno in z besedami.
- NSPACE(S(n)) = {L | L je jezik ∧ L je nedeterministične prostorske zahtevnosti S (n)}
- NSPACE(S(n)) ima vse L - je za katere w ∈? L je lahko nedeterministično rešljiv na ⩽ S (|w|) prostoru. Odločitveni problem D ima nedeterministično prostorsko zahtevnost S(n), če je (njegov) jezik L(D) nedeterministične prostorske zahtevnosti S(n).
- NSPACE(S(n)) = {D | D je odločitveni problem ∧ D ima nedeterministično prostorsko zahtevnost S(n)}
- NSPACE(S(n)) ima vse D-je čigar primeri d so lahko nedeterministično rešljivi na ⩽ S (|⟨d⟩|) prostoru.
Zapišo relacijo DSPACE(S(n)) z razredi DTIME formalno in z besedami
L ∈ DSPACE(S(n)) ∧ S(n) ⩾ log2(n) ⇒ ∃c : L ∈ DTIME(c^S(n))
Kar je lahko rešljivo na prostoru O(S(n)), je lahko tudi rešljivo (največ) v času O(c^S(n)).
Zapišo relacijo NTIME(T(n)) z razredi DTIME formalno in z besedami
L ∈ NTIME (T(n)) ⇒ ∃c : L ∈ DTIME(c^T(n))
Kar je lahko rešljivo nedeterministično v času O(T(n)), je lahko rešljivo deterministično največ v času O(c^T(n)). Posledično, zamenjava nedeterminističnega algoritma z determinističnim povzroči največ eksponentno rast v času, ki je potreben za reševanje problema.
