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.

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