{{TOC limit}} pozn. státnicové otázky pro I2/3 jsou označené touto ikonkou: (🎓)

Vyčíslitelnost

Def. TS, RJ a RSJ. Uzavřenost RJ na doplňky. Postova v. (🎓)

Definice Turingova stroje, rekurzivního a rekurzivně spočetného jazyka. Uzavřenost rekurzivních jazyků na doplňky. Postova věta.

{{Zkazky|

• stačilo na 1*A4: definice TS, M(w)↓ a M(w)↑, definice RS a RSJ, věty o doplňcích RJ a RSJ (bez dk), postova věta s lehkým důkazem uvedeným zde, bez dalších dotazů

}}

{{thesis | Ke každému algoritmu v intuitivním smyslu existuje TS, který jej implementuje.

| Churchova-Turingova (1936) }}

{{multiple image

|align = tright |direction = horizontal

| image1 = Tm.jpg

| width1 = 310 | caption1 = TS $M = (Q, ∑, δ, q_0, F)$

| image2 = ZSV 3729090544640692881.png

| width2 = 310 | caption2 = 💡 ∀RJ je i RSJ

}}

Turingův stroj

• (k-páskový deterministický) TS je 5-tice: M = (Q, ∑, δ, q₀, F)

  • Q je konečná množina stavů (řídící jednotky)

  • ∑ je konečná pásková abeceda

    • obsahuje znak λ pro prázdné políčko

  • $δ : Q \times ∑^k -> Q \times ∑^k \times \{R, N, L\}^k ∪ \{⊥\}$ je přechodová fce

    • ⊥ je nedefinovaný přechod

  • q₀ ∈ Q je počáteční stav

  • F ⊆ Q je množina přijímajících stavů.

• Konfigurace TS obsahuje:

  • stav řídící jednotky

  • slovo na pásce

    • 💡 (od nejlevějšího neprázdného políčka do nejpravějšího)

  • pozice hlavy na pásce

    • 💡 čtené políčko v rámci slova

výpočet TS

• M(w)↓ tj. výpočet konverguje pokud výpočet nad vstupem w skončí

  • TS přijímá slovo w

    • po skončení se nachází v přijímacím stavu

  • TS odmítá slovo w

    • po skončení se NEnachází v přijímacím stavu

• M(w)↑ tj. výpočet diverguje pokud výpočet nad vstupem w nikdy neskončí

• fce f turingovsky vyčíslitelná pokud ex. TS který jí počítá (💡 tj. f(x)↓=y)

• ∀ k-páskový TS se dá převezt na 1-páskový

Rekurzivní a rekurzivně spočetný jazyk

• L(M) označíme jazyk slov přijímaných TS M

• L je rekurzivně spočetný (také částečně rozhodnutelný), pokud ∃TS M t.ž.: L = L(M).

• L je rekurzivní (také rozhodnutelný), pokud ∃TS M t.ž.: sevždy zastaví a L = L(M)

💡 RSJ je spočetně ⇒ ∀ jazyk není RSJ

Uzavřenost rekurzivních jazyků na doplňky

• L je RJ ⇒ {{overline|L}} je RJ

• L i {{overline|L}} jsou RSJ ⇒ L je RJ

z toho nám vyjde:

Postova věta

{{theorem | L je RJ ⇔ L i {{overline|L}} jsou RSJ

| Postova }}

Dk (přes oba směry implikace) ::

:: ⇒ L je RS, pro {{overline|L}} vytvořím TS M, {{overline|L}}=L(M) který přijme když původní TS (rozhodující RJ L) odmítne a zacyklí se když původní TS přijme :: ⇐ pustím oba TS a čekám na 1. co se zastaví (jeden se určo zastaví protože jeden přijíma A a druhý {{overline|A}})

GČ, UTS (🎓)

• Gödelovo číslo, univerzální Turingův stroj. *

Gödelovo číslo

• přiřadí každému symbolu a formuli unikátní přirozené číslo

• Je-li w_e kod TS M => e je Gödelovo číslo stroje M

💡 1 TS může mít ∞ mnoho bin. řetězců co ho kódují => má i ∞ mnoho GČ

Kódování instrukcí TS M = (Q, ∑, δ, q₀, F) ::

:: Nejdřív do abecedy Γ = {0, 1, L, N, R, |, #, ; }, pak z abecedy $Γ$ do binární. :: $Q = \{q_0, q_1, . . . , q_r\}$, r ≥ 1, kde $q_0$ označuje počáteční, $q_1$ jediný { BÚNO } přijímající stav. :: $Σ = {X_0, X_1, X_2, . . . , X_s}, s ≥ 2$, $X_0, X_1, X_2$ označují postupně symboly $0, 1, λ$. :: $(x)_B$ značí binární zápis čísla $x$. :: $C_n = (i)_B|(j)_B|(k)_B|(l)_B|Z$ je kódem instrunkce $δ(q_i, X_j) = (q_k, X_l, Z)$, kde $Z ∈ \{L, N, R\}$ (v abecedě $Γ$) :: $C_1\#C_2\# . . . \#C_{n−1}\#C_n$ je kódem TS $M$, jde o konkatenací kódú všech instrukcí TS $M$ (v abecedě $Γ$) :: Bin. kód $M$ získáme přes: 0→000, 1→001, L→010, N→011, R→100, |→101, #→110, ; →111. :: <u>Bijekce $1w = e ∈ N$, určuje pro TS $M$ s bin kódem $w$ GČ $e$, pak TS značíme $M_e$</u>

Univerzální Turingův stroj

• Univerzální Turingův stroj U umí simulovat libovolný jiný TS M nad libovolným vstupem w.

• Vstup: dvojice w;x, kde w je bin kódem TS M, x je vstupní slovo pro M

{{zarovka |

• U(e,w) ≃ M(w), počítá stejnou funkci.

• Zakódování TS navíc umožní každému TS přiřadit přirozené číslo

• Svůj kód bude mít i UTS, tedy UTS bude schopen simulovat i sám sebe

• Pokud se M(w) zacyklí, musí se zacyklit i U(e,w)

| Simulace: $U(w; x)↓ ⇔ M(x)↓$ a $U(w; x)↓ = M(x)↓$ }}

• Simulace: $U(w; x)↓ ⇔ M(x)↓$ a $U(w; x)↓ = M(x)↓$

• 3-páskový UTS (💡 technicky jednodušší než 1-páskový a lze převést na 1-páskový): vstupno/výstupní, pracovní, stavová

Image:Uts.jpg

• Vstupní páska

  • kód simulovaného stroje M a jeho vstup.

  • oddělovač ’;’ z abecedy Γ.

  • 💡 pouze se čte a na závěr na ni přepíše obsah pásky stroje M po ukončení jeho výpočtu.

• **Pracovní páska M **

  • uložení slova z pracovní pásky M

  • Připomeňme si, že páskovou abecedu stroje M jsme nijak neomezovali, její znaky si na tuto zakódujeme v binární abecedě stejně, jako je tomu v kódu přechodové funkce M.

  • Ať b označuje délku nejdelšího zápisu znaku páskové abecedy v kódu w Turingova stroje M (dá se tedy s jistou rezervou říci, že hodnota b odpovídá \lceil log2 |Σ| \rceil, kde Σ je pásková abeceda simulovaného stroje M.

  • Pak tato páska bude rozdělena do bloků délky b oddělených symbolem „|“.

  • Každý blok bude kódovat obsah políčka pracovní pásky stroje M týmž způsobem, jakým je daný znak zakódovaný v kódu w přechodové funkce stroje M, doplněný nulami na začátku na délku b (jde o binárně zapsané číslo symbolu, jehož hodnotu nuly přidané na začátek nemění).

  • Polohu hlavy stroje M si UTS pamatuje polohou hlavy na této pracovní pásce.

• Stavová páska M

  • stav, v němž se aktuálně stroj M nachází.

  • Stav $q_i$ stroje M zakódován jako $(i)_B$

    • 💡 totéž číslo, co lze vyčíst z přechodové funkce M uložené v řetězci w na 1. pásce

Algoritmus UTS

1. Init

   • kontrola vstupu: kontrola správnosti vstupní pásky

   • příprava prac.pásky: překódujeme vstup na pracovní pásku, návrat na začátek pásky

   • příprava stav.pásky: na stavovou pásku zapíšeme 0 (💡 binárně zapsané číslo stavu q0)

2. Simulace

   • simuluj kroky M dokud ex. instrukce pro konfiguraci

3. Zakončení

   • úklid: přepíše obsah pracovní pásky do abecedy {0,1}

   • konec: přečte stavovou pásku a podle stavu přejde do přijímacího/odmítacícího stavu

Alg. nerozhodnutelné problémy (🎓)

{{Zkazky|

• (P. Kucera) Alg. nerozhodnutelne problemy - klasika, definice co to je problem, rozdil mezi rekurzivne spocetnym a rekurzivnim, Churchova teze a ekvivalence s TS, dale halting problem + ten snadny dukaz, Riceho veta a jeste jeden dva dalsi problemy jako zajimavost.

• Způsob zkoušení: Zdá se, že mu jde o témata, které mají praktický dopad (např. halting problem). Ptal se, jestli znám ještě další nerozhodnutelný problém. Dostali jsme se i k Riceově větě, ale bránil mi ji dokazovat, protože to nebylo v otázce. Známku mi neříkal. S Majerechem zkoušeli někoho společně. Uklidňovali ho, že mu chtějí pomoct.

• Algoritmicky nerozhodnutelne problemy - Zacal sem Church-Turingovou tezi a pojem algoritmus vztahl k TS. Pak sem zadefinoval Rekurzivne spocetne a rekurzivni jazyky. Halting problem, Diagonalni jazyk, Univerzalni jazyk, Postova veta. Pak sem presel od TS k CRF tady sem jako priklad uvedl K a K0, definoval CRF a ORF + intuitivni srovnani s TS U vetsiny veci sem mel i dukazy ( vycislitelnosti sem se bal nejvic z okruhu takze sem to mel celkem nadrceny ). Pak se dvorak ptal jak zjistim ze nejakekj problem je nerozhodnutelny ( aniz by clovek musel furt vymyslet specialni dukazy ) to sem chvili vahal ale pak sem si vzpomel na prevoditelnost Rekurzivnich a rekurzivne spocetnych mnozin pomoci prevodni fce ktera musi byt ORF coz se ukazalo jako spravna odpoved. Posledni sada otazek uz smerovala k tomu co se bude dit kdyz budu mit TS s orakulem, jestli potom budou vsechny problemy budou rozhodnutelne...tady sem nevedel, odpovidal sem hodne diplomaticky ( spravna odpoved je TS s 1 orakulem umi resit nejaky problemy, TS s 2 orakulama umi resit jeste vic problemu atd...ale nikdy nelze pokryt vsechny jazyky ) Jeste dodam ze tohle nakonec Dvorak okomentoval slovy ze je to spis takova zajimavost, nic zasadniho pro statnice.

• Algoritmicky nerozhodnutelné problémy - Napsal jsem Halting problém + ten jednoduchý důkaz. Dále jsem napsal Riceovu větu a jak souvisí s halting problémem. Nakonec jsem napsal Postův korespondenční problém. To zkoušejícímu stačilo a nebyly žádné další otázky.

• Halting problém (Kolman) . Tu som zadefinoval TS, spomenul som kódovanie TS (nič konkrétne iba že to je číslo), Postovu vetu a dokázal som, že L HALT nie je rekurzivný, na záver som spomenul, že to isté sa dá urobiť aj cez množiny. Žiadne doplnkové otázky.

• Co to je rozh. problém, halting problém, že to souvisí s tím, že množina K není rekurzivní, Riceova věta s důkazem.

• Nerozhodnutelné problémy - Stačilo ukázat, že halting problém + definice co to vůbec je problém. Definoval jsem Postův korespondenční problém, pár doplnění, OK.

• definice co to je problem, rozdil mezi rekurzivne spocetnym a rekurzivnim, Churchova teze a ekvivalence s TS, dale halting problem + ten snadny dukaz

}}

instance problému - vstup

rozhodovací problém(odpověď typu ano/ne) - jazyk řetězců popisujících pozitivní instance a otázku, zda dané slovo – instance problému – patří do tohoto jazyka (kladná instance daného problému)

Jazyk $L$ je rekurzivní (také rozhodnutelný), pokud ∃ TS $M$, který se vždy zastaví a $L = L(M)$.

Image:Diag.jpg {{theorem

| $L_{DIAG} = \{w_i ∈ \{0, 1\}^* | w_i ∉ L(M_i) \}$ není RSJ (tedy ani RJ) | diagonalizační jazyk

}}

Dk (sporem) ::

:: Předpokládáme že $L_{DIAG}$ je RSJ ⇒ ∃ TS M že $L_{DIAG} = L(M_e)$ z čekož nám vychází ale spor: :: $w_e \in L(M_e) ⇔ w_e ∈ L_{DIAG} ⇔ w_e \notin L(M_e)$, kde první ekvivalence vyplývá z toho, že $L_{DIAG} = L(M_e)$ a druhá ekvivalence z definice $L_{DIAG}$

univerzální jazyk

{{theorem

| $L_u = L(U)$ (kde U je UTS) je RSJ, ale není RJ | univerzální jazyk

}}

Dk (sporem) ::

:: To, že $L_u$ je RSJ jsme ukázali tím, že jsme popsali UTS, který jej přijímá. :: Zbývá tedy ukázat, že není rekurzivní. Z Postovy věty stačí dokázat pouze, že $\overline L_u$ není RSJ. :: Sporem nechť $\overline L_u = L(M)$. Pomocí stroje $M$ zkonstruujeme stroj $M’$, který bude přijímat diagonalizační jazyk $L_{DIAG}$. Už víme, že $L_{DIAG}$ není RSJ a dospějeme tím tedy ke sporu. :: $M’$ dostane na vstupu slovo $w$ a má rozhodnout, zda $w ∈ L_{DIAG}$, tedy jestli stroj s kódem $w$ odmítne slovo $w$. :: $M’$ udělá pouze to, že zkontroluje, zda w kóduje Turingův stroj způsobem, jaký jsme popsali při popisu UTS. Pokud $w$ nekóduje syntakticky správně TS, odpovídá prázdnému TS, který slovo $w$ určitě nepřijme a $M’$ tedy skončí přijetím. V opačném případě připíše $M’$ za $w$ kód $111$ (kód „;“) a za ně okopíruje opět slovo $w$. Poté $M’$ spustí na tomto slově stroj $M$, pokud $M$ přijme, přijme i $M’$, pokud se $M$ zastaví a odmítne, odmítne i $M’$, pokud se $M$ nezastaví, nezastaví se ani $M’$. :: $M’$ ale přijímá jazyk $L_{DIAG}$, protože $M’(w)$ přijme ⇔ $w$ je validním kódem TS $N$ a $N(w)$ nepřijme, což je ekvivalentní tomu, že $U(w;w)$ nepřijme a $M(w; w)$ přijme. Fakt, že $L(M’) = L_{DIAG}$, je však ve sporu s tím, že $L_{DIAG}$ není RSJ.

problém zastavení

{{theorem

| $L_{HALT} = \{w; x |~ w~ kóduje~ TS~ M~ a~ M(x)↓\}$ je RSJ, ale není RJ | problém zastavení

}}

Dk ::

:: sporem mejme f(x,y) ktera dobehne prave kdyz F(x,y) se zacykli; vezmeme kod f=e a pustme f(e,e) - kdyz dobehne, mela se F(e,e) zacyklit, a kdyz nedobehne, mela F(e,e) dobehnout, ale F je univ. funkce => spor

Dk (sporem) ::

:: Že $L_{HALT}$ je RSJ je zřejmé z existence UTS. $w;x \in L_{HALT} \Leftrightarrow U(w;x)↓$ :: Diagonalizací ukážeme, že $\overline L_{HALT}$ není RSJ, čímž bude důkaz dokončen díky Postové větě. :: Předpokládejme pro spor, že ∃ TS $M$, že $\overline L_{HALT} = L(M)$. :: Nyní definujme jazyk $L = \{w_i \in \{0, 1\}^*| M_i(w_i)↑\}$, jde vlastně o diagonálu $\overline L_{HALT}$. S pomocí TS $M$ sestrojíme nyní TS $M_e$ přijímající jazyk $L$. :: Pokud $M(w_i;w_i)$ přijme, pak přijme i $M_e(w_i)$, v opačném případě $M_e(w_i)↑$. To učiní i v případě, zjistí-li, že $w_i$ nekóduje syntakticky správně TS a odpovídá tedy prázdnému TS (to je zde nutné odlišit jen proto, že kdyby $w_i$ obsahovalo oddělovač „;“, pak by $w_i;w_i$ mohlo odpovídat výpočtu jiného TS nad jiným vstupem). :: TS $M_e$ přijme svůj vstup ⇔ $M_e↓$. Zřejmě platí, že $L(M_e) = L$. :: Nyní se podívejme, jestli $w_e \in L$ ($w_e$ je kód $M_e$): 1. Pokud $w_e ∈ L$, znamená to, že se $M_e(w_e)$ zastaví a přijme, protože $L = L(M_e)$, to ale současně znamená, že $M_e(w_e)↑$ podle definice $L$, což je pochopitelně ve sporu. 1. Nyní předpokládejme, že $w_e \notin L$, ale podle definice $L$ to znamená, že $M_e(w_e)↓$. Z toho jsme dostali $w_e ∈ L(M_e) = L$, což je však ve sporu s předpokladem. :: Jazyk $L$ použitý v důkazu není nic jiného než $L_{DIAG}$, pokud bychom předpokládali, že TS přijímají zastavením v jakémkoli stavu.

PRF, ČRF, RP, RSP a vlast. (🎓)

Definice primitivně a částečně rekurzivních funkcí, rekurzivních a rekurzivně spočetných predikátů. Jejich základní vlastnosti - podmíněný příkaz, omezená minimalizace, uzavřenost na aritmetické operace, (ne)uzavřenost na logické spojky a kvantifikátory (omezené i neomezené). {{Zkazky|

• Surynek - Základní definice, funkci x+y definovat jako ČRF, detaily ostrých inkluzí PRF/ORF/ČRF. Otázka: Je univerzální funkce pro třídu PRF také PRF? Ne, dokonce není ani ORF, protože nemůže být totální.

}}

Image:ZSV%201.jpg

podmíněná rovnost $f(x_1,..,x_n) \mathbf{≃} g(x_1,..,x_n)$ znamená: hodnota $f(x_1,..,x_n)$ je definována ⇔ definována i hodnota $g(x_1,..,x_n)$, a pak jsou si také rovny

{{zarovka |

• h nabývá nejmenší hodnoty y, pro níž je f definováno a rovno 0. Navíc pro všechny hodnoty nižší než y musí být hodnota f definována.

• Poslední proměnná ve funkci f má zvláštní význam. Snažíme se ji minimalizovat, to jest najít nejmenší y takové, aby f vracela nulu.

• Pokud se jako f předá funkce, která nikdy nevrací nulu, tak operátor minimalizace vytvoří funkci, která nebude nikde definovaná

:: (výše uvedený pseudokód se zacyklí). To se u předchozích operátorů stát nemohlo: pokud dostaly na vstupu všude def. fce, vrátily také všude def. funkci.

• Pokud nechceme zavádět nulární funkce, je nutné definici operátoru minimalizace doplnit o podmínku, že f je funkce alespoň dvou proměnných.

• Místo $↓=$ (zkratka za konverguje a rovná se) bychom v definici klidně mohli psát jen $=$. Použití $↓≠$

:: (zkratka za konverguje a nerovná se) je ale důležité, například pokud $f(x_1,...,x_n,0)↑$, tak $h(x_1,...,x_n)$ také není definováno, :: i kdyby třeba $f(x_1,...,x_n,1)=0$.

| minimalizace $M_n(f) = h$ }}

Základní funkce:

• nulová (konstantní) funkce $o(x) = 0$

• následník $s(x) = x + 1$

• projekce $I^j_n (x_1, .., x_j, .. , x_n) = x_j (∀j,n: 1 ≤ j ≤ n)$ (💡 vrací hodnotu j-tého parametru)

Operátory:

• substituce $S^m_n(f,g_1,...,g_m) = h$ kde: $h(x_1,...,x_n) ≃ f(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n))$

  • 💡 $f$ má $m$ proměnných a $g_1, .. , g_m$ $n$ proměnných

  • 💡 Operátor substituce je základní prvek programování — jednoduše úlohu, kterou mám řešit, vyřeším pomocí funkcí, které už naprogramoval někdo dřív.

• primitivní rekurze $R_n(f,g) = h$

  • kde: $h(0, x_2, ..., x_n) ≃ f(x_2, ..., x_n)$ :: $h(i+1, x-2, ..., x_n) ≃ g(i, h(i,x_2,...,x_n), x_2,..., x_n)$

  • 💡 f je fce n-1 proměnných a fce g n+1 proměnných (n ≥ 2)

  • 💡 operátor primitivní rekurze má sílu for-cyklu.

  • 💡 Proměnná x1 má zvláštní význam — slouží jako čítač

*minimalizace $M_n(f) = h$ (má sílu while-cyklu)

:: $\mathbf{h}(x_1,...,x_n)\downarrow ≃ min \{ y|\mathbf{f}(x_1,...,x_n,y)\downarrow = 0 \quad a \quad \forall z<y: \mathbf{f}(x_1,...,x_n,z)\downarrow \ne 0\}$ * μy[P(x,y)]- fce μ vrátí nejmenší y takové, aby platil predikát P(x,y) * Lze jí sestrojit pomocí operátoru minimalizace

PRF ⇐ lze odvodit ze 3 základních fcí a pomocí 2 op. substituce a prim. rekurze (NE minimalizace)

• 💡 všude definována (=totální) - for-cykly (vždy konvergují)

• 💡 PRF je ORF bez minimalizace

PRP (ORP) ⇐ ∃ pro něj PRF (ORF) charakteristická funkce

• predikát $R(x_1,...,x_n)$ je relace nebo libovolný fakt o n proměnných

• charakteristická fce predikátu R je

  ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 53: …ases}1 \quad & \̲m̲b̲o̲x̲{ pokud } R(x_1…

  • 💡 char. fce je ORF

• 💡 (Obecně) PRM je unární (obecně) PRP.

ČRF (partial μ-recursive functions) ⇐ lze odvodit ze 3 základních funkcí pomocí 3 operátorů (💡 mají navíc while-cyklus ⇒ divergence)

• ORF - je ČRF def. pro ∀ vstupy (totální)

RSP ⇐ ∃ pro něj ČRF charakteristická funkce

• částečná char. fce (=ČRF) predikátu $R$ je funkce $f_R : N^n → N$: $f_R(x_1, . . . , x_n)↓ ⇔ R(x_1, . . . , x_n), ∀(x_1, . . . , x_n) ∈ N$.

• 💡 je def.oborem nějaké ČRF

Jejich základní vlastnosti

• uzavřenost na aritmetické operace

  • (konečný součet a součin) f je PRF 2 proměnných ⇒ je PRF:

    • $g(z, x)=\sum_{y<z}f(y, x)$ (přičemž $g(0, x)=0$)

    • $h(z,x)=\prod_{y<z}f(y, x)$ (přičemž $h(0, x)=1$)

  • (důsledek) f je PRF 1 proměnné ⇒ je PRF:

    • $g(z)=\sum_{y<z}f(y)$ (přičemž $g(0)=0$)

    • $h(z)=\prod_{y<z}f(y)$ (přičemž $h(0)=1$)

• (podmíněný příkaz) - analogie switch/case/if-then

**$g_1(x), \dots, g_n(x)$, $n>0$ jsou PRF a $R_1(x), \dots, R_n(x)$ jsou PRP a $\forall x\in{\mathbb N}$ je splněn !1 z nich. **⇒ tato fce $f$ je PRF:

ParseError: KaTeX parse error: {align} can be used only in display mode.

• kvantifikátory (omezené i neomezené).

  • (omezená kvantifikace) $P$ binární PRP ⇒

    ParseError: KaTeX parse error: Undefined control sequence: \[ at position 24: …)=(\forall y<z)\̲[̲P(y, x)]

    a

    ParseError: KaTeX parse error: Undefined control sequence: \[ at position 24: …)=(\exists y<z)\̲[̲P(y, x)]

    jsou PRP.

  • (neomezená kvantifikace): P unární PRP⇒ (∃y)[P(y)] je RSP a (∀y)[P(y)] je doplněk RSP (∃y)[¬P (y)].

• (ne)uzavřenost na logické spojky * (logické spojky) :: $P$ a $R$ unární PRP ⇒ $R\wedge P$, $R\vee P$ a $\neg P$ jsou PRP * (konečná konjunkce a disjunkce) :: $P$ binární PRP ⇒ $A(x, z)=\bigwedge_{y<z}P(x, y)$ a $B(x, z)=\bigvee_{y<z}P(x, y)$ jsou PRP

• (omezená minimalizace) :: $P$ binární PRP ⇒ tato $f$ je PRF: ::

  ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 55: …x, y)\} \quad &\̲m̲b̲o̲x̲{pokud takové y…

  :: Funkci $f$ budeme také označovat pomocí

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 16: f(x, z)=\mu y<z\̲[̲P(x, y)]

  .

ČRF ⇔ TS, Kleene, UČRF, s-m-n (🎓)

Ekvivalence ČRF a Turingových strojů (na vyšší úrovni). Kleenova věta o normální formě (bez převodu ČRF na TS), univerzální ČRF, s-m-n věta.

{{Zkazky|

• Tu ekvivalenci jsem napsal jen v bodech (stylem „zakóduju výpočet TS do stringu“, „sestavím predikát, který kontroluje, zda výpočet TS je korektní“, atd., fakt hodně po povrchu), rozepsal jsem jen to, jak se pomocí TS implementuje substituce, a taky mu to celkem stačilo (měl jsem v plánu toho napsat mnohem víc, tohle byl jen takovej začátek), jen se ptal, jak se něco udělá (nevím už přesně co, něco jako jak se překóduje string do binární reprezentace a zpátky, nevím jestli v TS nebo ČRF), tak jsme to společně nějak vymysleli, a dobrý.

• (Loebl) - Ekvivalence ruznych definic algoritmicky vycislitelnych funkci - Moc jsem nevedel, co presne u tehle otazky bude chtit videt (jasne, Churchova teze, kterou jsem mimochodem nezformuloval tak uplne ciste spravne, ale dal?:) a tak jsem tam naflakal vsechno - CRF, ORF, PRF, RM, RSM, RSP, ORP, jazyky, DTS, NTS - CRF jsem odvodil ze zakladnich funkci pomoci operatoru, ukazal jsem inkluzi s ORF a PRF, naznacil jsem, jak si odpovidaji CRF a NTS a RSM, ORF a DTS a RM. Loebl byl velmi prijemny, prosel si to, chvili dumal nad tim, co se mnou (asi to nebylo uplne ono co chtel videt), rekl, ze tomu zjevne asi rozumim, ale, ze mu chybi nejake prakticke priklady a konkretni formalni prevody mezi vyjadrenimi a pak mi rekl, at mu tedy napisu jeste neco o UTS, pokud o nem neco vim. Nacrtnul jsem tu ctyrpaskovou konstrukci a kodovani UTS, ani jsem to nedopsal a rekl, ze staci.

• Majerech, Algoritimicky vycislitelne funkce, definice, vlastnosti. Pana Majerecha jsem se bal, ale nakonec byl opravdu hodny! Zdalo se mi, ze poznal, ze tomu clovek rozumi, par otazek a dal se jiz na nic neptal. Napsal jsem definice pres funkce/operatory, pres TS, dale pak mnoziny/predikaty/jazyky. Inkluze + co za funkce jsou, aby to nebylo ostre [bez definovani], par otazek na overeni, ze tomu rozumim a vse ok. Zadne detaily ci Velmi prijemne zkouseni. Behem zkouseni si k nam prisedl i Martin Mares, ktereho to evidentne bavilo a dokonce mi i jednou napovedel :-) Znamka: 1

*Loebl (SV) -- Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce. - Churchova-Turingova teze. Definoval jsem TS a popsal, jak počítá. Rekurzivně spočetné/rekurzivní jazyky. Postova věta. Definice PRF, ORF, ČRF (a predikáty) - zmínit, jakým programovacím konstruktům odpovídají odvozovací fce. Základní lemmata (konečný součet, popis ekvivalentní fce pro switch, atd.). Nakonec bez důkazu, že ČRF a TS jsou ekvivalentně silné. Ptal se na existenci UTS (stačila idea). Vše jsem měl přesně, takže řekl, že mu to stačí na 1. }}

otázky: vyšší úroveň? , bez převodu ČRF na TS? , smn důkaz? jak se něco udělá (nevím už přesně co, něco jako jak se překóduje string do binární reprezentace a zpátky, nevím jestli v TS nebo ČRF)

💡 efektivně vyčíslitelné = turingovsky vyčíslitelné = algoritmicky vyčíslitelné = algoritmicky řešitelné

Ekvivalence ČRF a TS (na vyšší úrovni)

{{theorem | $h$ je ČRF $n$ proměnných ⇒ $h$ je Turingovsky vyčíslitelná

| ČRF ⇒ TS }}

:💡 Přesněji, existuje Turingův stroj $M_h$ takový, že pro každou $n$-tici přirozených čísel $x_1, x_2, \dots, x_n$ platí

:: $M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow$ :: a platí-li $h(x_1, x_2, \dots, x_n)\downarrow=y$, potom výpočet Turingova stroje $M_h$ vydá na výstupu řetězec $(y)_B$.

Dk (konstrukcí TS, <Řešené_otázky_NTIN090/ČRF2TS>) ::

:: definujeme TS pro základní funkce a operátory pro odvození $h$: * Základní fce (nulová, následník, projekce) implementuji (vyčíslím) pomocí TS * Operátory simuluji na 3 pásk. TS: substituci, primitivní rekurzi jako for-cyklus (počítadlem cyklů), minimalizaci jako while-cyklus (taky počítadlem cyklů)

{{theorem

| Převod je navíc možno učinit efektivně. Jinými slovy, existuje Turingův stroj CRF2TS, který pokud na vstupu dostane kód ČRF $h$, spočítá Gödelovo číslo $e$ stroje $M_e$, který počítá funkci $h$. | 💡

}}

{{theorem

| funkce $f$ turingovsky vyčíslitelná ⇒ je $f$ ČRF | TS ⇒ ČRF

}}

Dk (jeden krok TS je PR - omezené cykly, TS pracuje, dokud neskončí = while-cyklus (tj. minimalizace), <u>tedy program = minimalizace čehosi, kde to cosi už je PR</u>) ::

• předpoklady: f je def. jako tur. vyčíslitelná ⇒ ∃ TS $M_e$ co jí počítá (💡 to je z definice tur.vyčíslitelnosti)

• zakóduju výpočet (tj: posloupnost konfigurací Ki) TS do stringu: K1;...;Kt

{{TODO|jak se to dělá?}}

• sestavím PRP T(g.č.TS, x, g.č.kódu výpočtu TS), který kontroluje, zda daný řetězec kódu TS kóduje výpočet TS nad vstupem x

• na predikát pustím minimalizaci y (

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 6: \mu y\̲[̲T(e, x, y)]

  )

• pomocí fce $\cal U$ z ní vytáhnu g.číslo poslední konfigurace

• tedy

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 18: …x)=\cal U(\mu y\̲[̲T(e, x, y)])

:: 💡 U je zřejmě PRF

Kleenova věta o n.f. (bez převodu ČRF na TS)

$\mathbf{ \varphi_e^{(n)}}$ je ČRF $n$ proměnných, kterou počítá stroj $M_e$ {{theorem

| $\exists PRF \quad \cal U(y)$ a PRP $T_n(e, x_1, \dots, x_n, y)$, pro které platí:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 104: …meq\cal U(\mu y\̲[̲T_n(e, x_1, \do…

| Kleenova věta o normální formě }}

💡 neboli, každý program se dá zjednodušit na 1 while cyklus :)

Dk ::

:podle důkazu TS ⇒ ČRF {{theorem

| $R$ je RSP $\Leftrightarrow \exists$ PRP $P$ tak, že:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 45: …rrow(\exists y)\̲[̲P(x_1, \dots, x…

| důsledek Kleeneho věty

}} 💡 RP jsou ty, které jsou algoritmicky rozhodnutelné, RSP jsou ty, které jsou algoritmicky ověřitelné, podá-li nám někdo certifikát (tedy $y$) dokazující jejich platnost. Tedy u RSP nejsme sice obecně schopni efektivně rozhodnout, jestli platí, ale pokud platí a někdo nám dá svědka $y$ stvrzující tento fakt, jsme schopni efektivně ověřit, že jde skutečně o certifikát platnosti.

univerzální ČRF

{{theorem | $\forall$ třídu proměnných $n>0$ $\exists$ univerzální ČRF: $\varphi_z^{(n+1)}(e, x_1, \dots, x_n)$ taková, že $\varphi_z^{(n+1)}(e, x_1, \dots, x_n)=\varphi_e^{(n)}(x_1, \dots, x_n)$ (tedy vyčísluje e-tou funkci)

| O univerzální funkci }}

💡 existuje i univerzální funkce, a to pro každou třídu $n$ proměnných (takže ta univerzální funkce pak dostane těch $n$ proměnných + číslo funkce, kterou má emulovat, a udělá to), přičemž je docela pěkná (je ve tvaru minimalizace PRP)

Dk(podle Kleeneovy) ::

::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 59: …q \cal{U}(\mu y\̲[̲T_n(e, x_1, \do…

:: 💡 Nicméně vzhledem k ekvivalenci ČRF a TS bychom také mohli vzít již zkonstruovaný univerzální TS a jemu odpovídající ČRF.

''s''_n^m věta

$\mathbf{ \varphi_e^{(n)}}$ je ČRF $n$ proměnných, kterou počítá stroj $M_e$

Churchovo $\lambda$-značení . Je-li $V$ výraz, pak pomocí $\lambda_{ x_1x_2...x_n}V$ označíme funkci na proměnných $x_1, x_2, \dots, x_n$, která je daná výrazem $V$.

{{theorem _ | $\forall$ m,n > 0 $\exists$ prostá PRF $s_n^m$ a $\forall x, y_1, \dots, y_m$ platí:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 56: …lambda z_1..z_n\̲[̲\varphi_x^{(m+n…

| s_n^m }}

Image:Smn.jpg :💡  říká, že pokud v naší univerzální funkci, která má $m+n$ sadu argumentů (jedním z nich je číslo programu, který má běžet),

:: $m$ argumentů (+ číslo programu) zafixujeme, :: dostaneme funkci zbytku ($n$) těch argumentů, :: a tato fixovací funkce bude hezká (prostá PRF).

Dk (program $s=s_n^m(x, y_1, \dots, y_m)$, na vstupu dostane z-ka a pak pustí TS $M_x$ na vstup y-nek a z-tek) ::

:: Neformálně popíšeme, co bude dělá program $s=s_n^m(x, y_1, \dots, y_m)$: :: Na vstupu dostane čísla $z_1, . . . , z_n$, poté spustí stroj $M_x$ na vstup $y_1, . . . , y_m, z_1, z_2, . . . , z_n$, :: 💡 Všechna tato čísla zná, jelikož je buď dostane na vstupu $M_s$ (v případě $z_1, . . . , z_n$), nebo je má zakódované do své přechodové funkce jako parametry (v případě $x, y_1, \dots, y_m$). :: 💡 Pro tuto úpravu není vůbec rozhodující, jak vypadají instrukce $M_x$, ani to, jak bude probíhat jeho výpočet, jediné, co je v $M_x$ třeba změnit jsou čísla stavů tak, aby nekolidovala s nově přidanými stavy. * Úprava přechodové funkce $M_x$ je jednoduchá a vystačí si s PR prostředky ⇒ $s_n^m$ je PRF. * Kód nového stroje obsahuje nějakým způsobem i hodnoty parametrů fce $s_n^m$, pro různé hodnoty těchto parametrů budou i různé výstupní hodnoty ⇒ $s_n^m$ je prostá.

další zdroje

• http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Algoritmicky_vy%C4%8D%C3%ADsliteln%C3%A9_funkce

Základní vlast. RM a RSM. (🎓)

Základní vlastnosti rekurzivních a rekurzivně spočetných množin. (Ne)uzavřenost na sjednocení, průnik a doplněk. Postova věta v kontextu množin. Existenční kvantifikátor a výběrová funkce. {{Zkazky|

• (inicialy JM... zeby Mlcek?) - Rekurzivne funkcie a rekurzivne spocetne mnoziny (nie je to priamo otazka z poziadavkov, nejak som mal proste rozpravat o danej teme), uz pri zadavani mi vravel, ze si mam pripravit vela prikladov, na co je to dobre. Zadefinoval som elementarne funkcie a operatory, vyznam operatorov(for, while), PRF,ORF,CRF, inkluzie a priklady funkcii, kvoli ktorym su inkluzie ostre, definoval som rekurzivne a r.spocetne mnoziny a uviedol som tam znenie tej dlhej vety o vlastnostiach r.s. mnozin. Na zaver som pridal nieco o halting probleme ako priklad vyuzitia celej tej teorie. Skusajuci si to pozrel, nemal nejake pripomienky a zacal sa pytat na tie priklady, tak som povedal ten halting problem, ekvivalenciu programov a este sa pytal, ci existuje funkcia, ktora nie je ani CRF - to som nejak previedol na TS a povedal, ze napriklad diagonalizacny jazyk. Toto mu stacilo, bolo to celkom v pohode.

• RS a RSM mnoziny, prevoditelnosti - pri zadani spominal aj simple a kreativne, ale nastastie sme sa az tam nedostali, to som sa uz neucil. Definicia zakladnych fcii, operatorov, definicia RS RSM mnozin, potom ze to je ekvivalentne s generovanim pomocou oborov hodnot, tie vety o vztahu rng a RSM, vzdy sa opytal aj na myslienku dokazu. Postova veta (tam sa mu viac pacila odpoved 'pustime dva programy a cakame, ktory skor zastane' nez ten predikat, ktoreho potom selektor je char fciou), potom som zadefinoval 1- a m-prevoditelnost, 1-uplnost, dokazal, ze K je 1-uplna, napisal halting problem a Kryl odchadzal spokojny.

• Majerech - CRF + RM + RSM - tady jsem kliku, ze jsem si vylosoval zrovna toto, ptz jinak bych tam mohl u Majerecha sedet doted.:) Vypsal jsem vsechny ty definice, nejdulezitejsi vety (Postovu jsem si dovolil i dokazat, coz je u me velmi nezvykle) a ruzna tvrzeni okolo, na ktere jsem si vzpomnel. Ptal se na usekovou fci a generovani bodu - to jsem tapal a radsi hned rekl, ze nevim (jak toto muze byt nekdy osvobozujici:) a zlehka nejake uzaverove vlastnosti. 1-

*Napsal jsem: **definice RM, RSM vč. definice ORF a ČRF (s drobnou chybou – dal jsem dohromady prvky a operátory nad funkcemi),

**generování (tři věty o oborech hodnot) (Tady se mě ptal, jak fungují ty programy pomocí kterých množiny generuji. Neměl jsem to rozmyšlené, takže to ze mě musel tahat a část říct), **1-převoditelnost, 1-úplnost, K je 1-úplná. Ptal se mě, k čemu ta 1-převoditelnost je. Dával mi návodné otázky a potom jsem si končeně vzpomněl, že asi myslí to, že můžu převést jednu množinu na druhou. Jen tak mimochodem se ptal, kolik je RM a kolik RSM.

**Všechno jsem psal bez důkazu a nechyběly mu. Nakonec mi řekl, že to mám tak za 1− a jestli chci čistou 1, tak ať mu formálně dokážu, že K je 1-úplná. Řekl jsem mu, že o 1 mi až tak nejde. }}

charakteristická funkce $χ_A(x)$ -- charakteristická fce predikátu náležení do množiny ($χ_A(x) = \downarrow 1$ pro $x\in A$ a $χ_A(x) \downarrow = 0$ pro $x\notin A$)

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 49: …ases}1 \quad & \̲m̲b̲o̲x̲{ pokud } R(x_1…

::💡 částečná charakteristická funkce množiny -- $χ_A(x) = \downarrow 1$ pro $x \in A$ a $χ_A(x)\uparrow$ pro $x \notin A$ $dom\,\!$ značí definiční obor, $rng\,\!$ obor hodnot

RM A ⊆ ℕ ⇐ je-li def. oborem ORF

:: 💡 také nazýváme jako unární RP (příklad: binarni predikat je mnozina dvojic, ale unarni predikat je mnozina prvku) :: 💡 tj.: char.fce $χ_A(x)$ je ORF

RSM A ⊆ ℕ ⇐ je-li def. oborem ČRF

:: 💡 také nazýváme jako unární RSP :: 💡 tj: A = dom ČRF f = {x | f(x)↓}

:: e-tá RSM $\mathbf{W_e} = dom~ φ_e = \{ x | φ_e(x)↓ \}$

:: Pomocí $\varphi^{(n)}_{e, s}$, kde $e, n,s\in{\mathbb N}$ označíme konečnou aproximaci $\varphi_{e, s}^{(n)}$ funkce $\varphi_e^{(n)}$, kterou definujeme následujícím způsobem:

::

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 100: …, x_n) \quad & \̲m̲b̲o̲x̲{pokud }(\exist…

:: **rekurzivní konečná aproximace ** $\mathbf{W_{e,s}} = dom φ_{e,s} = \{ x | φ_{e,s}(x)↓ \}$

{{lemma

| Predikát $H$ definovaný jako $H (e, s, x_1, . . , x_n) ⇔ φ_{e,s}(n)(x_1, . . , x_n)↓$ je PRP a platí, že:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 33: …. , x_n)↓⇔ (∃s)\̲[̲ φ_{e,s}(n) (x_…

. (v dk předpokladáme, že $T_n$ z Kleenovy věty je PRP a omezená kvantifikace je PR.) }}

{{theorem

| RM jsou uzavřeny na sjednocení, průnik a operaci doplňku | RM - uzavřenost na ∪, ∩ a doplňek

}}

Dk ::

předpokládáme, že signum, součet, součin a opatrné odčítání 1 (predecessor) jsou PRF/ORF :

::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 9: A∪B=\{x|\̲[̲χ_a(x)∨χ_b(x)]\…

::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 9: A∩B=\{x|\̲[̲sign(χ_a(x)+χ_b…

::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 17: …overline A=\{x|\̲[̲1\dot{-}χ_a(x)]…

:: 💡 tj: Ten samý jako pri logických operacích pro PRP, jenomže pro unární ORP (rekurzivní množiny). Platí: χA ∩ B(x) = χA(x).χB(x), χP ∩ R(x) = sign(χA(x) + χB(x)), χA(x) = 1 −• χA(x).

{{theorem

| Rekurzivně spočetné množiny jsou efektivně uzavřené na sjednocení a průnik, nikoliv na průnik. | RSM - uzavřenost na ∪, ∩ ale <u>NE na doplňek</u>

}}

Dk ::

:: A∪B - pustíme oba TS současně a když 1 skončí vstup patří do sjednocení :: A∩B - čekám na zastavení obou :: 💡 tj: Uvažme nejprve sjednocení a funkci f(x, y). Nechť e-tý program počítá následovně. Pro daný vstup x, y, u hledej nejmenší limit s, který již stačí, aby u patřilo do Wx,s nebo do Wy,s. Tedy φe(x, y, u) ≃ μs[u ∈ Wx,s ∨ u ∈ Wy,s]. Z vlastností konečných aproximací, vyplývá, že predikát použitý jako podmínka minimalizace je PRP. Platí tedy, že φe(x, y, u)↓ ⇔ u ∈ Wx ∪ Wy. Program s číslem e je konkrétní program, který sestrojíme s pomocí univerzální ČRF. Funkci f dostaneme pomocí s-m-n věty jako $f(x, y) = s_1^2(e, x, y)$. Podobně můžeme postupovat i v případě průniku a funkce g, stačilo by místo disjunkce použít konjunkci.

{{theorem

| $A$ je RM $\Leftrightarrow A$ i $\overline A={\mathbb N}\setminus A$ jsou RSM | Postova věta v kontextu množin

}}

Dk ::

:⇒ A je RM: A = dom μy[(λxy[1 ∸ χA(x)])≃0]

:: A' je RSM: A = dom μy[(λxy[χA(x)])≃0]

:⇐ paralelni beh obou char. funkci, jedna dobehne ::μs[x∈Wi,s ∨ x∈Wj,s]

Kódování uspořádaných dvojic, n-tic:

• $⟨x, y⟩_2$ je kód uspořádané dvojice [x, y] daný: $⟨x, y⟩_2 = (x + y).(x + y + 1) / 2 + x$

• $⟨x_1, . ., x_n⟩_n$ je kód uspořádané n-tice daný: $⟨x_1, . . ., x_n⟩_n = ⟨x_1, ⟨x_2, . . ., x_n⟩_{n-1}⟩_2$

• $π_{n,i}(⟨x_1, . ., x_n⟩_n) = x_i$ je inverze pro výběr $i$-tého prvku ze zakódované $n$-tice

• Lemma – Pro každé $n ≥ 2, i ≤ n$ jsou funkce $⟨x_1, . . . , x_n⟩_n$ a $π_n$ PRF, a $⟨x_1, . . . , x_n⟩_n$ je bijekcí mezi $N^{n+1}$ a $N$ ( důkaz pro πn předpokládá, že omezená minimalizace a kvantifikace jsou PRF ).

{{theorem

| Predikát $R ⊆ N^n$ je RSP ⇔ ∃ PRP $P ⊆ N^{n+1}$ , že:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 25: …. , x_n) ⇔ (∃y)\̲[̲P (x_1, . . , x…

. | důsledek Kleeneho věty

}} {{theorem

| $P(x_1, \dots, x_n, y)$ je RSP ⇒

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 33: …)=(\exists y)\;\̲[̲P(x_1, \dots, x…

je RSP | RSP jsou uzavřeny na <u>∃ kvantifikátor</u>

}}

Dk ::

:: Protože $P(x, y)$ je RSP, můžeme jej zapsat podle důsledku Kleeneho jako

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 16: P(x, y) = (∃z) \̲[̲Q(x, y, z)]

, kde $Q$ je PRP. Z toho plyne, že

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 17: …(x) = (∃y)(∃z) \̲[̲Q(x, y, z)]= (∃…

. :: Označíme-li si $D(x, u) = Q(x, π_{2,1}(u), π_{2,2}(u))$, pak $D$ je PRP, pro který platí, že $R(x) = (∃u) D(x, u)$. :: ⇒ podle důsledku Kleeneho: $R(x)$ je RSP.

{{theorem

| $R(x, y)$ je RSP ⇒ $\exists$ ČRF $f$ (také výběrová funkce nebo selektor pro $R$), že $f(x)\downarrow\Leftrightarrow(\exists y)R(x, y)$ a pokud $f(x)\downarrow$, pak $R(x, f(x))$. | výběrová funkce

}} 💡 $\exists f$ implementující $\exists y$ na predikátu $R(x, y)$

Dk ::

:: Podle důsledku Kleeneho můžeme $R$ zapsat jako

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 15: R(x, y) = (∃z)\̲[̲Q(x, y, z)]

pro nějaký PRP $Q$. A tedy $(∃y)R(x, y) ⇔ (∃y)(∃z)Q(x, y, z)$. Protože predikát $Q$ je PRP(totální), dostaneme, že funkce $g(x) ≃ μ⟨y, z⟩_2 Q(x, y, z)$. :: Nyní z nalezené hodnoty stačí vybrat $y$, tedy 1. prvek, celkově tedy definujeme funkci $f$ jako $f(x) ≃ π_{2,1}(g(x))$.

další zdroje

• Státnice_-_Rekurzivní_a_rekurzivně_spočetné_množiny

7. RM = ''rng'' rost. úsekové ČRF (🎓)

Rekurzivní množina jako obor hodnot rostoucí úsekové funkce.

$f$ je úseková fce, pokud její definiční obor tvoří počáteční úsek $\mathbb N\,\!$

{{theorem | A je RM $\Leftrightarrow$ je oborem hodnot nějaké rostoucí úsekové ČRF

| $RM = rng$ rostoucí úsekové ČRF }}

Dk (oběma směry - neformálně, <Řešené_otázky_NTIN090/RM_CRF>) ::

$\Rightarrow\,\!$: Předpokládejme nejprve, že $A$ je RM. Zkonstruujeme rostoucí, úsekovou ČRF $f(i)$ = "vrať $i$-tý nejmenší prvek z $A$".

• Začneme $f(0) \simeq \mu x(x\in A)\,\!$.

• Dále $f(n+1) \simeq \mu x(x > f(n) \wedge x \in A)\,\!$

$\Leftarrow\,\!$: Nyní předpokládejme, že $A = rng f$, kde $f\,\!$ je rostoucí úsekovou ČRF.

1. Pokud $f$ není ORF, znamená to že $f\,\!$ má konečné $dom\,\!$ (z def. úsekové fce), a tedy je konečná i samotná množina $A$ a je tedy triviálně rekurzivní.

2. Pokud je $f$ ORF je všude definovaná (totální): $y \in A=rng f \Leftrightarrow \exists x:f(x)=y \Leftrightarrow \exists x\!\leq\!y: f(x)=y$. Poslední ekvivalence platí, protože $f\,\!$ je rostoucí a úseková. Tedy $y \in A \Leftrightarrow y \in \{f(0),\ldots,f(y)\}.$

💡 Důsledek: Nechť $A$ je ∞ množina: $A$ je $RM ⇔ A=rng$ nějaké rostoucí ORF. (protože úsekové funkce s nekonečnou doménou musí být všude definované = totální)

RSM = ''rng'' ORF, či ČRF (🎓)

Rekurzivně spočetná množina jako obor hodnot obecně rekurzivní funkce, či částečně rekurzivní funkce. {{Zkazky|

• Funckia f je CRF ⇔ jej graf je RSM

  • Na ustnej sa ma pytal (kedze som to tam nemal uplne jasne vysvetlene, hlavne ze preco je riesenie korektne v jednom ⇔ ak je v prevedenom) veci ohladne toho, ale dost ma navadzal a spolu s nim som to tam aj vymyslel.

  • mi prošla bez dotazů, jsou to dvě věty, tak nějak jsem nastínil i důkazy, jen na pár řádek, zřejmě mu stačilo vidět myšlenku

}}

{{theorem | Následující tvrzení jsou ekvivalentní:

1. A je RSM.

2. A je ∅, nebo je $rng$ nějaké ORF

3. A je $rng$ nějaké ČRF.

4. A je $rng$ nějaké rostoucí ČRF.

| Generování RSM }}

Dk (neformální, <Řešené_otázky_NTIN090/GenRSM>) ::

Image:genRSM.jpg $1. ⇒ 2.$ (konstrukce ORF co pro jakékoli vstupy vrací prvky z A):

::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 111: …{2,1}(μ⟨x, s⟩_2\̲[̲x ∈ W_{e,s}])\q…

.

Každý prvek $W_e$ je tedy funkcí $g$ pro nějaký vstup $y$ vrácen, jenom nedokážeme odhadnout, pro jak velké $y$. Dohromady dostáváme, že $A = W_e = rng~ g$.

$2. ⇒ 3.$ : Plyne z toho, že každá ORF je i ČRF. ∅ je oborem hodnot ČRF, která není definovaná pro žádný vstup.

$3. ⇒ 1.$ (pomocí částečné aproximace vyrobíme z ČRF RSP => RSM): Předpokládejme, že $A$ je oborem hodnot ČRF $g ≃ φ_e$.

:: Uvědomme si, že rozhodnutí, zda $g(y)↓= x$ je RSP (plyne například z toho, že $φ_{e,s}(y)↓ = x$ je PRP a tedy

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 17: …(y)↓ = x ⇔ (∃s)\̲[̲φe,s(y)↓= x]

je RSP, dále je tedy i

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: (∃y)\̲[̲g(y)↓ = x]

RSP, a tedy množina

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 15: A = \{x | (∃y)\̲[̲g(y)↓ = x]\}

je RSM. Ze znalosti GČ $e$ funkce $g$ bychom opět s pomocí s-m-n věty mohli spočítat GČ funkce, jejíž doménou množina $A$ je. Pro úplnost totiž můžeme past

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 13: A = dom~ λx \̲[̲ μ⟨y, s⟩_2\[φ_{…

.

$1. ⇒ 4.$ (zkonstruujeme triviální rostoucí ČRF $h(x)=g(e,x)$ u které se $dom$=$rng$) : Předpokládejme, že $A = W_e$, tedy $A = dom φ_e$. Buď $g(e, x)$ fce definovaná jako:

::

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 55: …e \\ ↑ \quad & \̲m̲b̲o̲x̲{ jinak }\end{c…

.

:: Funkce $g(e, x)$ je zřejmě ČRF, například proto, že ji lze zapsat jako $g(e, x) = o(φ_e(x)) + x$ (tj. do nulové funkce vložíme $φ_e(x)$ jako argument, hodnota tedy na hodnote $φ_e(x)$ nezávisí, definovatelnost ano). Položme nyní $h(x) = g(e, x)$, potom je $A$ jak oborem hodnot, tak definičním oborem funkce $h$, funkce $h$ je rostoucí ČRF, jejíž GČ lze opět efektivně spočítat z $e$.

$4. ⇒ 3.$ : Toto je zřejmé. Implikaci $(3. ⇒ 1.)$ už máme hotovou.

{{TODO}}

1=>3 :Pro každou množinu $W_x$ vytvoříme množinu dvojic $R=\{\langle y,y\rangle:y \in W_x\}\,\!$. Množina $R\,\!$ je rekurzivně spočetná, tedy má ČRF selektor $\varphi\,\!$, :platí $dom(\varphi)=rng(\varphi)=W_x\,\!$.

:Myšlenka toho důkazu je, že body, kde $\varphi_x\,\!$ konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.

1<=3 :Máme ČRF $g\,\!$ a její obor hodnot. Zkonstruujeme pseudoinverzní funkci $h\,\!$ k ČRF $g\,\!$, tj. funkci takovou, že $dom(h)=rng(g)\,\!$ a to tak, že vyrobíme RS :predikát $Q(x,y)\Leftrightarrow g(x)\simeq y\,\!$ a to má ČRF selektor, který hledáme -- $h\,\!$.

≤₁, ≤_m a jejich vlastnosti, ''K'' a ''K₀'' 1-úplné, RSM a ¬RM.

1-převoditelnost, m-převoditelnost a jejich vlastnosti, 1-úplnost množin K a K0. Množiny K a K0 jsou rekurzivně spočetné, ale nejsou rekurzivní.

$A\leq_m B$ (množina $A$ je $m$-převoditelná na $B$) pokud ∃ ORF $f$, tž: $∀ x: x ∈ A ⇔ f(x) ∈ B$

$A\leq_1 B$ (množina $A$ je $1$-převoditelná na $B$) je-li $f$ navíc prostá

množina $A$ je $m$-úplná (resp. $1$-úplná) pro třídu RSM pokud: je $A$ RSM a ∀ jiná RSM je na ni $m$-převoditelná (resp. $1$-převoditelná).

:: 💡 budeme říkat pouze $A$ je $m$-úplná nebo $1$-úplná, dodatek „pro třídu RSM“ budeme vynechávat, protože jinými než RM a RSM se nebudeme zabývat.

9.1 vlastnosti ≤₁, ≤_m

• $A\leq_m B$ a $B$ RM $\Rightarrow A$ RM :: 💡 $A\leq_m B$ a $A$ není RM $\Rightarrow B$ není RM (protože: $(A\Rightarrow B)=(\neg B\Rightarrow \neg A)$) :: Dk: Je-li $B$ RM a $f$ je ORF převádějící $A$ na $B$, pak $x ∈ A ⇔ f(x) ∈ B$ a tedy $χ_A(x) = χ_B(f(x))$. $χ_A$ je jistě ORF a tedy $A$ je RM.

• $A\leq_m B$ a $B$ RSM $\Rightarrow A$ RSM :: 💡 $A\leq_m B$ a $A$ není RSM $\Rightarrow B$ není RSM :: Dk: Je-li $B$ RSM a platí-li $B = dom φ_e$ a je-li $f$ ORF, která převádí $A$ na $B$, pak

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 11: A = dom λx\̲[̲φe(f(x))]

  a jde tedy o RSM.

• $\leq_m$ a $\leq_1$ (relace) jsou reflexivní a tranzitivní :: Dk: To, že jsou $≤_m$ a $≤_1$ reflexivní relace plyne z toho, že identita je prostá ORF. Předpokládejme, že $A ≤_1 B$ a $B ≤_1 C$, nechť $f$ je prostá ORF převádějící $A$ na $B$ a $g$ buď prostá ORF převádějící $B$ na $C$. Pak $h(x) = g(f(x))$ je prostá ORF která převádí $A$ na $C$, což ukazuje, že $≤_1$ je tranzitivní. Pro $≤_m$ platí týž argument s vynecháním prostoty.

• $A$ $m$-úplná & $B$ RSM & $A\leq_m B \Rightarrow B$ je $m$-úplná :: 💡 platí pro 1-převoditelnost a 1-úplnost :: Dk: Toto plyne okamžitě z tranzitivity $≤_m$, $≤_1$ a definice úplnosti.

• $A\leq_mB \Rightarrow \overline A\leq_m\overline B$ :: 💡 platí pro 1-převoditelnost a 1-úplnost :: Dk: Plyne přímo z definice převoditelnosti, převod $A$ na $B$ zajistí stejná funkce jako převod $A$ na $B$.

Problém zastavení K₀ a jeho diagonála K

:: $K_0 =\{\langle x, y\rangle_2\;|\;\varphi_x(y)\downarrow\}=\{\langle x, y\rangle_2\;|\;y\in W_x\}$ - problém zastavení :: $K =\{x\;|\;\varphi_x(x)\downarrow\}=\{x\;|\;x\in W_x\}$ - diagonála $K_0$

💡 $K_1 =\{x\;|\;W_x\neq\emptyset\}$

{{theorem | $K$ a $K_0$ jsou RSM, ale nejsou RM

| $K$, $K_0$ RSM $\neg$RM }}

Dk (sporem jako u TS) ::

:: Z definice jsou obě RSM. Nechť $φ_z$ označuje univerzální ČRF. ::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 11: K = dom λx\̲[̲φ_z(x, x)]

. Pro spor $K$ je RM ⇒ $\overline K$ je RSM. :: Nechť $φ_e$ je ČRF, pro níž $\overline K = dom φ_e$ a ptejme se, zda $e ∈ \overline K$ nebo ne: :: Z def. $K$ ⇒ $e ∈ \overline K ⇔ φ_e(e)↑$ :: $\overline K = dom φ_e$ ⇒ $e ∈ \overline K ⇔ φ_e(e)↓$ :: ⇒ $φ_e(e)↓ ⇔ φ_e(e)↑$ ⇒ SPOR ⇒ $K$ tedy není RM. ::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 20: …= dom λ⟨x, y⟩_2\̲[̲φ_z(x, y)]

. Pro spor $K_0$ je RM a $χ_{K0}$ je její char. ORF: :: Definujeme $χ_{K}(x) = χ_{K_0}(⟨x, x⟩_2)$ ⇒ $χ_K$ char. ORF $K$ ⇒ SPOR s tím že $K$ není RM. ⇒ $K_0$ tedy není RM.

{{theorem

| Množiny $K$ a $K_0$ jsou 1-úplné. | 1-úplnost $K$, $K_0$

}}

Dk ::

:: $K$ je $1$-úplná: $K$ je RSM, stačí tedy ukázat, že libovolnou RSM lze na $K$ převést prostou ORF. :: Definujme funkci $φ_{e1}(e, x, y) ≃ φ_e(x)$. Podle s-m-n věty $φ_{s^2_1(e1,e,x)} (y) ≃ φ_e (e, x, y) ≃ φ_e(x)$. Definujme tedy funkci $f(e, x) = s_1^2(e_1, e, x)$. Protože $s_1^2$ je prostá PRF, je i $f$ prostá PRF. Navíc platí, že $φ_{f(e,x)}$ je buď všude definovaná konstantní funkce, pokud $x ∈ W_e$, nebo jde o funkci, která není definovaná pro žádný vstup v případě, že $x \notin W_e$, platí tedy, že: ::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 25: … φ_e(x)↓ ⇒ (∀y)\̲[̲φ_{e1} (e, x, y…

::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 29: … φ_e(x)↑ ⇒ (∀y)\̲[̲φ_{e1} (e, x, y…

:: Dohromady dostaneme požadovanou ekvivalenci $x ∈ W_e ⇔ f(e, x) ∈ K$, a z toho plyne, že funkce $g(x)$ definovaná jako $g(x) ≃ f(e, x)$, je prostá ORF, která převádí množinu $W_e$ na $K$. Protože $W_e$ byla libovolná množina, dostáváme, že

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: (∀e)\̲[̲W_e ≤_1 K]

, a $K$ je tedy $1$-úplná množina. :: $K_0$ je RSM (podle vlastností převoditelnosti). Ve větě nahoru jsme ukázali i to, že $K ≤_1 K_0$ pomocí prosté ORF $h(x) = ⟨x, x⟩_2$. Těžkost množiny $K_0$ tedy plyne z tranzitivity $1$-převoditelnosti.

Riceova v. - dk převoditelnost

Riceova věta - důkaz pomocí převoditelnosti. {{theorem

| $\cal C$ třída ČRF,

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 3: A_\̲c̲a̲l̲ ̲C = \{e | \varp…

je RM ⇔ $\cal C = \emptyset$ nebo $\cal C$ obsahuje všechny ČRF | Rice

}}

💡  

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 3: A_\̲c̲a̲l̲ ̲C

je mnozina indexu (Gödel.č.) funkci z třídy $\cal C$

Dk (pomocí převoditelnosti) ::

:: předpokládejme že $\cal C$ NEní ∅ a $\cal C$ NEobsahuje všechny ČRF :: ukážeme sporem že

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 9: K ≤_1 A_\̲c̲a̲l̲ ̲C

:: $e_0$ je GČ fce nedefinové pro žádný vstup a $φ_{e0} ∈ \overline{\cal C}$ :: $e_1$ je GČ fce $φ_{e1}∈C$ a $φ_{e0}≄ φ_{e1}$ ::

ParseError: KaTeX parse error: Undefined control sequence: \cases at position 26: …_2}(x, y)\simeq\̲c̲a̲s̲e̲s̲{ \varphi_{e_1}…

x\in K

ParseError: KaTeX parse error: Undefined control sequence: \cr at position 1: \̲c̲r̲ ̲\uparrow }

:: $φ_{e2}(x , y) ≃ φ_{s^1_1}(e, x) (y) ≃ φ_{f(x)}(y)$ ::

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 52: …∈ C ⇒ f(x) ∈ A_\̲c̲a̲l̲ ̲C

::

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 53: …∉ C ⇒ f(x)∉ A_\̲c̲a̲l̲ ̲C

:: tedy $x ∈ K ⇔ f(x) ∈ Ac$

VoR a důsledky (🎓)

Věta o rekurzi a její jednoduché důsledky (ne Riceova věta) {{Zkazky|

• Věty o rekurzi, došlo i na tu obligátní otázku, jestli počítá rychleji f(a) nebo a, od ní jsme se dostali až k Riceově větě a okrajově i k důkazu nerozhodnutelnosti halting problému

• Věta o rekurzi a její aplikace. Zkoušejícího zajímalo znění, důkaz (preferoval ten přes s-m-n větu, ale spokojil se i s diagonalizačním), aplikace (Riceova věta a její znění, existence množin jako $Wx=\{x\}$ s důkazem).

• Věty o rekurzi, Riceova věta - Napsal jsem základní větu, generování pevných bod a větu o rekurzi v závislosti na parametrech (vše samozřejmě s těmi jednoduchými důkazy). Napsal jsem Riceovu větu a její důkaz plynoucí ze základní věty o rekurzi. Ptal se mě odkud plynou důkazy, odpovědel jsem, že z Kleeneho věty a s.m.n. Pak se ještě ptal na trochu jinou verzi "Věty o programu co vypíše sám sebe", tam jsem trochu tápal, ale intuitivně jsem věděl (tu větu jsem znal, bohužel jsem ji neuvedl).

}}

{{theorem | ∀ ORF $f$ ∃ $n$: $φ_n ≃ φ_{f(n)}$

| VoR }}

:: 💡 ∀ ORF transformacni funkci algoritmu f ∃ n tak že oba TS počítají stejnou fci (mají stejný algoritmus) :: 💡 n se říká pevný bod f

Dk (přes s-m-n větu) ::

:: Nechť $e_1$ je číslem funkce, pro kterou platí $\varphi_{e_1}^{(2)}(e, x)\simeq\varphi_{f(\varphi_e(e))}(x),$ tuto funkci bychom snadno odvodili pomocí univerzální ČRF.
:: Nechť $b$ je Gödelovým číslem funkce $s_1^1(e_1, e)$, podle s-m-n věty tedy platí, že $\varphi_{\varphi_b(e)}(x)\simeq\varphi_{s_1^1(e_1, e)}(x)\simeq\varphi_{e_1}^{(2)}(e, x)\simeq\varphi_{f(\varphi_e(e))}(x).$
:: Protože $\varphi_b$ je PRF (podle s-m-n), je $\varphi_b(b)\downarrow$ a platí, že $\varphi_{\varphi_b(b)}\simeq\varphi_{f(\varphi_b(b))},$ $\varphi_b(b)$ je tedy hledaným pevným bodem $f$.

{{TODO|doplnit poznámky}}

Důsledky VoR

{{theorem | ∃ prostá PRF $g$, která ke GČ funkce $f$ určí její pevný bod

| 💡 }}

{{theorem | ∀ ORF $f$ má ∞ pevných bodů

| 💡 }}

{{theorem | ∃ $n ∈ N$, pro nějž:

1. $W_n = \{n\}$

2. ParseError: KaTeX parse error: Undefined control sequence: \[ at position 9: φ_n ≃ λx\̲[̲n]

| 💡 }}

Dk ::

1. Nechť $e$ je Gödelovo číslo funkce definované jako

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 21: …(2)}(x, y) ≃ μz\̲[̲x = y]

   (💡 tedy $φ_e^{(2)}(x, y)↓$ ⇔ $x = y$). Použijeme s-m-n větu a definujeme-li $f(x) ≃ s_1^1(e, x)$, dostaneme, že $φ_{f(x)} ≃ φ_{s-1-1(e,x)} ≃ φ_e(x, y)$ a tedy $W_{f(x)} = \{x\}$. Funkce $f$ je ORF (podle s-m-n), a tak podle VoR: $∃ n: φ_n ≃ φ_{f(n)}$, a tak $W_n = W_{f(n)} = \{n\}$.

2. Podobně, nechť $e$ je GČ funkce definované jako $φ_e^{(2)}(x, y) ≃ x$. Pomocí s-m-n věty definujeme-li $f(x) = s_1^1(e, x)$, dostaneme $φ_{f(x)}(y) ≃ x$ a s použitím VoR nalezneme $n$, pro něž je $φ_n(y) ≃ φ_{f(n)}(y) ≃ n$.

{{theorem

| $f(x,y)$ je ORF $⇒ ∃$ prostá ORF $n(y)$ taková, že $φ_{n(y)} ≃ φ_{f(n(y),y)} ∀y ∈ N$ | VoR s parametry

}}

Riceova v. - dk s VoR (🎓)

{{theorem | $\cal C$ třída ČRF,

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 3: A_\̲c̲a̲l̲ ̲C = \{e | \varp…

je RM ⇔ $\cal C = \emptyset$ nebo $\cal C$ obsahuje všechny ČRF

| Rice }}

Dk (sporem) ::

:: předpokládejme že $\cal C$ NEní ∅ a $\cal C$ NEobsahuje všechny ČRF :: předpokládejme sporem že

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 3: A_\̲c̲a̲l̲ ̲C

je rekurzivní :: definujme si fci $f$: ::

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 18: …x) = a ~~ x∉ A_\̲c̲a̲l̲ ̲C

::

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 18: …x) = b ~~ x∈ A_\̲c̲a̲l̲ ̲C

:: $f$ je ORF ::

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 5: a∈A_\̲c̲a̲l̲ ̲C

::

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 6: b∉ A_\̲c̲a̲l̲ ̲C

:: $n$ je pevný bod $f$ a $φ_n≃ φ_{f(n)}$ ::

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 20: …\cal C ⇒ n ∈ A_\̲c̲a̲l̲ ̲C ⇒ f(n)=b ⇒ f(…

::

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 20: …\cal C ⇒ n ∈ A_\̲c̲a̲l̲ ̲C ⇒ f(n)=a ⇒ f(…

:: ⇒ spor

Složitost

(Complexity)

Def. základních tříd složitosti. Definice třídy NP pomocí cert. a NTS a jejich ekvivalence. ≤^p_m, NPC a jejich vlastnosti (🎓)

Definice základních tříd složitosti. Definice třídy NP pomocí certifikátů a nedeterministických strojů a jejich ekvivalence. Polynomiální převoditelnost a úplnost a jejich vlastnosti

Definice základních tříd složitosti

typy problémů:

• odpověď typu ano/ne - rozhodovací problém (jestli vstup patří do binární relace $L\subseteq\{0, 1\}^*$)

  • vstup - instance problému

• úloha - pro daný vstup x nalézt y co splňuje požadovanou vlastnost (jestli oba patří do binární relace $R\subseteq\{0, 1\}^*\times\{0, 1\}^*$)

třídy jazyků a relací (tj. problémů a úloh) ::

💡 $f:\mathbf N\mapsto\mathbf N$ libovolná fce

• $DTIME(f(n))$, jazyk $L(M) ∈ DTIME(f(n)) ⇐$ ∃ TS $M$ co pracuje v čase $O(f(n))$.

• $DSPACE(f(n))$, jazyk $L(M) ∈ DSPACE(f(n)) ⇐$ ∃ TS $M$ co pracuje v prostoru $O(f(n))$.

• $DTIMEF(f(n))$, relace $R ∈ DTIMEF(f(n)) ⇐$ ∃ TS $M$ co pracuje v čase $O(f(n))$, $M(x)$ přijme ⇔ ∃ slovo $y$: $(x, y)\in R$ a na konci páska obsahuje $y$ :: 💡 Lze to také říci tak, že selektor pro predikát R je funkce spočitatelná v polynomiálním čase.

{{lemma|$DTIME(f(n)) ⊆ DSPACE(f(n))$}}

Definice třídy NP

Třídy polynomiálních jazyků, relací:

• $P= \bigcup_{i\in \mathbb N}DTIME(n^i)$ - problémy rozhodnutelné v polynomiálním čase

• $PSPACE=\bigcup_{i\in\mathbb N}DSPACE(n^i)$ - problémy rozhodnutelné v polynomiálním prostoru

• $PF=\bigcup_{i\in\mathbb N}DTIMEF(n^i)$ - úlohy řešitelné v polynomiálním čase

Třída polynomiálně ověřitelných úloh $NPF$ ($NP$ - nedeterministicky polynomiální, $F$ - funkce, úlohy řešitelné nedeterministickým Turingovým strojem v polynomiálním čase)

• Relace $R ∈ NPF$ ⇐ ∃ polynom $p(n)$: že $∀ (x, y)\in R$ je $|y|\leq p(|x|)$ a ověření zda $(x, y)\in R$ lze v polynomiálním čase.

Třída polynomiálně ověřitelných problémů $NP$ (nedeterministicky polynomiální)

• def. pomocí certifikátů: Jazyk $L ∈ \mathrm NP$ ⇐ ∃ polynom $p$ a jazyk $B\in P$ a pokud $∀ x\in\{0, 1\}^*$ platí:

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 41: …exists y)\;\Big\̲[̲|y|\leq p(|x|)\…

  :: 💡 $L ∈ \mathrm NP$ ⇐ ∃ polynomiální algoritmus (daný jazykem $B$), že polynomiálně dlouhý certifikát $y$ dosvědčuje fakt $x\in L$. Je opět nutné uvažovat pouze polynomiálně dlouhé certifikáty, neboť složitost ověřování se měří vzhledem k délce $x$ i certifikátu $y$. :: 💡 obecně platí P ⊆ NP, protože pokud umíme problém řešit polyn. nepotřebujeme certifikát

• def. pomocí NTS:

::💡 NTS $M=(Q, \Sigma, \delta, q_0, F)$, kde $\delta:Q\times\Sigma\mapsto\cal P(Q\times\Sigma\times\{R, N, L\})$.

třídy jazyků a relací (tj. problémů a úloh) ::

:: 💡 $f:\mathbf N\mapsto\mathbf N$ libovolná fce :: $NTIME(f(n))$, jazyk $L(M) ∈ NTIME(f(n)) ⇐$ ∃ NTS $M$ co pracuje v čase $O(f(n))$. :: $NSPACE(f(n))$, jazyk $L(M) ∈ NSPACE(f(n)) ⇐$ ∃ NTS $M$ co pracuje v prostoru $O(f(n))$.

{{theorem

| $NP=\bigcup_{i\in\mathbb N} NTIME(n^i)$ | ekvivalence definic NP

}}

Dk (přes oba směry implikace) ::

:: → : Předpokládejme nejprve, že L ∈ NP, to znamená, že ∃ polynom p a jazyk B ∈ P, pro které platí, že x ∈ L právě když existuje y, |y| ≤ p(|x|), pro které (x, y) ∈ B. NTS M’ , který bude přijímat L, bude pracovat ve dvou fázích. V první fázi zapíše na vstupní pásku za slovo x slovo y, tato fáze je nedeterministická a pro každé slovo y, takové že|y| ≤ p(|x|) existuje výpočet M’, který jej napíše. Na zápis y stačí čas p(|x|). Ve druhé fázi bude M’ simulovat práci TS M, který rozpoznává jazyk B, na vstupu (x, y), přičemž přijme, pokud (x, y) ∈ B. Zřejmě L = L(M) a M pracuje v polynomiálním čase. :: ← : Nyní předpokládejme, že L ∈ ∪i∈N NTIME(ni). To znamená, že x ∈ L právě když existuje polynomiálně dlouhý výpočet nedeterministického Turingova stroje M, kde L = L(M), jenž x přijme. V každém kroku tohoto výpočtu vybírá M z několika možných instrukcí, nechť řetězec y kóduje právě to, které instrukce byly v každém kroku vybrány. Řetězec y má délku nejvýš p(|x|) pro nějaký polynom p, protože M pracuje v polynomiálním čase a možností jak pokračovat z dané konfigurace podle přechodové funkce je jen konstantně mnoho. Simulací M s použitím instrukcí daných dle y můžeme deterministicky ověřit, zda y kóduje přijímající výpočet. Řetězec y tedy může sloužit jako polynomiálně dlouhý certifikát kladné odpovědi.

Polynomiální převoditelnost, úplnost a jejich vlastnosti.

{{multiple image |align = tright

|direction = horizontal

| image1 = Redukce.jpg | width1 = 331

| caption1 = Ilustrace polynomiálního převodu/redukce z jazyka $L_1$ na jazyk $L_2$ pomocí redukční fce $f$. Pro vstup $x∈\{0,1\}^*$ má otázka zda $x∈L_1$ stejnou odpověď jako otázka zda $x∈L_2$. 💡 myslím že je vidět proč se mu říká někdy redukce($f$ NENÍ prostá)

| image2 = Nphard.png | width2 = 223

| caption2 = ${NP}$-těžkost }}

$A\leq_m^pB$ (jazyk $A$ polynomiálně převoditelný/redukovatelný na $B$) pokud ∃ f: {0,1}→{0, 1} spočitatelná v polynomiálním čase a platí: $x ∈A ⇔f(x) ∈B$

vlastnosti:

• $\leq_m^p$ je reflexivní a tranzitivní. :: Dk: Reflexivita plyne z toho, že identita je funkce spočitatelná v polynomiálním čase. Tranzitivita plyne z toho, že složením dvou polynomů vznikne opět polynom, přesněji, je-li f funkce převádějící jazyk A na jazyk B, tedy A ≤mp B s použitím f, a g je funkce převádějící jazyk B na jazyk C, tedy B ≤mp C s použitím g, pak g ◦ f převádí A na C, jsou-li f i g spočitatelné v polynomiálním čase, lze totéž říci i o g ◦ f, tedy A ≤mp C s použitím g ◦ f.

• $A\leq_m^pB$ a $B\in P$ ⇒ $A\in P$ :: Dk: Je-li B ∈ P, pak existuje Turingův stroj M, který přijímá B v polynomiálním čase. Je-li f funkce, která převádí A na B, a je-li f spočitatelná v polynomiálním čase, pak TS M’, který pro vstup x spočítá f(x) a poté pustí M k rozhodnutí, zda f(x) ∈ B, přijímá A v polynomiálním čase.

• $A\leq_m^pB$ a $B\in NP$ ⇒ $A\in NP$ :: Dk: Platí z téhož důvodu jako { 2. }, protože tytéž argumenty lze použít i pro NTS.

Image:800px-P%20np%20np-complete%20np-hard.svg.jpg

Jazyk $A \in \mathbf{NP}$-hard (NP-těžký) ⇐ ∀ jazyk $B\in NP$: $B\leq_m^pA$.

Jazyk $A \in \mathbf{NPC}$ (NP-Complete, NP-úplný) ⇐ $A \in NP$ a $A \in NP$-hard.

:: 💡 problem je T-uplny, pokud patri do T a je T-silny, tedy kazdy problem v T se da na problem prevest v poly case

{{theorem

| A, B ∈ NP, $A\leq_m^pB$ je NP-úplný ⇒ B je NP-úplný |

}}

Dk ::

:: Tvrzení plyne přímo z tranzitivity relace $≤_m^p$ zaručené vlastnostami polynomiální převoditelnosti a definice NP-úplného problému.

Definice (existence certifikátu – CERT, rozhodovací problém):

• Instance : Řetězec w kódující DTS M, řetězec x a řetězec 1ᵗ pro nějaké t ∈ N.

• Otázka : Existuje řetězec y s |y| ≤ t, pro který platí, že M(x, y) přijme v t krocích?

{{theorem

| Problém CERT je NP-úplný. | NP-úplnost CERT

}}

<br style="clear: both">

Savičova věta.

{{Zkazky|

• Státnice: Napsal jsem vetu, myslenku dukazu (sestrojime turingac, simulujeme vsechny vetve, recyklujeme + pamatujeme stavy...) v pohode stacilo, zeptal se me jeste na par otazek a o.k.

• Státnice(I1): Trochu predbehnu - v prubehu zkouseni jsem se zeptal, zda je na pruchod touto otazkou nutno umet vetu dokazat. Odpoved:ano, idea dukazu nestaci. V mych materialech, jsem mel zneni nepresne [s rovnitkem namisto podmnozinitka mezi NSPACE a DSPACE. Rovnost je az ve vztahu NPSPACE a PSPACE]. Trval jsem na rovnitku s tim, ze jedna implikace je trivialni, [PK] si nebyl jisty, ze to takto plati a rekl at teda prejdu rovnou k te druhe implikaci(soudim, ze pro me to byly body dolu). Dukaz jsem delal na eng.Wikipedii. Nejprve jsem [spatne] zapsal algoritmus tak, ze snizoval delku cesty jen o 1 vrchol v kazdem zanoreni. [PK] nerekl co je spatne, ale chtel hned zanalyzovat prostorovou slozitost. Podrobne az na uroven zda se nacitani vstupu pocita nebo ne. Zde vyplynulo, "ze je neco spatne je" (napr. uz jen proto, ze pokud jen odecitam jednicku, nemusim pouzivat tento algoritmus, ale mohu proste prohledavat stavy do hloubky). V predpokladech jsem mel blbe "f nalezi o(log(n))" namisto "f nalezi male ci velke omega(log(n))". Nevzpominam si presne, ale rozdil (pro "o" vs. "omegy") byl v tom, ze jeden dovoluje prostor potrebny pro vstup stroje predpokladat "zadarmo" u druheho jej musim zapocitat do prost.slozitosti. Nahradil jsem odecitani jednicky pulenim intervalu a spolecne jsme uvarili prostorovou slozitost. Doplnujici otazky: def. prostorove konstruovatelna fce, ktere fce jsou prostorove konstruovatelne - ve smyslu je jich dostatecne (k rozumnemu analyzovani algoritmu)? Mj. jsem povedel, ze "problem maji ty vydatne sublinearni" s cimz [PK] nesouhlasil (log(n) je prostorove konstruovatelna - ale loglog(n) uz ne). Obecne [PK] jde do velkych detailu, zustava mily, dava prostor. Tato otazka byla nejspis za 3. U tohoto zkousejiciho velmi doporucuju pripravit si otazku na papir a precizne, nez povidat spatra o coz jsem se pokousel.

}}

{{:Řešené_otázky_NTIN090/Savitch_Sandbox}}

Cook-Levin - KACHL ∈ NPC (🎓)

{{Zkazky|

• NP-uplnost (meno neviem, inicialy ML) Zacal som definiciou Turingovho stoja a postupne som definoval vsetko az po NP-uplnost, dokazal kachlikovani, prave ked som pisal prevod KACHL->SAT tak prisiel skusajuci, pozrel sa na to vsetko a povedal ze to staci.

• Král: NP, NP-úplnost, příklady... Trochu jsem se zamotal do toho, jestli je třeba, aby se NTS zastavil po polynomiálním počtu kroků (v první chvíli jsem myslel, že ne a že když to bude třeba, tak že $NTS = DTS$, ale to je blbost - třeba to sice není, ale pokud tak tu definici dáme, tak se nic nezmění). Byl hodný.

• Matoušek - NP-úplnost - Přesná formální definice - rozhodovací problém, jazyk problému, NTS pro rozhodovací problém, složitost výpočtu NTS, NP. Převoditelnost aritmetických funkcí, problémů, NP-těžkost, NP-úplnost. Příklady problémů. Vztahy P, NP, NPC (obrázek s podmnožinami, je NPC doplněk k P v NP?). Alternativní definice NP přes ověřování řešení. Jak popsat NP, NPC laikovi.

• NP-úplné problémy - Definoval jsem nedeterministický Turingův stroj, třídu NTIME, NP-úplnost a dokázal převod obecného NTS počítajícího nějaký NP problém na KACHL (Cook-Levinova věta). Na závěr jsem zmínil, že ještě existují další NP-úplné problémy např. SAT, Batoh, Obchodní cestující atd. Žádné další převody jsem nespecifikoval. Tato odpověď byla přijata bez jediné otázky.

• Definoval jsem jazyk, problem, NP, prevody, NP-uplnost a strucne predvedl dukaz cook levina. Zkousejiciho opet neznam, ptal se jen na to jake dalsi NP-uplne problemy, jinak byl spokojen

• Čepek (příseděl Koubek a Dvořák) - Úplné problémy pro třídu NP, Cook-Levinova věta. - Člověk by řekl, že jednoduchá otázka, ale kurevsky mi zatopila, neb jsem nebyl schopen dát do kupy přesnou definici NP a převoditelnosti pomocí TS (a Čepek 5 minut před tím jednoho kolegu vyhodil, neb neznal definici). Naštěstí mě několikrát nakopli a tak jsme nakonec došli k tomu, co to teda je NP-úplný problém. C-L větu + důkaz převodem na kachlíkování jsem uměl, což Čepka evidetně potěšilo, takže nakonec v pohodě.

• definice NP, prevoditelnost, NPC, prevod na kachlikovani a na SAT

• Koubek: definoval jsem NP, NPC, atd., dokazal vetu kachlikovanim. Pak se me ptal co znamena pojem uplnosti obecne a naky jeho zneni nebo dusledek Cook-Levinovy vety (neco jako ze kdyz bych umel polynomialne resit NPC problem, tak uz vsechny NP problemy jdou resit polynomialne). Pak chtel co je PSPACE uplnost a nakej priklad (obecna booleovska formule). SAT ve zneni s KNF se mu uplne nelibil, prej se vetsinou definuje obecne. Kdyz mu prisedici Majerech rikal, ze jak jsem ho definoval se to u nas vetsinou dela, tak se Koubek mracil :)

• Hladík - Úplné problémy pro třídu NP + Cook Levinova věta. - Definice (od TS až k NPÚ), Důkaz Cook Levinovy věty (KACHL + převod na SAT), vyjmenovat problémy co byly na přednášce (zadání, otázka), ukázat převod SAT na KLIKA.

• NP-úplné problémy (Klazar) - Dal jsem do kupy důkaz úplnosti kachlíkování, pár převodů, ani mi je nenechal všechny přeříkat. Nakonec se zeptal, kam patří PRIMES (rozhodnout, zda něco je prvočíslo) - bez důkazu

}}

Kachlíkování (KACHL, anglicky Tiling)

• Instance: Množina barev B, přirozené číslo s, čtvercová síť S velikosti s x s, hrany jejíchž krajních políček jsou obarveny barvami z B. Dále je součástí instance množina K⊆BxBxBxB s typy kachlíků, které odpovídají čtverci, jehož hrany jsou obarveny barvami z B. Tyto kachlíky mají přesně definovaný horní, dolní, levý i pravý okraj a není možné je otáčet.

• Otázka: Existuje přípustné vykachlíkování čtvercové sítě S kachlíky z množiny K? Přípustné vykachlíkování je takové přiřazení typů kachklíků jednotlivým polím čtvercové sítě S, v němž kachlíky, které spolu sousedí mají touž barvu na vzájemně dotýkajících se hranách a kachlíky, které se dotýkají strany S, mají shodnou barvu s okrajem. Jednotlivé typy kachlíků lze použít víckrát.

{{theorem

| KACHL je NP-úplný problém. | Cook-Levin

}} 💡  neboli splnitelnost SAT je NP-úplná (tedy je nutne prevest KACHL na SAT ale to neni nutne dokazovat)

Dk ::

:: DTS->kachl; barva pro vsechny symboly * vsechny stavy; specialni barva pro posun hlavy vlevo/vpravo :: spodni okraj vstupni paska, obarveni vystupniho okraje je vystupni paska :: alt.: existuje vykachlikovani?

Dk(Myšlenka důkazu) ::

• Kachl je v NP (jistě jde verifikovat v polynomiálním čase)

• Kachl je NP těžký

  • Vezměme libovolný problém z NP, pak jeho nedeterministický turingáč řeší, jestli $I \in L$ (zda řetězec $I$ patří do jazyka $L$, neboli zda jeho nedeterministický turingáč přijme daný vstup $I$) v polynomiálním čase polynomu $P$

  • Zkonstruujeme síť $P\times P$, zkonstruujeme vhodné kachličky (7 druhů) a obarvení (barvy jsou z množiny $ABECEDA \cup (STAVY \times ABECEDA) \cup \lbrace q_l, q_r | q \in STAVY \rbrace$ tak, aby

    • Každý krok výpočtu NTS kódoval jeden vykachličkovaný řádek. NTS pracuje "paralelne" (existuje vice zpusobu vypoctu), takze si muzeme predstavit strom vypoctu, kde vetveni zajistuje prechodova funkce. Simulovat NTS pomoci deterministickeho TS zvladneme prochazenim tohoto stromu do sirky (nikoli do hloubky!)

    • Každý řádek popisoval jeden krok výpočtu NTS

• Tím jsme nalezli NP-úplný problém

{{TODO|}}

Dk(NTS → KACHL) ::

Všimněme si nejprve, že $KACHL ∈ NP$. To plyne z toho, že dostaneme-li vykachlíkování sítě $S$, tedy přiřazení typů kachlíků jednotlivým políčkům, dokážeme ověřit v polynomiálním čase, jde-li o přípustné vykachlíkování. Ve skutečnosti úloha nalezení správného vykachlíkování je polynomiálně ověřitelná a patří tedy do NPF, proto její rozhodovací verze patří do NP. Nechť $A ⊆ \{0, 1\} ^*$ je libovolný problém, který patří do NP, ukážeme, že $A ≤_m^p KACHL$. Podle definice NP-úplného problému to bude znamenat, že $KACHL$ je NP-těžký, a protože patří do NP, tak i NP-úplný problém. To, že $A ∈ NP$ znamená, že existuje NTS $M$, který přijímá $A$ (tj. $A = L(M)$), a počet kroků každého přijímajícího výpočtu je omezen polynomem $p(n)$, bez újmy na obecnosti můžeme předpokládat, že $p(n) ≥ n$, v opačném případě by M nepřečetl ani celý svůj vstup a pokud by platilo, že $p(n) ≤ n$, stačí vzít $max(p(n), n)$ místo $p(n)$. Připomeňme si, že podle definice $x ∈ A$, právě když existuje přijímající výpočet NTS M nad vstupem x, který má délku nejvýš $p(|x|)$. Nechť $M = (Q, Σ, δ, q_0, F )$, kde $Q$ obsahuje stavy $q_0$ a $q_1$ a $\{0, 1, λ\} ⊆ Σ$. Abychom si zjednodušili situaci, budeme předpokládat, že $M$ splňuje následující předpoklady:

1. $F = \{q_1\}$, tj. $M$ má jediný přijímající stav $q_1$ různý od $q_0$.

2. Pro každé $a ∈ Σ$ je $δ(q_1, a) = ∅$, tj. z přijímajícího stavu neexistuje definovaný přechod.

3. V počáteční konfiguraci hlava stojí na nejlevějším symbolu vstupního slova $x$, které je zapsáno počínaje od levého okraje vymezeného prostoru délky $p(|x|)$. Zbytek pásky je prázdný.

4. Během výpočtu se hlava $M$ nepohne nalevo od místa, kde byla v počáteční konfiguraci.

5. Přijímající konfigurace je daná jednoznačně a vypadá tak, že páska je prázdná a hlava stojí na nejlevější pozici vymezeného prostoru. To odpovídá tomu, že než se $M$ rozhodne přijmout, smaže nejprve obsah pásky a přesune hlavu k levému okraji vymezeného prostoru.

Není těžké ukázat, že ke každému NTS $M_1$ lze zkonstruovat NTS $M_2$, který přijímá týž jazyk jako $M_1$, „dělá totéž“ a splňuje uvedené podmínky . Většinu zmíněných předpokladů jsme již dříve použili, například při konstrukci univerzálního TS. Bez újmy na obecnosti tedy můžeme předpokládat, že $M$ splňuje uvedené podmínky. Nechť $x$ je instance problému $A$, popíšeme, jak z $M$, polynomu $p$ a instance $x$ vytvořit instanci Kachlíkování, pro kterou bude platit, že v ní existuje přípustné vykachlíkování, právě když existuje přijímající výpočet $M(x)$, tj. $M(x)$ přijme. Idea důkazu je taková, že hrany barev mezi dvěma řádky kachlíků budou kódovat konfigurace výpočtu NTS $M$ nad vstupem $x$. Vhodným výběrem kachlíků zabezpečíme, že v přípustném vykachlíkování bude řada kachlíků simulovat změnu konfigurace na následující pomocí přechodové funkce. Položíme tedy $B = Σ ∪ (Q × Σ) ∪ \{q_L, q_R | q ∈ Q\}$. Zatímco vstupní abecedou stroje $M$ je jen $\{0, 1, λ\}$, neboť $x$ musí být binární řetězec, pracovní abecedu stroje $M$ nijak neomezujeme, a proto zde používáme obecnou abecedu $Σ$, přičemž předpokládáme, že $λ ∈ Σ$.

Kachl0.png does not exist. Create it?{: alt="Kachl0.png"} vypocet.jpg does not exist. Create it?{: alt="vypocet.jpg"} $\stackrel{odpovídá}{\Rightarrow}$ Kachl.png does not exist. Create it?{: alt="Kachl.png"}

Přehled převodu obecného problému $A ∈ NP$ na problém $KACHL$. Horní hrana čtvercové sítě je obarvena počáteční konfigurací, spodní hrana přijímající konfigurací, boky jsou obarveny symbolem $λ$. Pro ukázku je zde řádek kachlíků s provedením instrukce $(q’, b, R) ∈ δ(q, a)$, dva kachlíky slouží k provedení instrukce, na ostatních místech je jen kopírovací kachlík pro okopírování barev na další řádek. Po ukončení výpočtu je dokopírována přijímající konfigurace až ke spodní hraně čtvercové sítě.

NP-úplnost SAT (z KACHL)

Image:Npc.jpg

:: Literál je buď proměnná nebo její negace. :: Pozitivní literál je každá proměnná $x$ . :: Negativní literál je každá negace proměnnej $\overline x$. :: Klauzule je disjunkcí literálů, která neobsahuje dva literály s touž proměnnou $x ∨ \overline y ∨ \overline z$. :: Formule $φ$ je v konjunktivně normální formě (KNF), pokud je konjunkcí klauzulí $(x ∨ y) ∧ \overline z$. :: Je-li $φ$ formulí na n proměnných a $t ∈ \{0, 1\}^n$ , pak $φ(t)$ značí hodnotu $φ$ v ohodnocení $t$.

Splnitelnost formule v KNF (SAT)

• Instance: Formule $φ$ na $n$ proměnných v KNF

• Otázka: ∃ ohodnocení, pro které je $φ$ splněná?

Důkaz transformací KACHL ∝ SAT: pomocí proměnných $x_{ijk}$, kde $x_{ijk} = 1$, pokud na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲i,j]

se nachází kachlík typu $k$. Jednotlivé klauzule se vytvoří tak, aby zaručovaly, že na každé pozici je právě jeden kachlík, že kachlíky navazují horizontálně, vertikálně i na kraje stěny.

{{theorem

| SAT je NP-úplný problém | NP-úplnost SAT

}}

Dk($SAT∈ NP$) ::

To, že $SAT$ patří do NP, plyne z toho, že pokud dostaneme vektor $t ∈ {0, 1}^n$, můžeme spočítat hodnotu φ(t) v polynomiálním čase. Certifikátem kladné odpovědi je tedy splňující ohodnocení. Toto ohodnocení je ve skutečnosti řešením úlohy splnitelnosti, v níž chceme splňující ohodnocení nalézt a ne jen zjistit, zda existuje, tato úloha tedy patří do NPF.

Dk($SAT∈ NPC \Leftarrow KACHL \leq_m^p SAT$ - neformální konstrukce SAT ze KACHL, <Řešené_otázky_NTIN090/KACHL_SAT>) ::

:: pomocí proměnných $x_{ijk}$, kde $x_{ijk} = 1$, pokud na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲i,j]

se nachází kachlík typu $k$. Jednotlivé klauzule se vytvoří tak, aby zaručovaly, že na každé pozici je právě jeden kachlík, že kachlíky navazují horizontálně, vertikálně i na kraje stěny:

1. Políčku

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j]

   přiřadíme !1 typ kachlíku: :: $β_{i, j} = C_{i, j} ∧ α_{i, j}$ pro $i, j = 1, . . . , s$. :: Políčku

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j]

   přiřazen alespoň 1 typ kachlíku: :: $C_{i, j} = ∨_{k = 1}^{|K|} x_{i, j, k}$ :: Políčku

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j]

   přiřazen nejvýš 1 typ kachlíku: :: $α_{i, j} = ∧_{k = 1}^{|K|} ∧_{l = k + 1}^{|K|}(\overline x_{i, j, k} ∨ \overline x_{i, j, l})$

2. Nad sebou umístěným políčkům

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j]

   a

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲(i + 1), j]

   nejsou přiřazeny nekompatibilní typy kachlíků: :: $γ_{i, j} = ∧ _{(p, q) ∈ V} \overline x_{i, j,p} ∨ \overline x_{(i + 1), j, q}$ pro ${ 1 ≤ i ≤ (s – 1) }, { 1 ≤ j ≤ s }$. :: Vedle sebe umístěným políčkům

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, j]

   a

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲i, (j + 1)]

   nejsou přiřazeny nekompatibilní typy kachlíků: :: $δ_{i, j} = ∧_{ (p, q) ∈ H} \overline x_{i, j,p} ∨ \overline x_{i, (j + 1), q}$ pro ${ 1 ≤ i ≤ s }$, ${ 1 ≤ j ≤ (s – 1) }$.

3. podmínky pro stěny: :: Definujeme:

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 19: … = ∧_{j = 1}^s \̲[̲ ∨_{k ∈ U_j} (x…

   . Formule $ε_u$ je splněna, pokud je na každém políčku v prvním řádku kachlík s barvou shodnou s příslušným horním okrajem. :: Definujeme:

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 19: … = ∧_{j = 1}^s \̲[̲ ∨_{k ∈ B_j} (x…

   . Formule $ε_b$ je splněna, pokud je na každém políčku v nejspodnějším řádku kachlík s barvou shodnou s příslušným spodním okrajem. :: Definujeme:

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 19: … = ∧_{j = 1}^s \̲[̲ ∨_{k ∈ L_i} (x…

   . Formule $ε_l$ je splněna, pokud je na každém políčku v nejlevějším sloupci kachlík s barvou shodnou s příslušným levým okrajem. :: Definujeme: $ε_r = ∧_{j = 1}^s ( ∨_{k ∈ R_i} (x_{i, s, k)})$. Formule $ε_l$ je splněna, pokud je na každém políčku v nejlevějším sloupci kachlík s barvou shodnou s příslušným levým okrajem.

S pomocí výše definovaných formulí nyní definujeme formuli $φ$ jako: ::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: φ = \̲[̲∧_{i = 1}^s ∧_{…

.

Z konstrukce okamžitě vyplývá, že $φ$ je formule v KNF a že velikost $φ$ je polynomiální v s a $|K|$, a v polynomiálním čase lze $φ$ i zkonstruovat.

{{Zdroje|

• http://ktiml.mff.cuni.cz/~kucerap/NTIN090/NTIN090-poznamky.pdf

• http://oai.cwi.nl/oai/asset/1834/1834A.pdf

}}

NP-úplnost 3-SAT (z SAT)

Image:Satisfiability-L.gif

Image:Satisfiability-R.gif Kubická CNF (vždy jen 3 proměnné v jedné disjunkci) $F$ na $n$ Booleovských proměnných. Existuje pravdivostní ohodnocení proměnných, které splňuje formuli $F$?

Splnitelnost formule v 3KNF (3SAT)

• Instance: Formule φ na n proměnných v 3KNF, tj. KNF, v níž každá klauzule obsahuje !3 literály.

• Otázka: ∃ ohodnocení, pro které je φ splněná?

{{theorem

| SAT je NP-úplný problém. | NP-úplnost SAT

}} :💡 3SAT není náhodní problém, analogicky definován 2SAT je již polynomiálně řešitelný

Dk ( $3SAT\in NP$ ) ::

:: Problém 3SAT je jen zvláštním případem problému SAT a z téhož důvodu jako v případě problému SAT, patří i 3SAT do třídy NP.

Dk ( $3SAT\in NPC \Leftarrow SAT\leq_m^p 3SAT$ ) ::

:: konstrukce 3SAT $φ$ z SAT fle $ψ = C_1 ∧ . . . ∧ C_m$ (kde klauzule $C_j = (e_1 ∨ . . . ∨ e_k)$ ) :: SAT klauzule se transformují na 3SAT případně doplní novými proměnnými nastavenými tak aby neovlivňovaly výsledek: :: ( k = 1 ) $α_j = (e_1 ∨ y_1^j ∨ y_2^j) ∧ (e_1 ∨ \overline y_1^j ∨ y_2^j) ∧ (e_1 ∨ y_1^j ∨ \overline y_2^j) ∧ (e1 ∨ \overline y_1^j ∨ \overline y_2^j)$ :: $y_1^j, y_2^j$ - nové proměnné, které se nevyskytují v ψ :: ( k = 2 ) $α_j = (e_1 ∨ e_2 ∨ y^j ) ∧ (e_1 ∨ e_2 ∨ \overline y^j )$. :: ( k = 3 ) $α_j = C_j$ :: ( k > 3 ) $α_j = (e_1 ∨ e_2 ∨ y_1^j) ∧ (\overline y_1^j ∨ e3 ∨ y_2^j) ∧ (\overline y_2^j ∨ e4 ∨ y_3^j) ∧ . . . ∧ (\overline y_{k−3}^j ∨ e_{k−1} ∨ e_k)$. :: Formule 3SAT : $φ = ∧_{j=1}^m α_j$ a lze ji i v polynomiálním čase zkonstruovat. :: SAT $ψ$ splnitelná ⇔ 3SAT $φ$ splnitelná (z konstrukce).

{{TODO|doplnit dukaz ekvivalence - u zkousky se vyzaduje}} <br style="clear:both;">

NP-úplnost VP (z 3-SAT)

Image:ZSV%201416994785854209736.png Image:ZSV%204921028494756709267.jpg

Vrcholové pokrytí (VP - Vertex Cover)

• Instance: Graf $G=(V, E)$ a přirozené číslo $k$

• Otázka: $∃S ⊆ V$ , $|S| ≤ k$ a z každé hrany obsahuje alespoň jeden vrchol?

{{theorem | $VP$ je NP-úplný problém.

| $VC ∈ NPC$ }}

Dk ($VP ∈ NP$) ::

:: pro danou množinu $S$ dokážeme ověřit v polynomiálním čase, jde-li o VP správné velikosti

Dk ($VP ∈ NPC$ - $3SAT\leq_m^p VP$ ) ::

:: 3SAT: $φ=C_1∧...∧C_m$ s proměnnými $U={u_1,...,u_n}$ :: Konstrukce grafu $G=(V,E)$ skrz pospojování podgrafů: :: $∀u_i:$ def.podgraf $T_i =(V_i, E_i)=(\{u_i, \overline u_i\}, \{ \{u_i, \overline u_i\} \})$: - VP musí použít vždy aspoň 1 vrchol :: $∀C_j$: def.trojůhelník $R_j =(V’_j, E’_j)$: - VP musí použít vždy aspoň 2 vrcholy :: podgrafy pospojujeme podle formule $φ$

Vp.png does not exist. Create it?{: alt="Vp.png"}

:: $G$ má $VP$ $|S| ≤ k ⇔ φ$ splnitelná :: $⇒ k = n + 2m$ :: VP pokrývá vždy 2 vrcholy z $R_j$, ex. 1 co není v $S$ => odp vrchol v $T_i$ musí být v $S$ => odpovídajicí proměnná v $T_i$ musí být true :: $⇐$ do $S$ patří ohodnocené $u_i / \overline u_i$ ($n$ vrcholů) :: mezi vrcholy z $R_j$ musí být aspoň 1 pokrytý vrcholem z $S$ :: ⇒ do $S$ přidáme ty ostatní 2

<br style="clear:both;">

NP-úplnost 3DM (z SAT)

{{:Řešené_otázky_NTIN090/3DM2SAT_Sandbox}}

<br style="clear:both;">

LOUP ∈ NPC (z 3DM)

{{Zkazky|

• Ten převod jsem napsal na 5 stránek (ale mám velké písmo), s tím že některé věci jsem vůbec nerozepisoval, a PK si to prohlídnul (na 5. stranu ani nekouk) a že dobrý, a že mu nemusíme psát romány, že stačí stručně, aby viděl, že to umíme, a že se případně dozeptá. No - jak je koho ctěná libost, ale když toho napíšete hodně, tak se asi na nic už dozeptávat nebude, takže pokud budete mít něco obsáhlého (jako jsem měl já) a napíšete všechno co víte a šikovně vynecháte to co nevíte, tak už toho co víte bude tolik, že na to co nevíte se vás nejspíš už nikdo ptát nebude (teda pokud to nebude něco zásadního - ale i tak to stačí napsat tak stručně, aby to ještě byla pravda a zároveň to ta nechybělo úplně).

}}

Image:ZSV%206409563349302832850.jpg Image:ZSV%206986917693546073969.jpg

Loupežníci (LOUP) anglicky Partition

• Instance: Množina $A$ a váha $∀a∈A: s(a)∈N$

• Otázka: Lze rozdělit prvky z $A$ na dvě poloviny se stejnou váhou? $(\sum_{a\in A'}s(a)=\sum_{a\in A\setminus A'}s(a)\;)$

💡 Je zvláště vhodný pro dokazování NP-úplnosti problémů obsahujících numerické paramaetry jako jsou: délky, šířky, ceny, kapacity, atd.

{{theorem | LOUP je NP-úplný problém.

| LOUP ∈ NPC }}

Dk ($LOUP ∈ NP$) ::

:: plyne z toho, že pro zadanou množinu $A’ ⊆ A$ se ověří v polynomiálním čase, zda obsahuje prvky poloviční ceny.

Dk ($LOUP ∈ NPC$ - $3DM\leq_m^p LOUP$ ) ::

:: Konstrukce instance LOUP:

:Trojrozměrné párování (3-dimensional matching - 3DM)

• Instance: Množina $M⊆ W\times X\times Y$, kde $W, X, Y$ jsou po dvou disjunktní množiny a $|W|= |X|= |Y| = q$.

• Otázka: Obsahuje $M$ perfektní párování? Jinými slovy, existuje množina $M'⊆ M$, $|M'| = q$, trojice v níž obsažené jsou po dvou disjunktní?

:: z kontruujeme LOUP množinu takto $A={m_1,..,m_k,b_1,b_2}$ (💡 použijeme tedy trojice $m_i∈M$ a pomocné prvky $b_1,b_2$) :: cenu prvku $m_i$ si reprezentujeme jako binární "segmentové číslo" v $3q$ blocích, definovaných podle složení trojice $m_i$ * $m_i = {w_{f(i)}, x_{g(i)}, y_{h(i)}}$ kde fce $f,g,h$ vrací odpovídající indexy prvků z trojice $m_i$ * ∀ blok (z segmentu) má $p = ⌈log_2(k + 1)⌉$ bitů * pokud je prvkem trojice nastaví se v bloku bit na 1 zprava (ten nejméně významny) a ostatní na 0 (tedy formálně: $s(a_i)=2^{p(3q-f(i))}+2^{p(2q-g(i))}+2^{p(q-h(i))}$) * počet bitů pro reprezentaci $s(a_i)$ je $3pq$ (polynomiální) ⇒ 💡 ceny $s(a_i)$ se dají zkontruovat v polynomiálním čase :: dále si vytvoříme stejné segmentové číslo $B$ s 1 zprava v ∀ bloku (tedy $B=\sum_{j=0}^{3q-1}2^{pj}$) :: Image:3dm2loup.png :: teď dokážeme že $A'\subseteq\{a_i\;|\;1\leq i\leq k\}: B=∑_{a_i∈A’} s(a_i) ⇔ M’=\{m_i|a_i∈A’ \}$ je 3DM :: určíme si poslední dva pomocné dva prvky z $A$: :: $s(b_1) = 2∑s(a_i) - B$ :: $s(b_2) = ∑s(a_i) + B$ :: celkem pro množ. $A$ tedy máme $∑s(a_i) + s(b_1) + s(b_2) = ∑s(a_i) + 2∑s(a_i) - B + ∑s(a_i) + B = 4∑s(a_i)$ :: pokud $A'\subseteq A: \sum_{a\in A'}s(a)=\sum_{a\in A\setminus A'}s(a) = 2∑s(a_i)$ :: ⇒ $b_1,b_2$ nemůžou být oba ani v jedné půlce :: ⇒ $\sum_{A'\setminus \{b_1\}}s(a) =B$ (💡 musí být po řádcích disjunktní jinak by nám nevyšlo $B$) a $A’\setminus \{b_1\}$ <u>určují perfektní párování v $M$</u> (=$3DM$) :: nyní definujme 3DM $M'⊆M$ a $A’=\{a_i|m_i∈M’ \}$ :: $∑_{a\in A'}s(a) + s(b_1) = 2∑s(a_i)$ :: $A’\cup \{b_1\}$ <u>tedy obsahuje prvky poloviční ceny</u> (=$LOUP$)

<br style="clear:both;">

Pseudopolyn. alg., číselné probl. a silná NPC. Př. pseudopolyn. alg. Batoh (🎓)

Pseudopolynomiální algoritmy, číselné problémy a silná NP-úplnost. Příklad pseudopolynomiálního algoritmu pro Batoh {{Zkazky|

• pseudopolynomialni algoritmy - formalni definice pseudopolynomialniho algoritmu, silne NPU problem. Algoritmus reseni SP. Priklad silne NPU (TSP s omezenim na vaze hran) a proc je silne NPU (prevod na HK). Nekolik otazek jak souvisi pseudopolynomialni algoritmy a aproximacni algoritmy.

• Definice len, max, číselnosti, NP-úplnosti, pseudopoly alg., silné NP-úplnosti (napsal jsem bez kvantifikátorů a tedy jsem je musel doplnit). Příklad silně NP-úplného (obchodní cestující) a slabě (součet podmnožiny, loupežníci). Pak padl dotaz k čemu je možné pseudopoly alg. využít - základ pro aproximační schémata.

• Definice obojiho, jedna veticka o tom, ze silne NP-uplne nemaji pseudopol. alg., strucne napsany pseudopol. problem pro batoh, veta o tom, ze pokud bychom nasli pro silne NP-uplny problem pseudopolynamialni alg., muselo by platit, ze $P=NP$. Nic dalsiho nebylo potreba vedet.

• Napsal jsem špatnou definici pseudopolynomiálních algoritmů, aproximací, AS, a ÚPAS. Na dotaz jestli znám nějaké AS jsem zmínil ÚPAS pro SP, a to že patrně obsahuje nějakou proceduru co cosi prořezává. Posléze se mi podařilo přijít na správnou definici pseudopolynomiálních algoritmů, a to jak by zhruba měl vypadat pseudopolynomiální algoritmus pro problém batohu. Tou dobou ale už všichni ze zkoušky odešli tak mě nechal jít :-)

}}

Číselný problém je rozhodovací problém $A$, pokud pro každý polynom p existuje instance $I$ problému $A$, pro kterou platí, že $max(I) > p(len(I))$.

• len(I) - délka binárního zakódování instance I

• max(I) - hodnota největšího zadaného čísla v instanci I (je obsaženo ve vstupu)

:: 💡 Pro Batoh je $len(I) = O(n log_2(B + V))$, ale

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 25: …max(\{B\} ∪ \{v\̲[̲i], s\[i] | 1 ≤…

. Například LOUP nebo Batoh jsou tedy číselné problémy, zatímco SAT nebo KLIKA číselné problémy nejsou.

• Algoritmus řešící $A$ je pseudopolynomiální , pokud je jeho časová složitost omezená polynomem dvou proměnných $max(I)$ a $len(I)$.

:: 💡 Alg. pro Batoh je pseudopolynomiální (viz níže). Je-li problém $A$ řešitelný pseudopolynomiálním algoritmem a není-li $A$ číselný problém, pak je zřejmě tento pseudopolynomiální algoritmus ve skutečnosti polynomiální. Pokud bychom tedy pro nějaký nečíselný NP-úplný problém (např. kliku nebo SAT) našli pseudopolynomiální algoritmus, znamenalo by to, že $P = NP$.

NP-úplný problém, pro který ∃ pseudopolynomiální alg., nazýváme slabě NP-úplný.

Pokud ∄ pseudopolynomiální alg. je silně NP-úplný (💡 pokud P ≠ NP). Silná/slabá NP-těžkost se definuje analogicky.

Formálně: $p$ je polynom a $A$ NP-úplný problém:

• $A(p)$ je restrikce problému $A$ na instance $I$ s $max(I) ≤ p(len(I))$.

• Silně NP-úplný je problém $A$, pokud ∃ polynom $p$, pro nějž je problém $A(p)$ NP-úplný.

• Slabě NP-úplný je problém $A$, pokud ∄ polynom $p$, pro nejž je problém $A(p)$ NP-úplný.

{{theorem | Problém Obchodního cestujícího je silně NP-úplný.

| OC je silně NP-úplný }}

Dk ::

:: 💡 $max(I)$ je v tomto případě největší vzdálenost mezi městy :: v grafu ex. Hamiltonovská kružnice <=> OC obejde všechny města a vzdálenost mezi městy je vždy 1 :: OC(1) je stále NP-úplný => OC je silně NP-úplný

Image:250px-Knapsack.svg.png

Příklad pseudopolynomiálního algoritmu pro Batoh

Batoh ( 0/1 knapsack problem ), úloha ::

• Instance : Množina n předmětů $A = {a_1, . . . , a_n}$, s každým předmětem velikost $s(a_i) ∈ N$ a cena či hodnota $v(a_i) ∈ N$. Přirozené číslo $B ≥ 0$ udávající velikost batohu.

• Cíl : Nalézt množinu předmětů $A‘ ⊆ A$, která dosahuje maximální souhrnné hodnoty předmětů v ní obsažených, a přitom se předměty z $A$ vejdou do batohu velikosti $B$.

Pseudopolynomiální alg. $Batoh(s, v, B)$ (💡 bottom-up [[#Metody_tvorby_algoritm.C5.AF :: _rozd.C4.9Bl_a_panuj.2C_dynamick.C3.A9_programov.C3.A1n.C3.AD|dynamické programování]]):

• Vstup : Pole velikostí(size) $s$, cen (value) předmětů $v$ ($|s|=|v|=n$) a velikost batohu $B$. Platí:

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: 0 <s\̲[̲i] ≤ B

  .

• Výstup : Mnž. $|M|≤ B$ a s maximální cenou.

• Prerekvizity : $V$ je suma cen všech předmětů ($V= Σ_{i = 1^n} v_i$).

:: Nechť $T$ je tabulka $(n + 1) × (V + 1)$, na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j, c]

( $0 ≤ j ≤ n , 0 ≤ c ≤ V$ ), bude podmnožina indexů ( $1, . . . , j$ ) prvků celkové ceny přesně $c$ s minimální velikostí. :: Nechť $S$ je tabulka $(n + 1) × (V + 1)$, na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲j, c]

je celková velikost předmětů v množině

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j, c]

. Pokud neexistuje množina s předměty ceny přesně $c$, je na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲j, c]

číslo $B + 1$.

Image:Batoh.png

<u>Batoh(s, v, B)</u>: 0: # Inicializace tabulek:

1: for (c = 0 to V) { 2: T[0, c] = ∅; # temp

3: S[0, c] = B + 1; # sums of sizes 4: }

5: S[0, 0] = 0; 6: # Cyklus přes všechny předměty:

7: for (j = 1 to n) { 8: T[j, 0] = ∅;

9: S[j, 0] = 0; 10: # Cyklus zvyšující cenový limit:

11: for (c = 1 to V) 12: if (v[j] ≤ c) && # zda předmět j může být součástí řešení

13: (S[j – 1, c] > <span style="color: red; font-weight:bold">S[j - 1, c - v[j]]</span> + s[j]) { # minimalizujeme celkovou velikost předmětů při zachování c 14: S[j, c] = <span style="color: red; font-weight:bold">S[j – 1, c − v[j]]</span> + s[j];

15: T[j, c] = T[j – 1, c − v[j]] ∪ {j}; 16: } else {

17: S[j, c] = S[j – 1, c]; 18: T[j, c] = T[j – 1, c];

19: } 20: }

21: c = max{c| S[n, c] ≤ B}; 22: return T[n, c];

💡 Kučerova verze algoritmu MINImalizuje celkovou velikost předmětů (při zachování celkové ceny), běžné verze např. na wikipedii MAXImalizují celkovou cenu (při zachování celkové velikosti předmětů) {{theorem

| Algoritmus Batoh nalezne pro zadaný vstup množinu předmětů s nejvyšší cenou, jež se vejdou do batohu velikosti $B$. Pracuje v čase $O(nV)$. | Batoh v čase $O(nV)$

}}

Dk ($O(nV)$) ::

:: Kroky 0 až 6 zvládneme jistě v čase $O(nV)$, uvažujeme-li aritmetické operace jako konstantní. Následují dva vnořené cykly v rámci nichž jsou použity aritmetické operace, na něž stačí konstantní čas. I řádek 14 lze provést v konstantním čase při vhodné reprezentaci množin v

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j, c]

. Můžeme například použít reprezentaci pomocí bitového pole délky n, nebo pomocí spojového seznamu, v obou případech je přidání prvku do množiny jednoduché.

Dk (korektnost indukcí) ::

:: Ukážeme, že na konci běhu algoritmu splňují tabulky T a S vlastnosti, jež jsme popsali v prerekvizitách algoritmu. Jmenovitě ukážeme, že:

1. Na pozici

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j, c]

   , $0 ≤ j ≤ n, 0 ≤ c ≤ V$ je po ukončení algoritmu podmnožina $\{1, . . . , j\}$ prvků celkové ceny přesně $c$ s minimální velikostí mezi všemi takovými množinami. Pokud neexistuje množina prvků s cenou přesně $c$, pak na pozici

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j, c]

   bude ∅.

2. Na pozici

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲j, c]

   , $0 ≤ j ≤ n, 0 ≤ c ≤ V$ je po ukončení algoritmu součet velikostí prvků v množině na pozici

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j, c]

   . Pokud neexistuje množina prvků s cenou přesně $c$, pak na pozici

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲j, c]

   je $(B + 1)$.

:: Tyto vlastnosti ukážeme indukcí podle $j$. :: Na začátku vyplníme nultý řádek v cyklu na řádcích 1 až 4, pro $j = 0$ tedy vlastnosti (1.) a (2.) platí. :: Nyní předpokládejme, že vlastnosti (1.) a (2.) platí pro řádky $0, . . ., (j – 1)$ a ukažme, že platí i pro $j$-tý řádek. ::

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j, 0]=∅

protože je to nejmenší množina prvků s cenou $0$. Takto provedeme nastavení

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: T\̲[̲j, 0]

a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲j, 0]

na řádcích 8 a 9. :: Pokud je $c > 0$, pak na ně narazíme na vhodném místě v rámci vnitřního cyklu. :: Pro $j > 0$ a $c > 0$ máme dvě možnosti, buď v nejmenší množině prvků ${1, . . . , j}$ s cenou $c$ není prvek $j$, potom se jedná o množinu uloženou podle indukční hypotézy na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: T\̲[̲j − 1, c]

, nebo se v této množině prvek $j$ vyskytuje. Pokud bychom z této nejmenší množiny prvek odstranili, museli bychom dostat nejmenší množinu s cenou (

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 6: c − v\̲[̲j])

z prvků $\{1, . . . , (j – 1)\}$, která je podle indukčního předpokladu uložena na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j – 1, c − v\[j…

. :: Z těchto dvou možností vybereme tu, která má menší velikost. Díky tomu také na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j, c]

uložíme ∅ a na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲j, c]

hodnotu $(B + 1)$ jedině tehdy, pokud obě množiny na pozicích

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j − 1, c]

a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j − 1, c − v\[j…

jsou ∅ a obě odpovídající velikosti jsou $(B + 1)$. :: Zde využíváme toho, že porovnávání v kroku 13 je ostré, a tedy k přiřazení v kroku 14 dojde jedině tehdy, když je množina na pozici

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 3: T \̲[̲j − 1, c − v\[j…

neprázdná, jinak by z ∅ přidáním prvku $j$ vznikla množina neprázdná. :: :: Na závěr tedy při platnosti (1.) a (2.) stačí v kroku 21 vybrat množinu s největší cenou. Množina cen, z nichž vybíráme, je vždy neprázdná, neboť přinejmenším

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: S\̲[̲n, 0] = 0

.

Aproximační algoritmy - definice a příklad (🎓)

{{Zkazky| *Majerech - Aproximační algoritmy a schémata - Definice AA, poměrová a relativní chyba, AS, PAS, ÚPAS, ÚPAS pro SP (pozor na písmena v popisu PROŘEŽ (1-d)z < y < z), AA pro TSP

}}

Optimalizační úloha A je buď maximalizační nebo minimalizační a skládá se z těchto tří částí:

1. Množina instancí $D_A ⊆ \{0, 1\}^*$.

2. Pro každou instanci $I ∈ D_A$ je dána množina přípustných řešení $S_A(I) ⊆ \{0, 1\}^*$.

3. Funkce $μ_A$, která každé instanci $I ∈ D_A$ a každému přípustnému řešení $σ ∈ S_A(I)$ přiřadí kladné racionální číslo $μ_A(I, σ)$, které nazveme hodnotou řešení σ.

• Pokud je A maximalizační úlohou, pak optimálním řešením instance $I ∈ D_A$ je $σ ∈ S_A(I)$, pro něž je $μ_A(I, σ)$ maximální (tj. $μ_A(I, σ) = max\{μ_A(I, σ) | σ ∈ S_A(I)\}$).

  • Pokud je $A$ minimalizační úlohou, pak optimálním řešením instance $I ∈ D_A$ je $σ ∈ S_A(I)$, pro něž je $μ_A(I, σ)$ minimální (tj. $μ_A(I, σ) = min\{μ_A(I, σ) | σ ∈ S_A(I)\}$).

  • Hodnotu optimálního řešení instance $I ∈ D_A$ označujeme $OPT_A(I)= μ_A(I, σ)$ (kde $σ$ je optimální řešení intance $I$).

• Řekneme, že algoritmus $ALG$ je aproximačním algoritmem pro optimalizační úlohu $A$, pokud pro každou instanci $I ∈ D_A$ vrátí $ALG$ se vstupem $I$ řešení $σ ∈ S_A(I)$, případně ohlásí, že žádné přípustné řešení neexistuje, pokud $S_A(I) = ∅$.

• Hodnotu řešení vráceného algoritmem $ALG$ na instanci $I$ označíme jako $ALG(I)$, tj. $ALG(I) = μ_A(I, σ)$, kde $σ ∈ S_A(I)$ je přípustné řešení vrácené algoritmem $ALG$.

• Pokud je $A$ maximalizační úloha, pak racionální číslo $ε ≥ 1$ nazveme aproximačním poměrem algoritmu $ALG$, pokud pro každou instanci $I ∈ D_A$ platí, že $OPT (I) ≤ ε.ALG(I)$ .

  • Je-li $A$ minimalizační úlohou, pak racionální číslo $ε ≥ 1$ nazveme aproximačním poměrem algoritmu $ALG$, pokud pro každou instanci $I ∈ D_A$ platí, že $ALG(I) ≤ ε.OPT(I)$ .

Příklad aproximačního algoritmu pro Bin Packing

Bin Packing – BP, úloha ::

• Instance : Konečná množina předmětů $U = {u_1, .., u_n}$, s každým předmětem asociovaná velikost $s(u)$, což je racionální číslo, pro které platí $0 ≤ s(u) ≤ 1$.

• Cíl : Najít rozdělení všech předmětů do co nejmenšího počtu po dvou disjunktních množin $U_1, . . ., U_m$ takové, že každá množina může mít velikost max 1.

:: 💡 Naším cílem je tedy minimalizovat $m$. :: 💡 Formálně je tedy $D_{BP}$ množinou řetězců kódujících instance $BP$, pro danou instanci $I= ⟨U, s(u)⟩$ je množina $S_BP(I)$ množinou všech možných rozdělení do dostatečného množství košů. Mírou řešení $μ_{BP}(σ)$ pro $σ ∈ S_{BP}(I)$ je počet košů, které řešení využívá, tedy hodnota $m$. Rozhodovací verze tohoto problému je shodná s problémem Rozvrhování, o jehož těžkosti víme, z toho plyne, že i úloha $BP$ je $NP$-těžká. Šance na to, že bychom našli polynomiální algoritmus, řešící $BP$ přesně, jsou tedy malé.

Algoritmus (First Fit pro Bin Packing – $FF-BP$) ::

• Ber jeden předmět po druhém,

  • ∀ předmět $u$ najdi první koš, do nějž se tento předmět ještě vejde,

  • pokud takový koš neexistuje, přidej nový koš obsahující jen předmět $u$.

💡 Algoritmus $FF-BP$ je zřejmě polynomiální.

{{theorem | ∀ instanci $I ∈ DBP$ platí, že $FF-BP(I) <2.OPT_{BP}(I)$.

| Aproximační poměr $FF-BP$ je 2 }}

Dk ::

:: V řešení, které vrátí $FF-BP$ je nejvýš jeden koš, který je zaplněn nejvýš z poloviny. Kdyby totiž existovaly dva koše $U_i$ a $U_j$ pro $i <j$, které jsou zaplněny nejvýš z poloviny, tak by $FF-BP$ nepotřeboval zakládat nový koš pro předměty z $U_j$, všechny by se vešly do $U_i$. :: Pokud $FF-BP(I) > 1$, pak z toho plyne, že: $FF-BP(I) <⌈2 Σ_{i = 1}^n s(u_i)⌉ ≤ 2⌈Σ_{i = 1}^n s(u_i)⌉$, kde první nerovnost plyne z toho, že po zdvojnásobení obsahu jsou všechny koše plné až na jeden, který může být zaplněn jen částečně. :: Rovnosti bychom přitom dosáhli jedině ve chvíli, kdy by byly všechny koše zaplněné právě z poloviny, což není podle našeho předpokladu možné. :: Druhá nerovnost plyne z vlastností zaokrouhlování. :: Na druhou stranu musí platit, že $OPT(I) ≥ ⌈Σ_{i = 1}^n s(u_i)⌉$. :: Dohromady tedy dostaneme, že $FF-BP(I) <2.OPT(I)$. Pokud $FF-BP(I) = 1$, pak i $OPT(I) = 1$ a i v tomto případě platí ostrá nerovnost.

{{lemma | Pro libovolnou hodnotu m ∃ instance $I ∈ D_{BP}$, pro niž je $OPT(I) ≥ m$ a $FF-BP(I) ≥ 5/3 \cdot OPT(I)$.

}}

Dk ::

:: Instance bude mít $U = {u_1, u_2, . . . , u_18m}$, s těmito prvky asociujeme váhy takto: :: $1≤ i ≤ 6m : s(ui) = 1/7 + ε$, $6m<j ≤ 12m : s(ui) = 1/3 + ε$, $12m<j ≤ 18m : s(ui) = 1/2 + ε$. Kde $ε > 0 je$ dostatečně malé kladné racionální číslo. Optimální rozdělení rozdělí prvky do $6m$ košů, do každého dá po jednom prvku s velikostmi $(1/7 + ε), (1/3 + ε), (1/2 + ε)$. Hodnotu ε zvolíme dostatečně malou tak, aby se každá z těchto trojic vešla do koše velikosti $1$. Algoritmus $FF-BP$ bude brát prvky jeden po druhém a vytvoří nejprve m košů, každý s šesti prvky velikosti $(1/7 + ε)$, přičemž hodnotu $ε$ zvolíme dostatečně malou na to, aby se tam vešly, ale protože je kladná, nevejde se k nim nic dalšího. Poté vytvoří $3m$ košů, každý se dvěma prvky velikosti $(1/3 + ε)$, k nimž se opět nic nevejde. :: Nakonec $FF-BP$ vytvoří $6m$ košů, každý s jedním prvkem velikosti$(1/3 + ε)$. Dohromady je $FF-BP(I) = 10m$, a tedy

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲ FF-BP(I) / OPT…

. :: 💡 Pochopitelně brát prvky v libovolném pořadí tak, jak to činí $FF-BP$ je nejhloupější možnou strategií. Na instanci popsanou v důkazu lemmatu by přitom stačilo, kdybychom nejprve prvky $U$ setřídili sestupně podle velikosti a poté je umísťovali do košů v pořadí od největšího k nejmenšímu. Algoritmus, který postupuje podle této strategie nazveme $FF-D-BP$ z anglického „decreasing“. Lze ukázat, že pro libovolnou instanci $I ∈ D_{BP}$ platí: $FF-D-BP(I) ≤ (11/9).OPT(I) + 4$.

Aproximační schémata, př. pro Batoh (🎓)

Aproximační schémata - definice a příklad aproximačního schématu pro Batoh Image:Schemes.jpg

{{Zkazky|

• definicia optimalizacnej ulohy, definicia aproximacneho algoritmu, aproximacneho pomeru, aproximacneho schema, PAS a UPAS, schema pre BATOH

}}

Nechť $A$ je libovolná optimalizační úloha. Algoritmus $ALG$ nazveme aproximačním schématem pro úlohu $A$, pokud na vstupu očekává instanci $I\in D_A$ a racionální číslo $\varepsilon>0$ a na výstupu vydá řešení $\sigma\in S_A(I)$, jehož hodnota se od optimální liší s aproximačním poměrem $(1+\varepsilon)$.

• Tj. pro maximalizační úlohu platí, že: $OPT(I)\leq(1+\varepsilon)ALG(I, \varepsilon)$

• a pro minimalizační úlohu platí, že: $ALG(I, \varepsilon)\leq(1+\varepsilon)OPT(I)\;.$

Předpokládejme, že algoritmus $ALG$ je aproximační schéma a očekává na vstupu instanci $I\in D_A$ a racionální číslo $\varepsilon$. Pomocí $ALG_\varepsilon$ označíme instanci algoritmu $ALG$, kde hodnota $\varepsilon$ je zafixována, vstupem $ALG_\varepsilon$ je tedy jen instance $I\in D_A$ a běh i výstup $ALG_\varepsilon$ na vstupu $I$ jsou totožné s algoritmem $ALG$ se vstupem $I$ a $\varepsilon$.

• Řekneme, že $ALG$ je polynomiální aproximační schéma (PAS), pokud je pro každé $\varepsilon$ časová složitost algoritmu $ALG_\varepsilon$ polynomiální v $len(I)$, kde $ALG_\varepsilon$ označuje algoritmus vzniklý dosazením konstanty $\varepsilon$ do $ALG$

• Řekneme, že $ALG$ je úplně polynomiální aproximační schéma (ÚPAS), pokud $ALG$ pracuje v čase polynomiálním v $len(I)$ a $\frac{1}{\varepsilon}$.

{{theorem

| Nechť $A$ je optimalizační úloha, jejíž přípustná řešení mají nezápornou celočíselnou hodnotu. Předpokládejme, že ∃ polynom dvou proměnných $q$, který pro každou instanci $I ∈ DA$ splňuje: $OPT(I) <q(len(I), max(I))$. Pokud ∃ úplně polynomiální aproximační schéma pro úlohu $A$, pak ∃ i pseudopolynomiální algoritmus pro $A$. |

}} 💡 Důsledek : Nechť $A$ je silně NP-úplná optimalizační úloha, která splňuje předpoklady věty. Pokud $P = NP$, pak neexistuje úplně polynomiální aproximační schéma pro úlohu $A$.

{{theorem | Pokud existuje polynomiální aproximační algoritmus $ALG$ pro úlohu obchodního cestujícího s aproximačním poměrem $ε$, kde $ε > 1$ je konstanta, potom $P = NP$.

| }}

Image:Schemes-input.jpg

Příklad aproximačního schématu pro Batoh - BAPX

• Vstup: Pole $s$ velikostí předmětů a pole $v$ cen předmětů, obě délky $n$, velikost batohu $B$, racionální číslo $\varepsilon>0$. Předpokládáme, že

  ParseError: KaTeX parse error: Undefined control sequence: \[ at position 36: …ots, n\})\;\big\̲[̲0<s\[i]\leq B\b…

• Otázka: Množina M předmětů, jejichž souhrnná velikost nepřesahuje B.

$BAPX(s, v, B, \varepsilon)$

1. Spočti index m, pro nějž je

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: v\̲[̲m] = max_{1\leq…

   .

2. if ($\varepsilon \geq n - 1$) return {m}

3. ParseError: KaTeX parse error: Undefined control sequence: \[ at position 26: …( \varepsilon v\̲[̲m]/n )⌋ - 1

4. c je nové pole délky n.

5. for ($i= 1; i\leq n;i++$)

   ParseError: KaTeX parse error: Undefined control sequence: \[ at position 2: c\̲[̲i] = ⌊v\[i]/2^t…

6. return Batoh(s, c, B) // Volání původního algoritmu

💡 algoritmus provede zaokrouhlení cen předmětů a jejich přeškálování podle $ε$

{{theorem | Schéma BAPX pracuje v čase $O(\frac{1}{\varepsilon}n^3)$. Pro libovolnou instanci $I = ⟨s, v, B⟩$ úlohy Batoh a libovolné $ε > 0$ platí, že $OPT(I) ≤ (1 + ε) BAPX(I, ε)$.

| Algoritmus BAPX je $O(\frac{1}{\varepsilon}n^3)$ }}

coNP, #P - def. a vlastnosti

Definice (Nesplnitelnost KNF (UNSAT), úloha):

• Instance : Formule $φ$ v KNF

• Otázka : Platí, že pro každé ohodnocení v je $φ(v) = 0$?

• Poznámka: Nevíme, jak by měl vypadat polynomiálně ověřitelný důkaz toho, že formule $φ$ je nesplnitelná, ale můžeme najít polynomiálně ověřitelný protipříklad, tedy důkaz toho, že $φ$ není nesplnitelná { = je splnitelná}, protože $SAT$ patří do NP.

coNP

Image:Chpvenndiagram.jpg Jazyk (problém) A ⊆ {0, 1} patří do třídy coNP, pokud jeho doplněk patří do třídy NP.

Jazyk A je co-NP-úplný, je-li $coNP$ a pro libovolný jiný jazyk $B ∈ co-NP$ platí, že $B ≤^m_p A$.

{{lemma | Jazyk $A$ je co-NP-úplný ⇔ $\overline A$ je NP-úplný. }}

{{lemma | Patří-li některý NP-úplný jazyk do $coNP$, pak $NP=coNP$ { nepředpokladané }. }} {{lemma | $P ⊆ ( NP ∩ coNP)$ { předpoklad, že $P ⊊ NP ∩ coNP$ }. }}

#P

Funkce $f$ patří do třídy #P, pokud existuje binární relace $R$ v NPF a $\forall x$: $f(x) = |\{y | (x, y) ∈ R\}|$. Pak $f$ je početní úlohou asociovanou s $R$, značíme pomocí $\#R = f$.

{{lemma | Pro každý problém $A ∈ NP$ $∃$ relace $R_A$ v NPF, tak že platí: $x ∈ A ⇔ \#RA(x) > 0$. }}

Dk ::

:: Relace RA bude obsahovat dvojice $(x, y)$, kde $y$ je polynomiálně velký certifikát dosvědčující to, že $x ∈ A$.

{{lemma | Výpočet $f ∈ \#P$ lze provést za pomoci polynomiálně mnoha dotazů na náležení prvku do množiny $\{(x, N) | f(x) ≥ N\}$. }}

Dk ::

:: Protože $f ∈ \#P$, existuje relace $R ∈ NPF$, pro kterou platí, že $f = \#R$. Z definice plyne, že existuje polynom p, pro který platí, že pokud $(x, y) ∈ R, pak |y| ≤ p(|x|)$. To $p(|x|)$ znamená, že $f(x) ≤ 2$ , pokud uvažujeme $x$ i $y$ jako binární řetězce. Binárním vyhledáváním $p(|x|)$ najdeme hodnotu $f(x)$ dotazy na $N = 0, . . . , 2p(|x|)$ , protože binární vyhledávání pracuje v logaritmickém čase, bude nám na toto vyhledání stačit $p(|x|)$ dotazů, je jich tedy polynomiálně mnoho.

{{lemma | Výpočet $f ∈ \#P$, $f(x)$ lze provést v polynomiálním prostoru vzhledem k $|x|$. }}

Dk ::

:: Nechť f ∈ #P, podle definice to znamená, že existuje relace R ∈ NPF, pro kterou platí, že f = #R. Z definice plyne, že existuje polynom p, pro který platí, že pokud (x, y) ∈ R,p(|x|) pak |y| ≤ p(|x|), což znamená, že f(x) ≤ 2 , a k reprezentaci hodnoty f(x) nám tedy postačí p(|x|) bitů. Algoritmus počítající f(x) bude postupně generovat všechny binární řetězce y délky nejvýš p(|x|), pro každý z nich ověříme, zda (x, y) ∈ R a pokud ano, zvýšíme hodnotu f o jedna. K ověření (x, y) ∈ R nám podle definice NPF stačí polynomiální čas, a tedy i prostor, pro uložení y i hodnoty f(x) nám také stačí polynomiální prostor, a celkový prostor je tedy polynomiální.

Funkce $f : \{0, 1\}* → N$ je polynomiálně převoditelná na funkci $g : \{0, 1\}* → N$, pokud existují polynomiálně spočitatelné funkce $α : \{0, 1\}* × N → N$ a $β : \{0, 1\}* → \{0, 1\}*$ , pro které platí, že:

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 16: (∀x ∈ {0, 1} ) \̲[̲f(x) = α(x, g(β…

( odpovídá polyn. algoritmu, spočítá $f(x)$ s jedním voláním $g$ ).

Funkce $f : \{0, 1\}$ je #P-těžká, pokud je každá funkce $g ∈ \#P$ polynomiálně převoditelná na $f$.

Funkce $f$ je #P-úplná, je-li #P-těžká a platí-li současně, že $f ∈ \#P$.

Nechť $A, B ∈ NPF$ jsou binární relace, řekneme, že polynomiálně spočitatelná funkce $β$ převádí $A$ na $B$ se zachováním počtu řešení, pokud $∀x ∈ \{0, 1\}* : |\{y | (x, y) ∈ A\}| = |\{y | (β(x), y) ∈ B\}|$.

{{lemma | Nechť $A ∈ NPF$ je taková, že libovolnou relaci z NPF lze na $A$ polynomiálně převést se zachováním počtu řešení, potom #A je #P-úplná úloha. }}

Poznámky:

• Například tedy #KACHL, #SAT , #HK, #LOUP a další jsou všechno #P-úplné úlohy { převody, které jsme si ukazovali, lze udělat tak, aby zachovávaly počty řešení, proto lze ukázat, že úlohy odpovídající problémům, jejichž těžkost jsme si ukazovali, jsou #P-úplné }.

• #SAT je #P-úplná funkce, protože redukce, již jsme si ukazovali pro převod obecného problému z NP na SAT zachovává počty řešení/certifikátů.

• Podobně to platí o dalších početních funkcích, asociovaných s dalšími NP-úplnými problémy a úlohami, jejichž těžkost jsme si ukazovali { s každým problémem A v NP je asociovaná úloha z NPF, která pro zadaný vstup najde certifikát náležení do A, pokud takový certifikát existuje }.

• Existují úlohy z PF takové, že s nimi asociované početní funkce jsou #P-úplné.

• #DNF-SAT je #P-úplná funkce, ačkoli DNF-SAT patří do P.

• Také určení počtu perfektních párování v bipartitním grafu je #P-úplná funkce, zatímco najít nějaké perfektní párování (pokud existuje) je polynomiálně řešitelná úloha.

Term je konjunkcí literálů, neobsahující dva literály s touž proměnnou.

Formule $φ$ je v disjunktivně normální formě (DNF), pokud je disjunkcí termů.

{{theorem

| #DNF-SAT je #P-úplná | #DNF-SAT je #P-úplná

}} Prerekvizita – Problém splnitelnosti formule v DNF je polynomiálně řešitelný { DNF-SAT je P }.

Dk ::

:: Protože úloha DNF-SAT zřejmě patří do NPF (dokonce do do PF), patří #DNF-SAT do #P. Popíšeme, jak převést #SAT (tj. #KNF-SAT, chceme-li explicitně zdůraznit, že jde o splnitelnost formule v KNF) na #DNF-SAT. Protože #KNF-SAT je #P-úplná funkce, bude to platit i o #DNF-SAT. Nechť $φ$ je formule v KNF, pomocí de-Morganových pravidel převedeme její negaci $¬φ$ na DNF, kterou si označíme pomocí $ψ ≡ ¬φ$, pak platí, že: $\#KNF-SAT(φ) = 2n − \#DNF-SAT(ψ)$, kde $n$ je počet proměnných formule $φ$. V převodu tedy funkce $ψ = β(φ)$ spočítá DNF negace zadané formule v KNF a funkce α(φ, c) odečte počet c = #DNF-SAT(ψ) od 2n. To vše lze jistě provést polynomiálně.

Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus (<strike>zkoušková</strike>, 🎓)

• http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Metody_tvorby_algoritm%C5%AF

Metody tvorby algoritmů: rozděl a panuj, dynamické programování

{{Zkazky|

• U dynamickýho programování jsem nějak sesmolil princip fungování a napsal jsem tam jeden konkrétní algoritmus (z grafiky - matchování vrcholů dvou mnohoúhelníků), na kterym jsem ukazoval, jak to funguje. To bylo OK, ale tahal ze mě pořád nějakej obecnej princip, jak to funguje. V rámci toho jsem ještě za pochodu vymýšlel algoritmus na batoh (to se mi vůbec nedělalo dobře, když vedle mě seděl a čekal na výsledek). Na konec jsme se teda asi dobrali toho, co chtěl slyšet - že se řešení konstruuje z menších podúloh stylem zdola nahoru (narozdíl od rozděl&panuj, kde to je v zásadě shora dolů).

• Dynamicke programovani (Dvorak) - idea, srovnani s rozdel a panuj, priklady (efektivni) a jejich casova slozitost, prejiti do souvisejicich oblasti - popsal sem floyd-washall a batoh od nej jsme presli pres pseudopolynomialni alg, aproximacni batoh (schema) k UPAS, ale byla to volna diskuse ale nevadilo to.

• Mel jsem srovnat s metodou Rozdel a panuj + ukazat nejaky priklad

• Motivaci a základní princip dynamického programování. Ukázáno na algoritmech výpočtu Fibonacciho čísel, batohu a Floyd-Warshalova algoritmu. U posledního jmenovaného ze mě zkoušející dostával formální důkaz proč požadujeme nezáporné hrany.

• Dvořák - Hladové algoritmy - Popsal jsem intuitivně o co jde (oiptimalizační hladové algoritmy), popsal jsem, jak to funguje a popsal jsem Krustalův hladový algoritmus. Bavili jsme se o jeho složitosti (kde jsem neznal způsob, jak to je "ideální"), potom o jeho korektnosti (to jsem taky detaily neznal - nikdy jsem to úplně 100% nepochopil a když jsem se na to koukal do Kapitol z diskrétní matematiky před šesti týdny znova, tak jsem to také úplně nepochopil). Nicméně mi se mě pan Dvořák snažil trochu popostrčit, ale kde nic není, ani smrt nebere. Ukončili jsme to s tím, že to hlavní jsem věděl a že to není fatální.

}}

prakticky otázka z bakaláře, očekává se nějaké naroubování na to co jsme se naučili na NMgr

ROZDILY oproti metode Rozdel a panuj (jsou to dve ruzne metody tvorby algoritmu)

Divide and conquer:

• Does more work on the sub-problems and hence has more time consumption.

• In divide and conquer the sub-problems are independent of each other.

Dynamic programming:

• Solves the sub-problems only once and then stores it in the table.

• In dynamic programming the sub-problem are not independent.

• http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Metody_tvorby_algoritm%C5%AF#Dynamick.C3.A9_programov.C3.A1n.C3.AD

• http://www.quora.com/What-is-the-difference-between-dynamic-programming-and-divide-and-conquer

• http://cs.wikipedia.org/wiki/Dynamick%C3%A9_programov%C3%A1n%C3%AD

• https://onedrive.live.com/view.aspx?cid=388a82b3c4ce1dfe&id=documents&resid=388A82B3C4CE1DFE%211759&app=OneNote&authkey=!ABoWVv2NQ4DuOcQ&&wd=target%28%2F%2FSlo%C5%BE.one%7C4a6ac938-39bb-4a44-a4e0-55bbd289b47b%2FMetody%20tvorby%20algoritm%C5%AF%7Cf7e91395-dd92-4345-b02e-e8f43a837b66%2F%29

Hladový algoritmus

• http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Metody_tvorby_algoritm%C5%AF

Amortizovaná složitost

• spíše z datových struktur, očekává se vysvětlení na příkladu

• https://onedrive.live.com/view.aspx?cid=388a82b3c4ce1dfe&id=documents&resid=388A82B3C4CE1DFE%211759&app=OneNote&authkey=!ABoWVv2NQ4DuOcQ&&wd=target%28%2F%2FSlo%C5%BE.one%7C4a6ac938-39bb-4a44-a4e0-55bbd289b47b%2FAmortizovan%C3%A1%20slo%C5%BEitost%7Cb6f7db98-f9ef-4fff-9943-ffdac3b251e0%2F%29

• http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Odhady_slo%C5%BEitosti

Průnik se státnicovými otázkami

Vyčíslitelnost:

Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce.

• PRF, ORF, ČRF (definice)

• Jejich základní vlastnosti

• ČRF ⇔ TS

• Kleenova věta

• s-m-n?

Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti.

• definice RM a RSM

• vlastnosti

  • (Ne)uzavřenost na sjednocení, průnik a doplněk.

  • Postova věta v kontextu množin.

  • Existenční kvantifikátor a výběrová funkce.

  • generování, rostoucí, def.obor

Algoritmicky nerozhodnutelné problémy (halting problem).

• definice TS, UTS

• definice halting problému

• Věta: Halting problém není algoritmicky rozhodnutelný. (+ důkaz)

• převoditelnost, Riceova věta

Věty o rekurzi a jejich aplikace, Riceova věta.

• Věta o rekurzi a její jednoduché důsledky

• Riceova věta - důkaz pomocí věty o rekurzi.

Složitost:

Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus.

• definice rozděl a panuj, dynamické programování a rozdíl mezi nimi

  • příklady

• definice hladového algoritmu + příklad

Amortizovaná složitost.

• Asymptotická složitost - definice

• Amortizovaná složitost - definice

Úplné problémy pro třídu NP, Cook-Levinova věta.

• definice: třídy NP, polynom.převoditelnost, NP-těžký, NP-úplný

• zmínit P =? NP

• Cook-Levinova věta + důkaz

Pseudopolynomiální algoritmy, silná NP-úplnost.

• Pseudopolynomiální algoritmy definice + příklad

• silná NP-úplnost definice + příklad (a souvisloti)

Aproximační algoritmy a schémata.

• definice Aproximační algoritmy a schémata a jejich souvislost s pseudopolynom. algoritmy

• příklad schémata pro batoh nebo soucet podmnozin

Ostatní

Image:Npc-small.png

• http://xkcd.com/

• If I just proved that P = NP, how do I start taking over the world?