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.
Zapišo relacijo NSPACE(S(n)) z razredi DSPACE formalno in z besedami
NSPACE(S(n)) ⊆ DSPACE(S^2(n)), if S(n) ⩾ log2(n) ∧ S(n) is ``well-behaved.’’
Kar je lahko rešljivo nedeterministično na prostoru O(S(n)), je lahko rešljivo deterministično na prostoru O(S^2(n)). Posledično, zamenjava nedeterminističnega algoritma z determinističnim povzroči največ kvadratno rast na prostoru, ki je potreben za reševanje problema.
Zapišo relacijo DTIME(T(n)) z razredi DSPACE formalno in z besedami
DTIME(T(n)) ⊆ DSPACE(T(n))
Kar je lahko rešljivo v času O(T(n)), je lahko rešljivo tudi na prostoru O(T(n)).
Zapiši definicijo razreda NP odločitvenih problemov formalno in z besedami
NP = ∪(i⩾1)NTIME(n^i)
je razred vseh odločitvenih problemov rešljivih nedeterministično v polinomskem času
Zapiši definicijo razreda PSPACE odločitvenih problemov formalno in z besedami
PSPACE = ∪(i⩾1)DSPACE(n^i)
je razred vseh odločitvenih problemov rešljivih v polinomskem prostoru
Zapiši definicijo razreda NPSPACE odločitvenih problemov formalno in z besedami
NSPACE = ∪(i⩾1)NSPACE(n^i)
je razred vseh odločitvenih problemov nedeterministično rešljivih v polinomskem prostoru
Zapiši definicijo razreda P odločitvenih problemov formalno in z besedami
P = ∪(i⩾1)DTIME(n^i)
je razred vseh odločitvenih problemov rešljivih v determinističnem polinomskem času
Kdaj je problem D NP-poln?
∀D ∈ NP velja D* ∈ NP ∧ D ⩽p D*
Kdaj je problem D NP-težek?
∀D ∈ NP velja D ⩽p D*
Dokaži da je PSPACE ⊆ NPSPACE
Vsaka deterministična TM polinomske prostorske razsežnosti je lahko prikazana tudi kot nedeterministična TM enake prostorske kompleksnosti
