Rozdíly

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

--- tin:ukoly:2011:4 [31. 12. 2011, 13.44:00] – [Příklad 4] hamilton pitel
+++ tin:ukoly:2011:4 [16. 08. 2026, 16.30:44] (aktuální) – odstraněno - upraveno mimo DokuWiki (Neznámé datum) 127.0.0.1
@@ Řádek 1: / Řádek 1: @@
-====== Úkol 4 ======
-Bc. Jan Kaláb %%<[email protected]>%%
-===== Příklad 1 =====
-**Pomocí počátečních funkcí, a operátorů kombinace, kompozice a primitivní rekurze výjádřete funkci počítající zbytek po celočíselném dělení:**
-**//mod//: ℕ² → ℕ, //mod//(//x//, //y//) = //z// takové, že //x// = //y// * //k// + //z// pro nějaké //k// ∈ ℕ.**
-**Je možné použít funkce //plus//(//x//, //y//) a //mult//(//x//, //y//) definované v přednáškách, kromě nich nepoužívejte žádné další funkce zavedené na přednáškách mimo funkce počáteční. Nepoužívejte zjednodušenou syntaxi zápisu funkcí – dodržte přesně definiční tvar operátorů kombinace, kompozice a primitivní rekurze.**
-  * //pred//(0) = //ξ//()
-  * //pred//(x + 1) = //π//²₁(x × //pred//(x)))
-  * //monus//(//x//, 0) = //π//¹₁(x)
-  * //monus//(//x//, //y// + 1) = //pred// ∘ //monus//(//x//, //y//)
-  * //min// ≡ //monus// ∘ (//π//²₁ × (//monus// ∘ (//π//²₁ × //π//²₂)))
-  * //sg// ≡ //min// ∘ %%((%%//σ// ∘ //ξ//()) × //π//¹₁)
-  * //gt// ≡ //sg// ∘ //monus// ∘ (//π//²₁ × //π//²₂)
-  * //mod//(//x//, 0) = //FAIL//
-  * //mod//(0, //y//) = 0
-  * //mod//(//x// + 1, //y//) = //plus// ∘ (//mod//(//x//, //y//) × (//gt// ∘ (//y// × (//σ// ∘ //mod//(//x//, //y//)))))((//mod//(//x//, //y//) + (//y// > (//mod//(//x//, //y//) + 1%%))%%))
-===== Příklad 2 =====
-**Mějme danou primitivně rekurzivní funkci //crypt//: ℕ → ℕ, která pro daný vstup (zakódovaný jako přirozené číslo) vrátí jeho zašifrovanou podobu (opět zakódovanou jako přirozené číslo).**
-**Navrhněte parciálně rekurzivní funkci //decrypt//: ℕ → ℕ takovou, že ∀//n// ∈ ℕ. //decrypt// ∘ //crypt//(//n//) = //n//. Můžete použít zjednodušenou formu zápisu funkcí.**
-**Pozn.: O vlastním fungování funkce //crypt// nemáte k dispozici žádné další informace. V případě, že existují //x//, //y// ∈ ℕ takové, že //x// ≠ //y// ∧ //crypt//(//x//) = //crypt//(//y//), pak výsledkem //decrypt// ∘ //crypt//(//x//) může být //x//, nebo //y//.**
-//decrypt//(//x//) = //μy//[¬//eq//(//crypt//(//y//), //x//) = 0]
-===== Příklad 3 =====
-**Mějme následující funkce:**
-  * **//f//(//n//) = //sqrt//(2)//n//³**
-  * **//g//(//n//) = 10000//n//² + 500//n// + 211**
-**Dokažte, že //O//(//g//(//n//)) ⊂ //O//(//f//(//n//)).**
-**Pozn.: Nezapomeňte, že důkaz má dvě části: (i) //O//(//g//(//n//)) ⊆ //O//(//f//(//n//)) a (ii) //O//(//g//(//n//)) ≠ //O//(//f//(//n//))**
-{{ o.png }}
-//sqrt//(2)//n//³ = 10000//n//² + 500//n// + 211\\
-//n// = 7071,12
-  - Z grafu funkcí a výsledku rovnice je zřejmé, že od //n// = 7072 je //g//(//n//) < //f//(//n//). A protože obě funkce mají stejný definiční obor (ℕ) můžeme tvrdit že //O//(//g//(//n//)) ⊆ //O//(//f//(//n//)).
-  - Protože výsledkem rovnice je pouze jeden kořen, je navíc zřejmé, že od //n// = 7072 se funkce nikde jinde nerovnají (neprotínají), a tudíž //O//(//g//(//n//)) ≠ //O//(//f//(//n//)).
-Tedy //O//(//g//(//n//)) ⊂ //O//(//f//(//n//)).
-===== Příklad 4 =====
-**Tři kamarádi se rozhodli navštívit autem všechny obce v jednom regionu. Rádi by svoji cestu naplánovali tak, aby každou obec navštívili právě jednou (průjezd obcí se počítá jako její návštěva). Pro zjednodušení předpokládejme, že křižovatky silnic jsou pouze uvnitř obcí.**
-**Dokažte redukcí z nějakého známého NP-těžkého problému, že problém existence vhodné trasy je NP-těžký.**
-**Nápověda: Zvlášť vhodný je jeden z níže uvedených problémů:**
-  * **[[wp>Vertex cover|Uzlové pokrytí neorientovaného grafu množinou uzlů (o velikosti k-uzlů)]]**
-  * **[[wp>Hamiltonian path problem|Existence Hamiltonské kružnice v neorientovaném grafu]]**
-  * **[[wp>Clique problem|Existence kliky dané velikosti]]**
-  * **[[wp>Graph coloring|Barvitelnost – lze daný neorientovaný graf obarvit určitým počtem barev]]**
-Z nabízených problémů je zvlášť vhodný problém existence Hamiltonské kružnice v neorientovaném grafu. Problém //Výlet// tedy redukujeme na problém //Hamilton// takto:
-  * Jako uzly grafu zakódujeme města
-  * Jako hrany zakódujeme silnice mezi městy
-Nyní je zřejmé, že problém //Hamilton// je ekvivalentní problému //Výlet//. A protože víme, že problém //Hamilton// je NP úplný, je problém výlet NP těžký.

Kalábovi

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku