Please enable JavaScript.
Coggle requires JavaScript to display documents.
Složitost a vyčíslitelnost, Přednášky - Coggle Diagram
Složitost a vyčíslitelnost
Vyčíslitelnost
Věty
Ricova věta
Důkaz
Pro netriviální C
M1
Konstanta
Pro triviální C
Formulace pomocí funkce
Jiné důsledky
Totální
Součet
Rostoucí
Nulová?
Změní malá na velká písmena
Postuv korespondenčí problém
Nerozhodnutlený
Bez důkazu
Dominové kostky
Protože můžeme opakovat kostky, nevím jak může být posloupnost dlouhá
Převoditelnost
1-Převoditelnost
m-převoditelnost (mapping) (minione)
B <=m A
Dostazem do A rozhodneme B
x e B
y e A
x -> y -> y e A <> b e A
Převodní funkce
Nemusí být prostá
Musí být vyčíslitelná
Identita
Vlastnosti (Kvaziuspořádání)
Reflexivní
Tranzitivní
A rozhodnutlený => B rozhodnutlený
A částečně rozhodnutelný => B je částečně rozhodnutlený
Turingovská převoditelnost
Oraculum...
Každý jazyk je převoditelný na jeho doplňek
Přiklady
Identita
Složitost
Definice
Rozhodovací problém
Odpověď - Ano x Ne
Jazyk kladných instancí
Zda instance x splňuje podmínku
Úloha
Relace
Pro x hledáme y
Odpověď
Graf konfigurací
Velikost
|V| <= |Q|
(n + 2)
f(n) * |Velikost abecedy| na f(n)
|E| <= |V|^2 <= 2^( 2
c
M * f(n))
Každá konfigurace je jednoznačně určená
Strom konfigurací
Stejné konfigurace se můžou objevit několikrát - jsou zde duplicity
Typy
Časová
Prostorová
Třídy složitostí
Deterministické třídy složitosti
Space(f(n))
Významné třídy
Třída řešitelná v polynomiálním čase
Třída řešitelná v polynomiálním prostoru
Třída řeštilná v exponenciálním čase
Problémy ověřitelné v polynomiálním čase
Složitě zjistitelný
Jednoduše ověřitelný
Verifikator
Př
Verifikator pro hamiltonovskou kruznici
Time(f(n))
Třída strojů přijímaných turnigovými stroji ktere apcuji v cease o(f)n))
Základní nedeterministické třídy složitosti
NTime
NSpace
L
Space(log n)
NL
NSpace(log n)
P
Polynomial
NP
Obtížně zjistitelná
Jednoduše zjistitelná
Mají polynomiální verifikatory
třída jazuky prijimanych nedeterministickym turingovym strojem
nedeterminismus hadanspravny certifikat
PSpace
NPSpace
NSpace (n^k)
ExpTime
Vztahy mezi t+r=idamy
Time < NTime < Space < NSpace
Space < NSpace
NTime < Space
NP < PSpace
Věty
Church-Turingova teze
Realné modely lze na Turingovu stroji simulovat s polynomiálním zpomalením/nárůstem prostoru
Cook and Reckhow
Složitost ramu a turingova stroje
Věta: Alternativní definice třídy NP
Důkaz
Savičova věta
Rozdílný důkaz pokud nemáme rozumnou f(n)
Na různých modelech
Turingův stroj
Pracuje v čase f(n)
RAM
TS s menším než lineárním prostorem
Počítá se pouze velikost pracovní pásky
Random Access Machine (RAM) (R)
Složitost na RAMu
Cena za vykonání instrukce
Definice
Řídící jednotka
Neomezená paměť
Paměť rozdělená do registrů ri, i e N
V každém registu může být libovolné přirozené číslo
Na začátku obsahují 0
[ri] označuje obsah registu ri
Nepřímá adresace [[ri]] = [r[ri]]
Proměnné v RAM
Pole
Skalární proménné
Proměmné
Program
Konečná posloupnost instrukcí p = I0, I1, ..., Il
Instrukce jsou vykonávané v pořadí daném programem
Insturkce
Programování v ramu
Cykly
Nepodmíněný skok
Podmíňený příkaz
Funkce a procedury
Nepřímá adresace
Není zde rekurzivní volání funkcí, které lze implementovat pomocí cyklu while
Proměnné
Load
Add
Sub
Copy
JNZ
Jump
Read
Print
Přijímací výpočet
Jazyk slov přijímaných RAMem R označime pomocí L(R)
RAM R příjme slovo w pokud R(w) šipka dolů (ukončí výpočet) a první číslo, které R zapíše na výstup je 1
Zamítající výpočet
Ram R odmítne slovo, pokud R(w) šipka dolů a R buď na výstup nezaíše nic nebo první zapsané číslo je jiné než 1
Přiklady
Součin čísel
Rozhodnutlenost na RAMu
(RAMem) částečně rozhodnutelný jazyk
(RAMem) rozhodnutelný jazyk
Přijímán nějakým RAMem, který se zastaví pro každý vstup
Každé slovo buď příjme nebo odmítne
Vyčíslitelnost na ramu
RAM vyčíslitelná funkce
Počítaná nějakým RAMem
?
Řetězové funkce vyčílistelné na RAMu
?
Převoditelnost
Turingův stroj - > RAM
Ke každému TS M existuje ekvivaletní RAM R
R simuluje práci M instrukci po instrukci
R počítá touž funkci jako M
R přijímá týž jazyk
Turingův stroj (M) (TS) (TM)
Varianty
Nedeterministický TS
Má více instrukcí, které z jednoho stavu může provádět a vybírá nedeterministicky
Není reálný výpočetní model
Dokáže řešit NP v polynomíálním čase pomocí hádání řešení a testování zda platí
NTS
Deterministický TS
DTS
TS s jednosměrně nekonečnou páskou
TS s více páskami (vstupnú/ výstupní/ pracovní)
K-páskový stroj
Má k pásek
Vstupní páska
Jen pro čtení
Pracovni pásky
Čtení i zápis
Výstupní páska
Často jen pro zápis
Na každé pásce je zvlaštní hlava
Hlavy na páskách se pohybují nezávisle
Přechodová funkce je typu ...
Převod 3 páskového stroje na 1 páskový
TS s více hlavami na páskách
TS s pouze binární abecedou
Definice
5tice
Množina stavů
Pásková abeceda
Obsahuje prázdný znak (lambda)
Budeme (často) rozlišovat páskovou (vnitřńí) a vstupní (vnější) abecedu
Přechodová funkce
Počáteční stav
Množina přijímacích stavů
Příjímající výpočet
Zamítající výpočet
Počáteční konfigureace
Počateční stav
Vstupní slovo zapsané na pásce
Nesmí obsahovat prázdné políčko
Hlavu na nejlevějším symbolem slova
Nedefinovaný přechod
Převrácené T
Výpočet končí pokud narazíme na nedefinovaný přechod
Příklady
Palindromy
Enumearator
Řeší jazyk NE
Enumeratorem pro jazyk L je turingův stroj E, který ignoruje svůj vstup a vypisuje retezce w e L
Enumerátor pro jazyk prvočísel
Převoditelnost
RAM -> Turingův stroj
Ke každému RAMu R existuje ekvivaletní TS M
Rozhodnutelnost
Jazyk je (Turingovský) částečně rozhodnutelný, je li přijímán nějakým TS M
L = L(M)
Jazyk je (Turingovský) rozhodnutelný, je li přijímán nějakým TS M, jehož výpočet s každým vstupem zastaví
Číslování
1.TS popíšeme řetězcem nad malou abecedou
Zakódování přechodové funkce
Instrukci zakódujeme
Všechny instrukce pak zakódujeme
Rětězec nad touto abecedou převedeme do binární abecedy
Každe´mu binárnímu řetězci w přiřadíme číslo index(w)
Každému Turingovu stroji takto přiřadíme Godelovo číslo
Univerzální turingův stroj
Simuluje TS M se vstupem x
M příjme právě kdyz U přijme
M odmítne právě když U odmítne
M neskončí právě když U neskončí (šipka nahoru)
Jazyk
Přiklady
Problem zasstavení (Halting problem) (HALT)
Zastaví se výpočet turingova stroje M a vstupu x?
Je částečně rozhodnutelný
Není rozhodnutelný
Univerzální jazyk (Lu)
Je částečně rozhodnutelný, ale není rozhodnutelný
Částečná rozhodnutelnost plyne z existence univerzálního stroje
Nerozhodnutlenost ukážeme diagonalizací
Lu reprezentujeme jako matici A
Jazyk daný doplňkem diagonály A není částečně rozhodnutelný
Z toho odvodíme, že Lu není rozhodnutelný
Postova věta
Jazyk L je rozhodnutlený právě když L i doplňek L jsou částećně rozhodnutelné jazyky
Diagonální jazyk DIAG = {<M> | <M> nelezi v L(M)}
#
DIAG nemá svůj řádek v matici A
Diag není částečně rozhodnutlený
Důkaz sporem
Kdyby byl DIAG částečně rozhodnutlený, tak extistuje TS M, který DIAG = L(M), pokud by ale takovy stroj eistoval, tak ho muzeme odsimulat pomoci Lu a je tedy v matici A
Není úplně takto...
Non Empty (NE)
Obsahuje kody turingovyxh sroju, ktere maji neprazdny jazyk
Je částečně rozhodnutelný
Není rozhodnutelný
Definice
Jazyk slov přijímaných Turingovým strojem M
L(M)
Množina slov (řetězců) na konečnou abecedou (Sigma)
Rozhodnutelnost
Rozhodnutelný (rekurzivní jazyk)
#
Jazyk je rozhodnutelný právě když jeho charakteristická funkce je algoritmicky vyčíslitelná
Častečně rozhodnutelný (Rekurzivně spočetný)
#
m-úplný jazyk
Částečně rozhodnutelný
Každý rozhodnutelný jazyk lze na m-úplný jazyk převést
Počítání jazyků
Otázky
Koli je jazyků nad abecedou E?
Kolik je částečně rozhodnutelných jazyků nad abecedou E?
Jsou všechny jazyky nad konečnou abacedou částečně rozhodnutelné?
Jazyk L je podmnožina řetězců, která odpovídá množině přirozených čísel A = {index(w) | w e L}
#
P(A) má větší mohutnost než A pro každou množinu A
#
Jazyků nad konečnou abecedou E není spočetně mnoho
#
Vlastnosti
Jsou li L1 a L2 (částečně) rozhodnutelné jazyky pak i jejich sjednocení, průnk, konkatenace a kleeneho uzávěr jsou (částečně) rozhodnutlené jazyky
Třída rozhodnutelných jazyků je uzavřená na operaci doplňku
Třída částečně rozhodnutelných jazyů není uzavřená na operaci doplňku
Certifikat
Jeli A částečně rozhodnutlený, pak existuje y certifikat a pro nej B pro který plati, že je rozhodnutelný
pokud je B částečně rozhodnutelný tak A je také částečně rozhdonutlený
Funkce
Turingův stroj M nad abecedou E počítá nějakou částečnou funkci fM : E
-> E
Značení
Je hodnota funkce fM(w) definovaná
Vyčíslitelnost
(Algoritmicky) vyčíslitelná funkce = Turingovsky vyčíslitelná
Intuitivně: Lze vyčístlit nějakým algoritmem
Částečná funkce f je algoritmicky vyčíslitelná pokud existuje turingův stroj M, který jí počítá
Je li f(x) nedefinovaná (šipka nahoru), pak M(x) se nezastaví (šipka nahoru)
Jeli f(x) definovaná a rovna y, pak M(x) se zastaví a na výstupní pásce je po ukončení M(x) řetěžec y
Je Turingovsky vyčíslitelná pokud existuje stroj M, který ji počítá
Každá turingovsky vyčíslitelná funkce má nekonečně mnoho různých Turingovských strojů, které ji počítají
Vyčíslitelná funkce = Částečné rekurzivní funkce
Totální vyčíslitelná funkce = obecně rekurzivní funkce
Definice
Totální funkce
Definováná pro každy vstup
Doména
Množina vstupů
Obor hodnot
Množina možných výstupů
Částečná funkce
funkce může být definovaná jen pro některé vstupy (doména)
Řetězcová funkce
Funkce jejiž vstupem je řetězec a výstupem je řetězec
Charakteristická funkce
Funkce, ktera umožnuje rozhodnout zda slovo patri do jazyka nebo ne
Vrátí 1 pokud vstupní slovo patří do jazyka
Vratí 0 pokud vstupní slovo nepatří do jazyka
Přiklady
Charakteristická funkce jazyka Lu není algoritmycky vyčílitelná
Lu není algoritmicky rozhodnutelný
Abeceda
Řetězec
Lexografické uspořádání
podle abecedy
podle délky
Číslování řetězců
Číslování binárních řetězců
Počítání
Množina A je spočetná
Existuje funkce f: A - > N (pokud lze prvky očíslovat)
Potenční množina
Nespočetná množina
Cantorova věta
Kódování objektů
<X> binární řetězec kódujicí objekt X
<X1,...,Xn>
Binární řetězec kódujíc´n tici objektů X1, ..., Xn
Rozhodnutelnost
Věta: Jazyk L je částečně rozhodnutlený, právě když pro něj existuje enumerátor E
Důkaz
Nekonečný jazyk je rozhodnutelný, právě když je oborem hodnot nějaké totální alogritmicky vyčíslitelné funkce
Věta: Jazyk L je rozhodnutelný, právě když pro něj existuje enumerátor E, který navíc vypisuje prvky L v (lexografickém) pořadí
Důkaz
Nekonečný jazyk je rozhodnutelný právě tehdy když, je oborem hodnot nějaké rostoucí totální algoritmicky vyčíslitelné funkce
Pro rozhodnutí konečného jazyka nám stačí konečný automat
Věta: Jazyk Lu je m-úplný
HALT je m-úplný
NE je m-úplný
Přednášky
5
M Převoditelnost
Ricova věta
4
Turingovská pŘevoditelnost
3
Číslování turnigových strojů