Bc. Jan Kaláb <[email protected]>

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)))))¹⁾

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.

Mějme následující funkce:

• f(n) = sqrt(2)n³
• g(n) = 10000n² + 500n + 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))

Nechť 𝓕 je množina funkcí e: ℕ → ℕ. Pro danou funkci e ∈ 𝓕 definujeme množinu funkcí O(e(n)) takto:

• O(e(n)) = {h(n) ∈ 𝓕 | ∃c ∈ ℝ⁺, ∃n₀ ∈ ℕ ∀n ∈ ℕ: n ≥ n₀ ⇒ 0 ≤ e(n) ≤ c · e(n)}

Z grafu funkcí 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)).

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ů:

• Uzlové pokrytí neorientovaného grafu množinou uzlů (o velikosti k-uzlů)
• Existence Hamiltonské kružnice v neorientovaném grafu
• Existence kliky dané velikosti
• Barvitelnost – lze daný neorientovaný graf obarvit určitým počtem barev