24 - Parciální rekurzivní funkce, časová a paměťová složitost (třídy složitosti, úplnost, SAT problém) Flashcards
Hierarchie funkcí
- Všechny funkce
- Parciálně rekurzivní funkce - Vyčíslitelné funkce (parciální vyčíslitelné) ( primitivně rekurzivní + minimalizace, Občas zastaví, občas ne, ekvivalent TS)
- μ -rekurzivní funkce (totální vyčíslitelné) (V programování cyklus while: vždy skončí,ale nevím za jak dlouho,resp. nedokážu to odhanout ihned na počátku)
- Primitivně rekurzivní funkce (V programování cyklus for:vždy skončí, dokážu ihned v počátku definovat počet opakování)
- Počáteční funkce
Funkce definice (funkce, totální, parciální a striktně parciální funkce)
Funkce = jako funkci budeme označovat zobrazení f:N^m→N^n
Totální funkce = Definována pro celý definiční obor.
• Například +:
○ plus:N×N→N
○ plus(x,y)=x+y
totální je opak striktně parciální
Parciální funkce
• Nemusí být definována pro celý definiční obor (ale může).
Striktně parciální funkce
• Není definována pro celý definiční obor.
• Příklad /:
○ Nemůžeme dělit nulou.
Počáteční funkce
= stavební kameny vyšších funkcí -> Hiearchie vyčíslitelných funkcí je založena na dostatečně elementárních tzv. počátečních funkcích, které tvoří „stavební kameny“ vyšších funkcí.
Nulová funkce
• (ksí) zobrazuje prázdnou n-tici na 0
• ξ()=0
Funkce následníka σ:N→N
• (sigma) zobrazuje číslo na číslo o 1 větší
• σ(x)=x+1
Projekce π_k^n:Nn→N
• (pí) vybírá k-tou složku z n-tice
• např. π_2^3 (7,6,4)=6, speciální případ π_0^3 (7,6,4)=()
Primitivně rekurzivní funkce
Primitivně rekurzivní funkce jsou funkce tvořené z počátečních funkcí kombinací, kompozicí a primitivní rekurzí
• Každá primitivně rekurzivní funkce je totální funkce
• Většina prakticky použitelných funkcí v současných počítačích jsou primitivně rekurzivní funkce.
Alt.zápis: místo h≡plus∘(π_1^3×π_3^3) můžeme zapisovat h(x, y, z)= plus(x, z)=x+z
Kombinace f:Nk→Nm a g:Nk→Nn (x - řetězení)
• Výsledek je zřetězení výsledků f a g.
○ f×g:Nk→N(m+n)
○ Konvence: n-tici (x_1, x_2, …, x_n )∈N budeme oznacovat jako x ̅.
○ f×g(x ̅ ):(f(x ̅ ),g(x ̅ )), x∈Nk
○ Příklad: π_1^3×π_3^3 (4,12,8)=(4,8)
Kompozice f:Nk→Nm a g:Nm→Nn (g∘f, čteme jako “g po f”.)
• Provede funkci f a výsledek dá na vstup funkci g.
○ g∘f, čteme jako “g po f”.
• g∘f:Nk→Nn
• g∘f(x ̅ )=g(f(x ̅)),x∈Nk
• Příklad: σ∘ξ()=1, σ∘σ∘ξ()=2
Primitivní rekurze
• Umožňuje vytvořit funkci f:N(k+1)→Nm na základě funkcí g:Nk→Nm a h:N(k+m+1)→Nm
• f(x ̅,0)=g(x ̅ ) (g definuje konec rekurze pro hloubku 0)
• f(x ̅,y+1)=h(x ̅,y,f(x ̅,y)), x∈Nk (h definuje jak z výsledku nižší hloubky vytvořit výsledek vyšší hloubky)
Příklad:
Funkce násobení
Zřejme:
(a) Pro y = 0 platí x ∗ 0 = 0
(b) Pro y > 0 je výsledek x + mult(x, y − 1)
Takže funkci mult můžeme definovat následujícím předpisem:
mult(x, 0) = 0
mult(x, y + 1) = x + mult(x, y)
Parciálně rekurzivní funkce
Parciálně rekurzivní funkce
Parciálně rekurzivní funkce je funkce, kterou lze vytvořit z primitivně rekurzivních funkcí a minimalizace.
• Každá parciální rekurzivní funkce je Turingovsky vyčíslitelná.
• Každý TS lze převést na parciálně rekurzivní funkci.
Operátorem minimalizace se parciálně rekurzuvní funkce liší od primitivně rekurzivních funkcí - zavádí totiž do výpočtu funkce potenciálně nekonečný cyklus.!!!
Minimalizace
• Najde nejmenší y pro které g vrací 0 a všechny nižší hodnoty y mají definované výsledky v g.
• Pomocí techniky minimalizace vytvoříme funkci f:Nn→N na základě jiné funkce funkce g:N(n+1)→N, tak že definujeme f(x ̅ ) jako nejměnší hodnotu y z N, pro kterou g(x ̅,y)=0 a zároveň g(x ̅,z) je definována pro všechna nezáporná cená čísla menší než y.
1. g(x ̅,y)=0
2. g(x ̅,z) je definována pro ∀z
Notace: f(x ̅ )=μy[g(x ̅,y)=0]
Složitost - základní pojmy, church turingova teze
Church-Turingova teze říká, že každý algoritmus je implementovatelný jistým TS a můžzeme tedy složitost algoritmu chápat jako složitost TS (čas a prostor).
Složitost
Složitost je vyjádření použitých zdrojů jako funkce závisející na velikosti vstupu.
Určujeme:
• složitost nejhoršího případu (nejčastější)
• nejlepšího případu
• průměrného případu (vážený průměr dle pravděpodobnosti)
Časová složitost = Počet kroků výpočtu TS (cena kroků může být shodná nebo i rozdílná)
Paměťová (prostorová) složitost = Potřebný počet buněk pásky (nepočítáme vstup)
* Je-li prostorová složitost n pak časová složitost nemůže být nižší než n+1 (jednoduše by nebylo kdy toho tolik zapsat). * Je-li jazyk přijímán vícepáskovým TS v čase t(n) je také přijímán jednopáskovým TS v čase t(n)^2.
Asymptotické omezení složitosti
Pro dostatečně velké vstupy se složitost stále více blíží k asymptotické složitosti (s tolerancí danou násobením nějakými konstantami)
Nedeterminismus a složitost
Nedeterministický TS lze simulovat deterministickým TS , ale jen za cenu exponenciálního nárůstu času.
Nedeterminismus nepřináší nic z pohledu vyčíslitelnosti, ale výrazně ovlivňuje složitost.
P vs NP
Popis tříd P (polynomial) a NP (nondeterministic polynomial)
Třída složitosti P obsahuje všechny úlohy, jejichž řešení lze nalézt deterministickým Turingovým strojem v polynomiálním čase.
Pro třídu NP platí totéž s tím rozdílem, že úlohy jsou v polynomiálním čase řešitelné hypotetickým nedeterministickým Turingovým strojem, který dokáže současně testovat mnoho možností řešení. Jsou to tedy ty problémy, jejichž řešení lze ověřit v polynomiálním čase, ovšem nevíme, zda je lze také v polynomiálním čase nalézt.
P = NP ? (Otazka, zda jsou tridy slozitosti N a NP totozne) - existují úlohy, u kterých je jednodušší ověřit řešení, než je vyřešit?)
Problém P (polynomiální) versus NP (nedeterministicky polynomiální) je důležitý otevřený problém v teoretické informatice; označuje se tak otázka, zda jsou třídy složitosti P a NP totožné. Zjednodušeně řečeno jde o otázku, zda každý problém, u kterého dokáže počítač rychle ověřit správnost nabídnutého řešení, dokáže počítač také sám rychle vyřešit. Všeobecně se předpokládá, že platí P ≠ NP, tedy že existují úlohy, které je složitější vyřešit než ověřit platnost řešení. Důkaz však stále nebyl nalezen a tento problém je zařazený mezi sedm tzv. problémů tisíciletí.
Třídy složitosti
Časově konstruovatelná funkce f - časová složitost je závislá na vstupu
• Vícepáskový TS pro libovolný vstup w zastaví přesně po t(|w|) krocích (např. f(n)=n logn, ne např. f(n)=c)
Prostorově konstruovatelná funkce s - prostorová složitost je závislá na vstupu
• Vícepáskový TS pro libovolný vstup w zastaví s využitím přesně s(|w|) buněk pásky (např. s(n)=n logn, ne např. s(n)=c)
Nejběžněji používané třídy jsou P a NP. Potom máme ještě další třídy…
Redukce, úplnost
R-redukce
• Jazyk L1 je R-redukovatelný na L2 jestliže existuje funkce f třídy R taková, že w∈L_1⇔f(w)∈L_2 - značíme L_1 ≤_Rm L_2
• (tj. jde o převod jednoho problému na problém jiný převodní funkcí, která má složitost R)
Pokud je L1 P-redukovatelný na L2, který je ve třídě P, pak i L1 je ve třídě P.
Pokud je L1, který není ve třídě P, P-redukovatelný na L2, pak i L2 není ve třídě P.
Jazyk C-těžký (angl. C-hard) = všechny jazyky třídy C lze na tento jazyk redukovat
Jazyk C-úplný (angl. C-complete) = Jazyk L0 je C-úplný pokud je C-těžký a patří do třídy C
Např. NP-úplné (NP-complete, NPC) problémy jsou takové nedeterministicky polynomiální problémy, na které jsou polynomiálně redukovatelné všechny ostatní problémy z NP
SAT problém
SAT představuje NP-úplný problém. To ve zkratce znamená, že není znám žádný efektivní algoritmus řešící všechny instance SAT problému v polynomiálním čase. Obecně se předpokládá, že takový algoritmus neexistuje (není to však dokázáno, viz Problém P versus NP). Dále může být široká škála přirozeně se vyskytujících problémů při rozhodování a optimalizacích transformována jako SAT problém.
Po lopatě: Máme Boolean expression a snažíme se přijít na to, jestli existuje ohodnocení takové, které nám vrátí true.
• SAT-problém je NP-úplný vzhledem k P-redukci
• První problém, jehož NP-úplnost vzhledem k P-redukci byla dokázána
• Lze zkonstruovat NTS, který přijímá SAT v P čase (každý konkrétní SAT-problém můžeme zakódovat jediným řetězcem)
Cookův teorém
Libovolný NP problém lze P-redukovat na SAT-problém.
Cookův teorém
Cookův teorém
Libovolný NP problém lze P-redukovat na SAT-problém.
