Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- tin:pulsemestralka [02. 01. 2012, 09.59:47] – [Churchvoa teze] typo pitel
+++ tin:pulsemestralka [02. 08. 2026, 13.51:45] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== Tahák ======
-===== Půlsemestrálka =====
-==== Gramatika ====
-[[wp>Formal grammar]]
-//G// = (//N//, //Σ//, //P//, //S//)
-  * //N// – konečná množina neterminálů
-  * //Σ// – konečná množina terminálů, disjunktní s //N//
-  * //P// – přepisovací pravidla, obecně ve tvaru (//Σ// ∪ //N//)* //N// (//Σ// ∪ //N//)* → (//Σ// ∪ //N//)*
-  * //S// ∈ //N// – startovací symbol
-Podle tvaru //P// se rozlišují třídy gramatik.
-==== Operace nad jazyky ====
-[[wp>Formal_language#Operations_on_languages|Formal language]]
-  * Konkatenace (zřetězení): //L//₁ · //L//₂ = {//xy// | //x// ∈ //L//₁, //y// ∈ //L//₂}
-  * Iterace a pozitivní iterace:
-    * //L//⁰ = {//ε//}
-    * //Lⁿ// = //L// · //Lⁿ//⁻¹ pro //n// ≥ 1
-    * //L//* = ∪ //Lⁿ// pro pro //n// ≥ 0
-    * //L//⁺ = ∪ //Lⁿ// pro pro //n// ≥ 1
-  * Doplněk: //L//′ = //Σ//* \ //L//
-  * Průnik: //L//₁ ∩ //L//₂ = {//w// | //w// ∈ //L//₁ ∧ //w// ∈ //L//₂}
-  * Sjednocení: //L//₁ ∪ //L//₂ = {//w// | //w// ∈ //L//₁ ∨ //w// ∈ //L//₂}
-==== Regulární jazyky ====
-[[wp>Regular language]]
-=== Gramatika ===
-[[wp>Regular grammar]]
-Viz [[#gramatika]].
-Rozlišujeme pravou a levou lineární, podle pozice neterminálu na pravé straně pravidel (v příkladu je pravá):
-  * //A// → //xB//; //A//, //B// ∈ //N//, //x// ∈ //Σ//*
-  * //A// → //x//; //x// ∈ //Σ//*
-Rozlišujeme pravou a levou regulární:
-  * //A// → //xB//; //A//, //B// ∈ //N//, //x// ∈ //Σ//
-  * //A// → //x//; //x// ∈ //Σ//
-  * //S// → //ε//, pokud se //S// neobjevuje na pravé straně žádného pravidla
-=== Konečný automat ===
-[[wp>Finite-state machine]]
-//M// = (//Q//, //Σ//, //δ//, //q//₀, //F//)
-  * //Q// – konečná množina stavů
-  * //Σ// – konečná vstupní abeceda
-  * //δ// – přechodová funkce ve tvaru //δ//: //Q// × //Σ// → 2<sup>//Q//</sup>(([[wp>Power set]], potenční množina))
-  * //q//₀ ∈ //Q// – počáteční stav
-  * //F// ⊆ //Q// – množina koncových stavů
-  * Konfigurace: //C// = (//q//, //w//), (//q//, //w//) ∈ //Q// × //Σ//* (Prostě stav ve kterém se automat právě nachází a co má ještě přečíst.)
-  * Přechod automatu: binární relace ⊢ ⊆ (//Q// × //Σ//*) × (//Q// × //Σ//*)
-    * (//q//, //w//) ⊢ (//q//′, //w//′) ⇔ //w// = //aw//′ ∧ //q//′ ∈ //δ//(//q//, //a//) pro //q//, //q//′ ∈ //Q//; //a// ∈ //Σ//; //w//, //w//′ ∈ //Σ//*
-== Deterministický konečný automat ==
-Pouze se změní //δ//: //Q// × //Σ// → //Q// ∪ {//nedef//}, //nedef// ∉ //Q//.
-== Úplně definovaný konečný automat ==
-Stejný jako deterministický, ale neobsahuje //nedef//, protože //δ//: //Q// × //Σ// → //Q// musí platit pro všechny //Q// × //Σ//.
-=== Pumping lemma ===
-[[wp>Pumping lemma for regular languages]]
-∃//p// > 0: ∀//w// ∈ //L//: |//w//| ≥ //p// ⇒ ∃//x//, //y//, //z// ∈ Σ*:
-  * //w// = //xyz// ∧
-  * 0 < |//y//| ≤ //p// ∧
-  * ∀//i// ≥ 0: //xyⁱz// ∈ //L//
-Dokazuje se sporem.
-Pumping lemma je podmínka nutná, nikoliv dostačující. Takže s ní dokážete, že jazyk není ragulární, ale na důkaz že regulární je nestačí. Jak tedy dokázat regulárnost? Třeba sestavit automat.
-=== Uzávěrové vlastnosti ===
-^  Sjednocení (∪)  |  ✔  |
-^  Průnik (∩)  |  ✔  |
-^  Konkatenace (•)  |  ✔  |
-^  Iterace (*)  |  ✔  |
-^  Doplněk (‾)  |  ✔  |
-^  Reverze (ᴿ)  |  ✔  |
-^  Substituce  |  ✔  |
-^  Morfismus  |  ✔  |
-^  Inverzní morfismus  |  ✔  |
-=== Rozhodnutelné problémy ===
-  * Problém neprázdnosti: //L// ≠ ∅
-  * Problém náležitosti: //w// ∈ //L//
-  * Problém ekvivalence: //L//(//G//₁) = //L//(//G//₂)
-==== Bezkontextové jazyky ====
-[[wp>Context-free language]]
-=== Gramatika ===
-[[wp>Context-free grammar]]
-Viz [[#gramatika]].
-Bezkontextová gramatika má konečnou množinu přepisovacích pravidel //P//, tvaru:
-  * //A// → //α//, //A// ∈ //N//, //α// ∈ (//N// ∪ //Σ//)*
-=== Zásobníkový automat ===
-[[wp>Pushdown automaton]]
-//M// = (//Q//, //Σ//, //Γ//, //δ//, //q//₀, //Z//₀, //F//)
-  * //Q// – konečná množina stavů
-  * //Σ// – konečná vstupní abeceda
-  * //Γ// – konečná zásobníková abeceda
-  * //δ// – přechodová funkce ve tvaru //δ//: //Q// × (//Σ// ∪ {//ε//}) × //Γ// → 2<sup>//Q// × //Γ//*</sup>
-  * //q//₀ ∈ //Q// – počáteční stav
-  * //Z//₀ ∈ //Γ// – počáteční symbol zásobníku
-  * //F// ⊆ //Q// – množina koncových stavů
-== Determinsitický zásobníkový automat ==
-[[wp>Deterministic pushdown automaton]]
-Automat je deterministický, pokud jsou splněný obě podmínky:
-  * ∀//q// ∈ //Q//, //a// ∈ //Σ// ∪ {//ε//}, //x// ∈ //Γ//: |//δ//(//q//, //a//, //x//)| ≤ 1\\ Existuje maximálně 1 přechod pro každou //δ//.
-  * ∀//q// ∈ //Q//, //x// ∈ //Γ//: pokud //δ//(//q//, //ε//, //x//) ≠ ∅, pak //δ//(//q//, //a//, //x//) = ∅ pro //a// ∈ //Σ//\\ Můžu mít přechod který nic nečte ze vstupu při daném vrcholu zásobníku, ale pak nesmím mít se stejným vrcholem zásobníku přechod který by něco četl. Proste to musí být jednoznačné!
-Jiný zápis toho samého (je tam hezká symetrie):
-  * ∀//a// ∈ //Σ//: |//δ//(//q//, //a//, //z//)| ≤ 1 ∧ //δ//(//q//, //ε//, //x//) = ∅, nebo
-  * ∀//a// ∈ //Σ//: //δ//(//q//, //a//, //z//) = ∅ ∧ |//δ//(//q//, //ε//, //x//)| ≤ 1
-== Rozšířený zásobníkový automat ==
-//δ//: //Q// × (//Σ// ∪ {//ε//}) × //Γ//* → 2<sup>//Q// × //Γ//*</sup>
-Rozdíl je v //Γ//*, automat tedy může číst 0–//n// symbolů ze sásobníku.
-=== Syntaktická analýza ===
-== Shora dolů ==
-[[wp>Top-down parsing]]
-Přijímá prázdným zásobníkem!
-//P// = ({//q//}, //Σ//, //N// ∪ //Σ//, //δ//, //q//, //S//, ∅)
-  * Je-li //A// → //α// pravidlo z //P//, pak //δ//(//q//, //ε//, //A//) ∋ (//q//, //α//)
-  * //δ//(//q//, //a//, //a//) = {(//q//, //ε//)} pro všechna //a// ∈ //Σ//
-== Zdola nahoru ==
-[[wp>Bottom-up parsing]]
-Vyžaduje rozšířený zásobníkový automat!
-//P// = ({//q//, //r//}, //Σ//, //N// ∪ //Σ// ∪ {//#//}, //δ//, //q//, //#//, {//r//})
-  - Redukce: Je-li //A// → //α// pravidlo z //P//, pak  //δ//(//q//, //ε//, //α//) ∋ (//q//, //A//)
-  - Shift: //δ//(//q//, //a//, //ε//) = {(//q//, //a//)} pro všechna //a// ∈ //Σ//
-  - Accept: //δ//(//q//, //ε//, //S#//) = {(//r//, //ε//)}
-=== Pumping lemma ===
-[[wp>Pumping lemma for context-free languages]]
-Nechť //L// je bezkontextový jazyk. Pak existuje konstanta //k// > 0 taková, že je-li //z// ∈ //L// a |//z//| ≥ //k//, pak lze //z// zapsat ve tvaru: //z// = //uvwxy//, //vx// ≠ ε, |//vwx//| ≤ //k// a pro všechna //i// ≥ 0 je //uvⁱwxⁱy// ∈ //L//.
-Opět platí [[#pumping_lemma|to samé, co u regulárních jazyků]].
-=== Uzávěrové vlastnosti ===
-^  Sjednocení (∪)  |  ✔  |
-^  Průnik (∩)  |  ✘((Jsou uzavřené pouze na průnik s regulárními jazyky))  |
-^  Konkatenace (•)  |  ✔  |
-^  Iterace (*)  |  ✔  |
-^  Doplněk (‾)  |  ✘  |
-^  Reverze (ᴿ)  |  ✔  |
-^  Substituce  |  ✔  |
-^  Morfismus  |  ✔  |
-^  Inverzní morfismus  |  ✔  |
-=== Rozhodnutelné problémy ===
-  * Problém neprázdnosti jazyka
-  * Probém příslušnosti řetězce //w// ∈ //Σ//* do jazyka
-  * Problém konečnosti jazyka
-=== Nerozhodnutelné problémy ===
-  * Problém ekvivalence jazyků bezkontextových gramatik
-  * Problém inkluze jazyků bezkontextových gramatik
-===== Semestrálka =====
-<note important>Vědět i to, co bylo na [[#půlsemestrálka|půlsemestrálce]]!</note>
-==== Churchova teze ====
-[[wp>Church–Turing thesis]]
-Když jde něco vyčíslit, jde to udělat Turingovým strojem.
-==== Turingovy stroje ====
-[[wp>Turing machine]]
-//M// = (//Q//, //Σ//, //Γ//, //δ//, //q//₀, //q<sub>F</sub>//)
-  * //Q// -- konečná množina stavů
-  * //Σ// -- konečná vstupní abeceda, //Δ// ∉ //Σ//
-  * //Γ// -- konečná pásková abeceda, //Σ// ⊂ //Γ//, //Δ// ∈ //Γ//
-  * //δ// -- parciální přechodová funkce, //δ//: (//Q// \ {//q<sub>F</sub>//}) × //Γ// → //Q// × (//Γ// ∪ {//L//, //R//}), kde //L//, //R// ∉ //Γ//
-  * //q//₀ -- počáteční stav, //q//₀ ∈ //Q//
-  * //q<sub>F</sub>// -- koncový stav, //q<sub>F</sub>// ∈ //Q//
-Jestli má stroj více pásek, nebo je nedeterministický nijak nezvětšuje jeho schopnost přijímat jazyky!
-Turingův stroj se nazývá úplný, když pro každý vstup zastaví (tzn. že se nezacyklí).
-Jazyk se nazývá rekurzivní, když ho přijímá úplný Turingův stroj, a rekurzivně vyčíslitelný, pokud ho přijímá nějaký Turingův stroj.
-Problém může být:
-  * rozhodnutelný -- pokud jeho jazyk je rekurzivní, čili pokud ho rozhodne (dokáže říct ano/ne) nějaký úplný TS.
-  * nerozhodnutelný -- pokud není rozhodnutelný LOL
-  * částečně rozhodnutelný -- pokud je jeho jazyk rekurzivně vyčíslitelný, tzn. existuje TS který dokáže říct vždy ano, ale pro některé případy kdy by měl říct ne se zacyklí (plyne z definice rekurzivně vyčíslitelného jazyka)
-TS jsou ekvivalentní s gramatikami typu 0 (rekurzivně vyčíslitelné).
-Speciálním případem TS jsou linárně omezené automaty (LOA), je to vlastně TS ale s konečnou páskou, a dokáží přijímat kontextové jazyky
-=== Uzávěrové vlastnosti ===
-^ ^  Kontextové  ^  Rekurzivní  ^  Rekurzivně vyčíslitelné  ^
-^  Sjednocení (∪)  |  ✔  |  ✔  |  ✔  |
-^  Průnik (∩)  |  ✔  |  ✔  |  ✔  |
-^  Konkatenace (•)  |  ✔  |  ✔  |  ✔  |
-^  Iterace (*)  |  ✔  |  ✔  |  ✔  |
-^  Doplněk (‾)  |  ✔  |  ✔  |  ✘  |
-^  Reverze (ᴿ)  |  ✔  |  ✔  |  ✔  |
-^  Substituce  |  ✘  |  ✘  |  ✔  |
-^  Morfismus  |  ✘  |  ✘  |  ✔  |
-^  Inverzní morfismus  |  ✔  |  ✔  |  ✔  |
-==== Cookův teorém ====
-Je-li //L// libovolný jazyk z NP, pak je redukovatelný na [[wp>Boolean satisfiability problem|SAT problém]].
-**Důkaz:** Protože //L// ∈ //NP//, exsituje nedeterministický Turingův stroj //M// a polynom //p//(//x//) tak, že pro každé //w// ∈ //L// stroj //M// přijímá maximálně v //p//(|//w//|) krocích. Jádro důkazu tvoří konstrukce polynomiální redukce //f// z //L// na //L<sub>SAT</sub>//: Pro každý řetězec //w// ∈ //L// bude //f//(//w//) množina klauzulí, které jsou splnitelné, právě když //M// přijímá //w//.
-==== Halting problem ====
-[[wp>Halting problem]]
-Zastaví daný TS pro daný vstup? Je to částečně rozhodnutelný problém.
-Důkaz:
-  - Předpokládejme, že problém je řešitelný. Tzn. existuje program <code php>bool halt(machine M, data w) {
-	if (M(w).finished) {
-		return true;
-	} else {
-		return false;
-	}
-}</code>
-  - Zkonstrujeme program <code php>void paradox(x) {
-	if (halt(x, x)) {
-		while (true);
-	} else {
-		return;
-	}
-}</code>
-  - Co se stane, pokud zavoláme ''paradox(paradox)''?
-    * Předpokládejme, že ''halt(paradox, paradox) == true''.
-      * Pak se tedy ''paradox(paradox)'' zacyklí. Víme ale, že pokud se ''paradox(paradox)'' zacyklí, pak ''halt(paradox, paradox) == false'', což je spor!
-    * Předpokládejme, že ''halt(paradox, paradox) == false''.
-      * Pak se tedy ''paradox(paradox)'' zastaví. Víme ale, že pokud se ''paradox(paradox)'' zastaví, pak ''halt(paradox, paradox) == true'', což je také spor!
-  - V obou případech jsme došli ke sporu, tudíž program ''halt'' nemůže existovat.
-  - Je ale zřejmé, že pokud má ''halt'' odpovědět ''true'', tak to dokáže vždy, tudíž je HP __částečně rozhodnutelný__.
-==== Redukce ====
-Je to technika dokazování, kdy nalezneme algoritmický převod z jednoho problému, na problém druhý, kdy o druhém víme zda je nebo není rozhodnutelný.
-Protože lze problémy specifikovat jako jazyky, jde vlastně o převod mezi jazyky, a platí že:
-  - Není-li jazyk //A// rekurzivně vyčíslitelný, pak ani jazyk //B// není rekurzivně vyčíslitelný.
-  - Není-li jazyk //A// rekurzivní, pak ani jazyk //B// není rekurzivní.
-  - Je-li jazyk //A// rekurzivně vyčíslitelný, pak i jazyk //B// je rekurzivně vyčíslitelný.
-  - Je-li jazyk //A// rekurzivní, pak i jazyk //B// je rekurzivní.
-==== Vyčíslitelné funkce ====
-[[wp>Computable function]]
-Funkce, které je možné spočítat v obecném smyslu bez ohledu na výpočetní systém. Existují **totální funkce** (pokrývají celý obor hodnot) a **striktně parciální** (nejsou pro některé hodnoty definovány, např //div//).
-I o TS můžeme uvažovat jako o funkcích. Úplný TS je totální funkce, obyčejný TS je parciální funkce (pokud se zacyklí, funkce není definovaná).
-//x//′ = (//x//₁, //x//₂, …, //x<sub>n</sub>//) ∈ ℕᵏ
-=== Primitivně rekurzivní funkce ===
-[[wp>Primitive recursive function]]
-Třída primitivně rekurzivních funkcí obsahuje funkce, které lze sestrojit pomocí počátečních funkcí a kombinace, kompozice a primitivní rekurze. **Každá** funkce v této třídě je totální.
-== Počáteční funkce ==
-  - nulová funkce: ξ() = 0
-  - fce následníka: σ(//x//) = //x// + 1
-  - fce projekce: πⁿ<sub>//k//</sub>: ℕ<sup>//n//</sup> → ℕ (vybírá k-tou složku z n-tice)
-== Základní funkce vytvořené z počátečních ==
-  - kombinace //f// × //g//:
-    - ℕᵏ → ℕⁿ⁺ᵐ
-    - //f// × //g//(//x//) = (//f//(//x//′), //g//(//x//′)), //x// ∈ ℕᵏ
-  - kompozice //g// ∘ //f//(//x//) = //g//(//f//(//x//′)), //x// ∈ ℕᵏ
-  - primitivní rekurze:
-    - //f//(//x//′, 0) = //g//(//x//′)
-    - //f//(//x//′, //y// + 1) = //h//(//x//′, //y//, //f//(//x//′, //y//)), //x// ∈ ℕᵏ
-=== Parcialně neboli rekurzivní funkce ===
-[[wp>Μ-recursive_function]]
-Zavedeme techniku takzvané **minimalizace**, které umožnuje vytvořit funkci //f//: ℕⁿ → ℕ z jiné funkce //g//: ℕⁿ⁺¹ → ℕ kde //f//(//x//′) je nejmenší //y// takové, že:
-  * //y//(//x//′, //y//) = 0
-  * //y//(//x//′, //z//) je definována pro ∀//z// < //y//, //z// ∈ ℕ
-Zapisujeme ji pak //f//(//x//′) = µ//y//[//g//(//x//′, //y//) = 0]
-=== Turingovsky vyčíslitelné funkce ===
-Funkce, které můžeme simulovat na TS.
-== Turingovsky vyčíslitelné parciální rekurzivní funkce ==
-  - Najdeme TS simulující počáteční funkce
-  - Najdeme TS simuljící primitivně rekurzivní funkce
-  - Najdeme TS simlujicí minimalizaci
-== Funkce pomocí TS ==
-Parametry funkce můžeme hodit na pásku TS a odělit pomocí Δ. Pokud po provedení výpočtu bude na pásce výsledek funkce pro tyto parametry, TS přijme. Pokud není pro dané parametry funkce definována, TS cyklí.
-== TS pomocí funkcí ==
-Sestaví funkce pro jednotlivé funkce TS a to pro ''mov'', ''sym'', ''state'', ''cursym'', ''nexthead'', ''nextstate'', ''nexttape'' a ''stoptime''

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku