20 - Časová a paměťová složitost
pátek 13. května 2016
10:32
Časová a paměťová složitost (třídy složitosti, úplnost, SAT problém).
[link]
[link]
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)
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)
Asymptotické horní omezení (Omikron) funkce 𝑓(𝑛) je množina funkcí:
Asymptotické dolní omezení (Omega) funkce 𝑓(𝑛) je množina funkcí:
Asymptotické oboustranné omezení (Theta) funkce 𝑓(𝑛) je množina funkcí:
Složitost výpočtu TS není příliš odlišná od současných počítačů.
Je-li prostorová složitost 𝒏 pak časová složitost nemůže být nižší než 𝒏+𝟏 (jednoduše by nebylo kdy toho tolik zapsat).
Je-li jazyk přijímán vícepáskovým TS v čase 𝒕(𝒏) je také přijímán jednopáskovým TS v čase 𝒕𝒏𝟐.
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 = NP ?
Problém P versus NP 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í.
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.
Třídy P a NP poprvé definoval americký informatik Stephen Cook.
Třídy složitosti
Třídy složitosti zavádíme jako prostředek ke kategorizaci (vytvoření hierarchie) problémů dle jejich složitosti.
𝐷𝑇𝑖𝑚𝑒𝑡𝑛=𝐿∃𝑘−𝑝á𝑠𝑘𝑜𝑣ý 𝐷𝑇𝑆 𝑀:𝐿=𝐿𝑀𝑎 𝑇𝑀∈𝑂𝑡𝑛
𝑁𝑇𝑖𝑚𝑒𝑡𝑛=𝐿∃𝑘−𝑝á𝑠𝑘𝑜𝑣ý 𝑁𝑇𝑆 𝑀:𝐿=𝐿𝑀𝑎 𝑇𝑀∈𝑂𝑡𝑛
𝐷𝑆𝑝𝑎𝑐𝑒𝑠𝑛=𝐿∃𝑘−𝑝á𝑠𝑘𝑜𝑣ý 𝐷𝑇𝑆 𝑀:𝐿=𝐿𝑀𝑎 𝑆𝑀∈𝑂𝑠𝑛
𝑁𝑆𝑝𝑎𝑐𝑒[𝑠(𝑛)]={𝐿|∃𝑘−𝑝á𝑠𝑘𝑜𝑣ý 𝑁𝑇𝑆 𝑀:𝐿=𝐿𝑀𝑎 𝑆𝑀∈𝑂(𝑠(𝑛))}
Časově konstruovatelná funkce 𝑓
Vícepáskový TS pro libovolný vstup 𝑤 zastaví přesně po 𝒕(|𝒘|) krocích (např. 𝑓𝑛=𝑛log𝑛, ne např. 𝑓(𝑛)=𝑐)
Prostorově konstruovatelná funkce 𝑠
Vícepáskový TS pro libovolný vstup 𝑤 zastaví s využitím přesně 𝒔(|𝒘|) buněk pásky (např. 𝑠𝑛=𝑛log𝑛, ne např. 𝑠(𝑛)=𝑐)
Pomocí tříd Dtime, Dspace, Ntime, Nspace se definují konkrétnější třídy složitosti (např. P, NP, PSPACE a DSPACE):
Nejběžněji používané třídy jsou P a NP. Potom máme ještě další třídy…
Hierarchie
(od nejsložitějších k nejméně složitým), (pozn.: n - délka vstupu, k - konstanta)
Vrchol hierarchie
PR - primitivně rekurzivní funkce (zanořené cykly s pevným počtem opakování: 𝒇𝒐𝒓 𝒊=.. 𝒕𝒐 ..)
R - μ-rekurzivní funkce (cykly s předem neurčeným počtem opakování: 𝒘𝒉𝒊𝒍𝒆..)
RE - rekurzivně vyčíslitelné funkce
Třídy nad exponenciální složitostí
- k-exponenciální čas/prostor založený na věži exponenciál o výšce 𝑘 (22…22𝑛)
k-EXP
k-NEXP
k-EXPSPACE
k-NEXPSPACE
ELEMENTARY - nekonečná věž exponenciál
Redukce a úplnost
ℛ-redukce
Jazyk L1 je ℛ-redukovatelný na L2 jestliže existuje funkce 𝑓 třídy ℛ taková, že 𝒘∈𝑳𝟏⇔𝒇𝒘∈𝑳𝟐 - značíme 𝐿1≤ℛ𝑚𝐿2
(tj. jde o převod jednoho problému na problém jiný převodní funkcí, která má složitost 𝓡)
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.
C-těžký jazyk
R-redukovat znamená provést redukci pomocí některé funkce z množiny R
Jazyk L0 je C-těžký vzhledem k R, pokud každý jazyk ze třídy C je možné R-redukovat na jazyk L0. 
Jazyk L0 je C-úplný vzhledem k R, pokud je C těžký vzhledem k R a taky patří do třídy C.
SAT - problém
(problém splnitelnosti booleovských formulí)
[link]
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í 𝒕𝒓𝒖𝒆.
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.
Notes
1. Otazka (predmet) (okruh): 26. Časová a paměťová složitost (TIN(
Kdo me primarne zkousel: 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal jsem s tím, že u řešení problémů nepotřebujeme znát přesný čas, tato informace je málo vypovídají atd., ale používáme aproximaci časové složitosti do nějakých tříd. Že máme spodní, horní a oboustranné omezení složitosti a pak chtěl definovat přesně Omikron, to jsem přesně zapsal na tabuli se slovním komentářem. Pak chtěl slyšet, co je to P a NP. To jsem definoval, ale pak se mi nepodařilo vydolovat z paměti odpověď na otázku, co to znamená NP-úplný. Ještě se ptal, jaký mají mezi sebou třídy P a NP vztah. Tak jsem několikrát zopakoval, že P vymezuje problémy, které jsou prakticky výpočetně řešitelné a NP už ne. To slyšet nechtěl, ale co přesně byla odpověď, to nevím. Přestal mě zkoušet se zazvoněním budíku. Ohodnotil mě na B 
From <[link]> 
2. Otázka (předmět) (okruh): TIN - Časová a paměťová složitost (třídy složitosti, úplnost, SAT problém)
Kdo mě primárně zkoušel: Holík a vstupoval do toho i Švéda
Co jsem k tomu řekl(a)/na co se ptali/co mně vytkli: V zadání bylo jen "Časová a paměťová složitost" a nebyl jsem si jistý, jestli to patří k PRL algoritmům nebo jinam, takže jsem se podíval do seznamu otázek a našel ji u TINu a při pohledu do závorky jsem věděl, že je zle. Pod "třídy složitosti" jsem si vybavil jen konstantní, lineární, logaritmické, atd., ale to jsem ani neřekl a navíc to není ono. Po letmém vysvětlení, k čemu vůbec složitost je, jsem ještě měl definovat co je &Omicron;, tak jsem to nějak popsal, ale na sousloví "asymptotická složitost" jsem si nevzpomněl. Pak jsem měl říci, co znamená NP problém, což se mi celkem povedlo. Dále ale chtěli vědět, co je to úplnost a od té chvíle až do konce jsem byl jako vygumovaný - věděl jsem, že jsem si to procházel, ale už téměř před 2 týdny, takže toho v hlavě moc nezůstalo. Nakonec jsem snad správně řekl jen to, že NP-úplný problém se dá převést na SAT problém, ale to, že redukcí, za mě musel říci Švéda - celkově katastrofa, protože celkově jsem jim toho ani moc neřekl, takže za E jsem byl vysloveně rád.
From <[link]> 
1. Otazka (předmět) (okruh): TIN 20 - Časová a paměťová složitost
Kdo me primarne zkousel: Rogalewicz
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začal jsem mluvit co je to časová a paměťová složitost (obecně, že je to počet kroků kolik musí udělat TS v závislosti na počtu položek N), pak se mě zeptal na třídy složitosti a jako příklad uvedl NP. Řekl jsem, že je to třída jazyků přijímaných NTS v polynom. čase. Pak se zeptal co je to úplnost, začal jsem že jazyk je NP úplný pokud jej lze redukovat na NP jazyk, ale hned jsem se opravil a řekl že na něj můžeme redukovat NP jazyk. Zeptal se mě na přílad NP úplného jazyka, řekl jsem SAT problém a začal jsem říkat co to je, ale zastavil mě. Pak se mě zeptal, jestli do třídy NP patří algoritmus na detekci datových typů, který používám v diplomce. To mě docela zaskočilo, řekl jsem že si nejsem jistý ale řekl jsem že ten algoritmus pracuje v rozumném čase a tak asi ano. On řekl, že ten problém je obecně nerozhodnutelný a že rozumného času dosahuji díky různým heuristikám. To bylo vše. Výsledek A.
From <[link]> 
1. Otazka (předmět) (okruh): Časová a paměťová složitost /třídy složitosti, úplnost, SAT problém/ (TIN) (20)
Kdo me primarne zkousel: Rogalewicz Adam, Mgr., Ph.D. UITS FIT VUT, Brno
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Definovali jsme si, co vlastně složitost reprezentuje. Pak se skočilo na SAT problém a jeho složitost. Vztah NTS a DTS pro jazyk Lsat.
From <[link]> 
1. Otazka (TIN) (20): Časová a pamětová složitost (na papírku bylo: "P,NP,SAT") 
Kdo me primarne zkousel: Janoušek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Začla jsem obecně, co je to složitost, co to je paměťová a časová vzhledem k TS. Tam mě hned zastavil a chtěl vědět, jaký je mezi nimi vztah. To jsem nevěděla, ale hned, jak to načl, tak jsem zi vzpomněla, že je to v opoře. Pak chtěl zadefinovat P a NP, napsala jsem na tabuli, pak vysvětlit, co to znamená. Následně chtěl vědět, co to znamená NP-úplný jazyk. Chtěla jsem to vzít oklikou přes redukovatelnost, ale to nechtěl slyšet. Nakonec se zeptal na Cookov teorem a o co jde v SAT problému.
From <[link]> 
1. Otazka (předmět) (okruh): TIN Časová a paměťová složitost 
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Dal som uvod, par definicii, nasledne diskusia o vztahu P a NP, otazka aky je vztah medzi jazykom a problemom.
From <[link]> 
1. Otázka (okruh): Časová a paměťová složitost (třídy složitosti, úplnost, SAT problém)
Kdo mě primárně zkoušel: Janoušek, Češka
Co jsem k tomu řekl(a)/na co se ptali/co mně vytkli:
Chtěli jen základy, ale stejně to ze mě tahali jak z chlupatý deky 
 Něco jsem řekl dobře, něco špatně a něco jsem promlčel. Snažili se opravdu hodně pomoct a navést, byli moc hodní.
From <[link]> 
2. Otazka (předmět) (okruh): Složitost (TIN)
Kdo me primarne zkousel: Češka
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
V podstatě chtěl úplný základy. Co je složitost, co je časová a prostorová a jak se to vyjadřuje. Pak jak se jinak určuje - to mi musel trochu napovědět - asymptotické omezení atp. Taky se ptal na vztah časové a prostorové složitosti (tzn. časová nemůže být menší, než prostorová). Pak chtěl definovat P a NP (neformálně) a co jsou prvky těch množin. Dál co je to NP-úplný problém a jaký je množinový vztah mezi P a NP. Někde jsem to trochu motal, v podstatě to byla otázka-odpověď. Výsledná B.
From <[link]> 