odvozování PRF
Konstanta Ck(x)=k
f1 = o(x) = λx[o]
f2 = I23(x1, x2, x3)
f3 = s(x)
f4 = S13(f3, f2)
f5 = R2(f1, f4)
f6 = S21(f5, I11, I11)
Sčítání
f1 = s(x)
f2 = I11(x)
f3 = I23(x1, x2, x3)
f4 = S13(f1, f3) = λx1x2x3[x2 + 1]
f5 = R2(f2, f4)
tj. f5(0, x2) = f2(x2) = x2
f5(x1 + 1, x2) = f4(x1, f5(x1, x2), x2) = f5(x1, x2) + 1
sum(x, y) = f5
Násobení
Jako sčítání, ale v kroku cyklu sčítáme x2 + x3.
Sign(x)
Pomocí for cyklu - konec rekurze vrací nulu, další kroky jedničku.
If
if = S23(+,
S23(*, S13(sign, I13), I23),
S23(*, S13(rsign, I13), I33))
Dělení
x/y = S32(R3(S12(o, I12), S34(if, S24(lt, S24(*, I44, s(I14), I24)), I12, I12, I22)
min(x, y
max(x, y)
n!
s-m-n věta, věta o rekurzi
Ukažte, že existuje prostá PRF f(x, y), pro
kterou platí, že
φf(x, y)(z)
≃φx(z)+φy(z).
Nechť e je Godelovo číslo takové, že φ(3)e(x, y, z) ≃ φx(z) + φy(z). Potom podle s-m-n věty platí φ(3)e(x, y, z) = φ(1)f(x, y)(z), kde f(x, y) = s21(e, x, y).
Ukažte, že existuje prostá primitivně rekurzivní funkce
f(x), pro níž platí, že
Wf(x)={x}.
Nechť e je Godelovo číslo takové, že φ(2)e(x, y) ≃ µz[x = y]. Potom podle s-m-n věty platí φ(2)e(x, y) = φf(x)(1)(y), kde f(x) = s11(e, x).
Ukažte, že existuje prostá primitivně rekurzivní funkce
f(x), pro níž platí, že
Wf(x)={x.y | y ∈ ℕ}.
Obdoba předchozího příkladu, akorát použít φ(2)e(x, y) ≃ µz[x.z = y].
Ukažte, že existuje přirozené číslo n, pro které
Wn={n}.
Z předchozího příkladu máme prostou PRF f(x), že Wf(x)={x}. Použijeme větu o rekurzi, tedy existuje pevný bod n, že φn ≃ φf(n), a tedy Wn={n}.
Ukažte, že existuje přirozené číslo n, pro které
Wn={0, ..., n}.
Obdoba předchozích příkladů, akorát použít φ(2)e(x, y) ≃ µz[x >= y] a větu o rekurzi.
Převoditelnost
Seznam problémů
| Klika |
| Instance: |
Graf G=(V, E) a přirozené číslo k. |
| Otázka: |
Obsahuje G jako podgraf úplný graf (kliku) s alespoň
k vrcholy? |
| Nezávislá množina |
| Instance: |
Graf G=(V, E) a přirozené číslo k. |
| Otázka: |
Existuje v grafu G nezávislá
množina velikosti alespoň k? Tj. existuje množina vrcholů
S⊆V, pro kterou platí, že |S|≥k a žádné
dva vrcholy v S nejsou spojeny hranou? |
| Orientovaná Hamiltonovská kružnice
(OHK) |
| Instance: |
Orientovaný graf G=(V, E). |
| Otázka: |
Existuje v grafu G hamiltonovská kružnice, tj. kružnice procházející všemi vrcholy? |
| Hamiltonovská cesta z s do
t
(HC(s, t)) |
| Instance: |
Orientovaný graf G=(V, E) a vrcholy s a t. |
| Otázka: |
Existuje v grafu G hamiltonovská cesta z vrcholu s do vrcholu t?
Tj. existuje v grafu G cesta z vrcholu s do t,
která prochází každým vrcholem grafu G právě jednou? |
| Hamiltonovská cesta (HC) |
| Instance: |
Orientovaný graf G=(V, E) a vrcholy s a t. |
| Otázka: |
Existuje v grafu G hamiltonovská cesta?
Tj. existuje v grafu G cesta,
která prochází každým vrcholem grafu G právě jednou? |
| Obchodní cestující (TSP) |
| Instance: |
Množina měst C={c1,...,cn}, vzdálenost d(ci,cj) přirozené číslo pro každá dvě města ci,cj, přirozené číslo B. |
| Otázka: |
Existuje cyklus, který navštíví každé město právě jednou a jehož délka nepřesahuje B? Tj. existuje permutace π: {1,...,n} -> {1,...,n} taková, že
( ∑i=1n-1 d(cπ(i), cπ(i+1)) ) ≤ B?
|
| Batoh |
| Instance: |
Množina předmětů
A, pro každý předmět a přirozené číslo
s(a) udávající jeho velikost a přirozené číslo
v(a) udávající jeho cenu, přirozená čísla B a
K. |
| Otázka: |
Existuje množina
předmětů A', pro kterou platí, že ∑a∈A' s(a)≤B
a ∑a∈A' v(a)≥K? |
| Rozvrhování |
| Instance: |
Počet procesorů
m, množina úloh U, pro každou úlohu u přirozené
číslo d(u) a přirozené číslo D. |
| Otázka: |
Existuje rozdělení
množiny předmětů U na m po dvou disjunktních podmnožin
U1, ..., Um tak, aby
pro každou z nich, tedy pro každé 1≤i≤m platilo, že
∑u∈Ui d(u)≤D? |
| Celočíselné programování |
| Instance: |
Matice nad
celými čísly
A typu m×n a, vektor celých čísel b délky m. |
| Otázka: |
Existuje vektor
celých čísel x délky n, pro který platí Ax≥b? |
| Binární celočíselné programování |
| Instance: |
Matice nad
celými čísly
A typu m×n a, vektor celých čísel b délky m. |
| Otázka: |
Existuje vektor
x∈{0, 1}n, pro který platí Ax≥b? |
| Minimální tranzitivně ekvivalentní
podgraf |
| Instance: |
Orientovaný graf
G=(V, E) a přirozené číslo k. |
| Otázka: |
Existuje podgraf
G' grafu G, který by obsahoval nejvýš k hran a
pro který by platilo, že tranzitivní uzávěr G' je shodný s
tranzitivním uzávěrem G? |
Převody
Klika -> Nezávislá množina: stačí udělat doplněk hran
Vrcholové pokrytí -> Nezávislá množina:
k := |V| - k
G := G
HK -> OHK: všechny hrany HK zorientujeme oběma směry
HK -> HC(s,t): vezmeme lib. vrchol s a přidáme nový vrchol t s hranami vedoucími
do všech sousedů s.
HC(s,t) -> HC: přidáme 2 nové vrcholy a připojíme první na s a druhý na t.
HC -> TSP: Z neorientovaného grafu vytvoříme neorientovaný úplný ohodnocený graf:
* každé hraně z původního grafu přiřadíme délku 1
* přidáme nové hrany tak, aby graf byl úplný a všem těmto hranám přiřadíme délku 2
* maximální délku cesty obchodního cestujícího nastavíme na počet vrcholů grafu, což způsobí, že žádná hrana s délkou 2 nemůže být částí řešení
HC -> Minimální tranzitivně ekvivalentní podgraf: Z neorientovaného grafu vytvoříme orientovaný graf:
* každou hranu zorientujeme v obou směrech
* k := |V|, protože:
* pokud původní graf obsahuje HC, tak musí být silně souvislý
* silně souvislý graf má HC právě když má tranzitivně ekvivalentní podgraf o |V| hranách
LOUP -> BATOH:
s(a) := s(a)
v(a) := s(a)
B := 1/2 Sum(s(a))
K := 1/2 Sum(s(a))
LOUP -> ROZVRHOVÁNÍ:
m := 2
U := A
d(u) := s(a)
D := 1/2 Sum(s(a))
LOUP -> Binární celočíselné programování:
m := 2, n := |A|
/ s(a1) ... s(an) \
matice A := | |
\ -s(a1) ... -s(an) /
vektor B := ( 1/2 Sum(s(a)), -1/2 Sum(s(a)) )