Řešené otázky NTIN090: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Průnik se státnicovými otázkami)
(8. Pseudopolynomiální algoritmy, číselné problémy a silná NP-úplnost. Příklad pseudopolynomiálního algoritmu pro Batoh (🎓))
Řádka 527: Řádka 527:
 
==7. NP-úplnost Loupežníků (převod z Trojrozměrného párování)==
 
==7. NP-úplnost Loupežníků (převod z Trojrozměrného párování)==
 
==8. Pseudopolynomiální algoritmy, číselné problémy a silná NP-úplnost. Příklad pseudopolynomiálního algoritmu pro Batoh (🎓)==
 
==8. Pseudopolynomiální algoritmy, číselné problémy a silná NP-úplnost. Příklad pseudopolynomiálního algoritmu pro Batoh (🎓)==
 +
''silná NP-úplnost''
 +
* záleží na dvou proměnných:
 +
** 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)
 +
* lze ukázat na obchodním cestujícím. Max(I) je v tomto případě největší vzdálenost mezi městy
 +
 
==9. Aproximační algoritmy - definice a příklad (🎓)==
 
==9. Aproximační algoritmy - definice a příklad (🎓)==
  

Verze z 6. 11. 2014, 17:17

Obsah

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

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

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

Vyčíslitelnost

1. 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.

1.1 Turingův stroj

  • (k-páskový deterministický) TS je 5-tice: M = (Q, ∑, δ, q0, F)
    • Q je konečná množina stavů (řídící jednotky)
    • ∑ je konečná pásková abeceda
      • obsahuje znak λ pro prázdné políčko
    • $ δ : Q \times ∑^k -> Q \times ∑^k \times \{R, N, L\}^k ∪ \{⊥\} $ je přechodová fce
      • ⊥ je nedefinovaný přechod
    • q0 ∈ Q je počáteční stav
    • F ⊆ Q je množina přijímajících stavů.
  • Konfigurace TS obsahuje:
    • stav řídící jednotky
    • slovo na pásce
      • 💡 (od nejlevějšího neprázdného políčka do nejpravějšího)
    • pozice hlavy na pásce
      • 💡 čtené políčko v rámci slova
  • 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ý

1.2 Rekurzivní a rekurzivně spočetný jazyk

  • L(M) označíme jazyk slov přijímaných TS M
  • L je rekurzivně spočetný (také částečně rozhodnutelný), pokud ∃TS M t.ž.: L = L(M).
  • L je rekurzivní (také rozhodnutelný), pokud ∃TS M t.ž.: sevždy zastaví a L = L(M)

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

💡 každý rekurzivní jazyk je i rekurzivně spočetný

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

  • L je RJ ⇒ L' je RJ
  • L i L' jsou RSJ ⇒ L je RJ

z toho nám vyjde:

1.4 Postova věta

Věta ( Postova ) L je RJ ⇔ L i L jsou RSJ

Dk (přes oba směry implikace)
⇒ L je RS pro L vytvořím TS M, 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ý A)

2. GČ, UTS

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

2.1 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Č

2.2 Univerzální Turingův stroj

  • Univerzální Turingův stroj U umí simulovat libovolný jiný TS M nad libovolným vstupem w.
    • U dostane na vstupu kód e stroje M a vstup w a vrátí stejný výsledek, jako by vrátil M na vstupu w.
      • 💡 tj.: U(e,w) ≃ M(w)
      • 💡 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.
    • UTS skončí, pokud by M skončil
      • 💡 Pokud se M(w) zacyklí, musí se zacyklit i U(e,w)
    • přijme, pokud by M přijal
    • na pásce zanechá slovo, které by na ní zanechal M
      • 💡 tj.: počítá stejnou funkci.
  • UTS jako 4-páskový TS (technicky jednodušší než 1-páskový)
    • 💡 lze převést na 1-páskový
    • Vstupní páska
      • kód simulovaného stroje M a jeho vstup.
      • oddělovač ’;’ z abecedy Γ.
      • 💡 pouze se čte a na závěr na ni přepíše obsah pásky stroje M po ukončení jeho výpočtu.
    • Pracovní páska M
      • uložení slova z pracovní pásky M
      • Připomeňme si, že páskovou abecedu stroje M jsme nijak neomezovali, její znaky si na tuto zakódujeme v binární abecedě stejně, jako je tomu v kódu přechodové funkce M.
      • Ať b označuje délku nejdelšího zápisu znaku páskové abecedy v kódu w Turingova stroje M (dá se tedy s jistou rezervou říci, že hodnota b odpovídá \lceil log2 |Σ| \rceil, kde Σ je pásková abeceda simulovaného stroje M.
      • Pak tato páska bude rozdělena do bloků délky b oddělených symbolem „|“.
      • Každý blok bude kódovat obsah políčka pracovní pásky stroje M týmž způsobem, jakým je daný znak zakódovaný v kódu w přechodové funkce stroje M, doplněný nulami na začátku na délku b (jde o binárně zapsané číslo symbolu, jehož hodnotu nuly přidané na začátek nemění).
      • Polohu hlavy stroje M si UTS pamatuje polohou hlavy na této pracovní pásce.
    • Stavová páska M
      • stav, v němž se aktuálně stroj M nachází.
      • Stav $ q_i $ stroje M zakódován jako $ (i)_B $
        • 💡 $ (i)_B $ - číslo i zapsané binárně.
        • 💡 totéž číslo, co lze vyčíst z přechodové funkce M uložené v řetězci w na 1. pásce

Algoritmus UTS

  1. Init
    • kontrola vstupu: kontrola správnosti vstupní pásky
    • příprava prac.pásky: překódujeme vstup na pracovní pásku, návrat na začátek pásky
    • příprava stav.pásky: na stavovou pásku zapíšeme 0 (💡 binárně zapsané číslo stavu q0)
  2. Simulace
    • simuluj kroky M dokud ex. instrukce pro konfiguraci
  3. Zakončení
    • úklid: přepíše obsah pracovní pásky do abecedy {0,1}
    • konec: přečte stavovou pásku a podle stavu přejde do přijímacího/odmítacícího stavu

3. Algoritmicky nerozhodnutelné problémy (🎓)

  • diagonalizační jazyk LDIAG = {wi ∈ {0, 1}* | wi ∉ L(Mi) }
    • LDIAG není rekurzivně spočetný (tedy ani rekuznivní)
  • univerzální jazyk Lu = L(U)
    • Lu je rekurzivně spočetný, ale není rekurzivní
  • problém zastavení LHALT = {w; x | w kóduje TS M a M(x) ↓}
    • LHALT je rekurzivně spočetný, ale není rekurzivní
      • 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

4. Def. PRF a ČRF, RP a RSP. Základní vlastnosti.

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

4.1 PRF - primitivně rekurzivní fce ⇐ existuje její odvození ze 3 základních funkcí pomocí 2 operátorů substituce a prim. rekurze (NE minimalizace) (🎓)

  • podmíněná rovnost ≃
    • f(x1,...,xn) ≃ g(x1,...,xn) znamená: hodnota f(x1,...,xn) je definována ⇔ definována i hodnota g(x1,...,xn), a pak jsou si také rovny
  • Základní funkce
    • nulová (konstantní) funkce o(x) = 0 (∀x)
    • následník s(x) = x + 1 (∀x)
    • projekce $ I^j_n (x1, ..., xj, ... , xn) = xj $ (∀j,n: 1 ≤ j ≤ n)
      • 💡 vrací hodnotu j-tého parametru
  • Operátory
    • substituce $ S^m_n(f,g1,...,gm) = h $ kde: h(x1,...,xn) ≃ f(g1(x1,...,xn),...,gm(x1,...,xn))
      • 💡 f funkce m proměnných a g1, ... , gm jsou funkce n proměnných
      • 💡 Operátor substituce je základní prvek programování — jednoduše úlohu, kterou mám řešit, vyřeším pomocí funkcí, které už naprogramoval někdo dřív.
    • primitivní rekurze $ R_n(f,g) = h $
      • kde:
        • h(0, x2, ..., xn) ≃ f(x2, ..., xn)
        • h(i+1, x2, ..., xn) ≃ g(i, h(i,x2,...,xn), x2,..., xn)
      • 💡 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

4.1.1 PRP - primitivně (obecně) rekurzivní predikát <= jeho charakteristická funkce je PRF (ORF)

  • predikát $ R(x_1,...,x_n) $ je relace nebo libovolný fakt o n proměnných
  • charakteristická fce predikátu R je
    • $ \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} $
    • 💡 char. fce je ORF

4.2 ČRF - částečně rekurzivních fce (partial μ-recursive functions) ⇐ lze odvodit ze 3 základních funkcí pomocí 3 operátorů (🎓)

Nový operátor

  • minimalizace Mn(f) = h
$ \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\} $
  • 💡 tj.: 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.
  • 💡 Je vidět, že operátor minimalizace má sílu while-cyklu.
  • 💡 Poslední proměnná ve funkci f má zvláštní význam. Snažíme se ji minimalizovat, to jest najít nejmenší y takové, aby f vracela nulu.
  • 💡 Pokud se jako f předá funkce, která nikdy nevrací nulu, tak operátor minimalizace vytvoří funkci, která nebude nikde definovaná (výše uvedený pseudokód se zacyklí). To se u předchozích operátorů stát nemohlo: pokud dostaly na vstupu všude def. fce, vrátily také všude def. funkci.
  • 💡 Pokud nechceme zavádět nulární funkce, je nutné definici operátoru minimalizace doplnit o podmínku, že f je funkce alespoň dvou proměnných.
  • 💡 Místo ↓= (zkratka za konverguje a rovná se) bychom v definici klidně mohli psát jen =. Použití ↓≠ (zkratka za konverguje a nerovná se) je ale důležité, například pokud f(x1,...,xn,0)↑, tak h(x1,...,xn) také není definováno, i kdyby třeba f(x1,...,xn,1)=0.
  • μy[P(x,y)]- fce μ vrátí nejmenší y takové, aby platil predikát P(x,y)
    • Lze jí sestrojit pomocí operátoru minimalizace
  • 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)

4.2.1 RSP - rekurzivně spočetný predikát ⇐ jeho charakteristická funkce je ČRF

  • proč to kučera def.jinak?
  • 💡 je def.oborem nějaké ČRF

4.3 Jejich základní vlastnosti

PRF⊂ORF⊂ČRF

ZSV 5.png

  • uzavřenost na aritmetické operace
    • (konečný součet a součin) f je PRF 2 proměnných ⇒ je PRF:
      • $ g(z, x)=\sum_{y<z}f(y, x) $ (přičemž $ g(0, x)=0 $)
      • $ h(z,x)=\prod_{y<z}f(y, x) $ (přičemž $ h(0, x)=1 $)
    • (důsledek) f je PRF 1 proměnné ⇒ je PRF:
      • $ g(z)=\sum_{y<z}f(y) $ (přičemž $ g(0)=0 $)
      • $ h(z)=\prod_{y<z}f(y) $ (přičemž $ h(0)=1 $)
  • (podmíněný příkaz) - analogie switch/case/if-then
    • $ g_1(x), \dots, g_n(x) $, $ n>0 $ jsou PRF a $ R_1(x), \dots, R_n(x) $ jsou PRP a $ \forall x\in{\mathbb N} $ je splněn !1 z nich.
    • ⇒ tato fce $ f $ je PRF: $ \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} $
  • kvantifikátory (omezené i neomezené).
    • (omezená kvantifikace)
    $ P $ binární PRP ⇒ $ V_P(z, x)=(\forall y<z)[P(y, x)] $ a $ E_P(z, x)=(\exists y<z)[P(y, x)] $ jsou PRP.
  • (ne)uzavřenost na logické spojky
    • (logické spojky)
    $ P $ a $ R $ unární PRP ⇒ $ R\wedge P $, $ R\vee P $ a $ \neg P $ jsou PRP
    • (konečná konjunkce a disjunkce)
    $ P $ binární PRP ⇒ $ A(x, z)=\bigwedge_{y<z}P(x, y) $ a $ B(x, z)=\bigvee_{y<z}P(x, y) $ jsou PRP
  • (omezená minimalizace)
    $ P $ binární PRP ⇒ tato $ f $ je PRF:
    $ f(x, z)= \begin{cases} \min\{y<z\;|\;P(x, y)\} \quad &\mbox{pokud takové y existuje}\\ z \quad &\mbox{jinak.} \end{cases} $
    Funkci $ f $ budeme také označovat pomocí $ f(x, z)=\mu y<z[P(x, y)] $.

5. ČRF ⇔ TS, Kleenova v., UČRF, s-m-n v. (🎓)

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

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

Věta ( ČRF ⇒ TS ) $ h $ je ČRF $ n $ proměnných ⇒ $ h $ je Turingovsky vyčíslitelná

  • Přesněji, existuje Turingův stroj $ M_h $ takový, že pro každou $ n $-tici přirozených čísel $ x_1, x_2, \dots, x_n $ platí
$ M_h((x_1)_B\#(x_2)_B\#\dots\# (x_n)_B)\downarrow\Leftrightarrow h(x_1, x_2, \dots, x_n)\downarrow $
a platí-li $ h(x_1, x_2, \dots, x_n)\downarrow=y $, potom výpočet Turingova stroje $ M_h $ vydá na výstupu řetězec $ (y)_B $.
Dk (zakladni funkce vycislim; substituci provedu paralelne na nekolika paskach; prim. rekurzi delam pocitadlem cyklu; minimalizaci taky)
definujeme TS pro základní funkce a operátory pro odvození $ h $:
  • Základní fce
    • nulová funkce $ o(x)=0 $
      • ekvivalentní této operaci na TS: smaže celou pásku a zapíše 0
    • následník $ s(x) $
      • implementuje přičtení 1 k bin.číslu
    • projekce $ I^j_n (x_1,..,x_n) $
      • smaze j-1 bloků
      • přeskočí j
      • smaže zbytek
      • vrátí se na začátek
  • Operátory
    • substituce $ S_n^m $
kde: $ h(x_1,...,x_n) ≃ f(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n)) $
  • 3 pásky:
  • na 1. pásce je vstup
  • postupne simulujeme stroje $ M_gi $ na 2. pásce, výsledky prekopirujeme na konec 3.
  • na 3. pasce pustime stroj $ M_f $
  • výsledek je na 3.
  • primitivní rekurze $ R_n $
kde: $ h(0, x_2, ..., x_n) ≃ f(x_2, ..., x_n) $
$ h(i+1, x_2, ..., x_n) ≃ g(i, h(i,x_2,...,x_n), x_2,..., x_n) $
  • 3 pásky (for-cyklus):
  • na 1. pásce je vstup, na 2.pásce 0 (čítač pro for), na 3. je 1. bez prvního čísla
  • na 3. pustíme $ M_f $
  • dokud je číslo na 2. < číslo na začátku 1.
  • 2.pásku zkopírujem před výsledek na 3. a na konec zkopirujem 1. (bez prvního čísla)
  • na 3. pasce pustime stroj $ M_g $
  • výsledek je na 3.
  • minimalizace $ M_n(\mathbf{f})=\mathbf{h} $
$ \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\} $
  • 2 pásky (while-cyklus):
  • na 1. pásce je vstup + #0 (čítač pro while)
  • dokud simulace $ M_f $ na 2.pásce nevrátí 0
  • smaz 2. a nahraj naní 1. pásku s čítačem+1
  • nasimuluj $ M_f $ na 2.
  • čítač y zapiš na 1.

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


Věta ( TS ⇒ ČRF ) funkce $ f $ turingovsky vyčíslitelná ⇒ je $ f $ ČRF

Dk
idea:
  • 1 krok TS je PR (omezené cykly)
  • TS pracuje, dokud neskončí = while-cyklus (tj. minimalizace)
  • program = minimalizace čehosi, kde to cosi už je PR
postup:
  • zakóduju výpočet (tj: posloupnost konfigurací Ki) TS do stringu: K1;...;Kt
  • sestavím PRP predikát T(č.TS, x, č.kódu výpočtu TS), který kontroluje, zda řetězec kóduje výpočet TS
  • na predikát pustím minimalizaci y
  • z ní vytáhnu g.číslo poslední konfigurace
  • $ f(x)=\cal U(\mu y[T(e, x, y)]) $
  • U je zřejmě PRF
  • f je def. jako tur. vyčíslitelná

5.2 Kleenova věta o NF (bez převodu ČRF na TS)

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

Věta ( Kleenova věta o normální formě ) $ \exists PRF \quad \cal U(y) $ a PRP $ T_n(e, x_1, \dots, x_n, y) $, pro které platí:

$ (\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)]) $

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

Dk

podle důkazu TS ⇒ ČRF

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

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

5.3 univerzální ČRF

       \textsf{\textbf{(O univerzální funkci)} \\\forall třídu proměnných $n>0$ \exists univerzální ČRF:  $\varphi_z^{(n+1)}(e, x_1, \dots, x_n)$ taková, že\\ $\varphi_z^{(n+1)}(e, x_1, \dots, x_n)=\varphi_e^{(n)}(x_1, \dots, x_n)$\\ (vyčísluje e-tou funkci)
           existuje i univerzální funkce, a to pro každou třídu n  proměnných (takže ta univerzální funkce pak dostane těch n  proměnných + číslo funkce, kterou má emulovat, a udělá to), přičemž je docela pěkná (je ve tvaru minimalizace PRP)
       Dk:
           podle Kleeneovy:
           \latex \textsf{$\varphi_z^{(n+1)}(e, x_1, \dots, x_n) \simeq\cal U(\mu y[T_n(e, x_1, \dots, x_n, y)])

5.4 s-m-n věta

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

Věta ( s-m-n ) $ \forall $ m,n > 0 $ \exists $ prostá PRF $ s_n^m $ a $ \forall $x, y1, … , ym platí: $ \varphi_{(n)}^{s_n^m(x,y1,.., ym)} = \lambda z1..zn[\varphi_x^{(m+n)}(y_1, .., y_m, z_1, .., z_n)] $

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

část argumentů (včetně čísla programu) zafixujeme,
dostaneme funkci zbytku těch argumentů,
a tato funkce bude hezká (PRF).
Původní funkce má argumentů m+n, zafixujeme prvních m a pak už máme jen těch zbylých n.
Dk
$ s=s_n^m(x, y_1, y_2, \dots, y_m) $, na vstupu dostane z-ka a pustí $ M_x $ na vstup y-nek a z-tek

6. 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. (🎓)

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

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

9. 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í.

Problém zastavení $ K_0 $ a jeho diagonála $ K $:

  • $ K_0 =\{\langle x, y\rangle_2\;|\;\varphi_x(y)\downarrow\}=\{\langle x, y\rangle_2\;|\;y\in W_x\} $
  • $ K =\{x\;|\;\varphi_x(x)\downarrow\}=\{x\;|\;x\in W_x\} $
  • $ K_1 =\{x\;|\;W_x\neq\emptyset\} $

Věta ( $ K $, $ K_0 $ RSM $ \neg $RM ) $ K $ a $ K_0 $ jsou RSM, ale nejsou RM


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

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

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

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

9.1 vlastnosti

  • $ A\leq_m B $ a $ B $ RM $ \Rightarrow A $ RM
    • 💡 $ A\leq_m B $ a $ A $ není RM $ \Rightarrow B $ není RM
      • protože: $ (A\Rightarrow B)=(\neg B\Rightarrow \neg A) $
  • $ A\leq_m B $ a $ B $ RSM $ \Rightarrow A $ RSM
    • 💡 $ A\leq_m B $ a $ A $ není RSM $ \Rightarrow B $ není RSM
  • $ \leq_m $ a $ \leq_1 $ (relace) jsou reflexivní a tranzitivní
  • $ A $ $ m $-úplná & $ B $ RSM & $ A\leq_m B \Rightarrow B $ je $ m $-úplná
    • 💡 platí pro 1-převoditelnost a 1-úplnost
  • $ A\leq_mB \Rightarrow \overline A\leq_m\overline B $
    • 💡 platí pro 1-převoditelnost a 1-úplnost

Věta ( 1-úplnost $ K $, $ K_0 $ ) Množiny $ K $ a $ K_0 $ jsou 1-úplné.

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

Věta ( Rice ) $ \cal C $ třída ČRF, $ A_\cal C = \{e | \varphi_e ∈ C\} $ je RM ⇔ $ \cal C = \emptyset $ nebo $ \cal C $ obsahuje všechny ČRF

💡  $ A_\cal C $ je mnozina indexu (Gödel.č.) funkci z třídy $ \cal C $ 💡  bud C netrivialni trida nejakych CRF; pak mnozina indexu funkci ve tride $ B=\{e|φ_e \in C\} $ je nerekurzivni

Dk
předpokládejme že C NEní ∅ a C NEobsahuje všechny ČRF
ukážeme sporem že K ≤1Ac
e0 je gč fce nedef.pro žádný vstup a φe0∈C' e1 je gč fce φe1∈C a φe0≄ φe1
φe2≄ φe1je-li x ∈ K ≄ ↑
φe2(x , y) ≃ φs11(e, x) (y) ≃ φf(x)(y)
x∈K ⇒ φf(x)≃φe1 ⇒ φf(x)(y) ∈ C ⇒ f(x) ∈ Ac x∉K ⇒ φf(x)≃φe0 ⇒ φf(x)(y) ∉ C ⇒ f(x)∉ Ac
tedy x ∈ K ⇔ f(x) ∈ Ac

11. Věta o rekurzi a její jednoduché důsledky (ne Riceova věta). (🎓)

12. Riceova věta - důkaz pomocí věty o rekurzi. (🎓)

Věta ( Rice ) $ \cal C $ třída ČRF, $ A_\cal C = \{e | \varphi_e ∈ C\} $ je RM ⇔ $ \cal C = \emptyset $ nebo $ \cal C $ obsahuje všechny ČRF

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


Dk (sporem)
předpokládejme že C NEní ∅ a C NEobsahuje všechny ČRF
předpokládejme sporem že Ac je rekurzivní
definujme si fci f:
  • f(x) = a x∉$ A_\cal C $
  • f(x) = b x∈$ A_\cal C $
    • f je ORF
    • a∈$ A_\cal C $
    • b∉$ A_\cal C $
n je pevný bod f a φn≃ φf(n)
φn∈C ⇒ n ∈ Ac ⇒ f(n)=b ⇒ f(n)∉ Ac ⇒ φf(n)∉C
φn∉C ⇒ n ∈ Ac ⇒ f(n)=a ⇒ f(n)∈ Ac ⇒ φf(n)∈C
⇒ spor

Složitost

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

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

prakticky otázka z bakaláře, očekává se nějaké neroubová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.


0.2 Hladový algoritmus

0.3 Amortizovaná složitost

1. 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 (🎓)

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

   typy problémů
       odpověď typu ano/ne - rozhodovací problém
       vstup - instance problému
       úloha - pro daný vstup x nalézt y  co splňuje požadovanou vlastnost
   \latex Nechť $f:\mathbf N\mapsto\mathbf  N$ je libovolná funkce, \\ pak definujeme následující třídy jazyků a relací (tj. problémů a úloh):
       \latex \textsf{ $DTIME(f(n))$, jazyk $L\subseteq\{0, 1\}^*$ patří do třídy $DTIME(f(n))$, pokud existuje TS $M$ takový, že $L=L(M)$ a pro každé slovo $x$ délky $n$ skončí výpočet $M(x)$ nejvýše po $O(f(n))$ krocích.
       \latex \textsf{ $DSPACE(f(n))$, jazyk $L\subseteq\{0, 1\}^*$ patří do třídy $DSPACE(f(n))$, pokud existuje TS $M$ takový, že $L=L(M)$ a pro každé slovo $x$ délky $n$ použije výpočet $M(x)$ během své práce nejvýše $O(f(n))$ buněk pracovní pásky.
       \latex \textsf{ $DTIMEF(f(n))$, relace $R\subseteq\{0, 1\}^*\times\{0, 1\}^*$ patří do třídy $DTIMEF(f(n))$, pokud existuje TS $M$, jehož výpočet nad vstupem $x$ délky $n$ se zastaví po nejvýše $O(f(n))$ krocích, $M(x)$ přijme, právě když existuje $y$, pro nějž $(x, y)\in R$, a v tom případě obsahuje po ukončení výpočtu jeho páska toto slovo $y$
           Lze to také říci tak, že selektor pro predikát R je funkce spočitatelná v polynomiálním čase.
   \latex \textsf{$ \begin{align} P&= \bigcup_{i\in \mathbb N}DTIME(n^i)\\ PSPACE&=\bigcup_{i\in\mathbb N}DSPACE(n^i)\\ PF&=\bigcup_{i\in\mathbb N}DTIMEF(n^i) \end{align} $\\ Třída $P$ tedy obsahuje problémy rozhodnutelné v polynomiálním čase, třída $PSPACE$ obsahuje problémy rozhodnutelné v polynomiálním prostoru a konečně třída $PF$ obsahuje úlohy řešitelné v polynomiálním čase.

1.2 Definice třídy NP

   \latex \textsf{ Binární relace $R\subseteq\{0, 1\}^*\times\{0, 1\}^*$ patří do třídy  $NPF$, pokud platí:
       \latex Existuje polynom $p(n)$, pro který platí, že v~každé dvojici $(x, y)\in R$ je $|y|\leq p(|x|)$ a
       \latex ověření toho, zda $(x, y)\in R$ lze provést v~polynomiálním čase.
       \latex Třídu polynomiálně ověřitelných úloh nazveme $NPF$, kde $NP$ znamená nedeterministicky polynomiální a $F$ znamená funkce, název tak volíme proto, že jde o~úlohy řešitelné nedeterministickým Turingovým strojem v~polynomiálním čase, i když k~tomu se dostaneme později.

pomocí certifikátů

  • Jazyk $$ L\subseteq\{0, 1\}^* $$ patří do třídy $$ \mathrm NP $$, pokud existuje polynom $p$ a jazyk $$ B\in P $$ a pokud pro každé $$ x\in\{0, 1\}^* $$ platí, že $$$ x\in L\Leftrightarrow (\exists y)\;\Big[|y|\leq p(|x|)\mbox{ a }(x, y)\in B\Big]. $$$
    • Neformálně řečeno jazyk $L$ patří do třídy $\mathrm NP$, pokud existuje polynomiální algoritmus (daný jazykem $B$), který je schopen ověřit, že polynomiálně dlouhý certifikát $y$ dosvědčuje fakt $x\in L$. Je opět nutné uvažovat pouze polynomiálně dlouhé certifikáty, neboť složitost ověřování se měří vzhledem k~délce $x$ i certifikátu $y$.

pomocí nedeterministických strojů

  • Nedeterministický Turingův stroj je pětice $$ M=(Q, \Sigma, \delta, q_0, F) $$, jejíž prvky mají týž význam jako v případě deterministického TS s tím rozdílem, že $$\delta:Q\times\Sigma\mapsto\cal P(Q\times\Sigma\times\{R, N, L\}).$$ Tj. danému stavu a symbolu na pásce přiřazuje několik přechodů do jiných stavů se zápisem různých symbolů a s různými pohyby. V případě, že množina možných přechodů je prázdná, není přechod definován.
       \latex Nechť $f:\mathbb N\mapsto\mathbb N$ je libovolná funkce, pak definujeme \\ následující třídy jazyků a relací (tj. problémů a úloh):
           \latex $NTIME(f(n))$, jazyk $L\subseteq\{0, 1\}^*$ patří do třídy $NTIME(f(n))$, pokud existuje NTS $M$, který pracuje v čase $O(f(n))$ a $L=L(M)$.
           \latex $NSPACE(f(n))$, jazyk $L\subseteq\{0, 1\}^*$ patří do třídy $NSPACE(f(n))$, pokud existuje NTS $M$, který pracuje v prostoru  $O(f(n))$  a $L=L(M)$.

a jejich ekvivalence

       \latex $NP=\bigcup_{i\in\mathbb N} NTIME(n^i)$
       Dk:

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

   A≤mpB (polynomiálně převoditelný) pokud ∃ f: {0,1}*→{0, 1}* spočitatelná v polynomiálním čase a platí: x ∈A  ⇔f(x) ∈B
   vlastnosti
       \latex $\leq_m^p$ je reflexivní a tranzitivní.
       \latex $A\leq_m^pB$ a $B\in P$ ⇒ $A\in P$
       \latex $A\leq_m^pB$ a $B\in NP$ ⇒ $A\in NP$
   \latex \textsf{Jazyk $A$ je \textbf{NP-těžký}, pokud pro každý jazyk $B\in NP$  platí, že $B\leq_m^pA$.
   O jazyku A řekneme, že je NP-úplný, pokud je NP-těžký  a navíc patří do třídy NP.
       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
   A,B ∈ NP,A≤mpB aA je NP-úplný ⇒B  je NP-úplný

2. Savičova věta.

3. Cookova-Levinova věta - NP-úplnost Kachlíkování (🎓)

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.
Cook-Levin
KACHL je NP-úplný problém.

💡  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?


Myšlenka důkazu:

  • Kachl je v NP (jistě jde verifikovat v polynomiálním čase)
  • Kachl je NP těžký
    • Vezměme libovolný problém z NP, pak jeho nedeterministický turingáč řeší, jestli $ I \in L $ (zda řetězec $ I $ patří do jazyka $ L $, neboli zda jeho nedeterministický turingáč přijme daný vstup $ I $) v polynomiálním čase polynomu $ P $
    • Zkonstruujeme síť $ P\times P $, zkonstruujeme vhodné kachličky (7 druhů) a obravení (barvy jsou z množiny $ ABECEDA \cup STAVY \times ABECEDA \cup \lbrace q_l, q_r | q \in STAVY \rbrace $ tak, aby
      • Každý krok výpočtu kódoval jeden vykachličkovaný řádek
      • Každý řádek popisoval jeden krok výpočtu
  • Tím jsme nalezli NP-úplný problém

4. NP-úplnost Splnitelnosti (převod z Kachlíkování).

5. NP-úplnost 3-Splnitelnosti (převod z obecné Splnitelnosti)

6. NP-úplnost Vrcholového pokrytí (převod z 3-Splnitelnosti)

7. NP-úplnost Loupežníků (převod z Trojrozměrného párování)

8. Pseudopolynomiální algoritmy, číselné problémy a silná NP-úplnost. Příklad pseudopolynomiálního algoritmu pro Batoh (🎓)

silná NP-úplnost

  • záleží na dvou proměnných:
    • 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)
  • lze ukázat na obchodním cestujícím. Max(I) je v tomto případě největší vzdálenost mezi městy

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

10. Aproximační schémata - definice a příklad aproximačního schématu pro Batoh (🎓)

11. Třídy co-NP a P - definice a vlastnosti.