Státnice - Věty o rekurzi I2
Vety o rekurzi a jejich aplikace, Riceova veta (6×🎓)[editovat | editovat zdroj]
Zážitky ze zkoušek |
---|
|
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ž:
- Wₙ = {n}
- φₙ ≃ λx[n]
- Dk
- 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}.
- 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) |
---|
|
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