{{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)
}}
<math>≃</math> - podmíněně rovno
[[Image:Tm.jpg|right|thumb|306px|'''TS''' <math>M = (Q, ∑, δ, q_0, F)</math>]]
===Turingův stroj===
* '''(k-páskový deterministický) TS''' je 5-tice: '''M = (Q, ∑, δ, q<sub>0</sub>, F)'''
** Q je konečná '''množina stavů''' (řídící jednotky)
** ∑ je konečná '''pásková abeceda'''
*** obsahuje znak λ pro prázdné políčko
** <math>δ : Q \times ∑^k -> Q \times ∑^k \times \{R, N, L\}^k ∪ \{⊥\}</math> je '''přechodová fce'''
*** ⊥ je nedefinovaný přechod
** q<sub>0</sub> ∈ 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 '''ne'''prá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 ===
[[Image:ZSV 3729090544640692881.png|right|thumb|460px|💡 '''∀RJ je i RSJ''']]
* '''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í RS
=== 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 protože jedn 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Č
;Definice (kódování instrukcí TS: M = (Q, ∑, δ, q<sub>0</sub>, F)):
: Nejdřív do abecedy Γ = {0, 1, L, N, R, |, #, ; }, pak z abecedy Γ do binární.
: <math>Q = \{q_0, q_1, . . . , q_r\}</math>, r ≥ 1, kde q0 označuje počáteční, q1 jediný { BÚNO } přijímající stav.
: <math>Σ = {X_0, X_1, X_2, . . . , X_s}</math>, s ≥ 2, X0, X1, X2 označují zaradom symboly 0, 1, λ.
: <math>(x)_B</math> značí binární zápis čísla x.
: <math>(i)_B|(j)_B|(k)_B|(l)_B|Z</math> je kódem instrunkce δ(qi, Xj) = (qk, Xl, Z), kde Z ∈ {L, N, R} v abecedě Γ.
:: 💡 <math>(i)_B</math> - číslo i zapsané binárně.
: C1#C2# . . . #Cn−1#Cn 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.
: Bijekce 1we = e ∈ N, určuje pro TS M s bin kódem we Gödelovo číslo e, pak TS značíme Me.
===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:''' <math>U(w; x)↓ ⇔ M(x)↓</math> a <math>U(w; x)↓ = M(x)↓</math>
}}
* '''Simulace:''' <math>U(w; x)↓ ⇔ M(x)↓</math> a <math>U(w; x)↓ = M(x)↓</math>
* '''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|right|thumb|460px|'''3-páskový UTS''']]
** '''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 <math>q_i</math> stroje M zakódován jako <math>(i)_B</math>
**** 💡 totéž číslo, co lze vyčíst z přechodové funkce M uložené v řetězci w na 1. pásce
====Algoritmus UTS====
# '''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)
# '''Simulace'''
#* simuluj kroky M dokud ex. instrukce pro konfiguraci
# '''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 <math>L</math> je '''rekurzivní''' (také '''rozhodnutelný'''), pokud ∃ TS <math>M</math>, který se vždy zastaví a <math>L = L(M)</math>.
[[Image:Diag.jpg|right|thumb|460px|<math>L_{DIAG}</math>]]
{{theorem
| <math>L_{DIAG} = \{w_i ∈ \{0, 1\}^* | w_i ∉ L(M_i) \}</math> není RSJ (tedy ani RJ)
| diagonalizační jazyk
}}
;Dk (sporem)
: Předpokládáme že <math>L_{DIAG}</math> je RSJ ⇒ ∃ TS M že <math>L_{DIAG} = L(M_e)</math> z čekož nám vychází ale '''spor''':
: <math>w_e \in L(M_e) ⇔ w_e ∈ L_{DIAG} ⇔ w_e \notin L(M_e)</math>, kde první ekvivalence vyplývá z toho, že <math>L_{DIAG} = L(M_e)</math> a druhá ekvivalence z definice <math>L_{DIAG}</math>
===univerzální jazyk===
{{theorem
| <math>L_u = L(U)</math> (kde U je UTS) je RSJ, ale není RJ
| univerzální jazyk
}}
;Dk (sporem)
: To, že <math>L_u</math> 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 <math>\overline L_u</math> není RSJ.
: Sporem nechť <math>\overline L_u = L(M)</math>. Pomocí stroje <math>M</math> zkonstruujeme stroj <math>M’</math>, který bude přijímat diagonalizační jazyk <math>L_{DIAG}</math>. Už víme, že <math>L_{DIAG}</math> není RSJ a dospějeme tím tedy ke '''sporu'''.
: <math>M’</math> dostane na vstupu slovo <math>w</math> a má rozhodnout, zda <math>w ∈ L_{DIAG}</math>, tedy jestli stroj s kódem <math>w</math> odmítne slovo <math>w</math>.
: <math>M’</math> udělá pouze to, že zkontroluje, zda w kóduje Turingův stroj způsobem, jaký jsme popsali při popisu UTS. Pokud <math>w</math> nekóduje syntakticky správně TS, odpovídá prázdnému TS, který slovo <math>w</math> určitě nepřijme a <math>M’</math> tedy skončí přijetím. V opačném případě připíše <math>M’</math> za <math>w</math> kód <math>111</math> (kód „;“) a za ně okopíruje opět slovo <math>w</math>. Poté <math>M’</math> spustí na tomto slově stroj <math>M</math>, pokud <math>M</math> přijme, přijme i <math>M’</math>, pokud se <math>M</math> zastaví a odmítne, odmítne i <math>M’</math>, pokud se <math>M</math> nezastaví, nezastaví se ani <math>M’</math>.
: <math>M’</math> ale přijímá jazyk <math>L_{DIAG}</math>, protože <math>M’(w)</math> přijme ⇔ <math>w</math> je validním kódem TS <math>N</math> a <math>N(w)</math> nepřijme, což je ekvivalentní tomu, že <math>U(w;w)</math> nepřijme a <math>M(w; w)</math> přijme. Fakt, že <math>L(M’) = L_{DIAG}</math>, je však ve '''sporu''' s tím, že <math>L_{DIAG}</math> není RSJ.
===problém zastavení===
{{theorem
| <math>L_{HALT} = \{w; x |~ w~ kóduje~ TS~ M~ a~ M(x)↓\}</math> 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 <math>L_{HALT}</math> je RSJ je zřejmé z existence UTS. <math>w;x \in L_{HALT} \Leftrightarrow U(w;x)↓</math>
: Diagonalizací ukážeme, že <math>\overline L_{HALT}</math> není RSJ, čímž bude důkaz dokončen díky Postové větě.
: Předpokládejme pro spor, že ∃ TS <math>M</math>, že <math>\overline L_{HALT} = L(M)</math>.
: Nyní definujme jazyk <math>L = \{w_i \in \{0, 1\}^*| M_i(w_i)↑\}</math>, jde vlastně o diagonálu <math>\overline L_{HALT}</math>. S pomocí TS <math>M</math> sestrojíme nyní TS <math>M_e</math> přijímající jazyk <math>L</math>.
: Pokud <math>M(w_i;w_i)</math> přijme, pak přijme i <math>M_e(w_i)</math>, v opačném případě <math>M_e(w_i)↑</math>. To učiní i v případě, zjistí-li, že <math>w_i</math> nekóduje syntakticky správně TS a odpovídá tedy prázdnému TS (to je zde nutné odlišit jen proto, že kdyby <math>w_i</math> obsahovalo oddělovač „;“, pak by <math>w_i;w_i</math> mohlo odpovídat výpočtu jiného TS nad jiným vstupem).
: TS <math>M_e</math> přijme svůj vstup ⇔ <math>M_e↓</math>. Zřejmě platí, že <math>L(M_e) = L</math>.
: Nyní se podívejme, jestli <math>w_e \in L</math> (<math>w_e</math> je kód <math>M_e</math>):
:# Pokud <math>w_e ∈ L</math>, znamená to, že se <math>M_e(w_e)</math> zastaví a přijme, protože <math>L = L(M_e)</math>, to ale současně znamená, že <math>M_e(w_e)↑</math> podle definice <math>L</math>, což je pochopitelně ve '''sporu'''.
:# Nyní předpokládejme, že <math>w_e \notin L</math>, ale podle definice <math>L</math> to znamená, že <math>M_e(w_e)↓</math>. Z toho jsme dostali <math>w_e ∈ L(M_e) = L</math>, což je však ve '''sporu''' s předpokladem.
: Jazyk <math>L</math> použitý v důkazu není nic jiného než <math>L_{DIAG}</math>, 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 1.jpg|right|thumb|460px|'''PRF⊂ORF⊂ČRF''']]
{| class="wikitable" border="1"
! !! funkce !! predikát !! množina !! problém
|-
|částečně rekurzivní /<br> rekurzivně spočetný || ČRF || RSP || RSM || částečně rozhodnutelný
|-
|obecně rekurzivní || ORF || ORP || rekurzivní množina || rozhodnutelný
|-
|primitivně rekurzivní || PRF || PRP || nezavádí se || nezavádí se
|}
=== PRF - primitivně rekurzivní fce ⇐ lze odvodit ze 3 základních fcí a pomocí 2 op. substituce a prim. rekurze (NE minimalizace) (🎓)===
* '''podmíněná rovnost <math>f(x_1,..,x_n) \mathbf{≃} g(x_1,..,x_n)</math>''' znamená: hodnota <math>f(x_1,..,x_n)</math> je definována ⇔ definována i hodnota <math>g(x_1,..,x_n)</math>, a pak jsou si také rovny
* '''Základní funkce'''
** '''nulová''' (konstantní) '''funkce''' <math>o(x) = 0 (∀x)</math>
** '''následník''' <math>s(x) = x + 1 (∀x)</math>
** '''projekce''' <math>I^j_n (x_1, .., x_j, .. , x_n) = x_j (∀j,n: 1 ≤ j ≤ n)</math>
*** 💡 vrací hodnotu j-tého parametru
* '''Operátory'''
** '''substituce''' <math>S^m_n(f,g_1,...,g_m) = h</math> kde: <math>h(x_1,...,x_n) ≃ f(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n))</math>
*** 💡 <math>f</math> funkce <math>m</math> proměnných a <math>g_1, .. , g_m</math> jsou funkce <math>n</math> 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''' <math>R_n(f,g) = h</math>
*** kde:
**** <math>h(0, x_2, ..., x_n) ≃ f(x_2, ..., x_n)</math>
**** <math>h(i+1, x-2, ..., x_n) ≃ g(i, h(i,x_2,...,x_n), x_2,..., x-n)</math>
*** 💡 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č'''
* 💡 vždy se zastaví => PRF odpovídají programům, které mohou používat jen for-cykly (vždy konvergují)
* 💡 PRF je ORF bez minimalizace
==== PRP - primitivně (obecně) rekurzivní predikát ⇐ ∃ pro něj PRF (ORF) charakteristická funkce ====
* '''predikát''' <math>R(x_1,...,x_n)</math> je relace nebo libovolný fakt o n proměnných
* '''charakteristická fce''' predikátu R je
** <math> \chi_P(x_1,\dots,x_n)\simeq \begin{cases}1 \quad & \mbox{ pokud } R(x_1,\dots,x_n) \\ 0 \quad & \mbox{ jinak }\end{cases}</math>
** 💡 char. fce je ORF
* 💡 (Obecně) PRM je unární (obecně) PRP.
=== ČRF - částečně rekurzivních fce (partial μ-recursive functions) ⇐ lze odvodit ze 3 základních funkcí pomocí 3 operátorů (🎓)===
{{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 <math>↓=</math> (zkratka za konverguje a rovná se) bychom v definici klidně mohli psát jen <math>=</math>. Použití <math>↓≠</math> (zkratka za konverguje a nerovná se) je ale důležité, například pokud <math>f(x_1,...,x_n,0)↑</math>, tak <math>h(x_1,...,x_n)</math> také není definováno, i kdyby třeba <math>f(x_1,...,x_n,1)=0</math>.
| '''minimalizace''' <math>M_n(f) = h</math>
}}
'''Nový operátor'''
*'''minimalizace''' <math>M_n(f) = h</math> (má sílu while-cyklu)
:<math>\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\}</math>
:* '''μy[P(x,y)]'''- fce μ vrátí nejmenší y takové, aby platil predikát P(x,y)
:** Lze jí sestrojit pomocí operátoru minimalizace
* '''obecně rekurzivní (ORF)''' je ČRF definovaná pro všechny vstupy
** 💡 neboli '''totální fce''' - def.pro všechny vstupy (=vždy se zastaví)
* 💡 ČRF mohou navíc používat právě while-cyklus (který ale může běžet do nekonečna a tak vznikne divergence)
==== RSP - rekurzivně spočetný predikát ⇐ ∃ pro něj ČRF charakteristická funkce ====
* '''částečná char. fce''' (=ČRF) predikátu <math>R</math> je funkce <math>f_R : N^n → N</math>: <math>f_R(x_1, . . . , x_n)↓ ⇔ R(x_1, . . . , x_n), ∀(x_1, . . . , x_n) ∈ N</math>.
* 💡 je def.oborem nějaké ČRF
* 💡 RSM je unární RSP
=== 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:
*** <math>g(z, x)=\sum_{y<z}f(y, x)</math> (přičemž <math>g(0, x)=0</math>)
*** <math>h(z,x)=\prod_{y<z}f(y, x)</math> (přičemž <math>h(0, x)=1</math>)
** '''(důsledek)''' f je PRF 1 proměnné ⇒ je PRF:
*** <math>g(z)=\sum_{y<z}f(y)</math> (přičemž <math>g(0)=0</math>)
*** <math>h(z)=\prod_{y<z}f(y)</math> (přičemž <math>h(0)=1</math>)
* '''(podmíněný příkaz) - analogie switch/case/if-then'''
**<math>g_1(x), \dots, g_n(x)</math>, <math>n>0</math> jsou PRF a <math>R_1(x), \dots, R_n(x)</math> jsou PRP a <math>\forall x\in{\mathbb N}</math> je splněn !1 z nich.
**⇒ tato fce <math>f</math> je PRF: <math>\begin{align} f(x)=g_1(x)&\Leftrightarrow R_1(x)\\ f(x)=g_2(x)&\Leftrightarrow R_2(x)\\ &\vdots&\\ f(x)=g_n(x)&\Leftrightarrow R_n(x) \end{align}</math>
* kvantifikátory (omezené i neomezené).
** '''(omezená kvantifikace)'''
*: <math>P</math> binární PRP ⇒ <math>V_P(z, x)=(\forall y<z)[P(y, x)]</math> a <math>E_P(z, x)=(\exists y<z)[P(y, x)]</math> jsou PRP.
* (ne)uzavřenost na logické spojky
** '''(logické spojky)'''
*: <math>P</math> a <math>R</math> unární PRP ⇒ <math>R\wedge P</math>, <math>R\vee P</math> a <math>\neg P</math> jsou PRP
** '''(konečná konjunkce a disjunkce)'''
*: <math>P</math> binární PRP ⇒ <math>A(x, z)=\bigwedge_{y<z}P(x, y)</math> a <math>B(x, z)=\bigvee_{y<z}P(x, y)</math> jsou PRP
* '''(omezená minimalizace)'''
*: <math>P</math> binární PRP ⇒ tato <math>f</math> je PRF:
*: <math>f(x, z)= \begin{cases} \min\{y<z\;|\;P(x, y)\} \quad &\mbox{pokud takové y existuje}\\ z \quad &\mbox{jinak.} \end{cases} </math>
*: Funkci <math>f</math> budeme také označovat pomocí <math>f(x, z)=\mu y<z[P(x, y)]</math>.
==Č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
| <math>h</math> je ČRF <math>n</math> proměnných ⇒ <math>h</math> je Turingovsky vyčíslitelná
| ČRF ⇒ TS
}}
:💡 Přesněji, existuje Turingův stroj <math>M_h</math> takový, že pro každou <math>n</math>-tici přirozených čísel <math>x_1, x_2, \dots, x_n</math> platí
:: <math>M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow</math>
:: a platí-li <math>h(x_1, x_2, \dots, x_n)\downarrow=y</math>, potom výpočet Turingova stroje <math>M_h</math> vydá na výstupu řetězec <math>(y)_B</math>.
; Dk (konstrukcí TS, [[Řešené_otázky_NTIN090/ČRF2TS| zde komplet včetně nižší úrovně]])
: definujeme TS pro základní funkce a operátory pro odvození <math>h</math>:
:* '''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 <math>h</math>, spočítá Gödelovo číslo <math>e</math> stroje <math>M_e</math>, který počítá funkci <math>h</math>.
| 💡
}}
{{theorem
| funkce <math>f</math> turingovsky vyčíslitelná ⇒ je <math>f</math> Č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 <math>M_e</math> 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 (<math>\mu y[T(e, x, y)]</math>)
* pomocí fce <math>\cal U</math> z ní vytáhnu g.číslo poslední konfigurace
* tedy <math>f(x)=\cal U(\mu y[T(e, x, y)])</math>
: 💡 U je zřejmě PRF
=== Kleenova věta o n.f. (bez převodu ČRF na TS) ===
<math>\mathbf{ \varphi_e^{(n)}}</math> je ČRF <math>n</math> proměnných, kterou počítá stroj <math>M_e</math>
{{theorem
| <math>\exists PRF \quad \cal U(y)</math> a PRP <math>T_n(e, x_1, \dots, x_n, y)</math>, pro které platí:
<math>(\forall n\in\mathbb N) (\forall e\in{\mathbb N})\; \varphi_e^{(n)}(x_1, \dots, x_n) \simeq\cal U(\mu y[T_n(e, x_1, \dots, x_n, y)])</math>
| 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
| <math>R</math> je RSP <math>\Leftrightarrow \exists</math> PRP <math>P</math> tak, že: <math>R(x_1, \dots, x_n)\Leftrightarrow(\exists y)[P(x_1, \dots, x_n, y)]</math>
| 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 <math>y</math>) 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 <math>y</math> stvrzující tento fakt, jsme schopni efektivně ověřit, že jde skutečně o certifikát platnosti.
=== univerzální ČRF ===
{{theorem
| <math>\forall</math> třídu proměnných <math>n>0</math> <math>\exists</math> univerzální ČRF: <math>\varphi_z^{(n+1)}(e, x_1, \dots, x_n)</math> taková, že <math>\varphi_z^{(n+1)}(e, x_1, \dots, x_n)=\varphi_e^{(n)}(x_1, \dots, x_n)</math> (tedy vyčísluje e-tou funkci)
| O univerzální funkci
}}
💡 existuje i univerzální funkce, a to pro každou třídu <math>n</math> proměnných (takže ta univerzální funkce pak dostane těch <math>n</math> 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):
: <math>\varphi_z^{(n+1)}(e, x_1, \dots, x_n) \simeq \cal{U}(\mu y[T_n(e, x_1, \dots, x_n, y)])</math>
: 💡 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''<sub>n</sub><sup>m</sup> věta ===
<math>\mathbf{ \varphi_e^{(n)}}</math> je ČRF <math>n</math> proměnných, kterou počítá stroj <math>M_e</math>
'''Churchovo <math>\lambda</math>-značení''' . Je-li <math>V</math> výraz, pak pomocí <math>\lambda_{ x_1x_2...x_n}V</math> označíme funkci na proměnných <math>x_1, x_2, \dots, x_n</math>, která je daná výrazem <math>V</math>.
{{theorem _
| <math>\forall</math> m,n > 0 <math>\exists</math> prostá PRF <math>s_n^m</math> a <math>\forall x, y_1, \dots, y_m</math> platí: <math>\varphi^{(n)}_{s_n^m(x,y_1,.., y_m)} = \lambda z_1..z_n[\varphi_x^{(m+n)}(y_1, .., y_m, z_1, .., z_n)]</math>
| ''s''<sub>n</sub><sup>m</sup>
}}
[[Image:Smn.jpg|right|thumb|460px|příklad použití <math>s_n^m</math> věty]]
:💡 říká, že pokud v naší univerzální funkci, která má <math>m+n</math> sadu argumentů (jedním z nich je číslo programu, který má běžet),
:: <math>m</math> argumentů (+ číslo programu) zafixujeme,
:: dostaneme funkci zbytku (<math>n</math>) těch argumentů,
:: a tato fixovací funkce bude hezká (prostá PRF).
;Dk (program <math>s=s_n^m(x, y_1, \dots, y_m)</math>, na vstupu dostane z-ka a pak pustí TS <math>M_x</math> na vstup y-nek a z-tek):
: Neformálně popíšeme, co bude dělá program <math>s=s_n^m(x, y_1, \dots, y_m)</math>:
: Na vstupu dostane čísla <math>z_1, . . . , z_n</math>, poté spustí stroj <math>M_x</math> na vstup <math>y_1, . . . , y_m, z_1, z_2, . . . , z_n</math>,
: 💡 Všechna tato čísla zná, jelikož je buď dostane na vstupu <math>M_s</math> (v případě <math>z_1, . . . , z_n</math>), nebo je má zakódované do své přechodové funkce jako parametry (v případě <math>x, y_1, \dots, y_m</math>).
: 💡 Pro tuto úpravu není vůbec rozhodující, jak vypadají instrukce <math>M_x</math>, ani to, jak bude probíhat jeho výpočet, jediné, co je v <math>M_x</math> třeba změnit jsou čísla stavů tak, aby nekolidovala s nově přidanými stavy.
:* Úprava přechodové funkce <math>M_x</math> je jednoduchá a vystačí si s PR prostředky '''⇒ <math>s_n^m</math> je PRF.'''
:* Kód nového stroje obsahuje nějakým způsobem i hodnoty parametrů fce <math>s_n^m</math>, pro různé hodnoty těchto parametrů budou i různé výstupní hodnoty '''⇒ <math>s_n^m</math> 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 <math>χ_A(x)</math>''' -- charakteristická fce predikátu náležení do množiny (<math>χ_A(x) = \downarrow 1</math> pro <math>x\in A</math> a <math>χ_A(x) \downarrow = 0</math> pro <math>x\notin A</math>)
<math>χ_A(x_1,\dots,x_n)\simeq \begin{cases}1 \quad & \mbox{ pokud } R(x_1,\dots,x_n) \\ 0 \quad & \mbox{ jinak }\end{cases}\,\!</math>
::💡 '''částečná charakteristická funkce množiny''' -- <math>χ_A(x) = \downarrow 1</math> pro <math> x \in A</math> a <math>χ_A(x)\uparrow</math> pro <math>x \notin A</math>
<math> dom\,\!</math> značí '''definiční obor''', <math> rng\,\!</math> '''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 <math>χ_A(x)</math> 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''' <math>\mathbf{W_e} = dom~ φ_e = \{ x | φ_e(x)↓ \}</math>
: Pomocí <math>\varphi^{(n)}_{e, s}</math>, kde <math>e, n,s\in{\mathbb N}</math> označíme '''konečnou aproximaci''' <math>\varphi_{e, s}^{(n)}</math> funkce <math>\varphi_e^{(n)}</math>, kterou definujeme následujícím způsobem:
::<math>\varphi^{(n)}_{e, s}(x_1, \dots, x_n)\simeq \begin{cases} \varphi^{(n)}_e(x_1, \dots, x_n) \quad & \mbox{pokud }(\exists y<s)[T_n(e, x_1, \dots, x_n, y)]\\ \uparrow\quad & jinak \end{cases}</math>
: '''rekurzivní konečná aproximace ''' <math>\mathbf{W_{e,s}} = dom φ_{e,s} = \{ x | φ_{e,s}(x)↓ \}</math>
{{lemma
| Predikát <math>H</math> definovaný jako <math>H (e, s, x_1, . . , x_n) ⇔ φ_{e,s}(n)(x_1, . . , x_n)↓</math> je PRP a platí, že: <math>φ_e(n) (x_1, . . . , x_n)↓⇔ (∃s)[ φ_{e,s}(n) (x_1, . . , x_n)↓]</math> . (v dk předpokladáme, že <math>T_n</math> 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 :
: <math>A∪B=\{x|[χ_a(x)∨χ_b(x)]\}</math>
: <math>A∩B=\{x|[sign(χ_a(x)+χ_b(x))]\}</math>
: <math>\overline A=\{x|[1\dot{-}χ_a(x)]\}</math>
: 💡 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 <math>f(x, y) = s_1^2(e, x, y)</math>. Podobně můžeme postupovat i v případě průniku a funkce g, stačilo by místo disjunkce použít konjunkci.
{{theorem
| <math>A</math> je RM <math>\Leftrightarrow A</math> i <math>\overline A={\mathbb N}\setminus A</math> 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:'''
* <math>⟨x, y⟩_2</math> je '''kód uspořádané dvojice''' [x, y] daný: <math>⟨x, y⟩_2 = (x + y).(x + y + 1) / 2 + x</math>
* <math>⟨x_1, . ., x_n⟩_n</math> je '''kód uspořádané n-tice''' daný: <math>⟨x_1, . . ., x_n⟩_n = ⟨x_1, ⟨x_2, . . ., x_n⟩_{n-1}⟩_2</math>
* <math>π_{n,i}(⟨x_1, . ., x_n⟩_n) = x_i</math> je '''inverze pro výběr <math>i</math>-tého prvku ze zakódované <math>n</math>-tice'''
* Lemma – Pro každé <math>n ≥ 2, i ≤ n</math> jsou funkce <math>⟨x_1, . . . , x_n⟩_n</math> a <math>π_n</math> PRF, a <math>⟨x_1, . . . , x_n⟩_n</math> je bijekcí mezi <math>N^{n+1}</math> a <math>N</math> ( důkaz pro πn předpokládá, že omezená minimalizace a kvantifikace jsou PRF ).
{{theorem
| Predikát <math>R ⊆ N^n</math> je RSP ⇔ ∃ PRP <math>P ⊆ N^{n+1}</math> , že: <math>R(x_1, . . , x_n) ⇔ (∃y)[P (x_1, . . , x_n, y)]</math>.
| důsledek Kleeneho věty
}}
{{theorem
| <math>P(x_1, \dots, x_n, y)</math> je RSP ⇒ <math>R(x_1, \dots, x_n)=(\exists y)\;[P(x_1, \dots, x_n, y)]</math> je RSP
| RSP jsou uzavřeny na <u>∃ kvantifikátor</u>
}}
;Dk:
: Protože <math>P(x, y)</math> je RSP, můžeme jej zapsat podle důsledku Kleeneho jako <math>P(x, y) = (∃z) [Q(x, y, z)]</math>, kde <math>Q</math> je PRP. Z toho plyne, že <math>R(x) = (∃y)(∃z) [Q(x, y, z)]= (∃⟨y, z⟩_2) [Q(x, y, z)]</math>.
: Označíme-li si <math>D(x, u) = Q(x, π_{2,1}(u), π_{2,2}(u))</math>, pak <math>D</math> je PRP, pro který platí, že <math>R(x) = (∃u) D(x, u)</math>.
: ⇒ podle důsledku Kleeneho: <math>R(x)</math> je RSP.
{{theorem
| <math>R(x, y)</math> je RSP ⇒ <math>\exists</math> ČRF <math>f</math> (také '''výběrová funkce''' nebo selektor pro <math>R</math>), že <math>f(x)\downarrow\Leftrightarrow(\exists y)R(x, y)</math> a pokud <math>f(x)\downarrow</math>, pak <math>R(x, f(x))</math>.
| výběrová funkce
}}
;Dk:
: Podle důsledku Kleeneho můžeme <math>R</math> zapsat jako <math>R(x, y) = (∃z)[Q(x, y, z)]</math> pro nějaký PRP <math>Q</math>. A tedy <math>(∃y)R(x, y) ⇔ (∃y)(∃z)Q(x, y, z)</math>. Protože predikát <math>Q</math> je PRP(totální), dostaneme, že funkce <math>g(x) ≃ μ⟨y, z⟩_2 Q(x, y, z)</math>.
: Nyní z nalezené hodnoty stačí vybrat <math>y</math>, tedy 1. prvek, celkově tedy definujeme funkci <math>f</math> jako <math>f(x) ≃ π_{2,1}(g(x))</math>.
=== 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 množiny přirozených čísel ((∀x)(∀y) [ f(x)↓ ∧ (y < x) ⇒ f(y)↓ ])
{{theorem
| A je RM <math>\Leftrightarrow</math> je oborem hodnot nějaké rostoucí úsekové ČRF (tj. existuje rostoucí úseková ČRF f, pro níž platí <math>A=rng~ f</math>).
| <math>RM = rng</math> rostoucí úsekové ČRF
}}
;Dk:
<math> \Rightarrow\,\!</math>: Definujeme ČRF <math> f\,\!</math>, která bude rostoucí a úseková.
* Začneme <math> f(0) \simeq \mu_x(x\in M)\,\!</math>.
* Dále <math> f(n+1) \simeq \mu_y(y > f(n) \wedge y \in M)\,\!</math>
<math> \Leftarrow\,\!</math>: Máme <math> f\,\!</math> rostoucí úsekovou ČRF.
# V případě, že je <math> f\,\!</math> má konečné <math> dom\,\!</math> (tohle ale nejsme schopni efektivně rozpoznat!), víme jak, známe <math> D=dom(f)\,\!</math> a tedy <math> rng(f)\,\!</math> je rekurzivní.
# V případě, že je <math> f\,\!</math> je všude definovaná (totální): <math> y \in M=rng(f) \Leftrightarrow \exists x:(f(x)=y)) \Leftrightarrow \exists x\!\leq\!y: (f(x)=y) </math> Poslední ekvivalence platí, protože <math> f\,\!</math> je rostoucí a úseková. Tedy <math> y \in M \Leftrightarrow y \in \{f(0),\ldots,f(y)\}. </math>
{{TODO|důkaz}}
: → :Předpokládejme nejprve, že A je rekurzivní množina. To znamená, že její charakteristická funkce χA(x) je obecně rekurzivní. Popíšeme funkci f(i), která pro dané i vrátí i-tý nejmenší prvek množiny A (počítáme od 0, tj. první prvek je vrácen pro i = 0). Je-li A konečná množina, není pro i ≥ |A| hodnota f(i) definována. Takto popsaná funkce bude rostoucí i úseková. Intuitivní algoritmus, který bude počítat funkci f(i) je jednoduchý: Najdi nejmenší prvek množiny A a poté i-krát hledej nejmenší větší prvek. První cyklus while najde index nejmenšího (tedy 0-tého) prvku, který do množiny A patří. Poté algoritmus i-krát opakuje hledání následujícího prvku. Hledání následujícího prvku je obsaženo v druhém cyklu while. První inicializační cyklus si definujeme jako ČRF h(v) = μy[χA(y) ≃ 1], všimněte si, že tato funkce na svém parametru vůbec nezávisí, vždy najde nejmenší prvek množiny A. Funkci uvnitř cyklu for si definujeme jako ČRF g(i, u, v) = μz[(z > u) ∧ χA(z) ≃ 1]. Funkce g dostává jako druhou hodnotu hodnotu z rekurze, tedy aktuální hodnotu naposledy nalezeného prvku, následně hledá nejmenší prvek množiny A, který je větší než tento poslední nalezený prvek uložený v z. Pomocí primitivní rekurze odvodíme funkci f = R2(h, g) a poté stačí položit f(i) ≃ f (i, i) (připomeňme si, že primitivní rekurze odvodí funkci alespoň dvou proměnných, proto funkci f odvodíme takovouto oklikou).
: ← : Nyní předpokládejme, že A = rng f, kde f je rostoucí úseková ČRF. Pokud f není ORF, znamená to podle definice úsekové funkce, že doména f je konečná, a tedy je konečná i samotná množina A a je tedy triviálně rekurzivní. Předpokládejme tedy, že f je obecně rekurzivní, tedy všude definovaná funkce, pro kterou platí, že f(i) vrátí i-tý nejmenší prvek množiny A. Charakteristickou funkci můžeme nyní spočítat jednoduchým způsobem. Množina A je nekonečná, a proto musí obsahovat prvek, který je větší nebo roven x, ve skutečnosti platí, že i-tý prvek musí být větší nebo roven i, jinými slovy platí, že i ≤ f(i). Proto ve skutečnosti stačí hledat i ≤ x a mohli bychom se tedy obejít bez obecného cyklu while a nahradit jej cyklem for, toho využijeme při odvození funkce χA. Definujme funkci g(x) = μi ≤ x[f(i) ≥ x]. Nyní platí, že x ∈ A, právě když x = f(g(x)), přičemž rovnost je primitivně rekurzivní predikát, a proto je charakteristická funkce χA obecně rekurzivní. Pokud je f dokonce primitivně rekurzivní funkce, dostaneme, že i χA je primitivně rekurzivní funkce, neboť omezená minimalizace použitá v odvození funkce g je primitivně rekurzivní. V každém případě je-li f ORF, je ORF i χA a A je tedy rekurzivní množina.
• Důsledek: Nechť A je nekonečná množina, pak A je rekurzivní, právě když je oborem hodnot nějaké rostoucí ORF { protože úsekové funkce s nekonečnou doménou musí být totální }.
: 💡 '''Důsledek:''' Nechť A je nekonečná množina, pak A je RM ⇔ je oborem hodnot nějaké rostoucí ORF. (protože úsekové funkce s nekonečnou doménou musí být 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
| Nechť A je množina, potom jsou následující tvrzení ekvivalentní:
# Množina A je rekurzivně spočetná.
# A je prázdná, nebo je oborem hodnot nějaké ORF, tj. <math>\exists</math>ORF g, pro niz <math>A = rng~g=\{x|(\exists y)[g(y)=x]\}</math>
# A je oborem hodnot nějaké ČRF.
# A je oborem hodnot nějaké rostoucí ČRF.
| Generování RSM
}}
;Dk:
1=>3
:Pro každou množinu <math>W_x</math> vytvoříme množinu dvojic <math> R=\{\langle y,y\rangle:y \in W_x\}\,\!</math>. Množina <math> R\,\!</math> je rekurzivně spočetná, tedy má ČRF selektor <math> \varphi\,\!</math>, :platí <math> dom(\varphi)=rng(\varphi)=W_x\,\!</math>.
:Myšlenka toho důkazu je, že body, kde <math> \varphi_x\,\!</math> konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.
1<=3
:Máme ČRF <math> g\,\!</math> a její obor hodnot. Zkonstruujeme pseudoinverzní funkci <math> h\,\!</math> k ČRF <math> g\,\!</math>, tj. funkci takovou, že <math> dom(h)=rng(g)\,\!</math> a to tak, že vyrobíme RS :predikát <math> Q(x,y)\Leftrightarrow g(x)\simeq y\,\!</math> a to má ČRF selektor, který hledáme -- <math> h\,\!</math>.
{{TODO|důkaz}}
: Důkaz { 1. → 2. } : Předpokládejme, že A je neprázdná rekurzivně spočetná množina, jejíž Göde- lovo číslo si označíme pomocí e, tedy A = We = dom φe. Naším cílem je zkonstruovat obecně
rekurzivní funkci g tak, aby platilo A = rng g. Náš postup navíc ukáže, jak z Gödelova čísla e určit Gödelovo číslo funkce g. Rozeberme si nejprve, proč nemůžeme postupovat stejně jako v případě rekurzivních množin. Už postup, kterým jsme u rekurzivní množiny hledali nejmenší prvek, v případě rekurzivně spočetné množiny selže. Pokud by totiž 0 nepatřila do A, tak se cyklus while, v němž bychom nejmenší prvek hledali, zarazí už při výpočtu φe(0), neboť tato hodnota není definovaná. Podobně nemůžeme hledat nejmenší prvek větší než zadaný parametr. Musíme proto postupovat opatrněji. Za pvé, nemůžeme sice přímo najít nejmenší prvek, ale můžeme najít nějaký prvek množiny A = We, a to například následující funkcí: a(e) = π2,1(μ⟨x, s⟩2[x ∈ We,s]). Jedná se při tom o selektor rekurzivně spočetného predikátu (∃y)[y ∈ We] protože tento predikát je splněn díky neprázdnosti We, bude pro dané e hodnota a(e) definovaná. Takto nalezený prvek použijeme jako jakéhosi žolíka, kterého vrátí konstruovaná funkce g ve chvíli, kdy si neví jinak rady. Sestrojíme nejprve funkci φe1(2)(e, z), která si vyloží parametr z jako dvojici z = ⟨x, s⟩2, ověří, zda x ∈ We,s a pokud ano, vrátí hodnotu x, v opačném případě vrátí žolíka a(e), tedy:
φe1(2)(e, z = ⟨x, s⟩2) ≃ IF (x ∈ We) THEN x ELSE a(e). Protože We,s je rekurzivní množina, a hodnota a(e) je pro dané e vždy definovaná vzhledem k neprázdnosti We, bude hodnota φe1(2)(e, z) definovaná pro každé z. Všimněme si, že definice funkce φe1(2) nezávisí na hodnotě e, ta je jí předána jako parametr. Nyní už odvodíme g(z) ≃ φe1 (e, z), a tedy podle s-m-n věty platí:
g(z) ≃ φs-1-1 (e1,e)(z) ≃ φe1(2)(e, z). Takto jsme tedy spočítali i Gödelovo číslo funkce g z e. Zřejmě platí, že g(z) ∈ We pro každé z, uvažme naopak, že pro každý prvek b ∈ We existuje s, pro něž b ∈ We,s, a tedy g(⟨b, s⟩2) = b. Každý prvek We 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 = We = rng g.
: Důkaz { 2. → 3. } : Plyne z toho, že každá ORF je i ČRF. Prázdná množina je oborem hodnot ČRF, která není definovaná pro žádný vstup.
: Důkaz { 3. → 1. } : : Předpokládejme, že A je oborem hodnot částečně rekurzivní funkce g ≃ φe. Uvědomme si, že rozhodnutí, zda g(y)↓= x je rekurzivně spočetný predikát (plyne například z toho, že φe,s(y)↓ = x je primitivně rekurzivní predikát a tedy g(y)↓ = x ⇔ (∃s)[φe,s(y)↓= x] je rekurzivně spočetný predikát, dále je tedy i (∃y)[g(y)↓ = x] rekurzivně spočetný predikát, a tedy
množina A = {x | (∃y)[g(y)↓ = x]} je rekurzivně spočetná. Ze znalosti Gödelova čísla e funkce g bychom opět s pomocí s-m-n věty mohli spočítat Gödelovo číslo funkce, jejíž doménou množina A je. Pro úplnost totiž můžeme past A = dom λx [ μ⟨y, s⟩2[φe,s(y)↓= x] ].
: Důkaz { 1. → 4. } : Předpokládejme, že A = We, tedy A = dom φe. Buď g(e, x) funkce definovaná jako: g(e, x) = IF (x ∈ We) THEN x ELSE ↑. 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ödelovo číslo lze opět efektivně spočítat z e.
: Důkaz { 4. → 3. } : Toto je zřejmé. Implikaci { 3. → 1. } už máme hotovou.
: Poznámka : Bod { 2. } věty naznačuje, odkud rekurzivně spočetné množiny (recursively enumerable sets) dostaly své jméno. Je-li A rekurzivně spočetná množina, nejsme sice obecně schopni algoritmicky rozhodnout, zda x ∈ A, ale jsme schopni efektivně vypsat (enumerate) všechny prvky A. O funkci g z tvrzení { 2. } budeme též říkat, že generuje množinu A. Na rozdíl od rekurzivních množin však nejsme schopni vypsat prvky rekurzivně spočetné množiny systematicky, tedy v rostoucím pořadí, a nepodaří se nám ani vyhnout tomu, abychom při výpisu nějaký prvek zopakovali. Funkci, která by byla rostoucí a jejímž oborem hodnot je množina A, sice můžeme zkonstruovat, ale musíme v tom případě rezignovat na obecně rekurzivní funkce a na to, aby daná funkce byla všude definovaná, jak ukazuje bod (iv). Taková funkce přitom není pro generování množiny A použitelná.
==≤<sub>1</sub>, ≤<sub>m</sub> a jejich vlastnosti, ''K'' a ''K<sub>0</sub>'' 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í.''
<math>A\leq_m B</math> (množina <math>A</math> je '''<math>m</math>-převoditelná''' na <math>B</math>) pokud ∃ ORF <math>f</math>, tž: <math>∀ x: x ∈ A ⇔ f(x) ∈ B</math>
<math>A\leq_1 B</math> (množina <math>A</math> je '''<math>1</math>-převoditelná''' na <math>B</math>) je-li <math>f</math> navíc prostá
množina <math>A</math> je '''<math>m</math>-úplná''' (resp. '''<math>1</math>-úplná''') pro třídu RSM pokud: je <math>A</math> RSM a ∀ jiná RSM je na ni <math>m</math>-převoditelná (resp. <math>1</math>-převoditelná).
: 💡 budeme říkat pouze <math>A</math> je ''<math>m</math>-úplná'' nebo ''<math>1</math>-úplná'', dodatek „pro třídu RSM“ budeme vynechávat, protože jinými než RM a RSM se nebudeme zabývat.
===9.1 vlastnosti ≤<sub>1</sub>, ≤<sub>m</sub>===
* <math>A\leq_m B</math> a <math>B</math> RM <math>\Rightarrow A</math> RM
:: 💡 <math>A\leq_m B</math> a <math>A</math> není RM <math>\Rightarrow B</math> není RM (protože: <math>(A\Rightarrow B)=(\neg B\Rightarrow \neg A)</math>)
:: '''Dk:''' Je-li <math>B</math> RM a <math>f</math> je ORF převádějící <math>A</math> na <math>B</math>, pak <math>x ∈ A ⇔ f(x) ∈ B</math> a tedy <math>χ_A(x) = χ_B(f(x))</math>. <math>χ_A</math> je jistě ORF a tedy <math>A</math> je RM.
* <math>A\leq_m B</math> a <math>B</math> RSM <math>\Rightarrow A</math> RSM
:: 💡 <math>A\leq_m B</math> a <math>A</math> není RSM <math>\Rightarrow B</math> není RSM
:: '''Dk:''' Je-li <math>B</math> RSM a platí-li <math>B = dom φ_e</math> a je-li <math>f</math> ORF, která převádí <math>A</math> na <math>B</math>, pak <math>A = dom λx[φe(f(x))]</math> a jde tedy o RSM.
* <math>\leq_m</math> a <math>\leq_1</math> (relace) jsou reflexivní a tranzitivní
:: '''Dk:''' To, že jsou <math>≤_m</math> a <math>≤_1</math> reflexivní relace plyne z toho, že identita je prostá ORF. Předpokládejme, že <math>A ≤_1 B</math> a <math>B ≤_1 C</math>, nechť <math>f</math> je prostá ORF převádějící <math>A</math> na <math>B</math> a <math>g</math> buď prostá ORF převádějící <math>B</math> na <math>C</math>. Pak <math>h(x) = g(f(x))</math> je prostá ORF která převádí <math>A</math> na <math>C</math>, což ukazuje, že <math>≤_1</math> je tranzitivní. Pro <math>≤_m</math> platí týž argument s vynecháním prostoty.
* <math>A</math> <math>m</math>-úplná & <math>B</math> RSM & <math>A\leq_m B \Rightarrow B</math> je <math>m</math>-úplná
:: 💡 platí pro 1-převoditelnost a 1-úplnost
:: '''Dk:''' Toto plyne okamžitě z tranzitivity <math>≤_m</math>, <math>≤_1</math> a definice úplnosti.
* <math>A\leq_mB \Rightarrow \overline A\leq_m\overline B</math>
:: 💡 platí pro 1-převoditelnost a 1-úplnost
:: '''Dk:''' Plyne přímo z definice převoditelnosti, převod <math>A</math> na <math>B</math> zajistí stejná funkce jako převod <math>A</math> na <math>B</math>.
===Problém zastavení K<sub>0</sub> a jeho diagonála K ===
: <math>K_0 =\{\langle x, y\rangle_2\;|\;\varphi_x(y)\downarrow\}=\{\langle x, y\rangle_2\;|\;y\in W_x\} </math>
: <math>K =\{x\;|\;\varphi_x(x)\downarrow\}=\{x\;|\;x\in W_x\}</math>
💡 <math>K_1 =\{x\;|\;W_x\neq\emptyset\} </math>
{{theorem
| <math>K</math> a <math>K_0</math> jsou RSM, ale nejsou RM
| <math>K</math>, <math>K_0</math> RSM <math>\neg</math>RM
}}
; Dk (sporem jako u TS)
: Z definice jsou obě RSM. Nechť <math>φ_z</math> označuje univerzální ČRF.
: <math>K = dom λx[φ_z(x, x)]</math>. Pro spor <math>K</math> je RM ⇒ <math>\overline K</math> je RSM.
:: Nechť <math>φ_e</math> je ČRF, pro níž <math>\overline K = dom φ_e</math> a ptejme se, zda <math>e ∈ \overline K</math> nebo ne:
:: Z def. <math>K</math> ⇒ <math>e ∈ \overline K ⇔ φ_e(e)↑</math>
:: <math>\overline K = dom φ_e</math> ⇒ <math>e ∈ \overline K ⇔ φ_e(e)↓</math>
:: ⇒ <math>φ_e(e)↓ ⇔ φ_e(e)↑</math> ⇒ '''SPOR''' ⇒ <math>K</math> tedy není RM.
: <math>K_0 = dom λ⟨x, y⟩_2[φ_z(x, y)]</math>. Pro spor <math>K_0</math> je RM a <math>χ_{K0}</math> je její char. ORF:
:: Definujeme <math>χ_{K}(x) = χ_{K_0}(⟨x, x⟩_2)</math> ⇒ <math>χ_K</math> char. ORF <math>K</math> ⇒ '''SPOR''' s tím že <math>K</math> není RM. ⇒ <math>K_0</math> tedy není RM.
{{theorem
| Množiny <math>K</math> a <math>K_0</math> jsou 1-úplné.
| 1-úplnost <math>K</math>, <math>K_0</math>
}}
; Dk:
: <math>K</math> je <math>1</math>-úplná: <math>K</math> je RSM, stačí tedy ukázat, že libovolnou RSM lze na <math>K</math> převést prostou ORF.
:: Definujme funkci <math>φ_{e1}(e, x, y) ≃ φ_e(x)</math>. Podle s-m-n věty <math>φ_{s^2_1(e1,e,x)} (y) ≃ φ_e (e, x, y) ≃ φ_e(x)</math>. Definujme tedy funkci <math>f(e, x) = s_1^2(e_1, e, x)</math>. Protože <math>s_1^2</math> je prostá PRF, je i <math>f</math> prostá PRF. Navíc platí, že <math>φ_{f(e,x)}</math> je buď všude definovaná konstantní funkce, pokud <math>x ∈ W_e</math>, nebo jde o funkci, která není definovaná pro žádný vstup v případě, že <math>x \notin W_e</math>, platí tedy, že:
::: <math>x ∈ W_e ⇒ φ_e(x)↓ ⇒ (∀y)[φ_{e1} (e, x, y)↓] ⇒ φ_{f(e,x)}(f(e, x))↓ ⇒ f(e, x) ∈ K</math>
::: <math>x\notin W_e ⇒ φ_e(x)↑ ⇒ (∀y)[φ_{e1} (e, x, y)↑] ⇒ φ_{f(e,x)}(f(e, x))↑ ⇒ f(e, x) \notin K</math>
:: Dohromady dostaneme požadovanou ekvivalenci <math>x ∈ W_e ⇔ f(e, x) ∈ K</math>, a z toho plyne, že funkce <math>g(x)</math> definovaná jako <math>g(x) ≃ f(e, x)</math>, je prostá ORF, která převádí množinu <math>W_e</math> na <math>K</math>. Protože <math>W_e</math> byla libovolná množina, dostáváme, že <math>(∀e)[W_e ≤_1 K]</math>, a <math>K</math> je tedy <math>1</math>-úplná množina.
: <math>K_0</math> je RSM (podle vlastností převoditelnosti). Ve větě nahoru jsme ukázali i to, že <math>K ≤_1 K_0</math> pomocí prosté ORF <math>h(x) = ⟨x, x⟩_2</math>. Těžkost množiny <math>K_0</math> tedy plyne z tranzitivity <math>1</math>-převoditelnosti.
==Riceova v. - dk převoditelnost==
''Riceova věta - důkaz pomocí převoditelnosti.''
{{theorem
| <math>\cal C</math> třída ČRF, <math>A_\cal C = \{e | \varphi_e ∈ C\}</math> je RM ⇔ <math>\cal C = \emptyset</math> nebo <math>\cal C</math> obsahuje všechny ČRF
| Rice
}}
💡 <math>A_\cal C</math> je mnozina indexu (Gödel.č.) funkci z třídy <math>\cal C</math>
;Dk (pomocí převoditelnosti):
: předpokládejme že <math>\cal C</math> NEní ∅ a <math>\cal C</math> NEobsahuje všechny ČRF
: ukážeme sporem že <math>K ≤_1 A_\cal C</math>
: <math>e_0</math> je GČ fce nedefinové pro žádný vstup a <math>φ_{e0} ∈ \overline{\cal C}</math>
: <math>e_1</math> je GČ fce <math>φ_{e1}∈C</math> a <math>φ_{e0}≄ φ_{e1}</math>
: <math>\varphi_{e_2}(x, y)\simeq\cases{ \varphi_{e_1}(y)&je-li $x\in K$\cr \uparrow }</math>
:: <math>φ_{e2}(x , y) ≃ φ_{s^1_1}(e, x) (y) ≃ φ_{f(x)}(y)</math>
: <math>x∈K ⇒ φ_{f(x)}≃φ_{e1} ⇒ φ_{f(x)}(y) ∈ C ⇒ f(x) ∈ A_\cal C</math>
: <math>x∉K ⇒ φ_{f(x)}≃φ_{e0} ⇒ φ_{f(x)}(y) ∉ C ⇒ f(x)∉ A_\cal C</math>
:: tedy <math>x ∈ K ⇔ f(x) ∈ Ac</math>
==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 <math>Wx=\{x\}</math> 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 <math>f</math> ∃ <math>n</math>: <math>φ_n ≃ φ_{f(n)}</math>
| 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ť <math>e_1</math> je číslem funkce, pro kterou platí <math>\varphi_{e_1}^{(2)}(e, x)\simeq\varphi_{f(\varphi_e(e))}(x),</math> tuto funkci bychom snadno odvodili pomocí univerzální ČRF.
: Nechť <math>b</math> je Gödelovým číslem funkce <math>s_1^1(e_1, e)</math>, podle s-m-n věty tedy platí, že <math>\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).</math>
: Protože <math>\varphi_b</math> je PRF (podle s-m-n), je <math>\varphi_b(b)\downarrow</math> a platí, že <math>\varphi_{\varphi_b(b)}\simeq\varphi_{f(\varphi_b(b))},</math> <math>\varphi_b(b)</math> je tedy hledaným pevným bodem <math>f</math>.
{{TODO|doplnit poznámky}}
===Důsledky VoR===
{{theorem
| ∃ prostá PRF <math>g</math>, která ke GČ funkce <math>f</math> určí její pevný bod
| 💡
}}
{{theorem
| ∀ ORF <math>f</math> má ∞ pevných bodů
| 💡
}}
{{theorem
| ∃ <math>n ∈ N</math>, pro nějž:
# <math>W_n = \{n\}</math>
# <math>φ_n ≃ λx[n]</math>
| 💡
}}
; Dk:
# Nechť <math>e</math> je Gödelovo číslo funkce definované jako <math>φ_e^{(2)}(x, y) ≃ μz[x = y]</math> (💡 tedy <math>φ_e^{(2)}(x, y)↓</math> ⇔ <math>x = y</math>). Použijeme s-m-n větu a definujeme-li <math>f(x) ≃ s_1^1(e, x)</math>, dostaneme, že <math>φ_{f(x)} ≃ φ_{s-1-1(e,x)} ≃ φ_e(x, y)</math> a tedy <math>W_{f(x)} = \{x\}</math>. Funkce <math>f</math> je ORF (podle s-m-n), a tak podle VoR: <math>∃ n: φ_n ≃ φ_{f(n)}</math>, a tak <math>W_n = W_{f(n)} = \{n\}</math>.
# Podobně, nechť <math>e</math> je GČ funkce definované jako <math>φ_e^{(2)}(x, y) ≃ x</math>. Pomocí s-m-n věty definujeme-li <math>f(x) = s_1^1(e, x)</math>, dostaneme <math>φ_{f(x)}(y) ≃ x</math> a s použitím VoR nalezneme <math>n</math>, pro něž je <math>φ_n(y) ≃ φ_{f(n)}(y) ≃ n</math>.
{{theorem
| <math>f(x,y)</math> je ORF <math>⇒ ∃</math> prostá ORF <math>n(y)</math> taková, že <math>φ_{n(y)} ≃ φ_{f(n(y),y)} ∀y ∈ N</math>
| VoR s parametry
}}
==Riceova v. - dk s VoR (🎓)==
{{theorem
| <math>\cal C</math> třída ČRF, <math>A_\cal C = \{e | \varphi_e ∈ C\}</math> je RM ⇔ <math>\cal C = \emptyset</math> nebo <math>\cal C</math> obsahuje všechny ČRF
| Rice
}}
;Dk (sporem)
: předpokládejme že <math>\cal C</math> NEní ∅ a <math>\cal C</math> NEobsahuje všechny ČRF
: předpokládejme sporem že <math>A_\cal C</math> je rekurzivní
: definujme si fci <math>f</math>:
:: <math>f(x) = a ~~ x∉ A_\cal C</math>
:: <math>f(x) = b ~~ x∈ A_\cal C</math>
::: <math>f</math> je ORF
::: <math>a∈A_\cal C</math>
::: <math>b∉ A_\cal C</math>
: <math>n</math> je pevný bod <math>f</math> a <math>φ_n≃ φ_{f(n)}</math>
: <math>φ_n∈\cal C ⇒ n ∈ A_\cal C ⇒ f(n)=b ⇒ f(n)∉ A_\cal C ⇒ φ_{f(n)} ∉ \cal C</math>
: <math>φ_n∉\cal C ⇒ n ∈ A_\cal C ⇒ f(n)=a ⇒ f(n)∈ A_\cal C ⇒ φ_{f(n)}∈ \cal C</math>
: ⇒ '''spor'''
=Složitost =
''(Complexity)''
==Def. základních tříd složitosti. Definice třídy NP pomocí cert. a NTS a jejich ekvivalence. ≤<sup>p</sup><sub>m</sub>, 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 <math>L\subseteq\{0, 1\}^*</math>)
** 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 <math>R\subseteq\{0, 1\}^*\times\{0, 1\}^*</math>)
; třídy jazyků a relací (tj. problémů a úloh):
: 💡 <math>f:\mathbf N\mapsto\mathbf N</math> libovolná fce
* <math>DTIME(f(n))</math>, jazyk <math>L(M) ∈ DTIME(f(n)) ⇐</math> ∃ TS <math>M</math> co pracuje v čase <math>O(f(n))</math>.
* <math>DSPACE(f(n))</math>, jazyk <math>L(M) ∈ DSPACE(f(n)) ⇐</math> ∃ TS <math>M</math> co pracuje v prostoru <math>O(f(n))</math>.
* <math>DTIMEF(f(n))</math>, relace <math>R ∈ DTIMEF(f(n)) ⇐</math> ∃ TS <math>M</math> co pracuje v čase <math>O(f(n))</math>, <math>M(x)</math> přijme ⇔ ∃ slovo <math>y</math>: <math>(x, y)\in R</math> a na konci páska obsahuje <math>y</math>
:: 💡 Lze to také říci tak, že selektor pro predikát R je funkce spočitatelná v polynomiálním čase.
=== Definice třídy NP===
'''Třídy polynomiálních jazyků, relací:'''
* <math> P= \bigcup_{i\in \mathbb N}DTIME(n^i)</math> - problémy rozhodnutelné v polynomiálním čase
* <math> PSPACE=\bigcup_{i\in\mathbb N}DSPACE(n^i)</math> - problémy rozhodnutelné v polynomiálním prostoru
* <math> PF=\bigcup_{i\in\mathbb N}DTIMEF(n^i) </math> - úlohy řešitelné v polynomiálním čase
'''Třída polynomiálně ověřitelných úloh''' <math>NPF</math> (<math>NP</math> - nedeterministicky polynomiální, <math>F</math> - funkce, ''úlohy řešitelné nedeterministickým Turingovým strojem v polynomiálním čase'')
* Relace <math>R ∈ NPF</math> ⇐ ∃ polynom <math>p(n)</math>: že <math>∀ (x, y)\in R</math> je <math>|y|\leq p(|x|)</math> a ověření zda <math>(x, y)\in R</math> lze v polynomiálním čase.
'''Třída polynomiálně ověřitelných problémů''' <math>NP</math> (nedeterministicky polynomiální)
* def. pomocí '''certifikátů''': Jazyk <math>L ∈ \mathrm NP</math> ⇐ ∃ polynom <math>p</math> a jazyk <math>B\in P</math> a pokud <math>∀ x\in\{0, 1\}^*</math> platí: <math>x\in L\Leftrightarrow (\exists y)\;\Big[|y|\leq p(|x|)\mbox{ a }(x, y)\in B\Big].</math>
:: 💡 <math>L ∈ \mathrm NP</math> ⇐ ∃ polynomiální algoritmus (daný jazykem <math>B</math>), že polynomiálně dlouhý certifikát <math>y</math> dosvědčuje fakt <math>x\in L</math>. Je opět nutné uvažovat pouze polynomiálně dlouhé certifikáty, neboť složitost ověřování se měří vzhledem k délce <math>x</math> i certifikátu <math>y</math>.
:: 💡 obecně platí P ⊆ NP, protože pokud umíme problém řešit polyn. nepotřebujeme certifikát
* def. pomocí '''NTS''':
::💡 '''NTS''' <math>M=(Q, \Sigma, \delta, q_0, F)</math>, kde <math>\delta:Q\times\Sigma\mapsto\cal P(Q\times\Sigma\times\{R, N, L\})</math>.
::; třídy jazyků a relací (tj. problémů a úloh):
::: 💡 <math>f:\mathbf N\mapsto\mathbf N</math> libovolná fce
::: <math>NTIME(f(n))</math>, jazyk <math>L(M) ∈ NTIME(f(n)) ⇐</math> ∃ NTS <math>M</math> co pracuje v čase <math>O(f(n))</math>.
::: <math>NSPACE(f(n))</math>, jazyk <math>L(M) ∈ NSPACE(f(n)) ⇐</math> ∃ NTS <math>M</math> co pracuje v prostoru <math>O(f(n))</math>.
{{theorem
| <math>NP=\bigcup_{i\in\mathbb N} NTIME(n^i)</math>
| 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.===
[[Image:Redukce.jpg|right|thumb|331px|Ilustrace polynomiální redukce z jazyka <math>L_1</math> na jazyk <math>L_2</math> pomocí redukční fce <math>f</math>. Pro vstup <math>x∈\{0,1\}^*</math> má otázka zda <math>x∈L_1</math> stejnou odpověď jako otázka zda <math>x∈L_2</math>.]]
[[Image:800px-P np np-complete np-hard.svg.jpg|right|thumb|500px|Eulerův diagram pro P, NP, NPC a NP-těžké množiny problémů. Levá strana platí pro <math>P≠NP</math>, a pravá pro <math>P=NP</math> (až na prázdný jazyk a jeho doplněk nejsou nikdy NPC)]]
<math>A\leq_m^pB</math> (jazyk <math>A</math> '''polynomiálně převoditelný''' na <math>B</math>) pokud '''∃''' f: {0,1}*→{0, 1}* spočitatelná v polynomiálním čase a platí: <math>x ∈A ⇔f(x) ∈B</math>
'''vlastnosti:'''
* <math>\leq_m^p</math> 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.
* <math>A\leq_m^pB</math> a <math>B\in P</math> ⇒ <math>A\in P</math>
:: '''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.
* <math>A\leq_m^pB</math> a <math>B\in NP</math> ⇒ <math>A\in NP</math>
:: '''Dk:''' Platí z téhož důvodu jako { 2. }, protože tytéž argumenty lze použít i pro NTS.
Jazyk <math>A</math> je '''NP-těžký''' (NP-hard) ⇐ ∀ jazyk <math>B\in NP</math>: <math>B\leq_m^pA</math>.
Jazyk <math>A</math> je '''NP-úplný''' (NP-Complete, NPC) ⇐ je ''NP-těžký'' a <math>NP</math>.
: 💡 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, <math>A\leq_m^pB</math> je NP-úplný ⇒ B je NP-úplný
|
}}
; Dk:
: Tvrzení plyne přímo z tranzitivity relace <math>≤_m^p</math> 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 1t 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
}}
== 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 <math>NTS = DTS</math>, 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 <math>I \in L</math> (zda řetězec <math>I</math> patří do jazyka <math>L</math>, neboli zda jeho nedeterministický turingáč přijme daný vstup <math>I</math>) v polynomiálním čase polynomu <math>P</math>
** Zkonstruujeme síť <math>P\times P</math>, zkonstruujeme vhodné kachličky (7 druhů) a obarvení (barvy jsou z množiny <math>ABECEDA \cup (STAVY \times ABECEDA) \cup \lbrace q_l, q_r | q \in STAVY \rbrace </math> 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 <math>KACHL ∈ NP</math>. To plyne z toho, že dostaneme-li vykachlíkování sítě <math>S</math>, 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ť <math>A ⊆ \{0, 1\} ^*</math> je libovolný problém, který patří do NP, ukážeme, že <math>A ≤_m^p KACHL</math>. Podle definice NP-úplného problému to bude znamenat, že <math>KACHL</math> je NP-těžký, a protože patří do NP,
tak i NP-úplný problém. To, že <math>A ∈ NP</math> znamená, že existuje NTS <math>M</math>, který přijímá <math>A</math> (tj. <math>A = L(M)</math>), a počet kroků každého přijímajícího výpočtu je omezen polynomem <math>p(n)</math>, bez újmy na obecnosti můžeme předpokládat, že <math>p(n) ≥ n</math>, v opačném případě by M nepřečetl ani celý svůj vstup a pokud by platilo, že <math>p(n) ≤ n</math>, stačí vzít <math>max(p(n), n)</math> místo <math>p(n)</math>. Připomeňme si, že podle definice <math>x ∈ A</math>, právě když existuje přijímající výpočet NTS M nad vstupem x, který má délku nejvýš <math>p(|x|)</math>. Nechť <math>M = (Q, Σ, δ, q_0, F )</math>, kde <math>Q</math> obsahuje stavy <math>q_0</math> a <math>q_1</math> a <math>\{0, 1, λ\} ⊆ Σ</math>. Abychom si zjednodušili situaci, budeme předpokládat, že <math>M</math> splňuje následující předpoklady:
# <math>F = \{q_1\}</math>, tj. <math>M</math> má jediný přijímající stav <math>q_1</math> různý od <math>q_0</math>.
# Pro každé <math>a ∈ Σ</math> je <math>δ(q_1, a) = ∅</math>, tj. z přijímajícího stavu neexistuje definovaný přechod.
# V počáteční konfiguraci hlava stojí na nejlevějším symbolu vstupního slova <math>x</math>, které je zapsáno počínaje od levého okraje vymezeného prostoru délky <math>p(|x|)</math>. Zbytek pásky je prázdný.
# Během výpočtu se hlava <math>M</math> nepohne nalevo od místa, kde byla v počáteční konfiguraci.
# 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 <math>M</math> 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 <math>M_1</math> lze zkonstruovat NTS <math>M_2</math>, který přijímá týž jazyk jako <math>M_1</math>, „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 <math>M</math> splňuje uvedené podmínky. Nechť <math>x</math> je instance problému <math>A</math>, popíšeme, jak z <math>M</math>, polynomu <math>p</math> a instance <math>x</math> 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 <math>M(x)</math>, tj. <math>M(x)</math> přijme. Idea důkazu je taková, že hrany barev mezi dvěma řádky kachlíků budou kódovat konfigurace výpočtu NTS <math>M</math> nad vstupem <math>x</math>. 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 <math>B = Σ ∪ (Q × Σ) ∪ \{q_L, q_R | q ∈ Q\}</math>. Zatímco vstupní abecedou stroje <math>M</math> je jen <math>\{0, 1, λ\}</math>, neboť <math>x</math> musí být binární řetězec, pracovní abecedu stroje <math>M</math> nijak neomezujeme, a proto zde používáme obecnou abecedu <math>Σ</math>, přičemž předpokládáme, že <math>λ ∈ Σ</math>.
[[File:Kachl0.png]] [[File:vypocet.jpg]] <math>\stackrel{odpovídá}{\Rightarrow}</math> [[File:Kachl.png]]
Přehled převodu obecného problému <math>A ∈ NP</math> na problém <math>KACHL</math>. Horní hrana čtvercové sítě je obarvena počáteční konfigurací, spodní hrana přijímající konfigurací, boky jsou obarveny symbolem <math>λ</math>. Pro ukázku je zde řádek kachlíků s provedením instrukce <math>(q’, b, R) ∈ δ(q, a)</math>, 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|right|thumb|222px|diagram sekvence převodů používaných v tomto předmětu]]
: Literál je buď proměnná nebo její negace.
: '''Pozitivní literál''' je každá proměnná <math>x</math> .
: '''Negativní literál''' je každá negace proměnnej <math>\overline x</math>.
: '''Klauzule''' je disjunkcí literálů, která neobsahuje dva literály s touž proměnnou <math>x ∨ \overline y ∨ \overline z</math>.
: Formule <math>φ</math> je v '''konjunktivně normální formě (KNF)''', pokud je konjunkcí klauzulí <math>(x ∨ y) ∧ \overline z</math>.
: Je-li <math>φ</math> formulí na n proměnných a <math>t ∈ \{0, 1\}^n</math> , pak <math>φ(t)</math> značí hodnotu <math>φ</math> v '''ohodnocení''' <math>t</math>.
'''Splnitelnost formule v KNF (SAT)'''
* '''Instance:''' Formule <math>φ</math> na <math>n</math> proměnných v KNF
* '''Otázka:''' '''∃''' ohodnocení, pro které je <math>φ</math> splněná?
Důkaz transformací '''KACHL ∝ SAT''': pomocí proměnných <math>x_{ijk}</math>, kde <math>x_{ijk} = 1</math>, pokud na pozici <math>[i,j]</math> se nachází kachlík typu <math>k</math>. 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
}}
{{TODO|důkaz}}
;Dk (KACHL → SAT - myšlenka) :
: pomocí proměnných <math>x_{ijk}</math>, kde <math>x_{ijk} = 1</math>, pokud na pozici <math>[i,j]</math> se nachází kachlík typu <math>k</math>. 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.
;Dk (KACHL → SAT)
To, že <math>SAT</math> patří do NP, plyne z toho, že pokud dostaneme vektor <math>t ∈ {0, 1}^n</math>, 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. <math>NP</math>-těžkost splnitelnosti ukážeme převodem z problému Kachlíkování. Uvažme instanci Kachlíkování danou množinou barev <math>B</math>, přirozeným číslem <math>s</math>, čtvercovou sítí <math>S</math> velikosti <math>s × s</math>, jejíž okraje jsou obarveny barvami z <math>B</math>, a množinou typů kachlíků <math>K = \{T1, . . . , T|K|\}</math>. Popíšeme, jak zkonstruovat formuli <math>φ</math> v KNF, která bude splnitelná právě tehdy, když tato instance má přípustné vykachlíkování. Formule <math>φ</math> bude využívat <math>\{ s . |K| \}</math> proměnných <math>x_{i , j ,k}</math> pro <math>\{ i, j = 1, . . . , s, \}</math> a <math>\{ k = 1, . . . , |K| \}</math>. Konstrukcí formule <math>φ</math> zabezpečíme, že ve splňujícím ohodnocení bude hodnota <math>xi, j, k = 1</math> odpovídat tomu, že na políčko <math>S[i, j]</math> umístíme kachlík Tk. V konstrukci použijeme následující dvě množiny určující nekompatibilní dvojice kachlíků:
::<math>V</math> = {(p, q) | spodní barva Tp se neshoduje s horní barvou Tq},
::<math>H</math> = {(p, q) | pravá barva Tp se neshoduje s levou barvou Tq}.
Množina V obsahuje dvojice typů, jež nemohou být umístěny nad sebe, tedy vertikálně. Množina H obsahuje dvojice typů, jež nemohou být umístěny vedle sebe, tedy horizontálně.
Podobné množiny si definujeme i pro barvy na okrajích, pro i = 1, . . . , s definujeme Ui, Bi, Li, Ri.
::<math>U_j</math> = {k | horní barva Tk se shoduje s barvou horního okraje S v j-tém sloupci}
::<math>B_j</math> = {k | spodní barva Tk se shoduje s barvou spodního okraje S v j-tém sloupci}
::<math>L_j</math> = {k | levá barva Tk se shoduje s barvou levého okraje S na j-tém řádku}
::<math>R_j</math> = {k | pravá barva Tk se shoduje s barvou pravého okraje S na j-tém řádku}
Množina <math>Ui</math> tedy obsahuje typy kachlíků, jež mohou být umístěny na políčko <math>S[1, i]</math>, množina <math>Bi</math>
obsahuje typy kachlíků, jež mohou být umístěny na políčko <math>S[s, i]</math>, množina <math>Li</math> obsahuje typy
kachlíků, jež mohou být umístěny na políčko <math>S[i, 1]</math>, a konečně <math>Ri</math> obsahuje typy kachlíků, jež
mohou být umístěny na políčko <math>S[i, s]</math>. Konstrukci formule <math>φ</math> popíšeme po částech.
# Pro <math>\{ i, j = 1, . . . , s \}</math> definujeme: <math>Ci, j = ∨k = 1|K| (xi, j, k)</math>. Klauzule <math>Ci, j</math> je splněna, pokud je na políčku <math>S[i, j]</math> přiřazen alespoň jeden typ kachlíku.
# Pro <math>\{ i, j = 1, . . . , s \}</math> definujeme: <math>αi, j = ∧k = 1|K| ∧l = k + 1|K|(xi, j, k ∨ xi, j, l)</math>. Formule <math>αi, j</math> je splněna, je-li políčku <math>S[i, j]</math> přiřazen nejvýš jeden typ kachlíku.
# Pro <math>\{ i, j = 1, . . . , s \}</math> definujeme: <math>βi, j = Ci, j ∧ αi</math>, j. Formule <math>βi, j</math> je tedy splněna, pokud políčku <math>S[i, j]</math> přiřadíme právě jeden typ kachlíku.
# Pro <math>\{ 1 ≤ i ≤ (s – 1) \}, \{ 1 ≤ j ≤ s \}</math> definujeme: <math>γi, j = ∧ (p, q) ∈ V (xi, j,p ∨ x(i + 1), j, q)</math>. Formule <math>γi, j</math> je splněna, pokud nad sebou umístěným políčkům <math>S[i, j]</math> a <math>S[(i + 1), j]</math> nejsou přiřazeny nekompatibilní typy kachlíků.
# Pro <math>{ 1 ≤ i ≤ s }</math>, <math>{ 1 ≤ j ≤ (s – 1) }</math> definujeme: <math>δi, j = ∧ (p, q) ∈ H (xi, j,p ∨ xi, (j + 1), q)</math>. Formule <math>δ_{i,j}</math> je splněna, pokud vedle sebe umístěným políčkům <math>S[i, j]</math> a <math>S[i, (j + 1)]</math> nejsou přiřazeny nekompatibilní typy kachlíků.
# Definujeme: <math>εu = ∧j = 1s [ ∨k ∈ Uj (x1, j, k)]</math>. 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: <math>εb = ∧j = 1s [ ∨k ∈ Bj (xs, j, k)]</math>. 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: <math>εl = ∧i = 1s [ ∨k ∈ Li (xi, 1, k)]</math>. 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: <math>εr = ∧i = 1s ( ∨k ∈ Ri (xi, s, k))</math>. 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 <math>φ</math> jako:
::<math>φ = [∧i = 1s ∧j = 1s (βi, j)] ∧ [∧i = 1(s - 1) ∧j = 1s (γi, j)] ∧ [∧i = 1s ∧j = 1(s - 1) (δi,j ∧ εu ∧ εb ∧ εl ∧ εr)]</math>.
Z konstrukce okamžitě vyplývá, že <math>φ</math> je formule v KNF a že velikost <math>φ</math> je polynomiální v s a <math>|K|</math>, a v polynomiálním čase lze <math>φ</math> i zkonstruovat. Zbývá ukázat, že pro výchozí instanci problému Kachlíkování existuje přípustné vykachlíčkování, právě když <math>φ</math> je splnitelná formule. Ve skutečnosti ukážeme, že ze splňujícího ohodnocení formule <math>φ</math> lze vyčíst přípustné vykachlíkování čtvercové sítě <math>S</math> a naopak z přípustného vykachlíkování lze určit splňující ohodnocení formule <math>φ</math>.
Předpokládejme nejprve, že existuje přípustné vykachlíčkování S kachlíky z <math>K</math>. Označme pomocí <math>S[i, j]</math> index typu kachlíku, který je na i-tém řádku a j-tém sloupci. Definujme <math>xi, j, k = 1</math> právě když je na políčku <math>S[i, j]</math> umístňen kachlík <math>Tk</math>. Není těžké ověřit, že každá z podformulí <math>βi ,j, γi, j, δi, j, εu, εb, εl, εr</math> je tímto ohodnocením splněna, a tedy že i celá formule <math>φ</math> je splněna. Předpokládejme na druhou stranu, že existuje splňující ohodnocení formule <math>φ</math> a pomocí <math>v[i, j, k]</math> označme hodnotu přiřazenou proměnné <math>xi, j, k</math> ve splňujícím ohodnocení. Díky tomu, že ohodnocení splňuje i formuli <math>βi,j</math>, existuje pro každé <math>\{ i, j = 1, . . . , s \}</math> právě jedno <math>k ∈ \{1, . . . , |K|\}</math>, pro kterou je <math>v[i, j, k] = 1</math>. Na pozici <math>S[i, j]</math> tedy dáme kachlík toho typu <math>Tk</math>, pro který je <math>v[i, j, k] = 1</math>. Lze snadno ověřit, že podmínky zakódované do formulí <math>γi, j, δi, j, εu, εb, εl, εr</math> zaručují, že tímto způsobem obdržíme přípustné vykachlíkování <math>S</math>.
== NP-úplnost 3-SAT (z SAT)==
[[Image:Satisfiability-L.gif|right|thumb|460px|'''input''']]
[[Image:Satisfiability-R.gif|right|thumb|460px|'''output''']]
Kubická CNF (vždy jen 3 proměnné v jedné disjunkci) <math>F</math> na <math>n</math> Booleovských proměnných. Existuje pravdivostní ohodnocení proměnných, které splňuje formuli <math>F</math>?
'''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 (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 (NPC - <math>SAT\leq_m^p 3SAT</math> ):
: konstrukce 3SAT <math>φ</math> z SAT fle <math>ψ = C_1 ∧ . . . ∧ C_m</math> (kde klauzule <math>C_j = (e_1 ∨ . . . ∨ e_k)</math> )
: SAT klauzule se transformují na 3SAT případně doplní novými proměnnými nastavenými tak aby neovlivňovaly výsledek:
: '''( k = 1 )''' <math>αj = (e1 ∨ y1j ∨ y2j) ∧ (e1 ∨ \overline y1j ∨ y2j) ∧ (e1 ∨ y1j ∨ \overline y2j) ∧ (e1 ∨ \overline y1j ∨ \overline y2j)</math>
:: <math>y_1^j, y_2^j</math> - nové proměnné, které se nevyskytují v ψ
: '''( k = 2 )''' <math>αj = (e1 ∨ e2 ∨ yj ) ∧ (e1 ∨ e2 ∨ \overline yj )</math>.
: '''( k = 3 )''' Definujeme: αj = Cj
: '''( k > 3 )''' <math>αj = (e1 ∨ e2 ∨ y1j) ∧ (\overline y1j ∨ e3 ∨ y2j) ∧ (\overline y2j ∨ e4 ∨ y3) ∧ . . . ∧ (\overline yk−3j ∨ ek−1 ∨ ek)</math>.
: Formuli φ nyní definujeme jako: <math>φ = ∧_{j=1}^m α_j</math> a lze ji i v polynomiálním čase zkonstruovat.
: SAT ψ splnitelná ⇔ 3SAT φ splnitelná (z konstrukce).
<br style="clear:both;">
== NP-úplnost VP (z 3-SAT)==
[[Image:ZSV 1416994785854209736.png|right|thumb|460px|'''input''']]
[[Image:ZSV 4921028494756709267.jpg|right|thumb|460px|'''output''']]
'''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 (<math>VP ∈ NP</math>)
: pro danou množinu <math>S</math> dokážeme ověřit v polynomiálním čase, jde-li o VP správné velikosti
;Dk (<math>VP ∈ NPC</math> - <math>3SAT\leq_m^p VP</math> )
: 3SAT: <math>φ=C_1∧...∧C_m</math> s proměnnými <math>U={u_1,...,u_n}</math>
: Konstrukce grafu <math>G=(V,E)</math> skrz pospojování podgrafů:
: <math>∀u_i:</math> def.podgraf <math>T_i =(V_i, E_i)=(\{u_i, \overline u_i\}, \{ \{u_i, \overline u_i\} \})</math>: - VP musí použít vždy aspoň 1 vrchol
: <math>∀C_j</math>: def.trojůhelník <math>R_j =(V’_j, E’_j)</math>: - VP musí použít vždy aspoň 2 vrcholy
: podgrafy pospojujeme podle formule <math>φ</math>
[[File:Vp.png]]
: <math>G</math> má <math>VP</math> <math>|S| ≤ k ⇔ φ</math> splnitelná
:: <math>⇒ k = n + 2m</math>
::: ohodnotíme Ti pokud je součástí <math>S (u_i=1, \overline u_i=0)</math>
::: VP pokrývá vždy 2 vrcholy z <math>R_j</math>, ten 1 zbývající je pak ohodnocen z <math>u_i / \overline u_i</math>
:: <math>⇐</math> do <math>S</math> patří ohodnocené <math>u_i / \overline u_i</math> (<math>n</math> vrcholů)
::: mezi vrcholy z <math>R_j</math> musí být aspoň 1 pokrytý vrcholem z <math>S</math>
:::: do <math>S</math> přidáme ty ostatní
<br style="clear:both;">
== NP-úplnost 3DM (z SAT) ==
[[Image:3dm input.jpg|right|thumb|460px|'''input''']]
[[Image:3dm output.png|right|thumb|460px|'''output''']]
'''Trojrozměrné párování (3-dimensional matching - 3DM)'''
* '''Instance:''' Množina <math>M⊆ W\times X\times Y</math>, kde <math>W, X, Y</math> jsou po dvou disjunktní množiny a <math>|W|= |X|= |Y| = q</math>.
* '''Otázka:''' Obsahuje <math>M</math> perfektní párování? Jinými slovy, existuje množina <math>M'⊆ M</math>, <math>|M'| = q</math>, trojice v níž obsažené jsou po dvou disjunktní?
{{theorem
| 3DM je NP-úplný problém.
| 3DM ∈ NPC
}}
; Dk(<math>3DM ∈ NP</math>):
: plyne z toho, že pokud máme k dispozici množinu <math>M'⊆ M</math>, dokážeme ověřit v polynomiálním čase, jde-li o párování velikosti <math>|M'| = q</math>.
; Dk(<math>3DM ∈ NPC</math> - <math>SAT\leq_m^p 3DM</math> ):
: Těžkost tohoto problému si ukážeme převodem z problému <math>SAT</math>. Nechť <math>\varphi=C_1\wedge C_2\wedge\dots\wedge C_m</math> je formule v KNF na
proměnných <math>U=\{u_1, \dots, u_n\}</math>. Sestrojíme instanci problému
<math>3DM</math>, pro kterou bude platit, že v této instanci existuje perfektní
párování, právě když je <math>\varphi</math> splnitelná. Konstrukci rozdělíme na
tři části, nejprve vytvoříme komponentu, která bude určovat, jakou
hodnotu která proměnná dostane, poté vytvoříme komponentu, která bude
zajišťovat propojení této hodnoty s klauzulemi, v nichž se tato
proměnná vyskytuje, nakonec doplníme trojice tak, abychom dostali
k splňujícímu ohodnocení skutečně perfektní párování a naopak.
Za každou proměnnou <math>u_i</math>, <math>i=1, \dots, n</math> přidáme nové vnitřní prvky
<math>a_i[1], \dots, a_i[m]</math> do <math>X</math> a <math>b_i[1], \dots, b_i[m]</math> do <math>Y</math>. Do
<math>W</math> přidáme prvky <math>u_i[1], \dots, u_i[m]</math> a <math>\overline u_i[1], \dots,
\overline u_i[m]</math>. Na těchto prvcích vytvoříme množiny trojic <math>T_i^f</math> a
<math>T_i^t</math> takto (viz též příklad na obrázku):
[[Image:3dm.jpg|right|thumb|256px|Ukázka množin <math>T_i^t</math> (plnou čarou) a <math>T_i^f</math> (čárkovaně) pro případ <math>m=3</math>.]]
<math>
\matrix{
T_i^t&=&\{(\overline u_i[j], a_i[j], b_i[j])\;|\;1\leq j\leq m\}\cr
T_i^f&=&\{(u_i[j], a_i[(j+1)\;{\rm mod}\;m], b_i[j])\;|\;1\leq j\leq m\}\cr
T_i&=&T_i^t\cup T_i^f\cr
}
</math>
Protože žádný z prvků <math>a_i[j]</math> ani <math>b_i[j]</math> se nebude vyskytovat
v jiných trojicích, je tímto vynuceno, že perfektní párování buď musí
obsahovat všechny trojice z </math>T_i^t</math>, nebo všechny trojice z <math>T_i^f</math>.
Pokud obsahuje trojice z </math>T_i^t</math>, znamená to, že žádná další vybraná
trojice nesmí obsahovat literál <math>\overline u_i</math>, tedy vynucujeme hodnotu 1,
true pro <math>u_i</math>, proto také <math>T_i^t</math>. Podobně pokud obsahuje perfektní
párování trojice z <math>T_i^f</math>, vynucujeme hodnotu 0, false, odtud
<math>T_i^f</math>.
Za klauzuli <math>C_j</math> přidáme nový prvek <math>s_1[j]</math> do množiny <math>X</math>, nový
prvek <math>s_2[j]</math> do množiny <math>Y</math> a množinu
trojic
<math>
S_j=\{(u_i[j], s_1[j], s_2[j])\;|\;u_i\in C_j\}\cup
\{(\overline u_i[j], s_1[j], s_2[j])\;|\;\overline u_i\in C_j\}</math>
Prvky <math>s_1[j]</math> a <math>s_2[j]</math> se opět nebudou vyskytovat v jiných
trojicích, díky tomu v perfektním párování musí být právě jedna
trojice z množiny <math>S_j</math>.
Navíc pokud se trojice <math>(u_i[j], s_1[j], s_2[j])</math> vyskytuje
v perfektním párování, znamená to, že <math>u_i[j]</math> se nemůže vyskytovat
v jiné trojici a to znamená, že v tomto párování jsou všechny trojice
z </math>T^t_i</math> a žádná z </math>T_i^f</math>. Podobně by to bylo, kdyby v perfektním
párování byla trojice s negativním literálem.
Těmito trojicemi jsme ale schopni v perfektním párování pokrýt jen
<math>mn+m</math> prvků z </math>2mn</math> prvků <math>u_i[j], \overline u_i[j]</math>, <math>i=1, \dots, n</math>, <math>j=1,
\dots, m</math>. Z toho <math>mn</math> jich pokryjeme trojicemi z </math>T_i^t</math> nebo
<math>T_i^f</math>, <math>i=1, \dots, n</math>. Trojicemi z </math>S_j</math>, <math>j=1, \dots, m</math> pokryjeme
dalších <math>m</math> prvků. Zbývá tedy <math>2mn-(mn+m)=mn-m=m(n-1)</math> prvků, jež
nejsme zatím schopni pokrýt, proto přidáme do množiny <math>M</math> trojice,
které nám jejich pokrytí zabezpečí. Do <math>X</math> přidáme prvky <math>g_1[k]</math> a do
<math>Y</math> prvky <math>g_2[k]</math> obojí pro <math>k=1, \dots, m(n-1)</math> a do <math>M</math> přidáme
množinu trojic
<math>G=\{(u_i[j], g_1[k], g_2[k]), (\overline u_i[j], g_1[k], g_2[k])\;|\;1\leq
k\leq m(n-1), 1\leq i\leq n, 1\leq j\leq m\}</math>
Tím je konstrukce dokončena, ještě si na závěr shrňme její výsledek:
<math>
\matrix{
W&=&\{u_i[j], \overline u_i[j]\;|\;1\leq i\leq n, 1\leq j\leq m\}\cr
X&=&\{a_i[j]\;|\;1\leq i\leq n, 1\leq j\leq m\}\;\cup\cr
&&\cup\;\{s_1[j]\;|\;1\leq j\leq m\}\cr
&&\cup\;\{g_1[j]\;|\;1\leq j\leq m(n-1)\}\cr
Y&=&\{b_i[j]\;|\;1\leq i\leq n, 1\leq j\leq m\}\;\cup\cr
&&\cup\;\{s_2[j]\;|\;1\leq j\leq m\}\cr
&&\cup\;\{g_2[j]\;|\;1\leq j\leq m(n-1)\}\cr
M&=&\Big(\bigcup_{i=1}^nT_i\Big)\cup\Big(\bigcup_{j=1}^mS_j\Big)\cup
G\cr
}
</math>
Zřejmě platí, že <math>M\subseteq W\times X\times Y</math>, navíc
<math>|M|=2mn+3m+2m^2n(n-1)</math> a <math>|W|=|X|=|Y|=2mn</math>. Velikost takto vytvořené
instance trojrozměrného párování je tedy polynomiálně velká a
v polynomiálním čase ji zřejmě lze i vytvořit.
Předpokládejme, že v </math>M</math> existuje perfektní párování <math>M'</math>, na jehož
základě zkonstruujeme ohodnocení <math>t</math>, které bude splňovat formuli
<math>\varphi</math>. Nechť <math>i</math> je libovolný index z </math>1, \dots, n</math>, jak jsme již
zdůvodnili, v </math>M'</math> jsou buď všechny trojice z </math>T_i^t</math>, nebo všechny
trojice z </math>T_i^f</math>, pokud <math>M'</math> obsahuje trojice z </math>T_i^t</math>, definujeme
<math>t(u_i):=1</math>, pokud <math>M'</math> obsahuje trojice z </math>T_i^f</math>, definujeme
<math>t(u_i):=0</math>. Nechť <math>C_j</math> je libovolná klauzule formule <math>\varphi</math>,
množina <math>M'</math> musí obsahovat právě jednu z trojic z </math>S_j</math>, neboť to je
jediná možnost, jak mohou být pokryty prvky <math>s_1[j]</math> a <math>s_2[j]</math> a dvě
obsahovat nemůže, protože každý z těchto prvků musí být pokryt právě
jednou. Nechť tato trojice je <math>(u_i[j], s_1[j], s_2[j])</math> pro nějaké
<math>i=1, \dots, n</math>. To znamená, že <math>u_i</math> je proměnná, vyskytující se jako
pozitivní literál v klauzuli <math>C_j</math>, navíc musí platit, že <math>u_i[j]</math> se
nemůže vyskytovat v žádné jiné trojici v <math>M'</math>, a proto <math>M'</math> obsahuje
trojice z <math>T_i^t</math> a nikoli trojice z <math>T_i^f</math>, a tedy <math>t(u_i)=1</math>, čímž
je klauzule <math>C_j</math> splněna. Podobně bychom postupovali v případě, kdy
trojicí v <math>S_j\cap M'</math> by byla <math>(\overline{u_i}[j], s_1[j], s_2[j])</math>,
tedy pokud by obsahovala negativní literál, jediný rozdíl by byl, že
bychom dostali, že <math>t(u_i)=0</math> a že <math>C_j</math> je splněna díky negativnímu
literálu <math>\overline{u_i}</math>.
Pokud je naopak <math>\varphi</math> splnitelná, zkonstruujeme perfektní párování
následovně. Nechť <math>t:U\mapsto\{0, 1\}</math> je ohodnocení splňující <math>\varphi</math>
a nechť <math>z_j</math> označuje literál, který je v </math>C_j</math> tímto ohodnocením
splněn pro <math>j=1, \dots, m</math>. Pokud je takových literálů víc, vybereme
prostě jeden z nich.
Pak položíme
<math>M'=\Big(\bigcup_{t(u_i)=1}T_i^t\Big)\cup
\Big(\bigcup_{t(u_i)=0}T_i^f\Big)\cup
\Big(\bigcup_{j=1}^m\{(z_j[j], s_1[j], s_2[j])\}\Big)
\cup G',
</math>
kde <math>G'</math> je množina vhodně vybraných trojic z <math>G</math>, které doplňují
párování o pokrytí zbylých literálů. Není těžké ověřit, že takto
definovaná množina <math>M'</math> tvoří perfektní párování <math>M</math>.
{{TODO|důkaz}}
<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 6409563349302832850.jpg|right|thumb|200px|'''input''']]
[[Image:ZSV 6986917693546073969.jpg|right|thumb|200px|'''output''']]
'''Loupežníci (LOUP) anglicky Partition'''
* '''Instance:''' Množina <math>A</math> a váha <math>∀a∈A: s(a)∈N</math>
* '''Otázka:''' Lze rozdělit prvky z <math>A</math> na dvě poloviny se stejnou váhou? <math>(\sum_{a\in A'}s(a)=\sum_{a\in A\setminus A'}s(a)\;)</math>
💡 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 (<math>LOUP ∈ NP</math>):
: plyne z toho, že pro zadanou množinu <math>A’ ⊆ A</math> se ověří v polynomiálním čase, zda obsahuje prvky poloviční ceny.
; Dk (<math>LOUP ∈ NPC</math> - <math>3DM\leq_m^p LOUP</math> ):
: Konstrukce instance LOUP:
:'''Trojrozměrné párování (3-dimensional matching - 3DM)'''
:* '''Instance:''' Množina <math>M⊆ W\times X\times Y</math>, kde <math>W, X, Y</math> jsou po dvou disjunktní množiny a <math>|W|= |X|= |Y| = q</math>.
:* '''Otázka:''' Obsahuje <math>M</math> perfektní párování? Jinými slovy, existuje množina <math>M'⊆ M</math>, <math>|M'| = q</math>, trojice v níž obsažené jsou po dvou disjunktní?
: z kontruujeme LOUP množinu takto <math>A={m_1,..,m_k,b_1,b_2}</math> (💡 použijeme tedy trojice <math>m_i∈M</math> a pomocné prvky <math>b_1,b_2</math>)
: cenu prvku <math>m_i</math> si reprezentujeme jako binární "segmentové číslo" v <math>3q</math> blocích, definovaných podle složení trojice <math>m_i</math>
:* <math>m_i = {w_{f(i)}, x_{g(i)}, y_{h(i)}}</math> kde fce <math>f,g,h</math> vrací odpovídající indexy prvků z trojice <math>m_i</math>
:* ∀ blok (z segmentu) má <math>p = ⌈log_2(k + 1)⌉</math> 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ě: <math>s(a_i)=2^{p(3q-f(i))}+2^{p(2q-g(i))}+2^{p(q-h(i))}</math>)
:* počet bitů pro reprezentaci <math>s(a_i)</math> je <math>3pq</math> (polynomiální) ⇒ 💡 ceny <math>s(a_i)</math> se dají zkontruovat v polynomiálním čase
: dále si vytvoříme stejné segmentové číslo <math>B</math> s 1 zprava v ∀ bloku (tedy <math>B=\sum_{j=0}^{3q-1}2^{pj}</math>)
: [[Image:3dm2loup.png|none|thumb|619px|Popis <math>3q</math> segmentů, ∀ obsahuje <math>p = ⌈log_2(k + 1)⌉</math> bitů binární reprezentace <math>s(a)</math>, použité pro převod 3DM na LOUP.]]
: teď dokážeme že <math>A'\subseteq\{a_i\;|\;1\leq i\leq k\}: B=∑_{a_i∈A’} s(a_i) ⇔ M’=\{m_i|a_i∈A’ \}</math> je 3DM
:: určíme si poslední dva pomocné dva prvky z <math>A</math>:
::: <math>s(b_1) = 2∑s(a_i) - B</math>
::: <math>s(b_2) = ∑s(a_i) + B</math>
:: celkem pro množ. <math>A</math> tedy máme <math>∑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)</math>
::: pokud <math>A'\subseteq A: \sum_{a\in A'}s(a)=\sum_{a\in A\setminus A'}s(a) = 2∑s(a_i)</math>
::: ⇒ <math>b_1,b_2</math> nemůžou být oba ani v jedné půlce
::: ⇒ <math>\sum_{A'\setminus \{b_1\}}s(a) =B</math> (💡 musí být po řádcích disjunktní jinak by nám nevyšlo <math>B</math>) a <math>A’\setminus \{b_1\}</math> <u>určují perfektní párování v <math>M</math></u> (=<math>3DM</math>)
:: nyní definujme 3DM <math>M'⊆M</math> a <math>A’=\{a_i|m_i∈M’ \}</math>
::: <math>∑_{a\in A'}s(a) + s(b_1) = 2∑s(a_i)</math>
::: <math>A’\cup \{b_1\}</math> <u>tedy obsahuje prvky poloviční ceny</u> (=<math>LOUP</math>)
<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 <math>P=NP</math>. 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'' <math>A</math>, pokud pro každý polynom p existuje instance <math>I</math> problému <math>A</math>, pro kterou platí, že <math>max(I) > p(len(I))</math>.
* '''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 <math>len(I) = O(n log_2(B + V))</math>, ale <math>max(I) = max(\{B\} ∪ \{v[i], s[i] | 1 ≤ i ≤ n\})</math>. Například LOUP nebo Batoh jsou tedy číselné problémy, zatímco SAT nebo KLIKA číselné problémy nejsou.
* Algoritmus řešící <math>A</math> je '''pseudopolynomiální''' , pokud je jeho časová složitost omezená polynomem dvou proměnných <math>max(I)</math> a <math>len(I)</math>.
: 💡 Alg. pro Batoh je pseudopolynomiální (viz níže). Je-li problém <math>A</math> řešitelný pseudopolynomiálním algoritmem a není-li <math>A</math> čí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 <math>P = NP</math>.
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ě:''' <math>p</math> je polynom a <math>A</math> NP-úplný problém:
* <math>A(p)</math> je restrikce problému <math>A</math> na instance <math>I</math> s <math>max(I) ≤ p(len(I))</math>.
* ''Silně NP-úplný'' je problém <math>A</math>, pokud ∃ polynom <math>p</math>, pro nějž je problém <math>A(p)</math> NP-úplný.
* ''Slabě NP-úplný'' je problém <math>A</math>, pokud ∄ polynom <math>p</math>, pro nejž je problém <math>A(p)</math> NP-úplný.
{{theorem
| Problém Obchodního cestujícího je silně NP-úplný.
| OC je silně NP-úplný
}}
;Dk:
: 💡 <math>max(I)</math> 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|right|thumb|250px|0/1 knapsack problem (💡 0/1 = buď předmět vezmu nebo ne)]]
=== Příklad pseudopolynomiálního algoritmu pro Batoh ===
; Batoh ( 0/1 knapsack problem ), úloha:
* '''Instance :''' Množina n předmětů <math>A = {a_1, . . . , a_n}</math>, s každým předmětem velikost <math>s(a_i) ∈ N</math> a cena či hodnota <math>v(a_i) ∈ N</math>. Přirozené číslo <math>B ≥ 0</math> udávající velikost batohu.
* '''Cíl :''' Nalézt množinu předmětů <math>A‘ ⊆ A</math>, která dosahuje maximální souhrnné hodnoty předmětů v ní obsažených, a přitom se předměty z <math>A</math> vejdou do batohu velikosti <math>B</math>.
; Pseudopolynomiální alg. <math>Batoh(s, v, B)</math> (💡 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) <math>s</math>, cen (value) předmětů <math>v</math> (<math>|s|=|v|=n</math>) a velikost batohu <math>B</math>. Platí: <math>0 < s[i] ≤ B</math>.
* '''Výstup :''' Mnž. <math>|M|≤ B</math> a s maximální cenou.
* '''Prerekvizity :''' <math>V</math> je suma cen všech předmětů (<math>V= Σ_{i = 1^n} v_i</math>).
: Nechť <math>T</math> je tabulka <math>(n + 1) × (V + 1)</math>, na pozici <math>T [j, c]</math> ( <math>0 ≤ j ≤ n , 0 ≤ c ≤ V</math> ), bude podmnožina indexů ( <math>1, . . . , j</math> ) prvků celkové ceny přesně <math>c</math> s minimální velikostí.
: Nechť <math>S</math> je tabulka <math>(n + 1) × (V + 1)</math>, na pozici <math>S[j, c]</math> je celková velikost předmětů v množině <math>T [j, c]</math>. Pokud neexistuje množina s předměty ceny přesně <math>c</math>, je na pozici <math>S[j, c]</math> číslo <math>B + 1</math>.
[[Image:Batoh.png|right|thumb|480px|běh alg. <math>Batoh(s, v, B)</math>, barvy ukazují jak vznikaly množiny (pokud se jen nekopírovaly z minulého kroku cyklu přes předměty), šipky ukazují směr průchodu alg. tabulkou (bottom-up)]]
<pre<noinclude></noinclude>>
<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];
</pre<noinclude></noinclude>>
💡 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 <math>B</math>. Pracuje v čase <math>O(nV)</math>.
| Batoh v čase <math>O(nV)</math>
}}
; Dk (<math>O(nV)</math>)
: Kroky 0 až 6 zvládneme jistě v čase <math>O(nV)</math>, 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 <math>T [j, c]</math>. 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:
# Na pozici <math>T [j, c]</math>, <math>0 ≤ j ≤ n, 0 ≤ c ≤ V</math> je po ukončení algoritmu podmnožina <math>\{1, . . . , j\}</math> prvků celkové ceny přesně <math>c</math> s minimální velikostí mezi všemi takovými množinami. Pokud neexistuje množina prvků s cenou přesně <math>c</math>, pak na pozici <math>T [j, c]</math> bude ∅.
# Na pozici <math>S[j, c]</math>, <math>0 ≤ j ≤ n, 0 ≤ c ≤ V</math> je po ukončení algoritmu součet velikostí prvků v množině na pozici <math>T [j, c]</math>. Pokud neexistuje množina prvků s cenou přesně <math>c</math>, pak na pozici <math>S[j, c]</math> je <math>(B + 1)</math>.
: Tyto vlastnosti ukážeme indukcí podle <math>j</math>.
: Na začátku vyplníme nultý řádek v cyklu na řádcích 1 až 4, pro <math>j = 0</math> tedy vlastnosti (1.) a (2.) platí.
: Nyní předpokládejme, že vlastnosti (1.) a (2.) platí pro řádky <math>0, . . ., (j – 1)</math> a ukažme, že platí i pro <math>j</math>-tý řádek.
: <math>T [j, 0]=∅</math> protože je to nejmenší množina prvků s cenou <math>0</math>. Takto provedeme nastavení <math>T[j, 0]</math> a <math>S[j, 0]</math> na řádcích 8 a 9.
: Pokud je <math>c > 0</math>, pak na ně narazíme na vhodném místě v rámci vnitřního cyklu.
: Pro <math>j > 0</math> a <math>c > 0</math> máme dvě možnosti, buď v nejmenší množině prvků <math>{1, . . . , j}</math> s cenou <math>c</math> není prvek <math>j</math>, potom se jedná o množinu uloženou podle indukční hypotézy na pozici <math>T[j − 1, c]</math>, nebo se v této množině prvek <math>j</math> vyskytuje. Pokud bychom z této nejmenší množiny prvek odstranili, museli bychom dostat nejmenší množinu s cenou (<math>c − v[j])</math> z prvků <math>\{1, . . . , (j – 1)\}</math>, která je podle indukčního předpokladu uložena na pozici <math>T [j – 1, c − v[j]]</math>.
: Z těchto dvou možností vybereme tu, která má menší velikost. Díky tomu také na pozici <math>T [j, c]</math> uložíme ∅ a na pozici <math>S[j, c]</math> hodnotu <math>(B + 1)</math> jedině tehdy, pokud obě množiny na pozicích <math>T [j − 1, c]</math> a <math>T [j − 1, c − v[j]]</math> jsou ∅ a obě odpovídající velikosti jsou <math>(B + 1)</math>.
: 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 <math>T [j − 1, c − v[j]]</math> neprázdná, jinak by z ∅ přidáním prvku <math>j</math> 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 <math>S[n, 0] = 0</math>.
==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í:
:# Množina instancí <math>D_A ⊆ \{0, 1\}^*</math>.
:# Pro každou instanci <math>I ∈ D_A</math> je dána množina přípustných řešení <math>S_A(I) ⊆ \{0, 1\}^*</math>.
:# Funkce <math>μ_A</math>, která každé instanci <math>I ∈ D_A</math> a každému přípustnému řešení <math>σ ∈ S_A(I)</math> přiřadí kladné racionální číslo <math>μ_A(I, σ)</math>, které nazveme '''hodnotou řešení''' σ.
* Pokud je A maximalizační úlohou, pak '''optimálním řešením''' instance <math>I ∈ D_A</math> je <math>σ ∈ S_A(I)</math>, pro něž je <math>μ_A(I, σ)</math> maximální (tj. <math>μ_A(I, σ) = max\{μ_A(I, σ) | σ ∈ S_A(I)\}</math>).
** Pokud je <math>A</math> minimalizační úlohou, pak optimálním řešením instance <math>I ∈ D_A</math> je <math>σ ∈ S_A(I)</math>, pro něž je <math>μ_A(I, σ)</math> minimální (tj. <math>μ_A(I, σ) = min\{μ_A(I, σ) | σ ∈ S_A(I)\}</math>).
** '''Hodnotu optimálního řešení''' instance <math>I ∈ D_A</math> označujeme <math>OPT_A(I)= μ_A(I, σ)</math> (kde <math>σ</math> je optimální řešení intance <math>I</math>).
* Řekneme, že algoritmus <math>ALG</math> je '''aproximačním algoritmem''' pro optimalizační úlohu <math>A</math>, pokud pro každou instanci <math>I ∈ D_A</math> vrátí <math>ALG</math> se vstupem <math>I</math> řešení <math>σ ∈ S_A(I)</math>, případně ohlásí, že žádné přípustné řešení neexistuje, pokud <math>S_A(I) = ∅</math>.
* Hodnotu řešení vráceného algoritmem <math>ALG</math> na instanci <math>I</math> označíme jako <math>ALG(I)</math>, tj. <math>ALG(I) = μ_A(I, σ)</math>, kde <math>σ ∈ S_A(I)</math> je přípustné řešení vrácené algoritmem <math>ALG</math>.
* Pokud je <math>A</math> maximalizační úloha, pak racionální číslo <math>ε ≥ 1</math> nazveme '''aproximačním poměrem''' algoritmu <math>ALG</math>, pokud pro každou instanci <math>I ∈ D_A</math> platí, že <math>OPT (I) ≤ ε.ALG(I)</math> .
** Je-li <math>A</math> minimalizační úlohou, pak racionální číslo <math>ε ≥ 1</math> nazveme '''aproximačním poměrem''' algoritmu <math>ALG</math>, pokud pro každou instanci <math>I ∈ D_A</math> platí, že <math>ALG(I) ≤ ε.OPT(I)</math> .
=== Příklad aproximačního algoritmu pro Bin Packing ===
; Bin Packing – BP, úloha:
* '''Instance :''' Konečná množina předmětů <math>U = {u_1, .., u_n}</math>, s každým předmětem asociovaná velikost <math>s(u)</math>, což je racionální číslo, pro které platí <math>0 ≤ s(u) ≤ 1</math>.
* '''Cíl :''' Najít rozdělení všech předmětů do co nejmenšího počtu po dvou disjunktních množin <math>U_1, . . ., U_m</math> takové, že každá množina může mít velikost max 1.
: 💡 Naším cílem je tedy minimalizovat <math>m</math>.
: 💡 Formálně je tedy <math>D_{BP}</math> množinou řetězců kódujících instance <math>BP</math>, pro danou instanci <math>I= ⟨U, s(u)⟩</math> je množina <math>S_BP(I)</math> množinou všech možných rozdělení do dostatečného množství košů. Mírou řešení <math>μ_{BP}(σ)</math> pro <math>σ ∈ S_{BP}(I)</math> je počet košů, které řešení využívá, tedy hodnota <math>m</math>. Rozhodovací verze tohoto problému je shodná s problémem Rozvrhování, o jehož těžkosti víme, z toho plyne, že i úloha <math>BP</math> je <math>NP</math>-těžká. Šance na to, že bychom našli polynomiální algoritmus, řešící <math>BP</math> přesně, jsou tedy malé.
; Algoritmus (First Fit pro Bin Packing – <math>FF-BP</math>):
* Ber jeden předmět po druhém,
** ∀ předmět <math>u</math> 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 <math>u</math>.
💡 Algoritmus <math>FF-BP</math> je zřejmě polynomiální.
{{theorem
| ∀ instanci <math>I ∈ DBP</math> platí, že <math>FF-BP(I) < 2.OPT_{BP}(I)</math>.
| Aproximační poměr <math>FF-BP</math> je 2
}}
;Dk:
: V řešení, které vrátí <math>FF-BP</math> je nejvýš jeden koš, který je zaplněn nejvýš z poloviny. Kdyby totiž existovaly dva koše <math>U_i</math> a <math>U_j</math> pro <math>i < j</math>, které jsou zaplněny nejvýš z poloviny, tak by <math>FF-BP</math> nepotřeboval zakládat nový koš pro předměty z <math>U_j</math>, všechny by se vešly do <math>U_i</math>.
: Pokud <math>FF-BP(I) > 1</math>, pak z toho plyne, že: <math>FF-BP(I) < ⌈2 Σ_{i = 1}^n s(u_i)⌉ ≤ 2⌈Σ_{i = 1}^n s(u_i)⌉</math>, 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 <math>OPT(I) ≥ ⌈Σ_{i = 1}^n s(u_i)⌉</math>.
: Dohromady tedy dostaneme, že <math>FF-BP(I) < 2.OPT(I)</math>. Pokud <math>FF-BP(I) = 1</math>, pak i <math>OPT(I) = 1</math> a i v tomto případě platí ostrá nerovnost.
{{lemma
| Pro libovolnou hodnotu m ∃ instance <math>I ∈ D_{BP}</math>, pro niž je <math>OPT(I) ≥ m</math> a <math>FF-BP(I) ≥ 5/3 \cdot OPT(I)</math>.
}}
;Dk:
: Instance bude mít <math>U = {u_1, u_2, . . . , u_18m}</math>, s těmito prvky asociujeme váhy takto:
: <math>1≤ i ≤ 6m : s(ui) = 1/7 + ε</math>, <math>6m< j ≤ 12m : s(ui) = 1/3 + ε</math>, <math>12m< j ≤ 18m : s(ui) = 1/2 + ε</math>. Kde <math>ε > 0 je</math> dostatečně malé kladné racionální číslo. Optimální rozdělení rozdělí prvky do <math>6m</math> košů, do každého dá po jednom prvku s velikostmi <math>(1/7 + ε), (1/3 + ε), (1/2 + ε)</math>. Hodnotu ε zvolíme dostatečně malou tak, aby se každá z těchto trojic vešla do koše velikosti <math>1</math>. Algoritmus <math>FF-BP</math> bude brát prvky jeden po druhém a vytvoří nejprve m košů, každý s šesti prvky velikosti <math>(1/7 + ε)</math>, přičemž hodnotu <math>ε</math> 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ří <math>3m</math> košů, každý se dvěma prvky velikosti <math>(1/3 + ε)</math>, k nimž se opět nic nevejde.
: Nakonec <math>FF-BP</math> vytvoří <math>6m</math> košů, každý s jedním prvkem velikosti<math>(1/3 + ε)</math>. Dohromady je <math>FF-BP(I) = 10m</math>, a tedy <math>[ FF-BP(I) / OPT(I) ] = 5/3</math>.
: 💡 Pochopitelně brát prvky v libovolném pořadí tak, jak to činí <math>FF-BP</math> je nejhloupější možnou strategií. Na instanci popsanou v důkazu lemmatu by přitom stačilo, kdybychom nejprve prvky <math>U</math> 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 <math>FF-D-BP</math> z anglického „decreasing“. Lze ukázat, že pro libovolnou instanci <math>I ∈ D_{BP}</math> platí: <math>FF-D-BP(I) ≤ (11/9).OPT(I) + 4</math>.
==Aproximační schémata - definice a příklad aproximačního schématu pro Batoh (🎓)==
[[Image:Schemes.jpg|right|thumb|485px|💡 inkluze tříd NP, APX, PAS, ÚPAS, P a Pseudo-PTIME]]
{{Zkazky|
* definicia optimalizacnej ulohy, definicia aproximacneho algoritmu, aproximacneho pomeru, aproximacneho schema, PAS a UPAS, schema pre BATOH
}}
Nechť <math>A</math> je libovolná optimalizační úloha. Algoritmus <math>ALG</math> nazveme '''aproximačním schématem''' pro úlohu <math>A</math>, pokud na vstupu očekává instanci <math>I\in D_A</math> a racionální číslo <math>\varepsilon>0</math> a na výstupu vydá řešení <math>\sigma\in S_A(I)</math>, jehož hodnota se od optimální liší s aproximačním poměrem <math>(1+\varepsilon)</math>.
* Tj. pro maximalizační úlohu platí, že: <math>OPT(I)\leq(1+\varepsilon)ALG(I, \varepsilon)</math>
* a pro minimalizační úlohu platí, že: <math>ALG(I, \varepsilon)\leq(1+\varepsilon)OPT(I)\;.</math>
Předpokládejme, že algoritmus <math>ALG</math> je aproximační schéma a očekává na vstupu instanci <math>I\in D_A</math> a racionální číslo <math>\varepsilon</math>. Pomocí <math>ALG_\varepsilon</math> označíme instanci algoritmu <math>ALG</math>, kde hodnota <math>\varepsilon</math> je zafixována, vstupem <math>ALG_\varepsilon</math> je tedy jen instance <math>I\in D_A</math> a běh i výstup <math>ALG_\varepsilon</math> na vstupu <math>I</math> jsou totožné s algoritmem <math>ALG</math> se vstupem <math>I</math> a <math>\varepsilon</math>.
* Řekneme, že <math>ALG</math> je '''polynomiální aproximační schéma''' ('''PAS'''), pokud je pro každé <math>\varepsilon</math> časová složitost algoritmu <math>ALG_\varepsilon</math> polynomiální v <math>len(I)</math>, kde <math>ALG_\varepsilon</math> označuje algoritmus vzniklý dosazením konstanty <math>\varepsilon</math> do <math>ALG</math>
* Řekneme, že <math>ALG</math> je '''úplně polynomiální aproximační schéma''' ('''ÚPAS'''), pokud <math>ALG</math> pracuje v čase polynomiálním v <math>len(I)</math> a <math>\frac{1}{\varepsilon}</math>.
{{theorem
| Nechť <math>A</math> je optimalizační úloha, jejíž přípustná řešení mají nezápornou celočíselnou hodnotu. Předpokládejme, že ∃ polynom dvou proměnných <math>q</math>, který pro každou instanci <math>I ∈ DA</math> splňuje: <math>OPT(I) < q(len(I), max(I))</math>. Pokud ∃ úplně polynomiální aproximační schéma pro úlohu <math>A</math>, pak ∃ i pseudopolynomiální algoritmus pro <math>A</math>.
|
}}
💡 '''Důsledek :''' Nechť <math>A</math> je silně NP-úplná optimalizační úloha, která splňuje předpoklady věty. Pokud <math>P = NP</math>, pak neexistuje úplně polynomiální aproximační schéma pro úlohu <math>A</math>.
{{theorem
| Pokud existuje polynomiální aproximační algoritmus <math>ALG</math> pro úlohu obchodního cestujícího s aproximačním poměrem <math>ε</math>, kde <math>ε > 1</math> je konstanta, potom <math>P = NP</math>.
|
}}
[[Image:Schemes-input.jpg|right|thumb|502px|'''💡 př. použití aprox.schématu''': <math>I</math> je moc složitá pro přímé nalezení <math>OPT</math>, zjednodušíme jí tedy a získáme řešení <math>ALG_\varepsilon(I)</math> to ještě můžeme přeložit zpět na řešení odpovídající původní instanci <math>I</math> (u BAPX to ani není nutné)]]
===Příklad aproximačního schématu pro Batoh - BAPX===
* '''Vstup:''' Pole <math>s</math> velikostí předmětů a pole <math>v</math> cen předmětů, obě délky <math>n</math>, velikost batohu <math>B</math>, racionální číslo <math>\varepsilon>0</math>. Předpokládáme, že <math>(\forall i\in\{1, \dots, n\})\;\big[0<s[i]\leq B\big]</math>
* '''Otázka:''' Množina M předmětů, jejichž souhrnná velikost nepřesahuje B.
<math>BAPX(s, v, B, \varepsilon)</math>
:# Spočti index m, pro nějž je <math>v[m] = max_{1\leq i\leq n} v[i]</math>.
:# if (<math>\varepsilon \geq n - 1</math>) return {m}
:# <math>t = ⌊log_2( \varepsilon v[m]/n )⌋ - 1</math>
:# c je nové pole délky n.
:# for (<math>i= 1; i\leq n;i++</math>) <math>c[i] = ⌊v[i]/2^t⌋</math>
:# 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 <math>ε</math>
{{theorem
| Schéma BAPX pracuje v čase <math>O(\frac{1}{\varepsilon}n^3)</math>. Pro libovolnou instanci <math>I = ⟨s, v, B⟩</math> úlohy Batoh a libovolné <math>ε > 0</math> platí, že <math>OPT(I) ≤ (1 + ε) BAPX(I, ε)</math>.
| Algoritmus BAPX je <math>O(\frac{1}{\varepsilon}n^3)</math>
}}
==coNP, #P - def. a vlastnosti==
Definice (Nesplnitelnost KNF (UNSAT), úloha):
* '''Instance :''' Formule <math>φ</math> v KNF
* '''Otázka''' : Platí, že pro každé ohodnocení v je <math>φ(v) = 0</math>?
* '''Poznámka''': Nevíme, jak by měl vypadat polynomiálně ověřitelný důkaz toho, že formule <math>φ</math> je nesplnitelná, ale můžeme najít polynomiálně ověřitelný protipříklad, tedy důkaz toho, že <math>φ</math> není nesplnitelná { = je splnitelná}, protože <math>SAT</math> patří do NP.
=== coNP ===
[[Image:Chpvenndiagram.jpg|right|thumb|346px|<math>coNP</math>]]
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 <math>coNP</math> a pro libovolný jiný jazyk <math>B ∈ co-NP</math> platí, že <math>B ≤^m_p A</math>.
{{lemma | Jazyk <math>A</math> je co-NP-úplný ⇔ <math>\overline A</math> je NP-úplný. }}
{{lemma | Patří-li některý NP-úplný jazyk do <math>coNP</math>, pak <math>NP=coNP</math> { nepředpokladané }. }}
{{lemma | <math>P ⊆ ( NP ∩ coNP)</math> { předpoklad, že <math>P ⊊ NP ∩ coNP</math> }. }}
=== #P ===
Funkce <math>f</math> patří do '''třídy #P''', pokud existuje binární relace <math>R</math> v NPF a <math>\forall x</math>: <math>f(x) = |\{y | (x, y) ∈ R\}|</math>.
Pak <math>f</math> je '''početní úlohou asociovanou s <math>R</math>''', značíme pomocí <math>\#R = f</math>.
{{lemma | Pro každý problém <math>A ∈ NP</math> <math>∃</math> relace <math>R_A</math> v NPF, tak že platí: <math>x ∈ A ⇔ \#RA(x) > 0</math>. }}
;Dk
: Relace RA bude obsahovat dvojice <math>(x, y)</math>, kde <math>y</math> je polynomiálně velký certifikát dosvědčující to, že <math>x ∈ A</math>.
{{lemma | Výpočet <math>f ∈ \#P</math> lze provést za pomoci polynomiálně mnoha dotazů na náležení prvku do množiny <math>\{(x, N) | f(x) ≥ N\}</math>. }}
;Dk
: Protože <math>f ∈ \#P</math>, existuje relace <math>R ∈ NPF</math>, pro kterou platí, že <math>f = \#R</math>. Z definice plyne, že existuje polynom p, pro který platí, že pokud <math>(x, y) ∈ R, pak |y| ≤ p(|x|)</math>. To <math>p(|x|)</math> znamená, že <math>f(x) ≤ 2</math> , pokud uvažujeme <math>x</math> i <math>y</math> jako binární řetězce. Binárním vyhledáváním <math>p(|x|)</math> najdeme hodnotu <math>f(x)</math> dotazy na <math>N = 0, . . . , 2p(|x|)</math> , protože binární vyhledávání pracuje v logaritmickém čase, bude nám na toto vyhledání stačit <math>p(|x|)</math> dotazů, je jich tedy polynomiálně mnoho.
{{lemma | Výpočet <math>f ∈ \#P</math>, <math>f(x)</math> lze provést v polynomiálním prostoru vzhledem k <math>|x|</math>. }}
;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 <math>f : \{0, 1\}* → N</math> je '''polynomiálně převoditelná''' na funkci <math>g : \{0, 1\}* → N</math>, pokud existují polynomiálně spočitatelné funkce <math>α : \{0, 1\}* × N → N</math> a <math>β : \{0, 1\}* → \{0, 1\}*</math> , pro které platí, že: <math>(∀x ∈ {0, 1} ) [f(x) = α(x, g(β(x)))]</math> ( odpovídá polyn. algoritmu, spočítá <math>f(x)</math> s jedním voláním <math>g</math> ).
Funkce <math>f : \{0, 1\}</math> je '''#P-těžká''', pokud je každá funkce <math>g ∈ \#P</math> polynomiálně převoditelná na <math>f</math>.
Funkce <math>f</math> je '''#P-úplná''', je-li '''#P-těžká''' a platí-li současně, že <math>f ∈ \#P</math>.
Nechť <math>A, B ∈ NPF</math> jsou binární relace, řekneme, že '''polynomiálně spočitatelná funkce <math>β</math> převádí <math>A</math> na <math>B</math> se zachováním počtu řešení''', pokud <math>∀x ∈ \{0, 1\}* : |\{y | (x, y) ∈ A\}| = |\{y | (β(x), y) ∈ B\}|</math>.
{{lemma | Nechť <math>A ∈ NPF</math> je taková, že libovolnou relaci z NPF lze na <math>A</math> 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 <math>φ</math> 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ť <math>φ</math> je formule v KNF, pomocí de-Morganových pravidel převedeme její negaci <math>¬φ</math> na DNF, kterou si označíme pomocí <math>ψ ≡ ¬φ</math>, pak platí, že: <math>\#KNF-SAT(φ) = 2n − \#DNF-SAT(ψ)</math>, kde <math>n</math> je počet proměnných formule <math>φ</math>. V převodu tedy funkce <math>ψ = β(φ)</math> 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
