Problémy, algoritmy a programovacie jazyky IB110 1 / 214 Algoritmický problém Problém čo je problém? 2 / 214 Algoritmický problém Problém čo je problém"; výpočtový problém • (nekonečná) množina vstupných inštancií prípustné vstupy • špecifikácia požadovaných výstupov funkcia vstupných inštancií 2 / 214 Algoritmický problém Riešenie problému Metóda riešenia problému popisuje efektívnu cestu, ktorá vedie k nájdeniu požadovaných výstupov. Popis pozostáva z postupnosti inštrukcií, ktoré môže ktokoľvek realizovať. existencia metódy riešenia problému znamená možnosť vypočítať riešenie automaticky v danom kontexte hovoríme o algoritme pre riešenie problému 3 / 214 Algoritmus — historický pohľad I koniec 19. storočia, priemyslová revolúcia, kauzálne chápanie sveta, zákony umožňujúce úplné pochopenie sveta program Davida Hilberta (a) celá matematika sa dá vybudovať z konečnej sady vhodných axióm (b) matematika vytvorená týmto spôsobom je kompletná v tom zmysle, že každé tvrdenie vyjádřitelné v jazyku matematiky sa dá dokázať alebo vyvrátiť v tejto teórii (z danej sady axiómov) (c) existuje metóda pre dokázanie resp. vyvrátenie každého tvrdenia. kľúčový pojem metódy Algoritmus — historický pohľad II • Kurt Gödel (1931) dokázal, že (a) neexistuje žiadna úplná (rozumná) matematická teória; v každej korektnej a dostatočne veíkej teórii je možné formulovať tvrdenia, ktoré nieje možné vnútri tejto teórie dokázať. Aby bolo možné dokázať správnosť týchto tvrdení, je nutné k teórii pridať nové axiómy a vybudovať tak novú, väčšiu teóriu (b) neexistuje metóda (algoritmus) pre dokazovanie matematických teorém • pre svoj dôkaz potreboval presnú definíciu pojmu metóda (algoritmus) (nie je možné dokázat neexistenciu algoritmu bez rigoróznej definície toho čo je a čo nieje algoritmus) • prvá formálna definícia pojmu algoritmu: Alan Turing (1936) • ďalšie definície a ich ekvivalencia Algoritmy Základné otázky Existujú problémy, ktoré nie sú riešiteľné automaticky (algoritmicky)? Ak áno, ktoré problémy sú algoritmicky riešiteľné a ktoré nie? 6 / 214 Programovacie jazyky Programovacie jazyky I • algoritmy musia byť zapísané jednoznačne a formálne • programovací jazyk -jazyk pre špecifikáciu algoritmov • program - zápis algoritmu v programovacom jazyku • strojový kód vs. programovací jazyk vyššej úrovne 7 / 214 Programovacie jazyky Programovacie jazyky II • ako prezentovať algoritmus reálnemu počítaču? • ako "prinútiť" počítač, aby realizoval výpočet tak, ako sme to zamýšľali? • programátori sú ľudia, uvažujú abstraktne a vyjadrujú sa pomocou slov a symbolov • počítače sú stroje, ktoré dokážu realizovať veľmi jednoduché úlohy • programovacie jazyky pomáhajú ľuďom komunikovať s počítačmi 8 / 214 Programovacie jazyky Vývojové diagramy 9 / 214 Programovacie jazyky Programovací jazyk vyššej úrovne jazyk pre popis algoritmov základné stavebné kamene • riadiace štruktúry • dátové štruktúry 10 / 214 Programovacie jazyky Riadiace štruktúry • postupnosť príkazov • podmienené vetvenie • ohraničená iterácia • podmienená iterácia kombinácia riadiacich štruktúr - vnorenie 11 / 214 Dátové typy • premenne • vektory, zoznamy • polia, tabuľky • zásobníky a fronty • stromy a hierarchie Programovacie jazyky 12 / 214 Programovacie jazyky Vlastnosti programovacích jazykov • presná syntax • presná sémantika 13 / 214 Programovacie jazyky Syntax • nejednoznačnosti; presný význam pre pojmy, ktoré sa používajú v bežnej komunikácii • Porovnanie "=" a priradenie "=" Java if (x==y) z = 3; else z = 4; FORTRAN IF (X .EQ. Y) THEN Z = 3 ELSE Z = 4 END FI Pascal if x = y then z := 3 else z:= 4 14 / 214 Programovacie jazyky Syntax - príklad • hypotetický programovací jazyk PL Príklad i input/V; 2 X :=0; 3 for Y from 1 to N do 4 X:=X+Y 5 od 6 OUtputX. 15 / 214 Programovacie jazyky Definícia syntaxe - syntaktické diagramy 16 / 214 Programovacie jazyky Definícia syntaxe — BNF (príkaz) ::= (for príkaz) | (priraďovací príkaz) | ... (for príkaz) ::= (premenná) from (hodnota) to {hodnota) BNF umožňuje generovať (syntakticky správne) programy 17 / 214 Programovacie jazyky Kontrola syntaktických chýb • program sa nedá vygenerovať použitím BNF • automatizovaný proces 18 / 214 Programovacie jazyky Sémantika for Y from 1 to N do • význam — odčítanie, príkaz pre tlačiareň, dnes je pekný deň 111 9 význam podľa použitých slov 111 • čo ak N = 3.14 111 • presná sémantika je nevyhnutná M! • manuál (dokumentácia) ako definícia sémantiky 111 19 / 214 Programovacie jazyky Sémantika - príklad Príklad procedúra P (s parametron V) (1) call V (s parametrom V), výsledok ulož do X (2) if X = 1 then return 0; else return 1 • procedúra, ktorá má ako svoj parameter názov procedúry • syntaktická korektnosť • call P(s parametrom P) - aká je návratová hodnota? • sémantika musí dať jednoznačnú odpoveď 20 / 214 Programovacie jazyky Výpočet programu • od programu v jazyku vyššej úrovne k manipulácii s bitmi • program je postupne transformovaný na strojovú úroveň • transformácia • kompilácia • interpretácia • kombinovaný prístup 21 / 214 Programovacie jazyky Kompilácia • program v jazyku vyššej úrovne je preložený do jazyka nižšej úrovne (jazyk symbolických adries) for Y from 1 to N do telo cyklu od LOOP: MOVE 0, Y CMP N, Y JEQ REST ADD 1, Y telo cyklu JMP LOOP do registra Y ulož 0 porovnaj hodnoty uložené v N a Y ak rovnosi, tak pokračuj príkazom REST pripočítaj 1 k Y prekladač 22 / 214 Programovacie jazyky Kompilácia - pokr. • preklad z jazyka symbolických adries do strojového kódu • assembler Optimalizácia kódu počas kompilácie 23 / 214 Programovacie jazyky Interpretácia • interpreter postupuje príkaz po príkaze • každý príkaz je okamžite preložený do strojového kódu a vykonaný Možnosť lepšie sledovať výpočet. Typicky jednoduchá tvorba interpretru. Nemožnosť optimalizácii. 24 / 214 Programovacie jazyky Programovacie esperanto • prečo rôzne programovacie jazyky? • programovací jayzk poskytuje programátorovi istú úroveň abstrakcie • potreba nových typov abstrakcií • vývoj hardwaru (paralelné počítače a programovanie vo vláknach) • nové aplikačné oblasti (mulimediálne aplikácie) • paradigmata - kategorizácia existujúcich programovacích jazykov 25 / 214 Programovacie jazyky Imperatívne programovanie • prístup blízky ľudskému uvažovaniu • imperatívne programovanie popisuje výpočet pomocou postupnosti príkazov a určuje presný postup, ako daný algoritmický problém riešiť • pamäť počítača je súborom pamäťových miest organizovaných do rôznych dátových štruktúr • program buduje, prechádza a modifikuje dátové štruktúry tak, že načíta dáta a mení hodnoty uložené v pamäti • príkazy, v závislosti na vyhodnotení podmienok, menia stav premenných • historicky najstaršie imperatívne programovacie jazyky: strojové jazyky • FORTRAN, ALGOL, COBOL, BASIC, Pascal, C, Ada • základné typy príkazov - priradenie, cykly, príkazy vetvenia 26 / 214 Programovacie jazyky Funkcionálně programovanie • výpočtom funkcionálneho programu je postupnosť vzájomne ekvivalentných výrazov, ktoré sa postupne zjednodušujú • výsledkom výpočtu je výraz v normálnej forme, ktorý sa nedá ďalej zjednodušiť • program je chápaný ako jedna funkcia, ktorá obsahuje vstupné parametry. Výpočet je vyhodnotením tejto funkcie. • imperatívny prístup: ako sa má vypočítať funkcionálny prístup: čo sa má vypočítať • Erlang, Haskell, Lisp, ML, Ozx, Scheme 27 / 214 Programovacie jazyky Logické programovanie • postavené na použití matematickej logiky • logický program je tvorený sadou pravidiel a jednoduchých logických tvrdení • dotaz sa rieši prehľadávaním množiny pravidiel. Hľadá sa dôkaz, ktorý poskytuje odpoveď na zadaný dotaz 28 / 214 Programovacie jazyky Objektovo orientované programovanie • pamäť počítača pozostáva z objektov • s každým objektom sú asociované operácie, ktoré môže objekt poskytovať (prístupné ako metódy volania) • program je súborom objektov, ktoré si posielajú správy obsahujúce požiadavky na realizáciu operácií a odpovede • Smalltalk, Java, C++, Python, Ruby. Lisp 29 / 214 Korektnost algoritmov IBllO 30 / 214 Prečo? lAlJ.» UvmtiS /in , iH^I "*^"/ku' 9.»Jiy4MJ- w^. is'Vt toJ «f -«t mHI^I f-í/^««i5(.i) ^vď i/So^íy/,' < " !cC. Flfil -C-WI l,,*jJ Ua Lnu /mJ. I ■ • 1962, Marinerl - štart rakety • 1981, Kanada - informácia o volebných preferenciách • 1985-87, Therac-25 - nesprávne dávky róntgenového žiarenia • problém Y2K • http://www.devtopics.com/20-famous-software-disasters/ Základy informatiky (IB110 31 / 214 Typy chýb • syntaktické chyby • until / until • for (k=0;k<101){ sum = sum + k } versus for (k=0;k<101;k=k+l){ sum = sum + k } • sémantické chyby • výsledná hodnota premennej cyklu a for (k=0;k=k+l;k<101){ sum = sum + k } versus for (k=0;k<101;k=k+l){ sum = sum + k } • logické chyby pre daný text zisti, kol'ko viet obsahuje slovo kniha • koniec vety indikuje výskyt symbolov ". " (bodka, medzera) • koniec vety indikuje výskyt symbolu "." (bodka) Počítače nerobia chyby J 32 / 214 Testovanie a ladenie • syntaktické chyby, run-time chyby • testovanie, testovacie sady • ladenie • nezaručujú bezchybnosť algoritmu 33 / 214 Čiastočná a úplná korektnost Špecifikácia algoritmického problému: 1. určenie množiny vstupných inštancií 2. určenie vzťahu medzi vstupnými inštanciami a požadovaným výstupom. • čiastočná korektnosť: pre každú vstupnú inštanciu X platí, že ak výpočet algoritmu na X skončí, tak výstup má požadovanú vlastnosť • konečnosť: výpočet skončí pre každú vstupnú inštanciu • úplná koreknosť: čiastočná korektnosť + konečnosť 34 / 214 Dôkaz korektnosti invarianty • kontrolné body programu • invariant = tvrdenie, ktoré platí pri každom priechode kontrolným bodom • čiastočná korektnosť konvergencia • s kontrolnými bodmi asociujeme kvantitatívnu vlastnosť • pri každom priechode kontrolným bodom sa hodnota kvantitatívnej vlastnostni znižuje • hodnota kvantitatívnej vlastnosi nesmie prekročiť dolnú hranicu • konečnosť výpočtu 35 / 214 Zrkladlový obraz Príklad - zrkadlový obraz Vstup: reťazec S Výstup: symboly reťazca S v obrátenom poradí Notácia • reverse( "fakulta") = '"atlukaf" • head( "fakulta") = "f" • tail( "fakulta") = "akulta" • symbol A označuje prázdny reťazec (reťazec neobsahuje žiaden symbol) • symbol • označuje zreťazenie (spojenie) dvoch reťazcov 36 / 214 Zrkladlový obraz Zrkadlový obraz — algoritmus X <- S: Y <- A ' 1 NO/ if y YES y ' Y^head(X) Y C« ' ' X<-t eaHX) 37 / 214 Zrkladlový obraz Zrkadlový obraz — kontrolné body a invarianty Assertion 1 ľ <- head«) -ľ X 2 —>2 —► • ••2 —>3 i-i) 39 / 214 Zrkladlový obraz Zrkadlový obraz — platnost invariantov 2 pre každý retazec S po vykonaní príkazov X platí rovnost S = reverse( Y) • X S, y^A 3 ak S = reverse(y) • X a X tak Y = reverse(S) A, 2 ak S = reverse(y) X a X ^ A, tak po vykonaní príkazov Y *— head(X) ■ Y; X *— tail(X) platí znovu tá istá rovnost pre nové hodnoty premenných X a Y dokázali sme čiastočnú korektnosť J 40 / 214 Zrkladlový obraz Zrkadlový obraz — konečnost • výpočet algoritmu je nekonečný práve ak prechádza kontrolným bodom 2 nekonečne veľa krát • s kontrolným bodom 2 asociujeme kvantitatívnu vlastnosť (tzv. konvergent) a ukážeme, že jej hodnota klesá a pritom je zdola ohraničená • konvergentem pre kontrolný bod 2 je dĺžka reťazca X • pri každom priechode kontrolným bodom 2 dĺžka reťazca X klesne o 1 • ak dĺžka X klesne na 0 (X je prázdny reťazec), tak výpočet neprechádza cyklom a nenavštívi kontrolný bod 2 dokázali sme konečnosť J 41 / 214 Zrkladlový obraz Zrkadlový obraz — korektnosť korektnosť = čiastočná korektnost + konečnosť J 42 / 214 Euklidov algoritmus Príklad - Euklidov algoritmus Vstup dve kladné celé čísla X a Y Výstup najväčší spoločný deliteľ Z čísel X a Y spoločný deliteľ Z Z delí X a Z delí Y (celočíselné) najväčší deliteľ pre každé číslo U > Z, buď U nedelí X alebo U nedelí Y Euklidov algoritmus Euklidov algoritmus - - implementácia function Euclid (X, Y) V ^X W ^Y while V ^ W do if V > W then V <- V - W fi if V < W then V <- W - V fi od return (V) Invariant 1 V a W sú násobkom Z Invariant 2V>ZaW>Z Invariant 3 neexistuje väčší spoločný deliteľ čísel V a W než číslo Z všetky invariatny platia v každom bode výpočtu Euklidov algoritmus Euklidov algoritmus — čiastočná korektnosť Invariant 1 V a 1/1/ sú násobkom Z Invariant 2V>ZaW>Z Invariant 3 neexistuje väčší spoločný deliteľ čísel V a 1/1/ než číslo Z Inicializácia V <-X, W <-Y • invarianty 1, 2, 3 sa priradením neporušia IF príkaz if V > 1/1/ then V <- V - 1/1/ fi • Fakt Ak V > W, tak dvojice čísel V, W a V -W,W majú rovnakých spoločných deliteľov • ak Z delí V/, U/a V > W, tak V - W > 0 a V -W>Z • invarianty 1, 2, 3 zostávajú zachované IF príkaz if W > V then W • symetricky W- V f i 45 / 214 Euklidov algoritmus Euklidov algoritmus — čiastočná korektnosť Invariant 1 V a W sú násobkom Z Invariant 2V>ZaW>Z Invariant 3 neexistuje väčší spoločný deliteľ čísel V a W než číslo Z while príkaz • všetky invarianty zostávajú v platnosti po prevedení jednotlivých príkazov cyklu • cyklus končí keď V = W • V je najväčším spoločným deliteľom V, W • V = Z čiastočná korektnosť 46 / 214 Euklidov algoritmus Euklidov algoritmus — konečnosť • výpočet je nekonečný práve ak while príkaz sa vykoná nekonečne veľa krát • konvergentem while cyklu je súčet V + W • pri každom vstupe do tela cyklu je V > Z > 0, W > Z > 0 a 9 pri vykonaní tela cyklu sa odčíta celé kladné číslo buď od V alebo od W • suma V + W sa pri každom priechode cyklom zníži aspoň o 1 • na začiatku je V+W = X + Ya preto sa cyklus vykoná nanajvýš X + Y krát konečnosť J 47 / 214 Príklad - triedenie vkladaním Insertion — Sort (A) for j: ^- 2 to length[A] do key ^ A\j\ while / > 0 A A[i] > key do A[i + 1] i: ^- i — 1 od 4[/ + 1] <- /cey od 4[/] Invariant na začiatku iterácie for cyklu obsahuje A[l.. .j — 1] tie isté prvky, ako obsahovalo na týchto pozíciách pole A na začiatku výpočtu, ale utriedené od najmenšieho po najväčší i / 214 I Insertsort Triedenie vkladaním - čiastočná korektnosť a konečnost Invariant na začiatku iterácie for cyklu obsahuje A[l.. .j — 1] tie isté prvky, ako obsahovalo na týchto pozíciách pole A na začiatku výpočtu, ale utriedené od najmenšieho po najväčší Inicializácia tvrdenie platí na začiatku výpočtu (J = 2, postupnosť A[l] obsahuje jediný prvok a je utriedená) FOR cyklus v tele cyklu sa hodnoty A\j — l],A\j — 2],A\j — 3],... posúvajú o jednu pozíciu doprava až kým sa nenájde vhodná pozícia pre A\j] Ukončenie for cyklus sa ukončí keď j = n + 1. Substitúciou n + 1 za j dostávame, že pole A[+ ... n obsahuje tie isté prvky, ako na začiatku výpočtu, ale utriedené. Konečnosť for cyklus nemení hodnotu riadiacej premennej cyklu 49 / 214 Formálna verifikácia Formálna verifikácia • interaktívne dokazovanie • dokazovanie formálnym odovedním (theorem proving) • overovanie modelu (model checking) 50 / 214 Zložitosť algoritmov IB110 51 / 214 Zložitost algoritmov • koreknosť algoritmu sama o sebe nezaručuje jeho použiteľnosť • dĺžka výpočtu a jeho pamäťová náročnosť • časová a priestorová zložitosť • zložitosť výpočtu závisí na vstupnej inštancii • zložitosť algoritmu vyjadrujeme ako funkciu dĺžky vstupnej inštancie 52 / 214 Optimalizácia zložitosti algoritmu Optimalizácia zložitosti algoritmu a na úrovni kompilácie • programátorská optimalizácia 53 / 214 Optimalizácia zložitosti algoritmu Optimalizácia - príklad 1 Vstup zoznam študentov a počet bodov, ktoré získali v záverečnom teste predmetu I BI 10 L(1),...,L(N) Výstup normalizované body (1) Nájdi maximálny počet bodov, MAX (2) každý bodový zisk vynásob hodnotou 100 a vydeľ hodnotou MAX Optimalizácia zložitosti algoritmu Implementácia (1) štandartne (2) for / from 1 to N do /.(/) <- /.(/) x 100/MAX od pre každé /.(/) potrebujeme 1 násobenie a 1 delenie Optimalizácia (1) štandartne (2) FAKTOR <- 100/ MAX (3) for / from 1 to A/ do /.(/) <- /.(/) x FAKTOR od zlepšenie o cca 50% I Optimalizácia zložitosti algoritmu Optimalizácia - príklad 2 • vyhľadávanie prvku X v neusporiadanom zozname • implementácia pomocou cyklu, v ktorom sa realizujú dva testy: (1) našli sme XI a (2) prehľadali sme celý zoznam? • optimalizácia: na koniec zoznamu pridáme prvok X a v cykle testujeme len podmienku (1) • po ukončení cyklu overujeme, či nájdený prvok X sa nachádza vo vnútri zoznamu alebo na jeho konci • zlepšenie o cca 50% Asymptotická zložitost Zložitosť • je zlepšenie o 50% (60%, 90% ...) dostačujúce? • ako charakterizovať zložitosť algoritmu? • ako porovnať zložitosť dvoch algoritmov? zložitosť algoritmu ako funkcia dĺžky vstupnej inštancie zložitosť v najhoršom prípade asymptotická zložitosť, O-notácia Asymptotická zložitost Asymptotická zložitost • jednoduchá charakterizácia efektivity algoritmu • umožňuje porovnat relatívnu efektivitu rôznych algoritmov • charakterizuje, ako rastie zložitost algoritmu s rastúcou dĺžkou vstupnej inštancie O-notácia Symbolom o{g{rí)) označujeme množinu fukciít.ž. ö{g{n)) = {f(n) | existuje kladná konštanta c a no také, že 0 < f (n) < cg{rí) pre všetky n > no}. Rovnosť f (n) = ö{g{n)) vyjadruje, že f {n) je prvkom množiny ö{g{n)). 58 / 214 Asymptotická zložitost Asymptotická zložitost - príklad Binárne vyhladávanie položky Y v telefónnom zozname s N položkami Xi,X2,...,XN pre N = 1000000 lineárne vyhľadávanie až 1 000 000 porovnaní zložitosť 0{N) binárne vyhľadávanie postup: v prvom kroku porovnaj Y s X500000 podľa výsledku porovnaj v druhom kroku Y buď s X250000 alebo s X750000 v najhoršom prípade 20 porovnaní zložitosť C(log2(A/)) Prečo? sme ako zložitosť vyhľadávania sme uvažovali len počet porovnaní? J 59 / 214 I Asymptotická zložitosť Robustnost O-notácie Fakt O-notácia zakrýva konštantné faktory • časová zložitosť algoritmu je relatívny pojem • zložitosť je relatívna voči fixovanej množine elementárnych inštrukcií • každý programovací jazyk resp. kompilátor môže mať inú množinu elementárnych inštrukcií • pokiaľ používajú štandartné inštrukcie, tak rozdiel v časovej zložitosti je práve o konštantný faktor • O-notácia je invariantná voči takýmto implementačným detailom Nevýhoda O-notácie: skryté konštanty, hraničná hodnota no 60 / 214 Analýza zložitosti algoritmov Príklad — bubblesort i procedure Bubblesort(4, n) 2 for / = 1 to n — 1 do 3 for j = 1 to n — i do 4 if A\j] > A\j + 1] then vymeň A\j] s A\j + 1] fi 5 od 6 od riadok 4 čas 0(1) for cyklus 3-5 čas ö{n — i) for cyklus 2-6 čas ö(Y,i=i(n ~ ')) = 0{n{n - 1) - E^i1 /) = 0(n2) celková časová zložitosť je ö{n2) Analýza zložitosti algoritmov Príklad — vnorené cykly 1 ľ max then max <— S[i] fi od Minimum nájdeme medzi zvyšnými n — 1 prvkami podobne. Celkove (n — 1) + (n — 2) porovnaní. Analýza zložitosti algoritmov Maximálny a minimálny prvok Prístup Rozdeľ a panuj O pole rozdeľ na dve (rovnako veľké) podpostunosti Q nájdi minimum a maximum oboch pod postupností Q maximálny prvok postupnosti je väčší z maximálnych prvkov pod postupností; podobne minimálny prvok function MAXMlN(x,y) if y — x < 1 then return (max(S[x], S[y]), min(S[x], S[y])) else (maxi, mini) <— Maxmin(x, [(x + y)/2j) (max2, mini) <- Maxmin(|_(x + y)/2j + 1, y) return (max(maxl, max2) min(m/nl, min2)) fi Analýza zložitosti algoritmov Maximálny a minimálny prvok Zložitosť: (počet porovnaní) T(n) 1 pre n = 2 7(Ln/2j)+7([n/2]) + 2 pre n > 2 Indukciou k n overíme, že T (n) < |n — 2. Pre n = 2 platí f • 2 - 2 > 1 = 7(2). Q Predpokladajme platnosť nerovnosti pre všetky hodnoty 2 < i < n, dokážeme jej platnosť pre n. T(n) = T([n/2\)+T(\n/2]) + 2 indukčný predp. <§Ln/2j-2 + |rn/2l-2 + 2 = |#i-2 Priemerná a očakávaná zložitost Priemerná a očakávaná zložitosť Priemerná zložitosť priemer zložitostí výpočtov na všetkých vstupoch danej dĺžky Quicksort - zložitost v najhoršom prípade je ö{n2), priemerná zložitost je ö{n log n) Očakávaná zložitosť zložitosť jednotlivých výpočtov je vážená frekvenciou výskytu príslušných vstupných inštancií Výhody: presnejšia informácia o efektivite algoritmu v prípade očakávanej zložitosti je relevancia voči aplikačnej oblasti Nevýhody: obtiažna analýza v prípade očakávanej zložitosti nutnost poznat presnú frekvenciu vstupných inštancií 66 / 214 Horné a dolné odhady zložitosti Horné a dolné odhady zložitosti Zložitosť algoritmu • v najlepšom prípade • v najhoršom prípade • priemerná zložitosť • očakávaná zložitosť Zložitosť problému • dolný odhad zložitosti problému • horný odhad zložitosti problému — zložitosť konkrétneho algoritmu pre problém • zložitosť problému I Horné a dolné odhady zložitosti Dolný odhad zložitosti problému - techniky Informačná metóda riešenie problému v sebe obsahuje isté množstvo informácie a v každom kroku výpočtu sme schopní určiť len časť tejto informácie (násobenie matíc, cesta v grafe, triedenie) Metóda sporu Varianta A: za predpokladu, že algoritmus má zložitosť menšiu než uvažovanú hranicu, vieme skonštruovať vstup, na ktorom nedá korektné riešenie. Varianta B: za predpokladu, že algoritmus nájde vždy korektné riešenie, vieme skonštruovať vstup, pre ktorý zložitosť výpočtu presiahne uvažovanú hranicu. Redukcia 68 / 214 I Horné a dolné odhady zložitosti Dolný odhad zložitosti pre problém maximálneho prvku postupnosti Dolný odhad Nech algoritmus A je algoritmus založený na porovnávaní prvkov a nech A rieši problém maximálneho prvku. Potom A musí na každom vstupe vykonat aspoň n — 1 porovnaní. < Dôkaz Nech x = (xi,... ,x„) je vstup dĺžky n, na ktorom A vykoná menej než n — 1 porovnaní a nech xr je maximálny prvok v x. Potom v x musí existovať prvok xp taký, že p ^ r a v priebehu výpočtu xp nebol porovnávaný so žiadnym prvkom väčším než on sám. Existencia takého prvku plynie z počtu vykonaných porovnaní. Ak v x zmeníme hodnotu prvku xp na xr + 1, tak A určí ako maximálny prvok xr - spor. 69 / 214 Horné a dolné odhady zložitosti Dolný odhad zložitosti pre problém vyhľadávania v telefónnom zozname binárny strom a jeho hĺbka 70 / 214 Horné a dolné odhady zložitosti Výzkum v oblasti zložitosti problémov • optimalizácia dátových štruktúr • dolné odhady zložitosti a dôkaz optimality • priestorová zložitosť • vzťah medzi priestorovou a časovou zložitosťou 71 / 214 HJWBBJM Rozhodnutelnost a praktická riešitelnost IB110 72 / 214 Kritérium efektivity T T Praktická použitelnost algoritmov Je každý algoritmus prakticky použiteľný? N = 1 000 000 vyhľadávanie v utriedenom zozname 0(log N)... 20 vyhľadávanie v zozname O(N)... 1 000 000 triedenie zoznamu 0(N log N)... 20 000 000 Hanojské veže Ö(2N)... milión presunov za minútu => 500 000 rokov Je riešením výkonnejší hardware a väčšia trpezlivosť? 73 / 214 I Kritérium efektivity Monkey Puzzle Problem http://www.keithharingart.com/ 74 / 214 Kritérium efektivity MP hlavolam Vstup N kariet (N = M2) Otázka Dajú sa karty usporiadať do štvorca M x M tak, aby sa susediace hrany zhodovali? B» í T7~ ~¥F JA. m > «í £> _čá_ % I W ľ> ~w Karty majú fixnú orientáciu (nemôžeme ich otáčať) Zaujíma nás len existencia riešenia (nepotrebujeme poznať usporiadanie vyhovujúce podmienkam) 75 / 214 Kritérium efektivity MP hlavolam - riešenie • je daný konečný počet kariet • každú kartu môžeme umiestnitna konečný počet pozícií • môžeme vyskúšať všetky možnosti • N = 25 x 25, počet možností 25 x 24---x 3 x 2 x 1 • 109 možností za sekundu => 490 miliónov rokov 76 / 214 Kritérium efektivity Hranice praktickej použiteľnosti ■' i Function ^^^ 20 60 100 300 1000 SN 100 300 500 1500 5000 Nx\og2N 86 354 665 2469 9966 N2 400 3600 10.000 90,000 1 million (7 digits) W3 8000 216.000 1 million (7 digits) 27 million (8 digits) 1 billion (10 digits) 2'v 1.048.576 a 19-digit number a 31-digit number a 91-digit number a 302-digit number N\ a 19-digit number an 82-digit number a 161-digit number a 623-digit number unimaginably large NN a 27-digit number a 107-digit number a 201-digit number a 744-digit number unimaginably large HJWBBJM Kritérium efektivity Number of nanoseconds since Big Bang 28 256 512 1024 2048 Kritérium efektivity Hranice praktickej použiteľnosti Function ^^^^^ 20 40 60 100 300 N2 1/2500 millisecond 1/625 millisecond 1/278 millisecond 1/100 millisecond 1/11 millisecond N5 1/300 second 1/10 second 78/100 second 10 seconds 40.5 minutes 2N 1/1000 second 18.3 minutes 36.5 years 400 billion centuries a 72-digit number of centuries N" 3.3 billion years a 46-digit number of centuries an 89-digit number of centuries a 182-digit number of centuries a725-digit number of centuries hranica: polynomiálna zložitosť prakticky riešiteľné vs prakticky neriešiteľné problémy 79 / 214 I Kritérium efektivity Prakticky neriešiteľné problémy • použiť výkonnejší počítač? pre algoritmus zložitosti 2N: ak dnes vyriešime inštancie veľkosti max. C, tak 1000 krát rýchlejším počítačom vyriešime inštancie veľkosti max. C+ 9.97. • zintenzívniť výzkum a nájsť efektívnejší algoritmus? • dokázať, že neexistuje efektívnejší algoritmus? Millenium Prize Problem, 1 000 000 http://www.claymath.org/millennium/ • je otázka dôležitá? existujú aj iné (dôležité) problémy podobného charakteru? 80 / 214 NP-úplné problémy NP-úplné problémy NP-úplné problémy problémy, pre ktoré majú lineárny dolný odhad zložitosti a exponenciá ny horný odh ad zložitosti nepoznáme lepší než exponenciálny algoritmus a zároveň nevieme dokázat, či existuje alebo neexistuje asymptoticky efektívnejší algoritmus 81 / 214 I NP-úplné problémy NP-úplné problémy - príklady dvojrozmerné pokrytie daných je N štvoruholníkov; je možné pokryť nimi štvorcovú plochu? Hamiltonovská cesta daný je neorientovaný graf; existuje v grafe cesta, ktorá navštívi každý vrchol práve jeden krát? obchodný cestujúci daný je neorientovaný graf s ohodnotenými hranami a konštanta K; existuje v grafe Hamiltonovský cyklus dĺžky nanajvýš K? problém rozvrhu daných je M miestností a N prednášok, každá prednáška má určený začiatok a koniec; je možné rozdeliť prednášky do daných miestností? splniteľnosť daná je logická formula; existuje priradenie hodôt jej premenným, pre ktoré je formula splnená? ... a tisíce ďalších 82 / 214 I NP-úplné problémy NP-úplné problémy - spoločná charakteristika • rozhodovacie problémy (odpoveď je "Ano" alebo "Nie") 9 existencia čiastočných riešení • hľadanie riešenia problému pomocou zpaätného vyhľadávania (backtracking); exponenciálny algoritmus • je extrémne ťažké rozhodnúť, či reišením vstupnej inštancie je "Áno" aelbo "Nie" • ak riešením inštancie je "Áno", tak je veľmi jednoduché dokázať to — pomocou tzv. certifikátu • obvykle je certifikát krátky reťazec (lineárny voči N) a jeho overenie je možné v polynomiálnom čase 83 / 214 I NP-úplné problémy Alternatívna charakterizácia NP-úplných problémov • predpokladajme, že máme magickú micu, ktorú budeme používať pri zpätnom vyhľadávaní (backtrackovanľ) riešenia inštancie • vždy, keď sa máme rozhodnúť, ako rozšíriť čiastočné riešenie, rozhodnutie urobíme tak, že si hodíme mincou • "magično" — minca vždy vyberie možnosť, ktorá vedie k riešeniu "Áno" (samozrejme, len ak existuje) • pojem nedeterminizmu • pre NP-úplné problémy máme nedeterministické polynomiálně algoritmy • NP v názve NP-úplný je skratka pre pre nedeterministický polynomiálny 84 / 214 I NP-úplné problémy Pojem úplnosti buď všetky NP-úplné problémy sú prakticky riešiteľné alebo žiaden z nich nie je prakticky riešiteľný • ak přejeden NP-úplný problém skonštruujeme polynomialny algoritmus, tak máme polynomiálně algoritmy pre všetky NP-úplné problémy • ak pre niektorý NP-úplný problém dokážeme neexistenciu polynomiálneho algoritmu, tak polynomialny algoritmus neexistuje pre žiaden NP-úplný problém 85 / 214 Dôkaz úplnosti Polynomialna časová redukcia Pre dané dva rozhodovacie problémy Pi a P2; polynomialna časová redukcia je algoritmus A taký, že • A má polynomiálnu časovú zložitost a • vstupnú inštanciu X problému Pi transformuje na vstupnú inštanciu Y problému P2 takú, že riešením X je "Áno" vtedy a len vtedy, ak riešení Y je tiež "Áno". Polynomiálna redukcia - príklad redukcia problému Hamiltonovskej cesty na problém obchodného cestujúceho Transformácia graf G = (V, H) (inštancia problému Hamiltonovskej cesty) graf G = (V, H) s ohodnotením w : H —> N a konštanta K, kde V = V, ~H = V x V, w(h) = 1 pre všetky hrany h e H, w{h) = 2 pre všetky hrany h e~H\H, a K = \V\ + 1 (inštancia problému obchodného cestujúceho) • transformácia sa dá vypočítať v polynomiálnom čase • v G Hamiltonovská cesta existuje vtedy a len vtedy ak riešením inštancie (G, w, K) problému obchodného cestujúceho je "Áno" Polynomiálna redukcia a existencia algoritmu Predpokladajme, že máme polynomialny algoritmus O pre problém obchodného cestujúceho. Ukážeme, ako za tohto predpokladu skonštruujeme polynomialny algoritmus H pre problém Hamiltonovskej cesty. Algoritmus H O vstup G transformuj na (G, w, K) O aplikuj O na (G, w, K) O ak riešením (G, w, K) je "Áno", tak vráť odpoveď "Áno" O v opačnom prípade vráť odpoveď "Nie" Polynomiálna reduckia a úplnost Fakt Všetky NP-úplné problémy sú vzájomne polynomiálně redukovatelne 0 ak chceme o probléme R dokázať, že je NP-úplný, nemusíme ukazovať redukciu medzi R a vetkými ostatnými NP-úplnými problémami • stačí ukázať polynomialnu redukciu problému R na jeden konkrétny NP-úplný problém • redukcia je tranzitívna Cookova veta Problém splniteľnosti je NP-úplný. Polynomialna redukcia - príklad 2 Redukcia 3-zafarbenia mapy na problém splniteľnosti 90 / 214 naros P=NP? problém P je trieda prakticky riešiteľných problémov (tj. problémov, pre ktoré existujú polynomiálně algoritmy) Fakt P C NP J Otvorený problém P = NP ? Dôsledky riešenia problému. 91 / 214 Čiastočné riešenie NP-úplných problémov • pseudopolynomialne algoritmy • aproximatívne algoritmy • náhodnostné algoritmy • kvantové algoritmy • genetické algoritmy 92 / 214 Ďalšie zložitostné trie Ešte ťažšie problémy • NP-úplné problémy môžu mať polynomiálně algoritmy • existujú problémy, ktoré dokázateľne nemôžu mať efektívnejšie než exponenciálne (prípadne ešte zložitejšie) algoritmy Príklady: pravdivost formule v bohatšej logike 93 / 214 Ďalšie zložitostné trie Priestorová zložitosť • časová zložitosť > priestorová zložitosť • polynomiálny priestor (PSPACE) • PSPACE-úplné problémy 94 / 214 Ďalšie zložitostné trie Teória výpočtovej zložitosti • pojem zložitostnej triedy • vzťahy medzi zložitostnými triedami • LOGTIME C LOGSPACEC PTIME C PSPACE C EXPTIME C EXPSPACE ... • analogicky pre nedeterminizmus • kľúčová otázka presného vzťahu P C N P C PSPACE 95 / 214 F I Nerozhodnutel nost IB110 96 / 214 Put the right kind of software into a computer, and it will do whatever you want it to. There may be limits on what you can do with the machines themselves, but there are no limits on what you can do with software. Time Magazin, April 198^ 97 / 214 Nerozhodnutelné problémy Otázka • existujú algoritmické problémy, ktoré sú prakticky neriešitelné? • je to len otázka dostatočne dlhého času, výkonného hardwaru resp. sofistikovaných algoritmov ??? • alebo existujú problémy, ktoré sú principiálne neriešiteľné ??? i / 214 Nerozhodnutelné problémy Pravidlá • uvažujeme algoritmické problémy (tj. problémy určené svojou množinou vstupných inštancií a požadovaným vzťahom medzi vstupom a výstupom) • problémy s nekonečnou množinou vstupných inštancií (v opačnom prípade pre problém vždy existuje algoritmus založený na vymenovaní všetkých vstupov a k ním príslušných výstupov) • algoritmus = program zapísaný v programovacom jazyku vyššej úrovne Nerozhodnutelné problémy Príklad - domino Vstup (konečná) množina T typov dlaždíc s farebnými hranami Otázka je možné dlaždicami pokryť ľubovoľne veľkú plochu tak, aby sa dlaždice vždy dotýkali hranami rovnakej farby? z každého typu je k dispozícii neobmedzený počet dlaždíc Nerozhodnutelné problémy Príklad - domino, inštancia 1 B ^ riešením inštancie 1 je "Áno" 101 / 214 Nerozhodnutelné problémy Príklad - domino, inštancia 2 b a riešením inštancie 2 je "Nie" 102 / 214 Nerozhodnutelne problémy Nerozhodnutelne problémy Definícia Problém, pre ktorý neexistuje žiaden algoritmus, sa nazýva nerozhodnutelný (algoritmicky neriešiteľný). prakticky riešiteľné problémy prakticky neriešiteľné problémy nerozhodnutelne problémy Nerozhodnutelné problémy Príklad - domino Fakt Problém domina je nerozhodnutelný • "zdroj" nerozhodnutelnosti • ekvivalencia s problémom pokrytia nekonečnej plochy • periodicita riešenia • je dôvodom potenciálne nekonečný počet možností? • dominový had a jeho varianty 104 / 214 Nerozhodnutelné problémy Príklad - Postov korešpondečný problém (PKP) Vstup dva zoznamy slov X = (xi,.. . x„) a Y = (yi,.. . y„) Otázka existuje konečná postupnost indexov taká, že spojením príslušných slov zoznamu X vznikne rovnaké slovo ako spojením príslušných slov zoznamu Y? 1 2 3 4 5 X Y abb bbab a aa bab ab baba aa aba a riešením inštancie je "Ano", príkladom postupnosti je 2, 1, 1, 4, 1, 5 1 2 3 4 5 X bb a bab baba aba Y bab aa ab aa a nesením istancie je nie I Nerozhodnuteľné problémy Príklad - ekvivalencia a verifikácia programov Ekvivalencia Vstup dva programovacie jazyky vyššej úrovne, ktorých syntax je daná syntaktickým diagramom alebo v BNF Otázka sú množiny syntakticky správnych programov pre oba jazyky zhodné? Verifikácia Vstup popis algoritmického problému a program v programovacom jazyku vyššej úrovne Otázka rieši program daný problém? (tj. odpoveď je "Áno" ak pre každú vstupnú inštanciu problému sa výpočet programu zastaví a dá správnu odpoveď) Pre oba problémy závisí nerozhodnuté!nosi na voľbe programovacieho jazyka resp. na voľbe jazyka pre popis algoritmického problému. Pre bežné jazyku sú oba problémy nerozhodnuteľné. 106 / 214 Nerozhodnutelné problémy Príklad - problém zastavenia Uvažujme algoritmy A a B s množinou vstupných inštancií N Algoritmus A while X^ldoX^X-2od return X Algoritmus B while X ŕ 1 do if X je sudé do X <- X/2 if X je liché do X <- 3X + 1 od return X Algoritmus A pre sudé čísla neskončí. O algoritme B nieje známe, či skončí pre všetky vstupné inštancie. Nerozhodnutelné problémy Príklad - problém zastavenia Vstup program R v programovacom jazyku L vyššej úrovne a množina vstupných inštancií programu R Otázka zastaví sa výpočet R pre každú vstupnú inštanciu? Problém zastavenia je nerozhodnuteľný. Notácia: R(x) j označuje, že výpočet R na x skončí; symbol R(x) j označuje, že neskončí. Nerozhodnutelne problémy Riceova veta Rozhodnuteľnosť je výnimka, ktorá potvrdzuje pravidlo Zaujíma nás netriviálna vlastnosť programu, ktorá je (1) pravdivá pre niektoré a nepravdivá pre ostane programy (2) nieje viazaná na syntax programu, ale vzťahuje sa k problému, ktorý program rieši. Riceova veta Všetky netriviálne vlastnosti programov sú nerozhodnutelne. Príklady: je výstupom programu vždy "Áno"?, zastaví program pre každý vstup? Metóda diagonalizácie Dôkaz nerozhodnutelnosti Analógia s dôkazom NP-úplnosti (1) dokážeme nerozhodnuteľnosť nejakého problému (2) nerozhodnuteľnosť ďalších problémov dokazujeme metódou redukcie V prípade nerozhodnutelnosti použijeme redukciu, ktorá nemusí byt polynomiálně časovo ohraničená. 110 / 214 Metóda diagonalizácie Redukcia Redukcia Pre dané dva rozhodovacie problémy Pi a P2; redukcia je algoritmus A ktorý vstupnú inštanciu X problému Pi transformuje na vstupnú inštanciu Y problému P2 takú, že riešením X je "Áno" vtedy a len vtedy, ak riešením Y je tiež "Áno". 111 / 214 Metóda diagonalizácie Redukcia - príklad redukcia problému zastavenia na problém verifikácie 112 / 214 I Metóda diagonalizácie Redukcia a dôkaz nerozhodnuteľnosti Fakt Ak P\ sa redukuje Pi a P\ je nerozhodnuteľný, tak aj Pi je nerozhodnuteľný. Predpokladajme, že P2 je rozhodnutelný a že B je algoritmus, ktorý ho rieši. Pomocou B skonštruujeme algoritmus pre P\. Konretne, vstupnú inštanciu X problému P\ prevedieme pomcou algoritmu redukcie na vstupnú inštanciu Y problému Pi- Použijeme algoritmus B a nájdeme riešenie Y. Ak riešením Y je "Áno" tak riešením X je tiež "Áno". Ak riešením Y je "Nie" tak riešením X je tiež "Nie". To je ale spor s predpokladom, že P\ je nerozhodnuteľný. 113 / 214 Metóda diagonalizácie Nerozhodnuteľnosť problému zastavenia Tvrdenie Neexistuje program v L, ktorý pre ľubovoľnú dvojicu (R, X) (R je syntakticky správny program v L a X je symbol reťazcov), dá na výstup "Áno" práve ak výpočet R pre vstup X skončí po konečnom počte krokov a dá na výstup "Nie" v opačnom prípade. Neexistenciu programu požadovaných vlastností dokážeme sporom. 114 / 214 I Metóda diagonalizácie Nerozhodnuteľnosť problému zastavenia Predpokladajme, že existuje program požadovaných vlastností, nazvime ho Q. Skonštruujeme nový program v jazyku L, nazvime ho S, nasledovne: O vstupom programu S je syntakticky správny program W v jazyku L Q program S prečíta W a vytvorí kópiu W O 5 aktivuje program Q so vstupom (W, W) (volaním Q ako procedúry) O výpočet Q na vstupe (W, W) skončí (z predpokladu o vlastnostiach Q) a vráti S odpoveď ("Áno" alebo "Nie"). O ak Q skončí s odpoveďou "Áno", tak S vstúpi do nekonečného cyklu (jeho výpočet sa lezastaví) © ak Q skončíš odpoveďou "Nie", tak S dá na výstup "Áno". 115 / 214 Metóda diagonalizácie Nerozhodnuteľnosť problému zastavenia - spor Z konštruckie programu S je zrejmé, že S sa pre každý vstup W zastaví (s odpoveďou "Áno") alebo jeho výpočet cyklí donekonečna. Uvážme výpočet S na vstupe W = S. S aktivuje program Q na vstupe (S, S) (bod 3). Podľa predpokladu Q zastaví. Sú dve možnosti: O Q skončíš odpoveďou "Anc" (tj. áno, program S sa na vstupe S zastaví); v takomto prípade ale S vstúpi do nekonečného cyklu. Dostávame spor. O Q skončíš odpoveďou "Nie" (tj. nie, program S sa na vstupe S nezastaví); v takomto prípade ale S dá odpverf "Áno". Opäť dostávame spor. 116 / 214 Metóda diagonalizácie Metóda diagonalizácie • Georg Cantor • obecná metóda, postavená na princípe rozdielnych kardinalít 9 dôkaz, že reálnych čísel je viac ako racionálnych; dolné odhady zložitosti problémov, ... 117 / 214 I Čiastočne rozhodnutelné problémy a stupne nerozhodnuteľnosti Konečné certifikáty pre nerozhodnuteľné problémy Analógia s NP-úplnými problémami. V prípade nerozhodnuteľných problémov požadujeme od certifikátov len konečnosť a existenciu algoritmu ktorý overí, či daný reťazec je certifikátom. PKP certifikátom odpovede "Áno" je konkrétna, konečná postupnosť indexov; ľahko overíme, či daná postupnosť indexov má požadovanú vlastnosť problém zastavenia certifikátom je samotný konečný výpočet; jednoducho overíme, či daná postupnosť krokov je korektným výpočtom programu na vstupe. hadové domino certifikátom je postupnosť dlaždíc a spôsob ich skladania domino certikát existuje pre odpoveď nie. Certifikátom je konečná plocha E. Pretože E je konečný a počet typov dlaždíc je tiež konečný, dokážeme overiť, že E sa nedá pokryť (preveríme všetky možnosti). I Čiastočne rozhodnutelné problémy a stupne nerozhodnuteľnosti Čiastočne rozhodnutelné problémy Všetky predchádzajúce problémy mali certifikát přejeden typ odpovede; hovoríme o tzv. jednosmernom cerfikáte. Definícia Nerozhodnutelne problémy, ktoré majú jednosmerný certifikát, sa nazývajú čiastočne rozhodnutelné. Čiastočne rozhodnutelné problémy majú algoritmus, ktorý je korektný pre jeden typ vstupných inštancií (tj. buď pre vstupy s odpoveďou "Áno", alebo pre vstupy s odpoveďou "Nie"). Algoritmus systematicky overuje všetky konečné reťazce, či sú certifikátom daného vstupu. Čiastočne rozhodnutelné problémy a stupne nerozhodnuteľnosti Dvojsmerné certifikáty • môže nastať situácia, keď pre daný problém máme certifikát ako pre odpoveď "Áno", tak aj (iný) certifikát pre odpoveď "Nie" (hovoríme o tzv. dvojcestnom certifikáte)? • príklad: problém Hamiltonovského cyklu. Certifikátom pre "Áno" vstup je permutácia vcholov (jednoducho overíme, či tvorí Hamiltonovský cyklus). Certifikátom pre "Nie" vstup sú všetky permutácie vrcholov (jednoducho overíme, že žiadna permutácia netvorí Hamiltonovský cyklus). Fakt Ak problém má dvojcestný certifikát, tak je rozhodnutelný. Algoritmus systematicky a striedavo overuje všetky konečné reťazce či sú certifikátom pre daný vstup. Konečnosť je zaručená, pretože každý vstup má svoj certifikát. Čiastočne rozhodnutelné problémy a stupne nerozhodnuteľnosti Ešte ťažšie problémy? • všetky čiastočne rozhodnutelné problémy sú vzájomne redukovatelne (analógia s NP-úplnými problémami, tkroé sú polynomiálně ekvivalentne) • existujú problémy, ktoré sú ťažšie než NP-úplné; platí analógia aj pre čiastočne rozhodnutelné problémy? problém verifikácie existuje redukcia problému zastavenia na problém verifikácie; opačná redukcia ??? úplný problém zastavenia (je výpočet programu konečný pre všetky vstupné inštancie?) Existuje redukcia problému zastavenia na úplný problém zastavenia; opačná redukcia ??? Problém verifikácie ani úplný problém zastavenia nemajú certifikáty I Čiastočne rozhodnutelné problémy a stupne nerozhodnuteľnosti Stupne nerozhodnuteľnosti • analogicky ako rozhodnutelné problémy môžeme zoskupiť do rôznych zložitostných tried, tak aj nerozhodnutelne problémy tvoria úrovne podľa stupňa nerozhodnuteľnosti • každá úroveň obsahuje problémy, ktoré sú ešte ťažšie než problémy predchádzajúcej úrovne • prvé dve úrovne hierarchie tvoria čiastočne rozhodnutelné a nerozhodnutelne problémy • ďalšie úrovne označujeme súhrnne ako vysoko nerozhodnutelne problémy I Čiastočne rozhodnutelné problémy a stupne nerozhodnuteľnosti Vysoko nerozhodnuteľné problémy - príklad modifikácia problému domina kde požadujeme, aby v nekonečnom pokrytí bola vopred specifikovaná dlaždica použitá nekonečne veľa krát 123 / 214 Univerzalita a robustnost IBllO 124 / 214 Jednoduchý výpočtový model Hľadáme čo najjednoduchší počítač (výpočtový model), ktorý je schopný realizovať všetky algoritmické výpočty. Prečo? • aký najjednoduchší model je schopný realizovať všetky výpočty? • obecnosť výsledkov o praktickej neriešitelnosti a nerozhodnutelnosti • presná formulácia a formálne dôkazy tvrdení týkajúcich sa praktickej neriešitelnosti a nerozhodnutelnosti Jednoduchý výpočtový model - dáta • dáta = reťazce symbolov • počet rôznych symbolov potrebných na zakódovanie reťazcov je konečný (podobne ako na zakódovanie všetkých čísel nám stačí v desiatkovej resp. binárnej sústave 10 resp. 2 číslice) • dáta môžeme zapisovať na jednorozmernú pásku, ktorá obsahuje políčka; na každom políčku je zapísaný jeden symbol, ktorý je prvkom vstupnej abecedy Linearizácia dátových štruktúr • linearizácia zoznamu • linearizácia dvojrozmerného poľa, matice • linearizácia stromu Dynamické dátové štruktúry a neohraničenosť jednosmernej pásky Jednoduchý výpočtový model - riadiaca jednotka b/a/*/d/a/b/b/*/b/ 127 / 214 Jednoduchý výpočtový model - riadiaca jednotka • výpočet je realizovaný riadiacou jednotkou • riadiaca jednotka je vždy v jednom z konečne veľa rôznych stavov (stav zodpovedá inštrukcii algoritmu) • riadiaca jednotka vždy snímá práve jedno políčko jednorozmernej pásky (hodnota, s ktorou manipuluje inštrukcia algoritmu) 9 atomické akcie • prečítanie symbolu z políčka pásky » zápis symbolu na políčko pásky a posun o jedno políčko na páske » zmena stavu riadiacej jednotky • závislosť zmeny na aktuálnych hodnotách Jednoduchý výpočtový model - základné operácie jeden krok výpočtu • prečítanie symbolu • podľa aktuálneho stavu riadiacej jednotky a prečítaného symbolu sa vykoná • zmena stavu • zápis symbolu • posun o jedno políčko vpravo alebo víavo Turingov stroj Alan Turing, 1936 129 / 214 Turingov stroj Turingov stroj Turingov stroj (TS) pozostáva z • (konečnej) množiny stavov • (konečnej) abecedy symbolov • nekonečnej pásky rozdelenej na políčka • čítacej a zapisovacej hlavy, ktorá sa pohybuje po páske a sníma vždy 1 políčko pásky • prechodového diagramu 130 / 214 Turingov stroj - prechodový diagram Prechodový diagram • orientovaný graf • vrcholy grafu sú stavy TS • hrana z vrcholu s do vrcholu t reprezentuje prechod a je označená dvojicou tvaru (a/b, L) alebo (a/b, R); a a je symbol, ktorý hlava TS z pásky číta (tzv. spínač) • b je symbol, ktorý na pásku zapisuje • L resp. R určuje smer pohyb hlavy doľava resp. doprava • požadujeme, aby diagram bol jednoznačný (deterministický Turingov stroj), tj. zo stavu nesmú vychádzať dve hrany s rovnakým spínačom • jeden zo stavov je označený ako štartovný (počiatočný) stav (označený šípkou) • niektoré zo stavov sú označené ako koncové stavy (označené výrazným ohraničením) Tu ringov stroj - výpočet Krok výpočtu prechod z s do ŕ označený (a/b, L) v prechodovom diagrame ak riadiaca jednotka TS je v stave s a hlava číta symbol a, tak hlava prepise symbol a symbolom b, posunie sa o 1 políčko doľava a stav riadiacej jednotky sa zmení na í (analogicky pre (a/b, R) a pohyb vpravo) Výpočet Výpočet začína v počiatočnom stave na najlavejšom neprázdnom políčku pásky. Výpočet prebieha krok po kroku tak, ako predpisuje prechodový diagram. Výpočet sa zastaví keď dosiahne niektorý z koncových stavov. I Turingov stroj Turingov stroj pre palindrómy .-. a/a, R f \b/b, R — -i J a/a, L return r , J b/b, L #/#, R 133 / 214 #|#|t7|fc|f>|ŕ7|#|#|-- t © # # # b b\a\#\# f © # # # b b\#\#\# n Turingov stroj # # # b b a # # FCD # # # b b a # # í© ■■■### í) &|a|#|#|--- t © ■■■### b b\a\#\# ■■■ \ © ■•• #|#|#|ŕ|ft|#|#|#|--- + © riß) 134 / 214 T ###bb### ####b### r@ Turingov stroj 135 / 214 I Turingov stroj Simulátor Turingových strojov http://www.f i.muni.cz/ xbarnat/tafj/turing 136 / 214 Turingov stroj ako algoritmus • Turingov stroj môžeme chápať ako počítač s jedným, fixovaným programom • softwarom je prechodový diagram; hardwarom je riadiaca jednotka a páska • jednotlivé TS sa líšia iba svojim softwarom, preto často hovoríme o programovaní Tu ringovho stroja Turingov stroj ako algoritmus • Turingov stroj môžeme naprogramovať tak, aby riešil rozhodovací problém • pre rozhodovací problém P, ktorého množina vstupných inštancií je kódovaná ako množina linearizovaných reťazcov, konštruujeme Turingov stroj M s počiatočným stavom s a dvoma koncovými stavmi YES a NO pre každý vstup X, ak M začne výpočet v stave s na najlavejšom symbole reťazca X, tak M skončí výpočet v stave YES a NO v závislosti na tom, či výstupom P pre X je "Áno" alebo "Nie" Turingov stroj ako algoritmus Turingove stroje môžu byť naprogramované aj pre riešenie iných než rozhodovacích problémov. V takomto prípade predpokladáme, že keď sa TS zastaví (prejde do koncového stavu), tak výstupom je reťazec zapísaný na páske medzi dvoma špeciálnymi znakmi (napr. !) Ak sa výpočet zastaví a na páske je iný počet symbolov ! ako 2, chápeme výpočet ako neukončený (tj. ako výpočet, ktorý cyklí donekonečna). 17 Churchova Tu ringová hypotéza Aké problémy sú riešitelné pomocou vhodne naprogramovaného TS? Churchova Turingova hypotéza Každý algoritmický problém, pre ktorý existuje program v nejakom programovacom jazyku vyššej úrovne a je riešiteľný na nejakom hardwaru, je riešiteľný aj na Turingovom stroji. Prečo hypotéza? CT hypotéza formuluje vzťah medzi dvoma konceptami: • matematicky presný pojem riešitelnosti na Turingovom stroji a • neformálny koncept algoritmickej riešitelnosti, ktorý je postavený na pojmoch "programovací jazyk vyššej úrovne", "program v programovacom jazyku" Churchova Turingova hypotéza Argumenty pre Churchovovu Tu ringovú hypotézu CT hypotézu formulovali v 30-tych rokoch nezávisle Alonso Church a Alan Turing. Od tej doby bolo navrhnutých množstvo "univerzálnych" modelov (absolútnych, schopných riešii všetky mechanicky riešitefné problémy) • Turingove stroje (Alan Turing) • lambda kalkulus (Alonso Church) • produkčné systémy (Emil Post) • rekurzívně funkcie (Stephen Kleené) • kvantové počítače • ... Fakt 0 všetkých navrhnutých formalizmoch je dokázané, že sú ekvivalentné v tom zmysle, že určujú zhodnú triedu algoritmicky riešitelných problémov. 141 / 214 Churchova Turingova hypotéza Dôsledky Churchovej Turingovej hypotézy • extrémne výkonné superpočítače nie sú silnejšie než malé počítače s jednoduchým programovacím jazykom; za predpokladu neohraničeného času a velkosti pamäte dokážu obidva riešiť tie isté algoritmické problémy • pojem algoritmicky riešiteľného (rozhodnutelného) problému je robustný, tj. je nezávislý na konkrétnej voľbe výpočtového modelu resp. programovacieho jazyka • CT hypotéza podporuje správnosť definície nerozhodnuteľných problémov 142 / 214 Modifikácie Turingovho stroja Argumentom podporujúcim CT hypotézu je aj robustnosť TS. Modifikácie • TS, ktorý má po skončení výpočtu zapísaný na páske len vstupný a výstupný reťazec • TS s jednosmerne nekonečnou páskou • TS s dvojrozmernou páskou • TS s konečným počtom pások (každá más svoju čítaciu/zapisovači u hlavu) Fakt Všetky uvedené modifikácie sú vzájomne ekvivalentné Dôkaz technikou simulácie: ukážeme, že výpočet jedného zariadenia sa dá simulovať na druhom zariadení a naopak rogramy s počítadlami (Counter Programs, CP) • programy manipulujú s prirodzenými číslami uloženými v preme • tri elementárne operácie X <— 0 priradí premennej hodnotu 0 X^Y + 1 X <— Y — 1 ak hodnota Y je 0, tak X priradí hodnotu 0 • jeden elementárny riadiaci príkaz ifX = 0 goto G, kde X je premenná a G je návestie pripojené k príkazu Modifikácie Turingovho stroja Programy s počítadlami - príklad A : if X = 0 goto G X<-X-l V <- Y + l V <-V-l B : if V = 0 goto A V <- V-l Z^Z + 1 if U = 0 goto B vykonanie goto G je ekvivalentom úspešného ukončenia výpočtu 145 / 214 I Modifikácie Turingovho stroja Turingove stroje a programy s počítadlami TS manipulujú so symbolmi, PS s číslami je možná ich vzájomná simulácia? Modifikácie Turingovho stroja Simulácia Turingovho stroja programom s počítadlami obsah pásky —> čísla pre jednoduchosť predpokladajme, že abeceda TS má desať znakov znaky očíslujeme a reťazce znakov prevedieme na čísla Príklad #-0 1-1 *-2 a-3 6-4 c-5 d-6 e-7 f - 8 g-- 9 reŕ'azec ...##ai) * eb!#3ía##... \/ ktorom je snímaný symbol b, prevedieme na dvojicu čísel 3427 a 393014 147 / 214 Simulácia Turingovho stroja programom s počítadlami zmena symbolu na páske zmena poslednej číslice v druhom čísle Príklad ak symbol b prepíšeme symbolom g, tak číslo 393014 sa zmení na 393019, PC pripočíta 5 krát hodnotu 1 posun hlavy doprava prvé číslo vynásobíme 10 a pripočítame k nemu poslednú číslicu druhého čísla druhé číslo vydělíme 10 (celočíselné) analogicky pre posun hlavy doľava zmena stavu stavu TS zodpovedá skupina inštrukcií CP; zmena stavu je simulovaná skokom na novú skupinu inštrukcií (príkaz goto) CP, ktorý simuluje TS, má len dve počítadlá! 52 I Modifikácie Turingovho stroja Simulácia programu s počítadlami Turingovym strojom čísla <— symboly hodnota každej premennej je zapísaná ako postupnosť symbolov = číslic; jednotlivé hodnoty sú vzájomne oddelené špeciálnym symbolom (napr. *) inštrukcie <— stavy každej inštrukcii programu zodpovedá skupina stav TS, vykonenie inštrukcie je simulované prechodom do príslušného stavu a realizácia postupnosti krokov, ktoré potrebným spôsobom upravia obsah premennej 149 / 214 I Modifikácie Turingovho stroja Simulácie ako redukcie Ak model A simuluje model B, tak máme redukciu medzi týmito modelmi. Redukcia prevedie program modelu A a jeho vstup X na program modelu B a jeho vstup Y. CT hypotéza ukazuje, že naše úvahy pri konštrukcii redukcií boli korektné. 150 / 214 I Modifikácie Turingovho stroja Simulácie ako redukcie Ak model A simuluje model B, tak máme redukciu medzi týmito modelmi. Redukcia prevedie program modelu A a jeho vstup X na program modelu B a jeho vstup Y. CT hypotéza ukazuje, že naše úvahy pri konštrukcii redukcií boli korektné. Príklad nerozhodnuteínosi problému zastavenia O formálne dokážeme nerozhodnuteínosi problému pre TS Q podlá CT hypotézy problém zastavenia nemôže byt rozhodnutelný ani pre žiaden iný programovací jazyk vyššetj úrovne (je ekvivalenty TS!) Fenomén algoritmus, ktorého vstupom je iný algoritmus J 150 / 214 I Univerzálny Turingov stroj Univerzálny algoritmus jeden z najdôležitejších dôsledkov CT hypotézy Existencia univerzálneho algoritmu, ktorý má schopnosť chovať sa ako akýkoľvek iný algoritmus. • vstupom pre univerzálny algoritmus je popis akéhokoľvek algoritmu A a akéhokoľvek jeho vstupu X • univerzálny algoritmus simuluje výpočet A na X • výpočet univerzálneho algoritmu sa zastaví práve ak výpočet A na X sa zastaví; ako výstup poskytne univerzálny algoritmus presne tú istú odpoveď ako poskytne A na X ak fixujeme algoritmus A a meníme X, tak univerzálny algoritmus sa chová presne ako algoritmus A 151 / 214 52 Univerzálny Turingov stroj Univerzálny algoritmus • môže byt vstupom univerzálneho algoritmu program v akomkoľvek programovacom jazyku? • využijeme CT hypotézu a poznatok o ekvivalencii všetkých známych formalizmov pre popis algoritmov • ku konštrukcii univerzálneho algoritmu potrebujeme len jazyk L\, v ktorom napíšeme program Ľ pre univerzálny algoritmus; program akceptuje ako vstup ľubovoľný program napísaný vo fixovanom konkrétnom jazyku Z. 2 • program Ľ je nezávislý na výbere modelu, pretože podľa CT hypotézy O môže byť napísaný v akomkoľvek jazyku Q dokáže simulovať akýkoľvek algoritmus popísaný v akomkoľvek jazyku Vhodným kandidátom pre jazyky L\ a Z. 2 sú Tu ringové stroje. 152 / 214 Univerzálny Turingov stroj Univerzálny Turingov stroj • potrebujeme popísať Turingov stroj ako lineárny reťazec nad konečnou abecedou symbolov 9 stačí linearizovať prechodový diagram • mark ** mark YES (#/#, L) * mark movea (a/#, R) * movea movea (a/a/, R)*... • linearizovaný prechodový diagram prevedieme štandartným spôsobom na reťazec nad fixovanou abecedou (napr. binárnou) • podobne linearizujeme a kódujeme aj vstup simulovaného TS • samotný program univerzálneho TS je jednoduchý svojim princípom: uchováva si aktuálny stav simulovaného TS, obsah jeho pásky a čítaný symbol; z linearizovaného popisu simulovaného TS odvodí, aké akcie sa majú realizovať v ďalšom kroku výpočtu simulovaného TS 153 / 214 I Univerzálny Turingov stroj Univerzálny program s počítadlami • vstupom je dvojica čísel; prvé číslo je kódom nejakého programu s počítadlami, druhé číslo je kódom jeho vstupu • univerzálny program je možné skonštruovať tak, aby využíval len dve počítadlá 154 / 214 Robustnost triedy prakticky riešiteľných problémo Modifikované programy s počítadlami Motivácia • TS manipuluje jednom kroku výpočtu s jedným symbolom pásky (s jednou číslicou čísla) m CP mení jednou inštrukciou hodnotu premennej o 1 (exponenciálne menej efektívne v porovnaní s TS) • narovnanie diskrepancie • CP musí mať možnosť k číslu pridať alebo odobrať číslicu v konštantnom čase Modifikácia množinu inštrukcií CP rozšírime o 2 nové inštruckie X^XxlO X <— X/10 celočíselné delenie 155 / 214 Robustnost triedy prakticky riešitelných problémov Polynomiálna redukcia Existencia redukcií medzi programovacími jazykmi vyššej úrovne (dostatočne silnými výpočtovými modelmi) ukazuje, že trieda rozhodnutelných problémov je invariantná voči voľbe jazyka (modelu). Otázka Aká je zložitosť redukcie? Fakt Ak oba modely manipulujú s číslami v inej než unárnej sústave, tak redukcia má polynomiálnu časovú zložitosť . 156 / 214 Robustnost triedy prakticky riešiteľných problémo Zložitosť redukcií medzi TS a modifikovanými CP Zložitosť výpočtu TS počet krokov výpočtu C P počet vykonaných inštrukcií Zložitosť výpočtu je funkciou dlžky vstupu; hodnota funkcie pre argument N zhora ohraničuje zložitosť výpočtov na všetkýh vstupoch dlžky N. Dĺžkou vstupu pre TS je počet znakov vstupného reťazca, dĺžkou vstupu pre CP je počet číslic počiatočných hodôt premenných. Redukcia TS —► modifikované CP krok výpočtu je simulovaný zmenou hodnoty každého počítadla; zmena je realizovateľná konštantným počtom inštrukcií Redukcia modifikované CP —► TS každá inštrukcia je simulovaná konštantným počtom krokov TS a modifikované CP sú polynomiálně ekvivalentné mm 157 / 214 Robustnost triedy prakticky riešitelných problémov Polynomiálna redukcia - dôsledky Nech výpočtové modely A a B sú polynomiálně ekvivalentné. Ak algoritmický problém P je riešitelný na A s časovou zložitostou O (f (N)) ( f je funkcia dĺžky vstupu), tak existuje program pre B, ktorý rieši problém P a jeho časová zložitosť je 0(p(f(A/))), pričom p je nejaká (fixovaná) polynomiálna funkcia. Naopak, ak P je riešiteľný na B v čase ö{g{N)), tak existuje program pre A, ktorý rieši P s časovou zložitosťou ö{q{f{N))), pričom q je nejaká (fixovaná) polynomiálna funkcia. Ak TS rieši problém v polynomiálnom čase, tak aj modifikový CP rieši tento problém v polynomiálnom čase (a naopak). Ak neexistuje polynomiálny TS pre daný problém, tak neexistuje ani polynomiálny modifikoaný CP pre tento problém. 158 / 214 Robustnost triedy prakticky riešiteľných problémo Robustnost triedy prakticky riešiteľných problémov CT hypotéza ukazuje robustnosť pojmu rozhodnutelný problém. Polynomiálna ekvivalencia zjemňuje toto pozorovanie na prakticky riešiteľné problémy. Sekvenčná výpočtová hypotéza Pojem prakticky riešiteľného problému je robustný, tj. je nezávislý na konkrétnej voľbe výpočtového modelu resp. programovacieho jazyka. Hypotéza sa nevztahuje na modely s neohraničeným zdrojom paralelizmu, preto sa označuje ako "sekvenčná". Triedy P, N P, PSPACE, EXPTIME sú robustné Triedy s lineárnou časovou zložitostou nie sú robustné. 159 / 214 Robustnost triedy prakticky riešitelných problémov Nedeterministické Turingove stroje pre rozhodovacie problémy • v prechodovom diagrame je povolené, aby s jedného stavu vychádzal ľubovoľný počet hrán označených zhodým spínačom (symbolom, ktorý sa číta) • stroj má možnosť výberu, ktorý z prechodov použije • pre vstup X dá TS odpoveď "Áno" (akceptuje) práve ak existuje taká postupnosť výberu prechodov, pre ktorú výpočet skončiv koncovom stave YES (stroj uváži všetky možné výpočty na X a akceptuje X práve ak aspoň jeden z výpočtov skončí v stave YES) • v opačnom prípade, tj. ak žiaden výpočet neskončiv stave YES, dá odpoveď "Nie" Nedeterministické TS sú ekvivalentné (deterministickým) TS. 160 / 214 Robustnost triedy prakticky riešitelných problémov P=NP? problém - revízia Formálna definícia tried P a NP Trieda P (NP) obsahuje rozhodovacie problémy, ktoré sú riešiteľné Turingovymi strojmi (nedeterministickými TS) s polynomiálnou časovou zložitosťou. P=NP? problém Sú deterministické a nedeterministické Turingove stroje polynomiálně ekvivalentné? 161 / 214 Robustnost triedy prakticky riešitelných problémov P=NP? problém - revízia Definícia NP-ťažkého a NP-úplného probému Rozhodovací problém sa nazýva NP-ťažký ak každý problém z triedy P je na neho polynomiálně redukovateľný. Rozhodovací problém sa nazýva NP-úplný ak je NP-ťažký a naviac patrí do triedy N P. Fakty Ak nejaký NP-úplný problém patrí do triedy P, tak P = NP. Ak P 7^ NP, tak žiaden NP-úplný problém nieje riešiteľný algoritmom polynomiálnej zložitosti. 162 / 214 Robustnost triedy prakticky riešitelných problémov Turingove stroje a dolné odhady zložitosti problémov • dôkaz nerozhodnuteľnosti problému redukcia problému o ktorom je už dokázané, že je nerozhodnutelný, na problém o ktorom chceme dokázať, že je nerozhodnutelný príklad redukcia problému zastavenia na problém domina • dôkaz vzťahu medzi zložitostnými triedami metóda diagonalizácie príklady P C EXPTIME, PSPACE c EXPSPACE • dôkaz, že problém nepatrí do zložitostnej triedy dôsledok úplnosti príklad žiaden EXPTIME-úplný problém nepatrí do triedy P pre dôkaz horných odhadov zložitosti problémov nie sú TS vhodné; naopak je vhodné použil: programovací jazyk vyššej úrovne 163 / 214 Robustnost triedy prakticky riešiteľných problémo Redukcia problému zastavenie na problém domina problém domina úlohou je pokryť hornú polovicu nekonečnej plochy s podmienkou, že prvá dlaždica v T (nazveme ju ŕ) je umiestnená niekde v spodnom riadku problém zastavenia odpoveď "Áno" pre vstup (M, X) taký, že výpočet M na X sa nezastaví 164 / 214 Robustnost triedy prakticky riešiteľných problémo Redukcia problému zastavenie na problém domina Redukcia Vstup dvojica (M,X) Výstup množina typov dlaždíc T a dlaždica t Princíp konštrukcie (T, t) pokrytie dlaždicami korešponduje s výpočtom; pokrytie nekonečnej plochy je možné len v prípade existencie nekonečného výpočtu 165 / 214 Robustnost triedy prakticky riešitelných problémov N [/ NJ K ^ / \J/ \l/ 1/ \ #/ \ #/ \ v \ & / \ b/ \ # / # / / # \ / #\ / #\ / o\ / o\ / tí \ /7/ÍV(; #\ #\ . \ #/ \ #/ \ */ \ b/ \ V # / \ / #\ / #\ / #\ / b\ / b\ /mva fA. / #\ #\ . \ #/ \ #/ \ */ \ b/ \ V* y\nva \ # / # / V / # \ / #\ / #\ / b\ />ivíFl\ / a \ / #\ #\ . \ #/ \ #/ \ #/ \»!V'a, 0/ \ a / \ */ # / \ / #\ / #\ / #\ /rnvlh b\ / o\ / a \ / #\ #\ \ #/ \ V y4pva N"va, 'X fflvV \ /;/ \ ť7 / \ #/ # / / #\ / #\ /mk, a\ / &\ / fc\ / a \ / # \ # \ \ #/ \ v \111k, a/ \ &/ \ r/ \ a / \ # / # / ' A' °/\ ° oV 1 V\ 2 2/\ 3 v\ 4 4x\ 4 4 XT4 Robustnost triedy prakticky riešitelných problémov 16 ©• na poličko sa nehodí žiadna dlaždica == , í vypočet nemoze pokračovat ^ - Jednosmerné TS alebo konečné automaty • TS sú robustné voči modifikáciám • existuje modifikácia, ktorá zmení (zmenší) výpočtovú silu TS? • áno, modifikácia ale musí ohraničiť výpočtový zdroj Turingovho stroja polynomiálny čas trieda P polynomiálny priestor trieda PSPACE (triedy P a PSPACE sú menšie než trieda rozhodnutelných problémov) jeden smer pohybu na páske ohraničenie spočíva v tom, že TS nemá možnosť vrátiť sa k informácii, ktorú už raz prečítal a ani nemá možnosť si o prečítanom úseku uchovať kompletnú informáciu (riadiaca jednotka má len konečný počet stavov) = konečné automaty Konečné automaty • vstupný reťazec sa číta zľava doprava, symbol po symbole • prečítaný symbol sa neprepisuje • výpočet sa zastaví po prečítaní posledného symbolu alebo v situácii, keď prechodový diagram neumožňuje žiadny ďalší krok • ak sa výpočet zastaví po prečítaní celého vstupu v stave YES, znamená to odpoveď "Áno" (konečný automat akceptuje vstup); ak sa výpočet zastaví v inom stave alebo sa zastaví a nie je prečítaný celý vstup, znamená to odpoveď "Nie" (automat zamieta vstup) Konečné automaty - dolné odhady Problém rozhodnúť, či daný reťazec obsahuje rovnaký počet symbolov a, b Tvrdenie Neexistuje konečný automat, ktorý rieši tento problém. Dôkaz Sporom. Predpokladajme, že existuje automat F, ktorý problém rieši. Označme N počet stavov automatu F. Uvážme vstupný reťazec, ktorý obsahuje presne N + 1 symbolov a, za ktorými nasleduje presne N + 1 symbolov b. Pri čítaní úvodnej sekvencie a-čok musia byť dve políčka, ktoré automat číta v tom istom stave {počet políčok je N + 1, počet stavov je N). Vytvorme nový vstupný reťazec tak, že odstránime všetky symboly medzi týmito dvoma a-čkami (viz obrázok). Výpočet na novom vstupnom reťazci skončiv tom istom stave a v tej istej pozícii ako výpočet na pôvodnom vstupnom reťazci. Ak automat akceptuje obidva reťazce dostávame spor {modifikovaný reiazec nemá požadovanú vlastnosť). Naopak, ak automat obidva reťazce zamieta - spor {pôvodný retazec má požadovanú vlastnosť). Automaty stav s stav s U.I Y a(a a a a\a a a a ifr ŕ b b b b b ŕ; fe b i 2\3 4 5 6/7 8 9 10 |1 2 3 4 5 6 7 8 9 10 F£S.' vyber zo slova stav s j V fl íí Ír a a b Ŕ /> b /; b /j /; Ŕ *l 1 2 3 v 4 5 6 1 2 3 4 Y 5 6 7 8 9 10 YES! (správne NOV) automat počíta presne ako na pôvodnej postupnosti X 171 / 214 I Automaty Konečné automaty ako model systému s udalosťami d pressed display dule c pressed iressed c pressed update 10 min.J * ~ pressed 172 / 214 I Automaty Konečné automaty - terminológia pojem jazyka ako ekvivalentu pojmu rozhodovací problém regulárny jazyk regulárne výrazy 173 / 214 Generatľvne výpočtové modely Generatívne výpočtové modely Fixujme rozhodovací problém P (resp. jazyk Pi) rozhodovanie určiť, či pre daný vstup X je odpoveď "Áno" alebo "Nie" (resp. určit, či X patrí do jazyka Z_x) generovanie vymenovať všetky vstupy, pre ktoré je odpoveď "Áno" (resp. vymenoval: všetky slová jazyka Pi) Motivácia návod, ako vytvoriť "správny" reťazec formálna gramatika 174 / 214 Generatľvne výpočtové modely Formálne gramatiky príklad 175 / 214 Generatľvne výpočtové modely Formálne gramatiky - vlastnosti Fakt Trieda jazykov generovaných formálnymi gramatikami je práve trieda rozhodnutelných problémov. Formálne gramatiky s obmedzeniami kontextové gramatiky reťazec na ľavej strane pravidla je nie je dlhší než reťazec na pravej strane pravidla bezkontextové gramatiky na ľavej strane každého pravidla je práve jeden neterminálny symbol regulárne gramatiky 176 / 214 Formaine gramatiky - problem syntaktickej analýzy Pre danú formálnu gramatiku a reťazec rozhodnúť, či je slovo sa gramatikou vygenerovať. rozhodnut, či program v programovacom jazyku (definovanom gramatikou) je syntakticky správny Problém syntaktickej analýzy je čiastočne rozhodnutelný pre formálne gramatiky rozhodnutelný pre kontextové gramatiky polynomiálně riešiteľný pre bezkontextové gramatiky je dôležité, aby sme pre definíciu syntaxe programovacieho jazyka použili čo najjednoduchší typ gramatiky Alternatívne výpočtové modely IB110 178 / 214 Alternatívne výpočtové modely Motivácia existencia veľkej triedy prakticky neriešiteľných (a/e rozhodnutelných) problémov, ktoré potrebujeme prakticky riešiť! Idea využiť principiálne iné spôsoby počítania • paralelné počítanie • súbežnosť • kvantové počítanie • molekulárne počítanie • náhodnosť pomôže to 111 Paralelizmus Princíp paralelizmu Praktický príklad Varianta A veža o základe 1 m x 10 m a výšky 1 m; 1 murár vs 10 murárov Varianta B veža o základe 1 m x ma výšky m; 1 murár vs 10 murárov Jednoduchý program Varianta AX^3; Y <- 4 Varianta BX^3; Y <- X paralelizovatelne problémy vs vnútorne sekvenčné problémy 180 / 214 Paralelné sčítovanie First step (A/72 processors) Second step (A74 processors) log2 Nth step (1 processor) 181 / 214 Paralelné sčitovanie pre sčítanie 1 000 čísel potrebujeme v 1. kroku 500 procesorov v 2. kroku 250 procesorov v 3. kroku 125 procesorov pri vhodne zvolenej dátovej štruktúre a organizácii komunikácie mezdi procesormi stačí na realizáciu celého výpočtu práve 500 procesorov pre sčítanie N čísel potrebujeme N/2 procesorov a počet (paralelných) výpočtových krokov je 0(log N) Paralelizmus - počet procesorov • počet procesorov potrebných k realizácii paralelného výpočtu ako funkcia veľkosti vstupnej inštancie (A//2 pre sčítanie N čísel) • je to realistické? indikátor, aké veľké vstupy môžeme riešiť s počtom procesorov, ktoré máme k dispozícii (viz analógia s časovou a priestorovou zložitostou) ak počet procesorov, ktoré máme k dispozícii, je menší, môžeme kombinovať paralelný a sekvenčný prístup Paralelené triedenie sekvenčné triedenie zoznamu L spájaním (mergesorť) procedúra sort-/. (1) ak L má len 1 prvok, je utriedený (2) inak (2.1) rozdeľ L na dve polovičky L\ a Z. 2 (2.2) sort-Z-i (2.3) sort-/_2 (2.4) spoj dva utriedené zoznamy do jedného utriedeného zoznamu počet vykonaných porovnaní je Ö{N log N) Paralelné triedenie paralelné triedenie zoznamu L spájaním procedúra parallel-sort-/. (1) ak L má len 1 prvok, je utriedený (2) inak (2.1) rozdeľ L na dve polovičky L\ a Z. 2 (2.2) súbežne volaj parallel-sort-Z-i a parallel-sort-Z-2 (2.3) spoj dva utriedené zoznamy do jedného utriedeného zoznamu počet (paralelných) porovnaní je (predpokladáme, že N je mocninou 2) v 1. kroku N postupností dĺžky 1; /V/2 procesorov; spojenie dvoch postupností = 1 porovnanie v 2. kroku /V/2 postupností dĺžky 2; /V/4 procesorov; spojenie dvoch postupností = 3 porovnania v 3. kroku /V/4 postupností dĺžky 4; /V/8 procesorov; spojenie dvoch postupností = 7 porovnaní spolu 1 + 3 + 7 + 15 H---------h (N - 1) < 2N porovnaní Paralelizmus - čas x priestor icia: v kontexte paralelných výpočtov sa pod priestorovou zložitosťou rozumie počet procesorov potrebných k realizácii výpočtu časová a priestorová zložitost paralelných výpočtov sú spolu tesne zviaza iné I zníženie jednej obvykle znamená zvýšenie druhej a naopak Paralelizmus - čas x priestor SEQUENTIAL PARALLEL Name Size (no. of processors) Time (worst case) Product (time x size) Bubblesort 1 0(N2) 0(N2) Mergesort 1 0(Nx\ogN) O(WxlogA0 (optimal) Parallelized mergesort 0(N) O(A0 0(W) Odd-even sorting network 0(Nx(\ogN)2) 0({\ogN)2) 0(Nx(\ogN)4) "Optimal" sorting network 0(N) 0(\ogN) 0(NxlogN) (optimal) Paralelné siete Spôsob komunikácie medzi procesormi zdieľaná pamäť súčasný zápis resp. čítanie z pamäťového miesta 111 v prípade súčasného zápisu nutnosť stratégie riešenia konfliktov sieť s fixovaným prepojením každý procesor je prepojený (môže komunikovať) len s ohraničením počtom susediacich procesorov; často ako špecializovaný hardware Triediaca siet x- y- V7, áÄ ->- menší z A a 7 ->- vetší z A a ľ Môže paralelizmus riešiť neriešiteľné? Fakt Každý paralelný algoritmus sa dá transformovať na sekvenčný algoritmus. (každý paralelný krok nahradíme postupnostou sekvenčných krokov; každý sekvenčný krok vykoná prácu jedného procesoru) Dôsledok Neexistuej paralelný algoritmus pre nerozhodnuteľný problém. (CT hypotéza sa vztahuje aj na paralelné výpočtové modely) Paralelizmus Paralelizmu a prakticky neriešiteľné problémy • existujú problémy, ktoré sú sekvenčne prakticky neriešiteľná a pritom sú prakticky riešiteľné paralelnými algoritmami? • špecifikácia pojmu "efektívneho" paralelného algoritmu ??? 191 / 214 Paralelizmu a prakticky neriešiteľné problémy • existujú problémy, ktoré sú sekvenčne prakticky neriešiteľná a pritom sú prakticky riešiteľné paralelnými algoritmami? • špecifikácia pojmu "efektívneho" paralelného algoritmu ??? • pozorovanie: pre problém z triedy N P máme nedeterministický algoritmus polynomiálnej časovej zložitosti; ak nedeterministický výber nahradíme paralelizmom, tak okamžite dostavama polynomiálně časovo ohraničený paralelný algoritmus pre tento problém • je to prijateľné riešenie? Paralelizmu a prakticky neriešiteľné problémy • existujú problémy, ktoré sú sekvenčne prakticky neriešiteľná a pritom sú prakticky riešiteľné paralelnými algoritmami? • špecifikácia pojmu "efektívneho" paralelného algoritmu ??? • pozorovanie: pre problém z triedy N P máme nedeterministický algoritmus polynomiálnej časovej zložitosti; ak nedeterministický výber nahradíme paralelizmom, tak okamžite dostavama polynomiálně časovo ohraničený paralelný algoritmus pre tento problém • je to prijateľné riešenie? • exponenciálny počet procesorov Paralelizmu a prakticky neriešiteľné problémy • existujú problémy, ktoré sú sekvenčne prakticky neriešiteľná a pritom sú prakticky riešiteľné paralelnými algoritmami? • špecifikácia pojmu "efektívneho" paralelného algoritmu ??? • pozorovanie: pre problém z triedy N P máme nedeterministický algoritmus polynomiálnej časovej zložitosti; ak nedeterministický výber nahradíme paralelizmom, tak okamžite dostavama polynomiálně časovo ohraničený paralelný algoritmus pre tento problém • je to prijateľné riešenie? • exponenciálny počet procesorov • čo ak prakticky neriešiteľný problém nepatrí do N P? Paralelizmu a prakticky neriešiteľné problémy • existujú problémy, ktoré sú sekvenčne prakticky neriešiteľná a pritom sú prakticky riešiteľné paralelnými algoritmami? • špecifikácia pojmu "efektívneho" paralelného algoritmu ??? • pozorovanie: pre problém z triedy N P máme nedeterministický algoritmus polynomiálnej časovej zložitosti; ak nedeterministický výber nahradíme paralelizmom, tak okamžite dostavama polynomiálně časovo ohraničený paralelný algoritmus pre tento problém • je to prijateľné riešenie? • exponenciálny počet procesorov • čo ak prakticky neriešiteľný problém nepatrí do N P? • otázka praktickej implementácie paralelného algoritmu, ktorý má síce polynomiálnu zložitosť, ale potrebuje exponenciálny počet procesorov (napr. otázka komunikácie) Paralelizmus Paralelná výpočtová téza Časť A Všetky "rozumné" paralelné výpočtové modely sú polynomiálně ekvivalentné. Časť B Paralelný čas je polynomiálně ekvivalenty sekvenčnému času. Se/o/enčný-PSPACE = Paralelný-PJ\ME 192 / 214 NC - Nickova trieda • polynomiálně časovo ohraničené paralelné algoritmy nemôžeme považovať za prakticky použiteľné • zmyslom zavedenia paralelizmu je výrazne redukovať výpočtový čas sublineárne algoritmy Trieda NC Trieda problémov riešiteľných paralelnými algoritmami s polylogaritmickou časovou zložitosťou a polynomiálnym počtom procesorov. Trieda NC je robustná Vztah sekvenčných a paralelných zložitostných tried NC C P C NP C PSPACE Otvorené problémy: o žiadnej z inklúzií nieje známe, či je ostrá, alebo predstavuje rovnosť Predpoklady O existujú problémy, ktoré sú prakticky (sekvenčne) riešiteľné, ale nie sú riešiteľné veľmi rýchlo paralelne s použitím rozumne veľkého hardwaru Q existujú problémy, ktoré sa dajú riešiť (sekvenčne) v polynomiálnom čase s využitím nedeterminizmu, ale nie bez neho O existujú problémy, ktoré sa dajú riešiť v rozmunom (tj. polynomiálnom) sekvenčnom priestore (tj. aj v rozumnom paralelnom čase), ale nie sú riešiteľné v rozumnom sekvenčnom čase bez využitia nedeterminizmu. Vztah sekvenčných a paralelných zložitostných tried NC C P C NP C PSPACE Príklady problémov NC sčítať N čísel rozhodnúť, či v grafe existuje cesta z vrcholu s do vrcholu P \ NC rozhodnúť, či c je najväčším spoločným deliteľom čísel a, i NP \ P problém Hamiltonovského cyklu; splniteľnosť logickej formi PSPACE \ PN slovný futbal Súbežnost situácie, keď paralelizmus nevyužívame k tomu, aby sme zefektívnili výpočty, ale keď paralelizmus vzniká v reálnych aplikáciách reaktívne a zapuzdrené systémy Úloha navrhnúť komunikačné protokoly pre komunikujúce objekty tak, aby spĺňali požadované vlastnosti Špecifikum úlohou systémov nieje nájsť konkrétne riešenie, ale počítať (byť funkčný) "donekonečna" Problém hotelovej sprchy • na poschodí je len jedna sprcha, na veľmi studenej chodbe • každý hosť sa chce osprchovať, ale nemôže čakať na voľnú sprchu na chodbe • ak by z času na čas kontroloval, či je sprcha voľná, môže nastať situácia, že sa nikdy neosprchuje možné riešenie • tabuľa pri vstupe do sprchy • hosť pri odchode zo sprchy zmaže z tabule číslo svojej izby a napíše na ňu číslo nasledujúcej izby (v nejakom fixovanom poradí) • každý hosť z času na čas kontroluje, či je na tabuli napísané číslo jeho izby a ak áno, osprchuje sa je to dobré riešenie? (prázdna izba, práve jedno sprchovanie v cykle, ...) Distribuované súbežné systémy • (súbežné) komponenty systému sú fyzicky oddelené • komponenty vzájomne komunikujú • typicky od systémov nepožadujeme vstupno - výstupné chovanie, ale kontinuálnu (neprerušenú, neukončenú) funkcionalitu • dôležité je chovanie systému v čase • okrem požiadavkov na jednotlivé komponenty, kladieme na systém globálne obmedzujúce podmienky • zdieľanie spločných zdrojov • prevencia uviaznutia (vzájomné čakanie, deadlock) » prevencia starnutia procesov (starvation) (algoritmické) protokoly Problém vzájomného vylúčenia zobecnenie problému hotelovej sprchy Problém vzájomného vylúčenia: je daných N procesov, každý proces opakovane (v nekonečnom cykle) vykonáva • súkromné aktivity (proces ich môže vykonávať nezávislé na ostatných procesoch) a • kritické aktivity (žiadne dva procesy nemôžu súčasne vykonávať svoje kritické aktivity) Protokol pre problém vzájomného vylúčenia pre dva procesy P\ a Pi protokol využíva 3 premenné Z globálna premenná (všetky procesy môžu menit jej hodnotu); nadobúda hodnoty 1 a 2 Xi lokálna premenná procesu P\, nadobúda hodnoty yes a no Xi lokálna premenná procesu P-i, nadobúda hodnoty yes a no počiatočná hodnota premenných X\ a Xi je no, počiatočná hodnota Zje buď 1 alebo 2 Protokol pre problém vzájomného vylúčenia (pre dva procesy) protokol pre proces Pi protokol pre proces P2 (1) opakuj v nekonečnom cykle (1) opakuj v nekonečnom cykle (1.1) vykonaj súkromné aktivity (11) vykonaj súkromné aktivity (1.2) Xi <- yes (1.2) X2 <- yes (1.3) Z<-1 (1.3) Z <- 2 (1.4) čakaj kým buď (1-4) čakaj kým buď X? nenadobudne hodnotu no alebo Xl nenadobudne hodnotu no alebo Z nenadobudne hodnotu 2 Z nenadobudne hodnotu 1 (1.5) vykonaj kritické aktivity (1-5) vykonaj kritické aktivity (1.6) Xi <- no (1.6) X2 <- no korektnosť protokolu vzájomné vylúčenie OK starnutie procesu OK uviaznutie OK Protokol pre problém vzájomného vylúčenia (pre N procesov) protokol pre /-ty proces P; (1) opakuj v nekonečnom cykle (1.1) vykonaj súkromné aktivity (1.2) pre každé J od 1 do N - 1 urob (1.2.1) X[l}^- J (1.2.2) Z[l] +- I (1.2.3) čakaj kým buď X[K] < J pre nejaké K ^ I alebo Z[J] + I (1.5) vykonaj kritické aktivity (1.6) X[l] +- 0 Vlastnosti distribuovaných súbežných systémov distribuované súbežné systémy sa odlišujú od sekvenčných systémov špecifikácia problému nemôžeme použiť špecifikáciu problému prostredníctvom množiny vstupných inštancií a fuknčnej závislosti medzi vstupom a požadovaným výstupom korektnosť nepostačuje dôkaz konečnosti výpočtu a správnosti vstupno-výstupného vzťahu efektívnosť nepostačuje vyjadrenie efektivity cez časovú (počet krokov od začiatku do ukončenia) a priestorovú zložitosť aké vlastnosti požadujeme od súbežných procesov? Vlastnosti živosti a bezpečnosti Vlastnosti, ktoré požadujeme od protokolov pre súbežné procesy (najčastejšie) spadajú do dvoch kategórií: bezpečnosť a živosť. bezpečnosť nikdy nenastanú "špatné" udalosti resp. vždy sa stávajú len "dobré" udalosti živosť určité "dobré" udalosti sa nakoniec stanú aby sme ukázali, že protokol porušuje vlastnosť bezpečnosti, stačí ukázať konkrétnu postupnosť akcií, ktoré vedú k zakázanej udalosti aby sme ukázali, že protokol porušuje vlastnosť živosti, musíme ukázať existenciu nekonečnej postupnosti akcií, ktoré nevedú k požadovanej dobrej udalosti Overovanie vlastností živosti a bezpečnosti testovanie a simulácia môžu odhaliť chybu, ale nemôžu dokázať platnosť požadovanej vlastnosti; techniky sú jednoduché formálna verifikácia matematická metóda, ktorá dokáže platnosť požadovanej vlastnosti; metóda overovania modelov (model checking) náročné na implementáciu a samotné overenie vlastnosti; pre niektoré systémy je problém nerozhodnuteľný Temporálna logika - jazyk pre popis vlastností súbežných systémov formule logiky sa vyjadrujú o pravdivosti základných tvrdení v čase (v priebehu výpočtu) základné konštrukcie: globálna platnosť (globally, G) a platnosť v budúcnosti (future, F) príklady - protokol vzájomného vylúčenia pre dva procesy P!-je-v-(1.4) => F (Pi-je-v-Cl.5)) G HPi-je-v-(1.5) A P2-je-v-(1.5) ]) Kvantové počítanie Kvantové počítanie • založené na princípoch kvantovej mechaniky • teoretický model: základnou jednotkou reprezentácie informácie je qubit, ktorý (zjednodušene) môže nadobúdať ľuboboľnú hodnotu z intervalu [0,1] • kvantové algoritmy • otázka konštrukcie kvantového počítača 207 / 214 Molekulárne počítanie Molekulárne (DNA) počítanie • DNA == reťazce nad abededou A, C, T, G • vývoj organizmu == manipulácia s reťazcacmi: kopírovanie, rozdeľovanie, spájanie • 1994: experiment, v ktorom pomocou manipulácie s molekulami bola vyriešená inštancia problému Hamiltonovskeho cyklu veľkosti 7; experiment predstavoval niekoľko dní laboratórnej práce • pozitívum: veľká miera paralelizmu • negatívum: veľký objem biologického materiálu potrebného k riešeniu rozsiahlejších inštancií • budúcnosť: 111 208 / 214 náhodnostný protokol pre večerajúcich filozofov 209 / 214 Porovnávanie reťazcov Na počítačoch A a B sú uložené databázy x a y; nech x a y sú binárne reťazce dĺžky n. Úlohou je rozhodnúť, či x a y sú zhodné. Zaujíma nás, koľko bitov si musia počítače A a B vymeniť, aby dokázali vyriešiť problém rovnosti. Dá sa dokázať, že neexistuje deterministický komunikačný protokol, ktorý by riešil problém rovnosti a pritom si A a B vymenili nanajvýš n — 1 bitov. T.j. protokol, v ktorom A pošle celý reťazec x počítaču B je optimálny. Porovnávanie reťazcov Randomizovaný protokol pre problém rovnosti Vstup x = xix2 ...xn,y = yiy2 ...yn Krok 1 A vyberie náhodne prvočíslo p z intervalu [2, n2]. Krok 2 A vypočíta číslo s = x mod p a pošle čísla s, p počítaču B. Krok 3 B vypočíta číslo q = y mod p. Ak q t^ s, tak B vráti odpoveď x^y. Ak q = s, tak B vráti odpoveď x = y. počet bitov, ktoré si počítače pošlú je 2 • |~log2 n2] < 4 • |~log2 n] t t I 2 pravděpodobnost, že protokol vráti nesprávnu odpoved je < JL^- Ak n = 1016, tak zložitosi: deterministického protokolu je 1016, zatiaľ čo zložitosi randomizovaného protokolu je 256. Pravdepodobnosi, že randomizovaný protokol vráti nesprávnu odopoved' je < 0.36892 • 10"14. Randomizovaný Quicksort Rand-Quicksort(A) Vstup zoznam prvkov A Krok 1 ak A má jeden prvok, je utriedený ak A má viac prvkov, tak náhodne vyber prvok x z A Krok 2 vytvor zoznam A< obsahujúci prvky z A menšie než x vytvor zoznam A> obsahujúci prvky z A väčšie než x Krok 3 výstup je Rand-QuicksortfA,^), x, Rand-QuicksortfAy) očakávaná zložitosť algoritmu je ö(N\ogN) Typy náhodnostných algoritmov Monte Carlo s ohraničenou pravdepodobnosťou je odpoveď nesprávna príklad: randomizovaný protokol pre problém rovnosti Las Vegas odpoveď je vždy správna; ciel': očakávaná zložitosť Las Vegas algoritmu pre problém je lepšia než zložitosť (deterministického) algorimtu príklad: randomizovaný Quicksort Náhodnostné zložitostné triedy Pravdepodobnostný Turingov stroj pracuje ako nedeterministický TS s tým rozdielom, že nedeterministický výber kroku výpočtu interpretujeme ako náhodnostnú volbu Trieda RP obsahuje rozhodovacie problémy, pre ktoré existuje polynomiálně časovo ohraničený pravdepodobnostný Turingov stroj s vlastnosťou: ak odpoveďou pre vstup X je "Nie", tak s pravdepodobnosťou 1 stroj dá správnu odpoveď ak odpoveďou je "Áno", tak stroj s pravdepodobnosťou > 1/2 dá yes. ^_____________________^_____________________ _______f P C RP C NP náhodnostné algoritmy nemôžu efektívne riešit problémy mimo NP; problémy z N P ale dokážu (často) riešit s väčšou efektivitou