Státnice - Věty o rekurzi I2

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Vety o rekurzi a jejich aplikace, Riceova veta (6×🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Věta o rekurzi a její aplikace (2013) - Zkoušejícího zajímalo znění, důkaz (preferoval ten přes s-m-n větu, ale spokojil se i s diagonalizačním), aplikace (Riceova věta a její znění, existence množin jako $ W_x=\{x\} $ s důkazem).
  • Věty o rekurzi, Riceova věta (2009) - Napsal jsem základní větu, generování pevných bod a větu o rekurzi v závislosti na parametrech (vše samozřejmě s těmi jednoduchými důkazy). Napsal jsem Riceovu větu a její důkaz plynoucí ze základní věty o rekurzi. Ptal se mě odkud plynou důkazy, odpovědel jsem, že z Kleeneho věty a s.m.n. Pak se ještě ptal na trochu jinou verzi "Věty o programu co vypíše sám sebe", tam jsem trochu tápal, ale intuitivně jsem věděl (tu větu jsem znal, bohužel jsem ji neuvedl).
  • vety o rekurzi (2009, Mlcek) - Ze zacatku jsme se bavili o tom, co jsem si pripravil, pak se to stocilo nekam, kde uz jsem se moc nechytal, ale prislo mi, ze mi spis chtel ukazat, jak se ty vety taky daj taky hezky a elegantne pouzit pro dukaz ruznejch kuriozit, takze to pak byla spis takova prednaska. Bohuzel jsem byl v takovym rozpolozeni, ze jsem si z ni moc neodnes :-) Kazdopadne docela pohoda.
  • Vety o rekurzii a ich aplikacie (2009, Mlcek) - Napisal som 2 z 3 zakladnych viet. Ukazal som ako sa to pouzije pri dokaze Rice. Samozrejme nasledovala otazka na 3. z viet o rekurzii (resp. pevnom bode), co vlastne viedlo na program, ktory na kazdom vstupe vypise vlasny program. Aj ked som nebol 100%-tny vo vsetkom, tiez prijemne skusanie
  • Vety o rekurzi a jejich dusledky (+ Riceova veta) (2009, Mlcek) Formuloval jsem a dokazal Vo pevnem bode, Vo generovani PB a Riceovu vetu (+ jeji dusledek). Dale to uz byl jen dialog jak se daji ty vety aplikovat (program co vypise svuj kod). Dalsi otazky jako co je to ze predikat Psi e x konverguje - rek. spoc. (halting problem), co je to mna K, Ko, jejich ekvivalence (jiz bez dukazu jen ustne).
  • Vety o rekurzii (2008,Mlček) - pre mňa najťažšia otázka, našťastie som si fotograficky zapamätal dôkaz Riceovej vety a niektoré vety o rekurzii, takže ma nevyhodil


Věta ( VoR ) ∀ ORF f ∃ (její pevný bod) n: φₙ ≃ φf(n)

💡 ∀ ORF transformacni funkci algoritmu f ∃ n tak že oba TS počítají stejnou fci (mají stejný algoritmus)
💡 n se říká pevný bod f
Dk (přes s-m-n větu)
Nechť e₁ je číslem funkce, pro kterou platí φₑ₁(e, x) ≃ φf(φₑ(e))(x), (tuto funkci bychom snadno odvodili pomocí univerzální ČRF).
Nechť b je Gödelovým číslem funkce s¹₁(e₁, e), podle s-m-n věty tedy platí, že :
φφb(e)(x) $ \stackrel{\text{dosadím s¹₁}}{≃} $ φs₁¹(e₁, e)(x) $ \stackrel{\text{obrácená sᵐₙ}}{≃} $ φₑ₁(e, x) $ \stackrel{\text{použijeme φₑ₁(e, x) ≃ φ_{f(φₑ(e))}(x)}}{≃} $ φf(φₑ(e))(x)
Protože φb je PRF (podle s-m-n), platí φb(b) a také platí, že φφb(b) ≃ φf(φb(b)), φb(b) je tedy hledaným pevným bodem f.

Důsledky VoR[editovat | editovat zdroj]

Věta ( 💡 ) ∃ prostá PRF g, která ke GČ funkce f určí její pevný bod

Věta ( 💡 ) ∀ ORF f má ∞ pevných bodů

Věta ( 💡 )n ∈ ℕ, pro nějž:

  1. Wₙ = {n}
  2. φₙ ≃ λx[n]
Dk
  1. Nechť e je Gödelovo číslo funkce definované jako φₑ⁽²⁾(x, y) ≃ μz[x = y] (💡 tedy φₑ⁽²⁾(x, y)↓x = y). Použijeme s-m-n větu a definujeme-li f(x) ≃ s₁¹(e, x), dostaneme, že φf(x) ≃ φs-1-1(e,x) ≃ φₑ(x, y) a tedy Wf(x) = {x}. Funkce f je ORF (podle s-m-n), a tak podle VoR: ∃ n: φₙ ≃ φf(n), a tak Wₙ = Wf(n) = {n}.
  2. Podobně, nechť e je GČ funkce definované jako φₑ⁽²⁾(x, y) ≃ x. Pomocí s-m-n věty definujeme-li f(x) = s₁¹(e, x), dostaneme φf(x)(y) ≃ x a s použitím VoR nalezneme n, pro něž je φₙ(y) ≃ φf(n)(y) ≃ n.

Věta ( VoR s parametry ) f(x,y) je ORF ⇒ ∃ prostá ORF n(y) taková, že φn(y) ≃ φf(n(y),y) ∀y ∈ N

Riceova v. - dk s VoR[editovat | editovat zdroj]

Věta (Rice)𝓒 třída ČRF, A𝓒 = {e | φₑ ∈ C } je RM ⇔ 𝓒 = ∅ nebo 𝓒 obsahuje všechny ČRF

💡  A𝓒 je mnozina indexů (Gödel.č.) funkci z třídy 𝓒

Dk (sporem)
předpokládejme že 𝓒 NEní ∅ a 𝓒 NEobsahuje všechny ČRF
předpokládejme sporem že A𝓒 je rekurzivní
definujme si fci f:
f(x) = a    x ∉ A𝓒
f(x) = b    x ∈ A𝓒
f je ORF
a ∈ A𝓒
b ∉ A𝓒
n je pevný bod f a φₙ≃ φf(n)
φₙ ∈ 𝓒 ⇒ n ∈ A𝓒 ⇒ f(n)=b ⇒ f(n)∉ A𝓒 ⇒ φf(n) ∉ 𝓒
φₙ ∉ 𝓒 ⇒ n ∉ A𝓒 ⇒ f(n)=a ⇒ f(n)∈ A𝓒 ⇒ φf(n) ∈ 𝓒
spor
Dk (pomocí převoditelnosti)  
 
předpokládejme že $ \cal C $ NEní ∅ a $ \cal C $ NEobsahuje všechny ČRF
ukážeme sporem že $ K ≤_1 A_\cal C $
$ e_0 $ je GČ fce nedefinové pro žádný vstup a $ φ_{e0} ∈ \overline{\cal C} $
$ e_1 $ je GČ fce $ φ_{e1}∈C $ a $ φ_{e0}≄ φ_{e1} $
$ \varphi_{e_2}(x, y)\simeq\cases{ \varphi_{e_1}(y)&je-li $x\in K$\cr \uparrow } $
$ φ_{e2}(x , y) ≃ φ_{s^1_1}(e, x) (y) ≃ φ_{f(x)}(y) $
$ x∈K ⇒ φ_{f(x)}≃φ_{e1} ⇒ φ_{f(x)}(y) ∈ C ⇒ f(x) ∈ A_\cal C $
$ x∉K ⇒ φ_{f(x)}≃φ_{e0} ⇒ φ_{f(x)}(y) ∉ C ⇒ f(x)∉ A_\cal C $
tedy $ x ∈ K ⇔ f(x) ∈ Ac $


Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓)   Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3)   Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita

🎓 - znamená kolikrát byla otázka u státnic