Základy informatiky Co počítače (ne)dokážu IB110 Ivana Černá Fakulta informatiky Masarykova univerzita podzim 2010 3> 3> 3> Technické řešení teto výukové pomůcky je spolufinancováno Evropským sociálním fondem a státním rozpočtem České republiky. INVESTICE DO ROZVOJE VZDĚLÁVÁNÍ IB110 Podzim 2010 2 » » » Literatüra ■ D. Harel, Y. Feldman:Algorithmics: The Spirit of Computing. Third Edition. Addison Wesley, 2004 ■ D. Harel: Computers Ltd. : what they really can't do. Oxford University Press, 2000. ■ J. Hromkovic: Algorithmic Adventures. From Knowledge to Magic. Springer, 2009. IB110 Podzim 2010 3 » » » Elektronická podpora v IS MU ■ interaktívna osnova https://is.muni.cz/auth/el/1433/podzim2010/IB110/index.qwarp ■ Diskusne forum predmetu IB110 Podzim 2010 4 3> 3> 3> Všetky obrázky použité v prezentáciách, pokiaľ nie je explicitne uvedené inak, šá prevzate z publikácie D. Harel, Y. Feldman:A/gonthmics: The Spirit of Computing. Third Edition. Addison Wešley, 2004 IB110 Podzim 2010 5 Problémy a algoritmy^Úvodne poznámky ^ ^ Problémy a algoritmy Úvodne poznámky Pi Pr IB110 Podzim 2010 6 Problemy a algoritmy^Uvodne poznamky ^ ^ Pocftace ■ Computers are amazing machines. They seem to be able to do anything. ■ It is all the more remarkable, therefore, that the digital computer can be thouhgt of as merely a large collection of switches, or bits. m A computer can directly execute only a small number of extremely trivial operations. ■ Computers may differ in size, types of elementary operations, speed, physical media, internal organization, external environment. m What is it that transforms such trivial operations on bits into the incredible feats we see computers perform? m What computers can and cannot solve? IB110 Podzim 2010 7 Problémy a algoritmy^Úvodne poznámky ^ ^ Historické zastavenia ■ cca 400 B.C. Euklidov algoritmus (software) ■ 1801 Joseph Jacquard, pletací stroj (hardware) ■ 1833 Charles Babbage, the difference engine - konkrétne operacie, the analytical engine - programovateľný stroj Ada Býron - programy ■ 1890 Herman Hollerith - stroj založený na diernych stítkoch použirý pri sďtaní obyvatelstva ■ 30-te roký: základy teorie algoritmov, pojem nerozhodnutel'nosti ■ 50-te, 60-te roký - technologický pokrok IB110 Podzim 2010 8 Problémy a algoritmy^Úvodne poznámky ^ ^ Čo je informatika (Computer Science)? prevládajúce názory ■ rozdielne schopnosti populácie v práci s poCítaCmi ■ informatika = ICT skills, informacne technologie ■ tendencia posudzoval! vedny obor podl'a jeho aplikacií definícia informatiky ako vedneho oború ■ mnohovrstevnost - matematika aZ inZniersky pristúp ■ co sú zakladne stavebne kamene vednej disciplíny? ■ jazyk, terminológia ■ definícia, presny vyznam zakladnych pojmov ■ axiomy, zakladne tvrdenia IB110 Podzim 2010 9 Problémy a algoritmy^Úvodne poznámky ^ ^ základné pojmy problém a algoritmus IB110 Podzim 2010 10 Problémy a algoritmy^Problémy a algoritmy ^ ^ Problémy a algoritmy Úvodne poznámky Problémy á algoritmy Programovacie jazyky IB110 Podzim 2010 11 Problémy a algoritmy^Probiemy a algoritmy ^ ^ Problém co jé problém? IB110 Podzim 2010 12 Problémy a algoritmy^Problémy a algoritmy ^ ^ Problém čo je problém? výpočtový problém (nekonečná) mnoZina vstupných inštancií prípustné vstupy špecifikácia poZadovaných výstupov funkcia vstupných inštancií IB110 Podzim 2010 12 Problémy a algoritmy^Problémy a algoritmy ^ ^ Riéšénié problému Metoda riešenia problému popisuje efektívnu cestu, ktorá vedie k nájdeniu poZádovanych výstupov. Popis pozostáva z postupnosti inštrukcií, ktore môZe ktokoľvek realizoval!. existencia metody rieseniá problemu znamená moznost vypocítát riesenie automaticky v danom kontexte hovoríme o algoritme pre riesenie problemu IB110 Podzim 2010 13 Problémy a algoritmy^Probiemy a algoritmy ^ ^ Algoritmus — historický pohľad I koniec 19. storočia, priemyslová revolúcia, kauzálne chápanie sveta, zákony umoZnujúce úplne pochopenie sveta program Davida Hilberta ) cela matematika sa da vybudovat z konecnej sady vhodných axiom ) matematika vytvorena tymto spôsobom je kompletnú v tom zmysle, ze kazde tvrdenie vyjadritel'ne v jazyku matematiky sa da dokazat alebo vyvratit v tejto teorii (z danej sady axiómov) ) existuje metóda pre dokazanie resp. vyvrátenie kazdeho tvrdenia. klucovy pojem metody IB110 Podzim 2010 14 Problémy a algoritmy^Probiemy a algoritmy ^ ^ Algoritmus — historicky pohľad II ■ Kurt Godel (1931) dokazal, Ze (a) neexistuje Ziadna uplna (rozumna) matematicka teoria; v kaZdej korektnej a dostatocne veľkej teorii je moZne formulovat tvrdenia, ktore nieje moZne vnútri tejto teárie dokaZat. Aby bolo moZne dokÚZat spravnost týchto tvrdení, je nutne k teúrii pridal: nove axiomy a výbudovat tak nová, väcsiu teóriu (b) neexistuje metoda (algoritmus) pre dokaZovanie matematických teorem ■ pre svoj dokaZ potreboval presná definíciu pojmu metoda (algoritmus) (nie je mozné dokázal: neexistenciu algoritmu bez rigoróznej definície toho Co je a Co nie je algoritmus) m prva formalna definícia pojmu algoritmu: Alan Turing (1936) d'alsie definície a ich ekvivalencia IB110 Podzim 2010 15 Problémy a algoritmy^Problémy a algoritmy ^ ^ Základné otázky Existujú problémy, ktoré nie sú riešiteľné automaticky (algoritmicky)? Ak ano, ktoré problémy sú algoritmicky riešiteľné a ktoré nie? IB110 Podzim 2010 16 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Problémy a algoritmy Ú Pr ^| Programovacie jazyky a paradigmata IB110 Podzim 2010 17 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Programovacie jazyky I algoritmy musia byť zapísané jednoznačne a formálne programovací jazyk - jazyk pre Specifikaciu algoritmov program - zapis algoritmu v programovacom jazyku strojovy kód vs. programovací jazyk vySSej urovne IB110 Podzim 2010 18 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Programovacie jazyky II ako prezentoval! algoritmus reálnemu počítaču? ako "prinátit" počítač, aby realizoval výpočet tak, ako sme to zamýšľali? programátori sá l'udia, uvaZujá abstraktne a vyjadrujU sa pomočou slov a symbolov počítače sá stroje, ktore dokaZu realizovat! vel'mi jednodučhe ulohy programovačie jazyky pomáhaju l'ud'om komunikovat! s počítačmi IB110 Podzim 2010 19 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Vyvojove diagramy IB110 Podzim 2010 20 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Programovací jazyk vyššéj úrovné jazyk pre popis algoritmov zakladné stavebné kamene ■ riadiace struktury ■ datové struktury IB110 Podzim 2010 21 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Riadiace štruktúry ■ postupnost príkazov ■ podmienené vetvenie ■ ohraničena iteracia ■ podmienena iteracia kombinacia riadiacich StruktUr - vnorenie IB110 Podzim 2010 22 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Datové typy Datové typy ■ premenne ■ vektory, zoznamy ■ polia, tabuľky ■ zásobníky á fronty ■ stromy á hierarchie IB110 Podzim 2010 23 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Datove typy Vlastnosti programovacích jazykov ■ presna syntax ■ presna semantika IB110 Podzim 2010 24 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Datove typy Syntax ■ nejednoznačnosti; presny vyznam pré pojmy, ktoré sa pouZívajU v béZnéj komunikacii ■ Porovnanié "=" a priradénié "=" 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 IB110 Podzim 2010 25 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Datové typy Syntax - príklad ■ hýpotetický programovací jaZýk PL Príklad 1 inputN; 2 X := 0; 3 for Y from 1 to N do 4 X := X + Y 5 od 6 outputX. IB110 Podzim 2010 26 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Datove typy Definícia syntaxe - syntaktické diagramy IB110 Podzim 2010 27 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Datové typy Définícia šyntaxé — BNF (príkaz) ::= (for príkaz) | (priraďovací príkaz) | ... (for príkaz) ::= (premenná) from (hodnota) to (hodnota) BNF umoznuje generoval! (syntakticky správne) programy IB110 Podzim 2010 28 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Datové typy Kontrola syntaktických chyb program sa neda vygeneroval! pouZitúm BNF automatizovany proces IB110 Podzim 2010 29 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Dátové typy Sémantika for Y from 1 to N do ■ význam — odčítanie, príkaz pre tlačiareň, dnes je pekný deň ??? ■ význam podl'a pouZitých slov ??? čo ak N = 3.14 ??? ■ presna sémantika je nevýhnutna !!! ■ manual (dokumentacia) ako definícia semantiký ??? IB110 Podzim 2010 30 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Datove typy Semantika - príklad Práklad procedura P (s parametron V) (1) call V (s parametrom V), výsledok ulož do X (2) if X = l then return O; else return l m procedura, ktora ma ako svoj parameter nazov procedury ■ syntakticka korektnost: ■ call P(s parametrom P) - aka je navratova hodnota? ■ semantika musá dat: jednoznacnu odpoved' IB110 Podzim 2010 31 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Prekladače a interpretry VýpoCet programu ■ od programu v jazykú vyssej úrovne k manipúlacii s bitmi ■ program je postúpne transformovany na strojovú úroveň ■ transformacia ■ kompilacia ■ interpretacia ■ kombinovaný prístúp IB110 Podzim 2010 32 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Prekladače a interpretry Kompilácia program v jazýku výssej urovne je preložený do jazýka nižsej urovne (jazýk sýmbolických adries) for Y from 1 to N do telo cyklu od MOVE 0, Y do registra Y ulož 0 LOOP\ CMP N, Y porovnaj hodnoty uložené v N a Y JEQ REST ak rovnost., tak pokračuj príkazom REST ADD 1, Y pripočítaj 1 k Y telo cýklu JMP LOOP prekladac IB110 Podzim 2010 33 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Prekladače a interpretry Kompiiacia - pokr. ■ preklad z jazyka symboličkyčh adries do strojoveho kodu ■ assembler Optimalizačia kodu počas kompilačie IB110 Podzim 2010 34 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Prekladače a interpretry Interpretácia ■ intérprétér postupujé príkaz po príkazé ■ kazdy príkaz jé okamzité prélozény do strojového kódu a vykonany Moznost lépsié slédovat vypocét. Typicky jédnoducha tvorba intérprétru. Némoznost optimalizacii. IB110 Podzim 2010 35 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata Programovacie esperanto ■ prečo rozne programovacie jazyky? ■ programovací jáyzk poskytuje programátorovi istu uroven abstrakcie ■ potreba novych typov ábstrakci í ■ vyvoj hardwaru (paralelné počítaCe a programovanie vo vláknach) ■ nove aplikačne oblasti (mulimediélne aplikécie) m paradigmatá - kategorizácia existujucich programovacích jazykov IB110 Podzim 2010 36 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata Imperatívne programovanie ■ prístup blízky ľudskému uvazovaniu ■ impératívné programovanié popisujé vypocét pomocou postupnosti pr íkazov a urcujé présny postup, ako dany algoritmicky problém riésit ■ pamat pocítaca jé suborom pamatovych miést organizovanych do rôznych datových struktur ■ program budujé, préchadza a modifikujé datové struktury tak, zé nacíta data a méní hodnoty ulozéné v pamäti ■ pr íkazy, v zavislosti na vyhodnotén í podmiénok, ménia stav préménnych ■ historicky najstarsié impérat ívné programovacié jazyky: strojové jazyky ■ FORTRAN, ALGOL, COBOL, BASIC, Pascal, C, Ada ■ zakladné typy príkazov - priradénié, cykly, pr íkazy vétvénia IB110 Podzim 2010 37 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata Funkcionaine programovanie ■ vypoctom fúnkcionalneho programú je postúpnost vzajomne ekvivalentnych vyrazov, ktore sa postúpne zjednodúsújú ■ vysledkom vypoctú je vyraz v normalnej forme, ktory sa neda d'alej zjednodúsit ■ program je chapany ako jedna fúnkcia, ktora obsahúje vstúpne parametry. Vypocet je vyhodnotením tejto fúnkcie. ■ imperatívny prístúp: ako sa ma vypocítat fúnkcionalny prístúp: co sa ma vypocítal! ■ Erlang, Haskell, Lisp, ML, Ozx, Scheme IB110 Podzim 2010 38 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata Logické programovanie ■ postavene na pouzitá matematičkej logiky ■ logičky program je tvoreny sadou pravidiel a jednodučhyčh logičkyčh tvrdená ■ dotaz sa riesi prehl'adavanám mnoziny pravidiel. Hl'ada sa dokaz, ktory poskytuje odpoved' na zadany dotaz IB110 Podzim 2010 39 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata Objektovo orientované programovanie ■ pamäť počítača pozostáva z objektov ■ s kaZdým objektom sú asociovane operacie, ktore moZe objekt poskytoval! (prístupne ako metody volania) ■ program je súborom objektov, ktore si posielajú spravy obsahujúce poZiadavky na realizaciú operacií a odpovede ■ Smalltalk, Java, C++, Python, Rúby. Lisp IB110 Podzim 2010 40 Spravnost algoritmov^Korektnosť ^ ^ Správnost algoritmov Korektnost Fo IB110 Podzim 2010 41 Spravnost algoritmov^Korektnost ^ ^ PreCo? ■ 1962, Marinérl - start rakéty ■ 1981, Kanada - informacia o volébnych préférénciach ■ 1985-87, Thérac-25 - néspravné davky rontgénového ziarénia ■ problém Y2K ■ http://www.dévtopics.com/20-famous-softwaré-disastérs/ IB110 Podzim 2010 42 Spravnost algoritmov;>Koréktnost ^ ^ Typy chyb ■ syntaktické chyby ■ until / untli ■ for (k=0;k<101){ sum = sum + k } versus for (k=0;k<101;k=k+1){ sum = sum + k } ■ sémantické chyby ■ výsledná hodnota premennej cyklu ■ for (k=0;k=k+1;k<101){ sum = sum + k } versus for (k=0;k<101;k=k+1){ 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) poatace nerobia chyby IB110 Podzim 2010 43 Správnosť algoritmov!3=-Korektnosť ^ ^ Testovanie a ladenie syntaktické chyby, run-time chyby testovanie, testovacie sady ladenie nezarucujU bezchybnost algoritmu IB110 Podzim 2010 44 Spravnost algoritmov^Korektnosť ^ ^ CiastoCna a úplna korektnosť 2pečifikačia algoritmičkeho problemu 1. určenie mnoziny vstupnyčh instančiá 2. určenie vztahu medzi vstupnymi instančiami a pozadovanym vystupom. ■ čiastočna korektnost': pre kazdu vstupnu instančiu X platá, ze ak vypočet algoritmu na X skončá, tak vystup ma pozadovanu vlastnosť ■ konečnosť: vypočet skončá pre kazdu vstupnu instančiu ■ uplna koreknost: čiastočna korektnosť + konečnosť IB110 Podzim 2010 45 Správnost: algoritmov^Korektnosť ^ ^ Dokaz korektnosti invariantý ■ kontrolne bodý programu invariant = tvrdenie, ktore platí pri kaZdom priechode kontrolným bodom ■ ciastocna korektnost konvergencia ■ s kontrolnými bodmi asociujeme kvantitatívnu vlastnost ■ pri kaZdom priechode kontrolným bodom sa hodnota kvantitatívnej vlastnostni ZniZuje ■ hodnota kvantitatívnej vlastnosi nesmie prekrocit dolnu hranicu ■ konecnost výpoctu IB110 Podzim 2010 46 Správnosť algoritmov!3=-Korektnosť ^ Príklady ^ Zrkadlový obraz Zrkadlový obraz : reťazec S i; symboly reťazca S v obrátenom poradí Noťacia ■ reverse(„fakulťa") = '„aťlukaf" ■ head(„fakulťa") = „f" ■ tail(„fakulťa") = „akulťa" symbol A oznaCuje prazdny reťazec (reťazec neobsahuje Žiaden symbol) ■ symbol • oznacuje zreťazenie (spojenie) dvoch reťazcov IB110 Podzim 2010 47 Sprévnost algoritmov^Korektnosť ^ Préklady ^ Zrkadlový obraz Algoritmus X <- S: Y<- A 1 ' V X<-tail(Z) IB110 Podzim 2010 48 Správnost: algoritmov^Korektnosť ^ Príklady ^ Zrkadlový obraz Kontrolne body a invarianty Invariant 1 vstupna podmienka Invariant 2 S = reverse( Y) • X charakteriZuje výpocet Invariant 3 Y = reverse(S) poZadovaný vZtah medZi vstupom S a výstupom Y IB110 Podzim 2010 49 Spravnost algoritmov^Korektnosť ^ Príklady ^ Zrkadlový obraz Platnosť invariantov dokaz jeme, ňze pre kaňzdíy platníy vst p: ak víypoňcet dosiahne kontrolnyí bod, tak tvrdenie je pravdivíe v akom poradí sa prechádzajú kontrolne body? 1 —> 2 —> 2 —► ..-2 —> 3 IB110 Podzim 2010 50 Spravnost algoritmov^Korektnosť ^ Príklady ^ Zrkadlový obraz Platnosť invariantov 2 pre kazdy retazec S po vykonan í príkazov X — S, Y — A plat í rovnost! S = reverse( Y) • X 2 —► 3 ak S = reverse( Y) • X a X = A, tak Y = reverse(S) ak S = reverse(Y) • X a X = A, tak po vykonan í pr íkazov Y — head(X) • Y; X — tail(X) plat í znovu ta ista rovnost! pre nove hodnoty premenných X aY dokazali sme ciastocnu korektnost IB110 Podzim 2010 51 Správnosť algoritmov^Korektnosť ^ Príklady ^ Zrkadlový obraz Konečnost: ■ výpočet algoritmu je nekonečný prave ak prechádza kontrolným bodom 2 nekonečne vel'a krat ■ s kontrolným bodom 2 asociujeme kvantitatívnu vlastnost! (tzv. konvergent) a ukáZeme, Ze jej hodnota klesá a pritom je zdola ohraničena ■ konvergentom pre kontrolný bod 2 je dlZka retazca X ■ pri kazdom priechode kontrolním bodom 2 dlzka retazca X klesne o 1 ■ ak dlzka X klesne na 0 (X je prazdný retazec), tak výpocet neprechádza cýklom a nenavstívi kontrolný bod 2 dokazali sme konecnost IB110 Podzim 2010 52 Spravnost algoritmov^Korektnosť ^ Príklady ^ Zrkadlový obraz Korektnosť korektnost: = ciastocna korektnost: + konecnost IB110 Podzim 2010 53 Sprévnost algoritmov^Korektnosť ^ Príklady ^ Euklidov algoritmus Euklidov algoritmus Vstup dve kladne čele čísla X a Y Vystup najvačsá spoločny delitel' Z čísel X a Y spoločny delitel' Z Z delí X a Z delá Y (čeločíselne) najvačsá delitel' pre kazde číslo U > Z, bud' U nedelí X alebo U nedelí Y IB110 Podzim 2010 54 Správnosť algoritmov!3=-Korektnosť ^ Príklady ^ 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 su nasobkom Z Invariant 2 V > Z a W > Z Invariant 3 neexistuje väčs í spoločný deliteľ č ísel V a W neZ č íslo Z vsetký invariatný platia v kaZdom bode výpočtu IB110 Podzim 2010 55 Správnost: algoritmov^Korektnosť ^ Príklady ^ Euklidov algoritmus Ciastocna korektnost Invariant 1 V a W su nasobkom Z Invariant 2 V > Z a W > Z Invariant 3 neexistuje väcsí spolocný delitel' císel V a W neZ císlo Z InicialiZacia V — X, W — Y ■ invariantý 1, 2, 3 sa priradením neporusia IF príkaZ if V > W then V — V - W fi ■ Fakt Ak V > W, tak dvojice císel V, W a V - W, W maju rovnakých spolocných delitel'ov ak Z delí V, W a V > W, tak V - W > 0a V - W > Z m invariantý 1, 2, 3 Zostavaju Zachovane IF príkaZ if W > V then W — W - V fi ■ sýmetrický IB110 Podzim 2010 56 Správnosť algoritmov^Korektnosť ^ Príklady ^ Euklidov algoritmus Čiastočná korektnost Invariant 1 V a W sú násobkom Z Invariant 2 V > Z a W > Z Invariant 3 neexistuje väčší spoločný dělitel' čísel V a W nez číslo Z while príkaz ■ vsetký invarianty zostavajú v platnosti po prevedení jednotlivých príkazov cýklú ■ čýklús končí ked' V = W V je najvačsím spoločným delitel'om V, W ■ V = Z čiastočna korektnost! IB110 Podzim 2010 57 Správnosť algoritmov^Korektnosť ^ Príklady ^ Euklidov algoritmus Konečnost: ■ výpočet je nekonečný prave ak while príkaz sa vykoná nekonečne vel'a krat ■ konvergentom while cyklu je súčet V + W m pri kaZdom vstupe do tela cyklu je V > Z > 0, W > Z > 0 a V = W i pri vykonaní tela cyklu sa odčíta cele kladne číslo bud' od V alebo od W ■ suma V + W sa pri kaZdom priechode cyklom znúZi aspoň o 1 na začiatku je V + W = X + Y a preto sa cyklus vykona nanajvys X + Y krat konečnost! IB110 Podzim 2010 58 Sprévnost algoritmov^Korektnosť ^ Príklady ^ Insertsort Triedenie vkladaním Insertion — Sort (A) for j — 2 to /ength[A] do key - A[j] i - j — 1 while i > 0 A A[i] > key do A[i + 1] — A[i] i — i — 1 od A[i + 1] — key od Invariant na začiatku iteracie for cyklu obsahuje A[1... j — 1] tie isté prvky, ako obsahovalo na tychto pozíciach pole A na začiatku vypočtu, ale utriedene od najmenšieho po najvacsí IB110 Podzim 2010 59 Spravnost algoritmov;>Koréktnost ^ Príklady ^ Insértsort Ciaštocna koréktnošť a konécnošť Invariant na zaáatku iteracie for cyklu obsahuje A[1... j — 1] tie isté prvky, ako obsahovalo na tychto poz íciach pole A na zaáatku vypoctu, ale utriedené od najmensieho po najvacsí Inicializacia tvrdenie platí na zaáatku vypoctu (j = 2, postupnost! A[1] obsahuje jediny prvok a je utriedena) FOR cyklus v tele cyklu sa hodnoty A[j — 1], A[j — 2], A[j — 3],... posuvaju o jednu poz íciu doprava az kym sa nenajde vhodna poz ícia pre A[j] Ukončenie for cyklus sa ukonc í ked' j = n + 1. Substituciou n + 1 za j dostavame, ze pole A[+... n obsahuje tie isté prvky, ako na zaáatku vypoactu, ale utriedene. Konecnost for cyklus nemen í hodnotu riadiacej premennej cyklu IB110 Podzim 2010 60 Sprévnost algoritmov;S=-Formalna verifikécia ^ ^ Spravnost algoritmov K S Formalna verifikacia IB110 Podzim 2010 61 Správnosť algoritmov;>Formálna verifikácia !3> ^ Formálna verifikácia ■ interaktívne dokazovanie ■ dokazovanie formálnym odvodením (theorem proving) m overovanie modelu (model checking) IB110 Podzim 2010 62 Zložitosť algoritmov^Optimalizácia ^ ^ Zlozitost algoritmov 3 Optimalizácia Asymptotická zloZitost Príklady Priemerná a očakávaná zloZitost Horne a dolne odhady zloZitosti IB110 Podzim 2010 63 Zlozitost: algoritmov;S=-Optimalizacia ^ ^ Zložitosť algoritmov koreknost algoritmu sama o sebe nezaručuje jeho pouzitel'nost dlzka vypočtu a jeho pamäťová naročnost časova a priestorova zlozitosť zlozitosť vypočtu zavisí na vstupnej instančii zlozitosť algoritmu vyjadrujeme ako funkčiu dlzky vstupnej instančie IB110 Podzim 2010 64 Zlozitost algoritmov;S=-Optimalizacia ^ ^ Optimalizacia zložitosti algoritmu ■ na urovni kompilacié ■ programatorska optimalizacia IB110 Podzim 2010 65 Zložitosť algoritmov^Optimalizácia ^ ^ Príklad 1 Vstup zoznam študentov a počet bodov, ktoré získali v záverečnom teste predmetu IB110 L(1),..., L(N) Výstup normalizovane body (1) Najdi maximalny počet bodov, MAX (2) kazdý bodový zisk vynasob hodnotou 100 a vydel' hodnotou MAX IB110 Podzim 2010 66 Zložitosť algoritmov^Optimalizácia ^ ^ Implementácia (1) štandartne (2) for l from 1 to N do L(l) — L(l) x 100/MAX od pre každé L(l) potrebujeme 1 násobenie a 1 delenie Optimalizácia (1) štandartne (2) FAKTOR — 100/MAX (3) for I from 1 to N do L(l) — L(l) x FAKTOR od zlepšenie o cca 50% IB110 Podzim 2010 67 Zložitosť algoritmov^Optimalizácia ^ ^ Príklad 2 ■ vyhľadávanie prvku X v neusporiadanom zozname ■ implementacia pomocou cyklu, v ktorom sa realizujU dva testy: (1) naSli sme X? a (2) prehľadali sme cely zoznam? ■ optimalizacia: na koniec zoznamu pridame prvok X a v cykle testujeme len podmienku (1) ■ po ukoncen í cyklu overujeme, ci najdeny prvok X sa nachadza vo vnutri zoznamu alebo na jeho konci ■ zlepsenie o cca 50% IB110 Podzim 2010 68 Zložitosť algoritmov;>Asymptoticka zložitosť ^ ^ ZloZitost algoritmov O T| Asympťoťicka zloziťosť ■ Príklady ■ Priemerna a ocakavaná zloziťosť ■ Horne a dolne odhady zloziťosťi IB110 Podzim 2010 69 Zlozitost algoritmov ;>Asymptoticka zlozitost ^ ^ Otazky ■ je Zlepsenie o 50% (60%, 90% ...) dostacujuce? ■ ako charakteriZovat ZloZitost algoritmu? ako porovnal! ZloZitosl! dvoch algoritmov? ZloZitosl! algoritmu ako funkcia dlZký vstupnej instancie ZloZitosl! v najhoršom prípade asýmptoticka ZloZitosl!, O-notacia IB110 Podzim 2010 70 Zlozitosť algoritmov;S=-Asymptoticka zlozitosť ^ ^ Asymptoticka zložitosť ■ jednodučha čharakterizačia efektivity algoritmu ■ umozňuje porovnat' relatívnu efektivitu roznyčh algoritmov ■ čharakterizuje, ako rastie zlozitosť algoritmu s rastáčou dlzkou vstupnej inňstančie O-notáčia Symbolom O(g(n)) označujeme mnozinu fukčiít.z. O(g(n)) = {f(n) | existuje kladná konstanta c a no take, že 0 < f (n) < cg (n) pre vsetky n > no}. Rovnosť f (n) = O(g (n)) vyjadruje, ze f (n) je prvkom mnoziny O(g (n)). IB110 Podzim 2010 71 Zlozitost algoritmov^Asymptoticka zlozitost ^ ^ Robustnosť O-notacie Fakt O-notacia zakryva konstantné faktory ■ casova zlozitost algoritmu jé rélatívny pojém ■ zlozitost! jé rélat ívna voci fixovanéj mnoziné éléméntarnych instrukci í ■ kazdy programovac í jazyk résp. kompilator mozé mat! inu mnozinu éléméntarnych instrukci í ■ pokial' pouz ívaju standartné instrukcié, tak rozdiél v casovéj zlozitosti jé pravé o konstantny faktor ■ O-notacia jé invariantna voci takymto impléméntacnym détailom Névyhoda O-notacié: skryté konstanty, hranicna hodnota no IB110 Podzim 2010 72 ZloZitost algoritmovAsymptotická zloZitost ^ Príklady ^ Binárne vyhľadávanie Binarne vyhladavanie poloZky Y v telefónnom zozname s N poloZkami Xi, X2,..., XN pre N = 1000000 linearne vyhladavanie aZ 1 000 000 porovnaní zloZitost O(N) binírne vyhľadavanie postup: v prvom kroku porovnaj Y s X500000 podl'a víysledku porovnaj v druhom kroku Y bud' s X250000 alebo s X750000 v najhorsom prípade 20 porovnaní zloZitost! O(log2(N)) Prečo? sme ako zloZitost vyhladavania sme uvaZovali len počet porovnaní? IB110 Podzim 2010 73 Zlozitost algoritmov;S=-Asymptoticka zlozitost ^ Príklady ^ Bubblesort 1 procedure BuBBLESORT(A, n) 2 for i = l to n - l do s for j = l to n - i do 4 if A[j ] > A[j + l] then vymeň A j] s A[j + l] fi 5 od e od riadok 4 for čyklus S -for čyklus 2 - čas O(l) čas O(n - i) čas OG^ÍOi - i)) O(n(n - l) - £^ i) = O(n2) čelkova časova zlozitost' je O(n2) IB110 Podzim 2010 74 ZloZitost algoritmovAsymptotická zloZitost ^ Príklady ^ Vnorene cykly 1 r — 0 2 for i = 1 to n do 3 for j = 1 to i do 4 for k = j to i + j do 5 r — r + 1 6 od 7 od 8 od (i + j) — j + 1 = i + 1 priradení i opakovaní čýklú 4-6, tj. i (i + 1) = i2 + i priradení n — 1 opakovaní čýklú 3-7, tj. ^/=a '2 + ' priradení y1 .2 + . = (n — 1)n(2n — 1) + (n — 1)n = n3 — n = £,(„3) IB110 Podzim 2010 75 Zložitosť algoritmovAsymptotická zložitosť !3> Príklady ^ Maximálny a minimálny prvok Problém nájdenia maximálneho a minimálneho prvku postupnosti S[1..n]. Zložitostné kritérium - počet porovnán í prvkov. max — S [1] for i from 2 to n do if S [i] > max then max — S [i] i od Minimum nájdeme medži žvySnými n — 1 prvkami podobne. Celkove (n — 1) + (n — 2) porovnán í. IB110 Podzim 2010 76 Zložitosť algoritmov;§=-Asymptotická zložitosť !3> Príklady ^ Maximálny a minimálny prvok Prístup Rozdel' a panuj | pole rozdel' na dve (rovnako vel'ke) podpostunosti ^ najdi minimum a maximum oboch podpostupností ^ maximálny prvok postupnosti je vacsí z maximainych prvkov podpostupností; podobne minimalny prvok function Maxmin(x, y) if y — x < 1 then return (max(S [x], S [y]), min(S [x], S [y])) else (max 1, m/n1) — Maxmin(x, [(x + y)/2j) (max2, m/n2) — Maxmin( [(x + y)/2j +1, y) return (max(max 1, max2) min(m/n1, m/n2)) fi IB110 Podzim 2010 77 Zlozitost algoritmov ;>Asymptoticka zlozitost ^ Príklady ^ Maximalny a minimalny prvok Zlozitost!: (pocet porovnan í) T(n) = í1 pré n = 2 \T(Ln/2J)+ T(ľn/21) + 2 pre n > 2 Indukciou k n overíme, ze T (n) < 5 n — 2. | Pre n = 2 plat í f • 2 — 2 > 1 = T(2). 1 Predpokladajme platnost! nerovnosti pre vsetky hodnoty 2 < i < n, dokazeme jej platnosť pre n. T (n) = T ([n/2j) + T ([n/21) + 2 indukcny predp. < 3 Ln/2J— 2 + 5 [n/21— 2 + 2 = 5 n — 2 IB110 Podzim 2010 78 ZloZitost algoritmov;S=-Asymptoticka zloZitost ^ Priemerná a oCakávana zlozitost ^ Priemerná a oCakávaná zložitosť t priemer zlozitost í výpoctov na vsetkých vstupoch danej d l zký Quicksort - zlozitost v najhoržom prípade je O(n2), priemerné zlozitost je O(n log n) zlozitost! jednotlivých výpoctov je vazena frekvenciou výskýtu pr íslusných vstupných instanci í Výhodý: presnejsia informacia o efektivite algoritmu v prípade očakévanej zložitosti je relevancia voči aplikačnej oblasti Nevýhodý: obtiazna analýza v prípade ožakévanej zložitosti nutnost poznat presnú frekvenciu vstupních inžtancií IB110 Podzim 2010 79 Zložitosť algoritmov^Asymptotická zložitosť !3> Horne a dolne odhady zložitosti ^ Horné a dolné odhady zložitosti ■ v najlepsom prípade ■ v najhorsom prípade ■ priemerná zlozitost ■ očakavaná zlozitost ■ dolny odhad zlozitosti problemu ■ horny odhad zlozitosti problemu — zlozitost! konkrétneho algoritmu pre problem ■ zlozitost! problemu IB110 Podzim 2010 80 Zlozitost algoritmov ;>Asymptoticka zlozitost ^ Horne a dolne odhady zlozitosti ^ Techniky Informacna metoda riesenie problemu v sebe obsahuje iste mnoZstvo informacie a v kaZdom kroku výpoctu sme schopní uršit len cast tejto informacie (násobenie matíc, cesta v grafe, triedenie) Metoda sporu Varianta A: Za predpokladu, Ze algoritmus ma ZloZitost menšsiu nešZ uvašZovanu hranicu, vieme skonšstruovat! vstup, na ktorom neda korektne riešsenie. Varianta B: Za predpokladu, Ze algoritmus najde vZdý korektne riešsenie, vieme skonšstruovat! vstup, pre ktorý ZlošZitost! výpošctu presiahne uvašZovanu hranicu. Redukcia IB110 Podzim 2010 81 Zlozitost: algoritmov;S=-Asymptoticka zlozitost: ^ Horne a dolne odhady zlozitosti ^ Príklad: maximainy prvok postupnosti Dolny 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, aspon n — 1 porovnaní. Dokaz Néch x = (xi,..., xn) jé vstup dlzky n, na ktorom A vykona ménéj néz n — 1 porovnaní a néch xr jé maximalny prvok v x. Potom v x musí éxistovat prvok xp taky, zé p = r a v priébéhu vypoctu xp nébol porovnavany so ziadnym prvkom väcsím néz on sam. Existéncia takého prvku plynié z poctu vykonanych porovnaní. Ak v x zménímé hodnotu prvku xp na xr + 1, tak A urcí ako maximalny prvok xr - spor. IB110 Podzim 2010 82 Zlozitosť algoritmov;S=-Asymptoticka zlozitost: ^ Horne a dolne odhady zlozitosti ^ Príklad: vyhfadavanie v telefónnom zozname binarny strom a jého hlbka IB110 Podzim 2010 83 ZloZitost algoritmov;>Asymptoticka zloZitost ^ Horne a dolne odhady zloZitosti ^ Vyzkum v oblasti zložitosti probiemov optimalizacia dítovych struktur dolne odhady zloZitosti a dokaz optimality priestorovaí zloňzitost' vzt'ah medzi priestorovou a ňčasovou zloňzitost'ou IB110 Podzim 2010 84 Prakticky riesiteľne problemy^Kritérium efektivity ^ ^ Prakticky rieSitefne problemy ^| Kriterium efektivity HNP-úplne problemy Redukcia Moalsie zlozitostne tr IB110 Podzim 2010 85 Prakticky riesitelne problemy^Kritérium efektivity ^ ^ Prakticka použitelnost algoritmov Je kaZdý algoritmus praktický pouZitelný? N = 1 000 000 e O(log N)... 20 e O(N)... 1 000 000 triedenie ZoZnamu O (N log N)... 20 000 000 Hanojske veZe O(2N)... miliín presunov Za minutu => 500 000 rokov Je riesením výkonnejsí hardware a väcsia trpeZlivost? IB110 Podzim 2010 86 Prakticky riesiteľne problemy^Kritérium efektivity ^ ^ Monkey Puzzle Problem http://www.keithharingart.com/ IB110 Podzim 2010 87 Prakticky riesitel'ne problemy^Kritérium efektivity ^ ^ MP hlavolam Vstup N kariet (N = M2) a Daju sa karty usporiadal! do stvorca M x M tak, aby sa susediače hrany zhodovali? Karty mají fixní orientáciu (nemôZeme ich otúča1!) Zaujíma nas len existencia riesenia (nepotrebujeme poznat! usporiadanie vyhovujuce podmienkam) IB110 Podzim 2010 88 Prakticky rieSitel'ne problémy^Kritérium efektivity ^ ^ MP hlavolam - riešenie ■ je dany konecny pocet kariet ■ kazdu kartu mozeme umiestnitna konecny pocet poz íci í ■ mozeme vyskusat vsetky moznosti ■ N = 25 x 25, pocet moznost í 25 x 24 -x 3 x 2 x 1 ■ 109 moznost í za sekundu 490 miliónov rokov IB110 Podzim 2010 89 Prakticky riesitefne problemy^Kriterium efektivity ^ ^ Hranice praktickej pouZitelnosti v 20 60 100 300 1000 5N 100 300 500 1500 5000 NX log2(V 86 354 665 2469 9966 M2 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) 2N 1.048.576 a 19-digit number a 31-digit number a 91-digit number a 302-digit number Ml 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 IB110 Podzim 2010 90 Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ Hranice praktickej použiteľnosti 20 40 60 100 300 N2 1/2500 millisecond 1/625 millisecond 1/278 millisecond 1/100 millisecond millisecond N5 1/300 second second 78/100 second 10 seconds 40.5 minutes 2N 1/1000 second 18.3 mi tm tes 36.5 years 400 billion centuries a 72-digit number of centuries NN 3.3 billion years a 46-digit number of centuries an 89-digit number of centuries a 182-digit number of centuries a 725-digit number of centuries hranica: polynomialna zložitosť prakticky rieSitel'ne vs prakticky nerieSitelne problémy IB110 Podzim 2010 92 Prakticky riešiteľné problémy^Kritérium efektivity ^ ^ Prakticky nériéšitéfné problémy i pouzit vykonnejs í poc ítac? pre algoritmus zložitosti 2N: ak dnes vyriešime inštancie veľkosti max. C, tak 1000 krat rýchlejším počítačom vyriešime inštancie veľkosti max. C + 9.97. ■ zintenz ívnit vyzkum a najst efekt ívnejsí algoritmus? ■ dokazat, ze neexistuje efekt ívnejs í algoritmus? Millenium Prize Problem, 1 000 000 http://www.claymath.org/millennium/ ■ je otazka dolezita? existujú aj iní (dolešití) problímy podobního charakteru? IB110 Podzim 2010 93 Prakticky riesitel'ne problemy^NP-úplne problemy ^ ^ Prakticky riesitefne problemy Kr NP-uíplníe problíemy ■ Redukcia IB110 Podzim 2010 94 Prakticky riesitelne problemy^NP-úplne problemy ^ ^ NP-Uplne problemy NP-uplne problemý problemý, pre ktore maju linearný dolný odhad ZloZitosti a exponencialný horný odhad ZloZitosti nepoznáme lepší nez exponenciálny algoritmus a zároveň nevieme dokazat, Ci existuje alebo neexistuje asymptoticky efektívnejší algoritmus IB110 Podzim 2010 95 Prakticky riešiteľné problémy^NP-úplné problemy ^ ^ NP-úplné problémy - príklady dvojrozmerne pokrytie danych je N stvoruholníkov; je mozne pokryt nimi stvorcovu plochu? Hamiltonovska cesta dany je neorientovany graf; existuje v grafe cesta, ktora navstívi kazdy vrchol prave jeden krat? obchodny cestujíci dany je neorientovany graf s ohodnotenymi hranami a konstanta K; existuje v grafe Hamiltonovsky cyklus dlzky nanajvys K? u daných je M miestností a N prednasok, kazda prednaska ma urceny zaciatok a koniec; je mozne rozdelil! prednísky do danych miestností? t! dana je logicka formula; existuje priradenie hodôt jej premenníym, pre ktoríe je formula splnenaí? ... a tisíce dalsích IB110 Podzim 2010 96 Prakticky rieSitel'ne problemy^NP-úplne problemy ^ ^ NP-úplne problémy - špoloCna charakteristika ■ rozhodovacie problemy (odpoveď je „Ano" alebo „Nie") m existencia ciastocnych riesen í ■ hľadanie riesenia problemu pomocou zpaatneho vyhl'adavania (backtracking); exponencialny algoritmus ■ je extrémne tazke rozhodnut;, ci reisen ím vstupnej instancie je „Áno" aelbo „Nie" ■ ak riesen ím instancie je „Áno", tak je velmi jednoduche dokazat to — pomocou tzv. certifikatu ■ obvykle je certifikat kratky reťazec (linearny voci N) a jeho overenie je mozne v polynomialnom case IB110 Podzim 2010 97 Prakticky riesiteľné problémy^NP-úplné problémy ^ ^ Alternatívna charakterizácia NP-úplnýčh probiemov ■ predpokladajme, že mame magičkú mičú, ktorú búdeme poúzívat pri zpätnom výhladavaní (backtrackovani) riešenia instančie ■ vždý, ked' ša mame rozhodnút, ako rozšíril! čiastočne riešenie, rozhodnútie úrobíme tak, že si hodíme minčoú i „magično" — minča vzdý výberie moznost, ktora vedie k riešeniú „Áno" (samozrejme, len ak existuje) ■ pojem nedeterminizmú ■ pre NP-úplne problemý mame nedeterminističke polýnomialne algoritmý ■ NP v nazve NP-úplný je skratka pre pre nedeterminističký polýnomialný IB110 Podzim 2010 98 Prakticky riešiteľné problémy^NP-úplné problémy ^ ^ Pojem úplnosti bud' všetky NP-úplné problémy sú prakticky riešiteľné alebo žiaden z nich nieje prakticky riešiteľný ■ ak pre jeden NP-úplny problem skonštruujeme polynomiúlny algoritmus, tak múme polynomialne algoritmy pre všetky NP-úplne problúemy ■ ak pre niektory NP-úplnú problem dokúžeme neexištenciu polynomialneho algoritmu, tak polynomialny algoritmuš neexištuje pre žiaden NP-úplny problem IB110 Podzim 2010 99 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ Dokaz úplnosti Polynomialna casova rédukcia Pré dané dva rozhodovacié problémy Pi a P2; polynomialna casova rédukcia jé algoritmus A taky, zé A ma polynomialnu casovu zlozitost! a ■ vstupnu instanciu X problému Pi transformujé na vstupnu instanciu Y problému P2 taku, zé riéséním X jé „Ano" vtédy a lén vtédy, ak riéséní Y jé tiéz „Ano". IB110 Podzim 2010 100 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ Polynomiálna redukcia - príklad redukcia problému Hamiltonovskej cesty na problém obchodného cestujúceho Transformácia graf G = (V, H) (instancia problemu Hamiltonovskej cesty) graf G = (V, H) s ohodnoten ím w : H — N a konstanta K, kde V = V, H = V x V, w (h) = 1 pre vsetky hrany h G H, w (h) = 2 pre vsetky hrany h G H \ H, a K = | V | + 1 (instancia problému obchodného cestujuceho) ■ transformácia sa da vypocítat v polynomialnom case v G Hamiltonovska cesta existuje vtedy a len vtedy ak riesením instancie (G, w, K) problému obchodného cestujuceho je „Áno" IB110 Podzim 2010 101 Prakticky riesiteľne problemy^NP-úplne problemy ^ Redukcia ^ Polynomialna redukcia a existencia algoritmu Prédpokladajmé, zé mamé polynomialny algoritmus O pré problém obchodného céstujucého. Ukazémé, ako za tohto prédpokladu skonstruujémé polynomialny algoritmus H pré problém Hamiltonovskéj césty. Algoritmus H ^ vstup G transformuj na (G, w, K) ^ aplikuj O na (G, w, K) ] ak riéséním (G, w, K) jé „Ano", tak vrat odpovéd' „Ano" 3 v opacnom prípadé vrat! odpovéd' „Nié" IB110 Podzim 2010 102 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ Polynomiálna reduckia a úplnost: Fakt Všetky NP-úplné problémy sú vzájomne polynomiálně redukovatel'né ■ ak chceme o probleme R dokázal!, Ze je NP-úplny, nemusíme ukazoval! redukciu medzi R a vetkými ostatnymi NP-ýplnymi problemami ■ staCí ukazal! polynomiýlnu redukciu problemu R na jeden konkretny NP-ýplny problem ■ redukcia je tranzitívna Cookova veta Problem splnitel'nosti je NP-uplny. IB110 Podzim 2010 103 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ Polynomiálna redukcia - príklad 2 Redukcia 3-zafarbenia mapy na problém splniteľnosti IB110 Podzim 2010 104 Prakticky riešiteľné problémy^NP-úplné problémy ^ Redukcia ^ P=NP? problem P je trieda prakticky rieSitel'nych problémov (tj. problémov, pre ktoré existujú polynomialne algoritmy) Fakt P C NP Otvoreny problem P = NP ? Dôsledky rieSenia problemu. IB110 Podzim 2010 105 Prakticky rieSitelne problemy^NP-úplne problemy ^ Redukcia ^ ČiaštoCne riešenie NP-úplnych problemov ■ pseudopolynomialne algoritmy ■ aproximatívne algoritmy ■ nahodnostne algoritmy ■ kvantove algoritmy ■ geneticke algoritmy IB110 Podzim 2010 106 Prakticky riešiteľné problémy^Ďalšie zložitostné triedy ^ ^ Prakticky riešiteľné problémy ^Kritérium efektivity HNP-úplné problémy Redukcia 10 Ďalšie zložitostné triedy IB110 Podzim 2010 107 Prakticky riesiteľné problémy^Ďalsie zložitostné triedy ^ ^ Este ťaZšie problemy NP-úplne problemý mozú mat! polýnomialne algoritmý ■ existújú problemý, ktore dokazatel'ne nemôzú mat! efektívnejsie nez exponenčialne (prípadne este zlozitejsie) algoritmý Príklady: pravdivost formule v bohatšej logike IB110 Podzim 2010 108 Prakticky riesiteľne problemy^Ďalšie zložitostné triedy ^ ^ Priestorova zlozitost: ■ casova zlozitost! > priestorova zlozitost ■ polynomialny priestor (PSPACE) ■ PSPACE-uplne problemy IB110 Podzim 2010 109 Prakticky riešiteľné problémy^Ďalšie zložitostné triedy ^ ^ Teória výpočtovej zložitosti ■ pojem zložitostnej triedy ■ vztahy medzi zložitostnymi triedami ■ LOGTIME C LOGSPACEC PTIME C PSPACE C EXPTIME C EXPSPACE ... ■ analogicky pre nedeterminizmus ■ kl'UCová otázka presneho vztahu P C NP C PSPACE IB110 Podzim 2010 110 Nerozhodnuteľnost^Nerozhodnuteľne problemy ^ ^ Nerozhodnutemost Nerozhodnutel'níe problíemy Metoída diagonalizíačie Čiastočne rozhodnutel'ne problemy a stupne nerozhodnutel'nosti IB110 Podzim 2010 111 Nerozhodnutelnost^Nerozhodnutefoe problemy ^ ^ 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 1984 IB110 Podzim 2010 112 Nerozhodnuteľnost^Nerozhodnuteľne problemy ^ ^ Otázka existuju algoritmicke problemý, ktore su praktický neriesitel'ne? je to len otaZka dostatocne dlheho casu, výkonneho hardwaru resp. sofistikovaných algoritmov ??? alebo existujýu problýemý, ktorýe suý principiaýlne neriesitel'nýe ??? IB110 Podzim 2010 113 Nerozhodnuteľnoslľ^Nerozhodnuteľne problemy ^ ^ Pravidla uvazujémé algoritmické problémy (tj. problémy urcéné svojou mnozinou vstupnych instanci í a pozadovanym vzt!ahom médzi vstupom a vystupom) problémy s nékonécnou mnozinou vstupnych instanci í (v opacnom pr ípadé pré problém vzdy éxistujé algoritmus zalozény na vyménovan í vsétkych vstupov a k n ím pr íslusnych vystupov) algoritmus = program zapísany v programovacom jazyku vysséj urovné IB110 Podzim 2010 114 Nerozhodnuteľnosť^Nerozhodnuteľne problemy ^ ^ Príklad - domino Vstup (konečna) mnoZina T typov dlaZdíc s farebnymi hranami a je moZne dlaZdicami pokryt! ľubovoľne vel'ku plochu tak, aby sa dlaZdice vZdy dotykali hranami rovnakej farby? z každého typu je k dispozícii neobmedzený počet dlaždíc IB110 Podzim 2010 115 Nerozhodnutel'nost;S=-Nerozhodnuteľne problemy ^ ^ Príklad - domino, instancia 1 Nerozhodnuteľnostľ^Nerozhodnuteľne problemy ^ ^ Príklad - domino, instancia 2 Nerozhodnuteľnost;S=-Nerozhodnuteľne problemy ^ ^ Nérozhodnutéfné problémy Defin ícia Problém, pre ktory neexistuje ziaden algoritmus, sa nazyva nerozhodnutelny (algoritmicky neriesiteľny). prakticky riesitelné problémy prakticky neriesitelné problémy nerozhodnutelné problémy IB110 Podzim 2010 118 Nerozhodnuteľnoslľ^Nerozhodnuteľné problémy ^ ^ Príklad - domino Fakt Problem domina je nerozhodnútel'ný i „zdroj" nerozhodnútel'nosti ■ ekvivalenčia s problemom pokrýtia nekonečnej pločhý ■ periodičita riesenia ■ je dôvodom potenčialne nekonečný počet mozností? ■ dominový had a jeho variantý IB110 Podzim 2010 119 Nerozhodnuteľnosť^Nerozhodnuteľne problemy ^ ^ Príklad - Postov korešpondečný problém (PKP) p dva ZoZnamý slov X = (x1;... xn) a Y = (y1;... yn) a existuje konecna postupnost indexov taka, Ze spojením príslusných slov ZoZnamu X vZnikne rovnake slovo ako spojením príslusných slov ZoZnamu Y? 1 2 3 4 5 X abb a bab baba aba Y bbab aa ab aa a riešením inštancie je „Áno", 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 riešením ištancie je „nie" IB110 Podzim 2010 120 NerozhodnuteľnosIľ^Nerozhodnuteľne problemy ^ ^ Príklad - ekvivalencia a verifikacia programov Ekvivaléncia Vstup dva programovacié jazyky vysséj urovné, ktorych syntax jé dana syntaktickym diagramom alébo v BNF Otazka su mnoziny syntakticky spravnych programov pré oba jazyky zhodné? Vérifikacia Vstup popis algoritmického problému a program v programovacom jazyku vysséj urovné a riési program dany problém? (tj. odpovéď jé „Ano" ak pré kazdu vstupnu instanciu problému sa vypocét programu zastav í a da spravnu odpovéd) Pre oba problémy závisí nerozhodnutefnost na vol'be programovacieho jazyka resp. na vol'be jazyka pre popis algoritmickeho problemu. Pre bezne jazyku su oba problámy nerozhodnutefná. IB110 Podzim 2010 121 Nerozhodnuteľnost^Nerozhodnuteľné 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 = 1 do X — X - 2 od return X Algoritmus B while X = 1 do if X je sude do X — X/2 if X je liche do X — 3X + 1 od return X Algoritmus A pre sude Čísla neskonCí. O algoritme B nieje žname, Ci skonCí pre vsetky vstupne instancie. IB110 Podzim 2010 122 Nerozhodnuteľnost^Nerozhodnuteľné 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 Otazka zastaví sa vypoCet R pre každu vstupnu inštanciu? Problém zastavenia je nerozhodnutelny. Notácia: R (x) j označuje, Ze výpočet R na x skončí; symbol R (x) j označuje, ze neskončí. IB110 Podzim 2010 123 Nerozhodnuteľnost^Nerozhodnuteľne problemy ^ ^ Riceova veta Rozhodnuteľnost je vynimka, ktora potvrdzuje pravidlo Zaujíma nas netrivialna vlastnost programu, ktorí je (1) pravdiva pre niektoré a nepravdiva pre ostane programy (2) nieje viazana na syntax programu, ale vztahuje sa k problemu, ktory program riesi. Riceova veta Vsetky netrivialne vlastnosti programov su nerozhodnutelne. Príklady: je vystupom programu vzdy „Áno"?, zastaví program pre kazdy vstup? IB110 Podzim 2010 124 NerozhodnuteľnosIľ^Metóda diagonalizácie ^ ^ Nerozhodnutelnost N .2 Metoda diagonalizácie ■ CiastoCne rozhodnuteľne problémy a stupne nerozhodnutel'nosti IB110 Podzim 2010 125 Nerozhodnuteľnost^Metóda diagonalizócie ^ ^ Dôkaz nérozhodnutéŕnosti Analógia s dôkazom NP-uplnosti (1) dokazeme nerozhodnutel'nost nejakého problému (2) nerozhodnuteľnost d'alsích problémov dokazujeme metódou redukcie V prípade nerozhodnutelnosti pouzijeme redukciu, ktorí nemusí byt polynomialne casovo ohranicení. IB110 Podzim 2010 126 Nerozhodnuteľnosť^Metóda diagonalizácie ^ ^ Redukcia Redukcia Pre dane dva rozhodovacie problemy P1 a P2; redukcia je algoritmus A ktory vstupnu instanciu X problemu P1 transformuje na vstupnu instanciu Y problemu P2 taku, Ze riesením X je „Áno" vtedy a len vtedy, ak riesením Y je tieZ „Áno". IB110 Podzim 2010 127 NerozhodnuteľnosIľ^Metóda diagonalizócie ^ ^ Redukcia - príklad redukcia problému zastavenia na problém verifikácie IB110 Podzim 2010 128 Nerozhodnuteľnosť^Metóda diagonalizácie ^ ^ Redukcia a dôkaz nérozhodnutélnosti Fakt Ák P1 sa redukuje P2 a P1 je nerozhodnutel'ny, tak aj P2 je nerozhodnutel'ny. Predpokladajme, ze P2 je rozhodnutel'ny a ze B je algoritmus, ktory ho riesi. Pomocou B skonstruujeme algoritmus pre P1. Konretne, vstupní instanciu X problemu P1 prevedieme pomcou algoritmu redukcie na vstupní instanciu Y problemu P2. Pouzijeme algoritmus B a najdeme riesenie Y. Ák riesením Y je „/Áno" tak riesením X je tiez „/Áno". Ák riesením Y je „Nie" tak riesením X je tiez „Nie". To je ale spor s predpokladom, ze P1 je nerozhodnutel'ny. IB110 Podzim 2010 129 Nerozhodnuteľnostľ^Metóda diagonalizócie ^ ^ Nerozhodnutefnosť problému zastavenia Tvrdenie Neexistuje program v L, ktorý pre l'ubovol'nu dvojicu (R, X) (R je syntakticky spravny program v L a X je symbol retazcov), dú na vystup „Áno" prúve ak vypocet R pre vstup X skoncí po konecnom pocte krokov a da na vystup „Nie" v opacnom prípade. Neexistenciu programu pozadovanych vlastností dokazeme sporom. IB110 Podzim 2010 130 Nerozhodnuteľnost;g=-Metóda diagonalizócie ^ ^ Nerozhodnutelnost problému zastavenia Predpokladajme, Ze existuje program poZadovaných vlastností, naZvime ho Q. Skonstruujeme nový program v jaZýku L, naZvime ho S, nasledovne: j\ vstupom programu S je sýntaktický spravný program W v jaZýku L ^ program S precíta W a výtvorí kopiu W ^ S aktivuje program Q so vstupom (W, W) (volaním Q ako procedurý) ^ výpocet Q na vstupe (W, W) skoncí (z predpokladu o vlastnostiach Q) a vrati S odpoved' („Áno" alebo „Nie"). ] ak Q skoncí s odpoved'ou „Áno", tak S vstupi do nekonecneho cýklu (jeho výpocet sa nezastaví) ] ak Q skoncí s odpoved'ou „Nie", tak S da na výstup „Áno". IB110 Podzim 2010 131 Nerozhodnuteľnost^Metóda diagonalizócie ^ ^ Nérozhodnutéfnosť problému zastavénia - spor Z konstruckie programu S je zrejmé, ze S sa pre kazdy vstup W zastaví (s odpoved'ou „AAno") alebo jeho vypocet cyklí donekonecna. Uvízme vípocet S na vstupe W = S. S aktivuje program Q na vstupe (S, S) (bod 3). Podl'a predpokladu Q zastaví. Sí dve moznosti: | Q skoncí s odpoved'ou „/Áno" (tj. íno, program S sa na vstupe S zastaví); v takomto prípade ale S vstípi do nekonecného cyklu. Dostaívame spor. | Q skoncí s odpoved'ou „Nie" (tj. nie, program S sa na vstupe S nezastaví); v takomto prípade ale S da odpved' „/Áno". Opat dostíavame spor. IB110 Podzim 2010 132 Nerozhodnuteľnosť^Metóda diagonalizócie ^ ^ Metoda diagonalizacie Géorg Cantor obécna métoda, postavéna na princ ípé rozdiélnych kardinal ít dokaz, zé réalnych c ísél jé viac ako racionalnych; dolné odhady zlozitosti problémov, ... IB110 Podzim 2010 133 Nerozhodnuteľnost^Metóda diagonalizácie ^Čiastočne rozhodnutelná problémy a stupne nerozhodnuteľnosti ^ Konečné certifikaty pre nerozhodnutefné problémy Analígia s NP-úplnými problemami. V prípade nerozhodnútelnýčh problemov pozadújeme od čertifikítov len konečnost a existenčiú algoritmú ktorý overí, či daní ret!azeč je čertifikítom. p čertifikatom odpovede „Ano" je konkretna, koneční postúpnost indexov; l'ahko overíme, či daní postúpnost indexov mí pozadovaní vlastnost čertifikatom je samotný koneční výpočet; jednodúčho overíme, či dana postúpnost krokov je korektným vípočtom program na vst pe. o čertifikítom je postúpnost dlazdíč a sposob ičh skladania čertikat existúje pre odpoved' nie. Čertifikatom je konečna pločha E. Pretoze E je konečný a počet týpov dlazdíč je tiez konečný, dokazeme overil', ze E sa neda pokrýt' (preveríme vsetký moznosti). IB110 Podzim 2010 134 Nerozhodnuteľnost;S=-Metóda diagonalizócie ^ Čiastocne rozhodnutelná problemy a stupne nerozhodnuteľnosti ^ Čiastocne rozhodnutefne problemy Vsétky prédchadzajucé problémy mali cértifikat pré jédén typ odpovédé; hovorímé o tzv. jédnosmérnom cérfikaté. Défin ícia Nérozhodnutél'né problémy, ktoré maju jédnosmérny cértifikat, sa nazyvaju ciastocné rozhodnutél'né. Ciastocné rozhodnutél'né problémy maju algoritmus, ktory jé koréktny pré jédén typ vstupnych instancií (tj. bud' pré vstupy s odpovéd'ou „Ano", alébo pré vstupy s odpovéd'ou „Nié"). Algoritmus systématicky ovérujé vsétky konécné rél!azcé, ci su cértifikatom daného vstupu. IB110 Podzim 2010 135 Nerozhodnuteľnost;g=-Metóda diagonalizácie Čiastočne rozhodnuteľné problémy a stupne nerozhodnuteľnosti ^ Dvojsmerné certifikáty môže nastat! situacia, ked' pre dany problem míme certifikat ako pre odpoved' „/Áno", tak aj (iny) certifikat pre odpoved' „Nie" (hovoríme o tzv. dvojcestnom certifikate)? príklad: problem Hamiltonovskeho cyklu. Certifikatom pre „Áno" vstup je permutacia vcholov (jednoducho overíme, či tvorí Hamiltonovsky cyklus). Certifikítom pre „Nie" vstup sí vsetky permutacie vrcholov (jednoducho overíme, Ze Ziadna permutácia netvorí Hamiltonovsky cyklus). Fakt Ák problem mí dvojcestny certifikat, tak je rozhodnutel'ny. Algoritmus systematicky a striedavo overuje vsetky konečne reťazce či sí certifikítom pre dany vstup. Konečnosť je zaručení, pretoZe kaZdy vstup mí svoj certifikít. IB110 Podzim 2010 136 Nerozhodnuteľnošlľ^Météda diagonalizécie ^ ČiaštoCne rozhodnuteľné problémy a štupne nerozhodnuteľnošti ^ ESte ťažSie problémy? ■ vSetky CiastoCne rozhodnutelne problemy sú vzájomne redukovatelne (analógia s NP-úplnými problémami, tkroé sú polynomiálně ekvivalentné) ■ existujú problemy, ktore sú tažsie než NP-úplne; platí analúgia aj pre CiastoCne rozhodnutelne problemy? problem verifikacie existuje redukcia problemu zastavenia na problem verifikácie; opacna redukcia ??? úplny problem zastavenia (je vypocet programu konecny pre vsetky vstupne instancie?) Existuje redukcia problemu zastavenia na úplny problem zastavenia; opacnú redukcia ??? Problem verifikúcie ani uplny problem zastavenia nemajú certifikaty IB110 Podzim 2010 137 Nerozhodnuteľnost^Metoda diagonalizacie ^ ČiastoCne rozhodnuteľnó problemy a stupne nerozhodnuteľnosti ^ Stupne nerozhodnuteľnosti analogicky ako rozhodnutel'ne problemy mozeme zoskupil! do rôznych zlozitostnych tried, tak aj nerozhodnutelne problemy tvoria írovne podl'a stupňa nerozhodnuteľnosti kazdí íroven obsahuje problemy, ktore su este ťazsie nez problemy predchíadzajuícej uírovne prvíe dve íurovne hierarchie tvoria ňciastoňcne rozhodnutel'níe a nerozhodnutel'níe problíemy d'alňsie uírovne oznaňcujeme síuhrnne ako vysoko nerozhodnutel'níe problíemy IB110 Podzim 2010 138 Nerozhodnuteľnost;S=-Metóda diagonalizacie ^ ČiastoCne rozhodnuteľnó problemy a stupne nerozhodnuteľnosti ^ Výsoko nerozhodnuteme problemý - príklad modifikacia problemu domina kde poZadujeme, abý v nekonecnom pokrýtí bola vopred specifikovana dlaZdica pouZita nekonecne vel'a krat IB110 Podzim 2010 139 Univerzalita a robustnost;S=-Vypoctovó model ^ ^ Univerzalita a robustnosť 1S Výpoctový model ^Turingov stroj Mchurchova Turing Huniverzalný Turin IB110 Podzim 2010 140 Univerzalita a robustnosť^VýpoCtovó model ^ ^ Jédnoduchý výpoCtový modél Hľadíme co najjednoduchsí pocítac (vypoctovy model), ktory je schopny realizoval! vsetky algoritmicke vypocty. Preco? ■ aky najjednoduchsí model je schopny realizoval' vsetky vypocty? ■ obecnost' vysledkov o praktickej neriesitel'nosti a nerozhodnutel'nosti ■ presna formulícia a formílne dokazy tvrdení tykajucich sa praktickej neriesitel'nosti a nerozhodnutel'nosti IB110 Podzim 2010 141 Univerzalita a robustnosti^-VypoCtový model ^ ^ Jednoduchý výpočtový model - dáta data = retazce sýmbolov ■ pocet rôzných sýmbolov potrebných na zakodovanie retazcov je konecný (podobne ako na zakodovanie všetkých čísel nam stačí v desiatkovej resp. binárnej sústave 10 resp. 2 číslice) ■ data môZeme zapisovat! na jednorozmerní písku, ktora obsahuje polícka; na kaZdom polícku je zapísaný jeden sýmbol, ktorý je prvkom vstupnej abecedý Linearizacia datových struktur ■ linearizacia zoznamu ■ linearizacia dvojrozmerneho pol'a, matice ■ linearizícia stromu Dýnamicke dítove struktírý a neohranicenost jednosmernej paský IB110 Podzim 2010 142 Univerzalita a robustnost^VýpoCtový model ^ ^ Jédnoduchý výpoCtový modél - riadiaca jédnotka IB110 Podzim 2010 143 Univerzalita a robustnost;S=-Výpoctovó model ^ ^ Jédnoduchý výpočtový modél - riadiaca jédnotka ■ vypocetje realizovany riadiacou jednotkou ■ riadiaca jednotka je vzdy v jednom z konecne vel'a roznych stavov (stav zodpovedá inštrukcii algoritmu) ■ riadiaca jednotka vzdy snímí príve jedno polícko jednorozmernej pasky (hodnota, s ktorou manipuluje inštrukcia algoritmu) ■ atomické akcie ■ prečítanie symbolu z polícka pasky ■ zapis symbolu na polícko pasky ■ posun o jedno polícko na paske ■ zmena stavu riadiacej jednotky ■ zavislost zmeny na aktualnych hodnotach IB110 Podzim 2010 144 Univerzalita a robustnost;>Vypoctovó model ^ ^ Jednoduchý výpoctový model - zakladne operacie jédén krok vypoctu ■ précítanié symbolu ■ podl'a aktualného stavu riadiacéj jédnotky a précítaného symbolu sa vykonía ■ zména stavu ■ zápis symbolu ■ posun o jédno polícko vpravo alébo vl'avo Turingov stroj Alan Turing, 1936 IB110 Podzim 2010 145 Univerzalita a robustnost;g=-Turingov stroj ^ ^ Univerzalita a robustnosť ■Vypoctovy mo< .4 Turingov stroj Bchurchova Tur Buniverzalny Tu IB110 Podzim 2010 146 Univerzalita a robustnost;>Turingov stroj ^ ^ Turingov stroj Turingov stroj (TS) pozostava z ■ (konecnej) mnoziny stavov ■ (konecnej) abecedy symbolov ■ nekonecnej pasky rozdelenej na polícka ■ cítacej a zapisovacej hlavy, ktora sa pohybuje po paske a sn íma vzdy 1 pol ícko pasky ■ prechodoveho diagramu IB110 Podzim 2010 147 Univerzalita a robustnostľ^Turingov stroj ^ ^ Turingov stroj - prechodový diagram Prechodovy diagram ■ orientovany graf ■ vrcholy grafu su stavy TS ■ hrana z vrcholu s do vrcholu t reprezentuje prechod a je oznacení dvojicou tvaru (a/b, L) alebo (a/b, R); ■ a je symbol, ktorí hlava TS z písky cíta (tzv. spínac) ■ b je symbol, ktory na písku zapisuje ■ L resp. R určuje smer pohyb hlavy doľava resp. doprava ■ pozadujeme, aby diagram bol jednoznacny (deterministicky Turingov stroj), tj. zo stavu nesmí vychadzat dve hrany s rovnakym spínacom ■ jeden zo stavov je oznaceny ako startovní (pociatocní) stav (oznacení sípkou) ■ niektore zo stavov sí oznacene ako koncove stavy (oznacene vyraznym ohranicením) IB110 Podzim 2010 148 Univerzalita a robustnost;g=-Turingov stroj ^ ^ Turingov stroj - vypočet Krok výpočtú prečhod z s do t označený (a/b, L) v prečhodovom diagrame ak riadiača jednotka TS je v stave s a hlava číta sýmbol a, tak hlava prepise sýmbol a sýmbolom b, posúnie sa o 1 políčko dol'ava a stav riadiačej jednotký sa zmení na t (analogicky pre (a/b, R) a pohyb vpravo) Výpočet Výpočet začína v počiatočnom stave na najlavejsom neprazdnom políčkú paský. Výpočet prebieha krok po krokú tak, ako predpisúje prečhodový diagram. Výpočet sa zastaví ked' dosiahne niektorý z končovýčh stavov. IB110 Podzim 2010 149 Univerzalita a robustnosť^Turingov stroj ^ ^ Univerzalita a robustnost^Turingov stroj ^ ^ Univerzalita a robustnosť^Turingov stroj ^ ^ Simu I ator Turingovych strojov http://www.fi.muni.cz/ xbarnat/tafj/turing IB110 Podzim 2010 153 Univerzalita a robustnosť^Turingov stroj ^ ^ Túringov štroj ako algoritmus i Turingov stroj môžeme chapat ako pocítac s jednym, fixovanym programom ■ softwarom je prechodovy diagram; hardwarom je riadiaca jednotka a paska ■ jednotlive TS sa líšia iba svojim softwarom, preto casto hovoríme o programovaníTuringovho stroja IB110 Podzim 2010 154 Univerzalita a robustnostľ^Turingov stroj ^ ^ Turingov stroj ako algoritmus i Turingov stroj môžeme naprogramoval! tak, aby riešil rozhodovací problém ■ pre rozhodovac í problém P, ktorého množina vstupných instanci í je kodovana ako množina linearizovanych retazcov, konštruujeme Turingov stroj M s pociatocnym stavom s a dvoma koncovými stavmi YES a NO pre kazdy vstup X, ak M zacne vypocet v stave s na najl'avejsom symbole retazca X, tak M skonc í vypocet v stave YES a NO v zavislosti na tom, ci vystupom P pre X je „Áno" alebo „Nie" IB110 Podzim 2010 155 Univerzalita a robustnost;>Turingov stroj ^ ^ Turingov stroj ako algoritmus Turingové strojé môzu byť naprogramované aj pré riésénié inych néz rozhodovacích problémov. V takomto prípadé prédpokladímé, zé kéd' sa TS zastaví (préjdé do koncového stavu), tak vystupom jé rétazéc zapísany na paské médzi dvoma spécialnymi znakmi (napr. !) Ak sa vypocét zastaví a na paské jé iny pocét symbolov ! ako 2, chapémé vypocét ako néukoncény (tj. ako vypocét, ktory cyklí donékonécna). IB110 Podzim 2010 156 Univerzalita a robustnosť^Churchova Turingova hypoteza ^ ^ Univérzalita a robustnosť ■Vypoctovy model ^Turingov stroj 15 Churchova Turingova hypoteza MlY/lodifikacie Turingovho stroja Hllniverzalny Turingov stroj IB110 Podzim 2010 157 Univerzalita a robustnosť^Churchova Turingova hypoteza ^ ^ Churchova Turingova hýpoteza Ake problemý su riesitelne pomocou vhodne naprogramovaneho TS? Churchova Turingova hýpoteza KaZdý algoritmický problem, pre ktorý existuje program v nejakom programovacom jazýku výssej írovne a je riesitelný na nejakom hardwaru, je riesitelný aj na Turingovom stroji. Preco hýpoteza? CT hýpoteza formuluje vzťah medzi dvoma konceptami: ■ matematický presný pojem riesitelnosti na Turingovom stroji a ■ neformalný koncept algoritmickej riesitelnosti, ktorí je postavený na pojmoch „programovací jazýk výssej urovne", „program v programovacom jazýku" IB110 Podzim 2010 158 Univerzalita a robustnosť^Churchova Turingova hypotéza ^ ^ Argumenty pre Churchovovu Turingovu hypotézu CT hypotézu formulovali v 30-tych rokoch nezávisle Alonso Church a Alan Turing. Od tej doby bolo navrhnutých mnoZstvo „univerzálnych" modelov (absolútnych, schopných riesit všetky mechanicky riešiteľné problémy) ■ Turingove stroje (Alan Turing) ■ lambda kalkulus (Alonso Church) ■ produkcne systemy (Emil Post) ■ rekurz ívne funkcie (Stephen Kleene) ■ kvantove poc ítace Fakt O vsetkych navrhnutych formalizmoch je dokazane, ze su ekvivalentne v tom zmysle, ze urcuju zhodnu triedu algoritmicky riesitel'nych problemov. IB110 Podzim 2010 159 Univerzalita a robustnostľ^Churchova Turingova hypoteza ^ ^ Dosledký Churchovej Turingovej hýpotezý ■ extremne vykonne superpocítace nie su silnejsie nez male pocítace s jednoduchym programovacím jazykom; za predpokladu neohraniceneho casu a velkosti pamate dokazu obidva riesiť tie iste algoritmickíe problíemy ■ pojem algoritmicky riesitelneho (rozhodnutelneho) problemu je robustníy, tj. je nezíavislíy na konkríetnej vol'be víypoňctovíeho modelu resp. programovacieho jazyka CT hypoteza podporuje spravnost definície nerozhodnuteľnych problíemov IB110 Podzim 2010 160 Univerzalita a robustnost;>Modifikócie Turingovho stroja ^ ^ Univerzalita a robustnosť ■Vypoctovy modél ^Turingov stroj Mchurchova Turingova hypotéza Modifikícié Turingovho stroja Mllnivérzalny Turingov stroj IB110 Podzim 2010 161 Univerzalita a robustnost^Modifikócie Turingovho stroja ^ ^ Modifikacié Turingovho stroja /Argumentom podporujucim CT hypotézu je aj robustnost TS. Modifikacie ■ TS, ktory ma po skoncen í vypoctu zap ísany na paske len vstupny a vystupny ret'azec ■ TS s jednosmerne nekonecnou paskou ■ TS s dvojrozmernou paskou TS s konecnym poctom pasok (kazda mas svoju c ítaciu/zapisovaciu hlavu) Fakt Vsetky uvedené modifikacie su vzajomne ekvivalentné Dokaz technikou simulacie: ukazeme, ze vypocet jedného zariadenia sa da simuloval! na druhom zariaden í a naopak IB110 Podzim 2010 162 Univerzalita a robustnosť^Modifikácie Turingovho stroja ^ ^ Programy s počítadlami (Counter Programs, CP) ■ programý manipúlújú s prirodzenými číslami úlozenými v premennýčh ■ tri elementírne operačie X — 0 priradí premennej hodnotú 0 X — Y + 1 X — Y — 1 ak hodnota Y je 0, tak X priradí hodnotú 0 ■ jeden elementarný riadiači príkaz ifX = 0 goto G, kde X je premenna a G je navestie pripojene k príkazú IB110 Podzim 2010 163 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Programy s počítadlami - príklad U — 0 Z — 0 if X = 0 goto G X - X - 1 V - Y + 1 V - V-1 if V = 0 goto A V - V-1 Z - Z+1 if U = 0 goto B vykonanié goto G jé ékvivaléntom íspésného ukoncénia vypoctu IB110 Podzim 2010 164 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Turingové strojé a programy s poCítadlami TS manipuluju so symbolmi, PS s císlami je mozna ich vzajomna simulacia? IB110 Podzim 2010 165 Univerzalita a robustnost;>Modifikócie Turingovho stroja ^ ^ Simulacia TS na CP obsah paský —> císla pre jednoduchost' predpokladajme, Ze abeceda TS mía desat' Znakov znaký ocíslujeme a reťazce znakov prevedieme na císla Príklad #-0 !- 1 *-2 a - 3 b - 4 c - 5 d - 6 e - 7 f - 8 g - 9 retazec ... ## ab * eb !# aga ## ... v ktorom je snímaný sýmbol b, prevedieme na dvojicu čísel 3427 a 393014 IB110 Podzim 2010 166 Univerzalita a robustnost;g=-Modifikácie Turingovho stroja ^ ^ Simulacia TS na CP zmena symbolu na paske zmena poslednej císlice v druhom cí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 prve císlo vynasobíme 10 a pripocítame k nemu poslednu císlicu druheho císla druhe císlo vydelíme 10 (celocíselne) analogicky pre posun hlavy dol'ava zmena stavu stavu TS zodpoveda skupina instrukci í CP; zmena stavu je simulovana skokom na novu skupinu instrukci í (pr íkaz goto) CP, ktory simuluje TS, ma len dve pocítadla! IB110 Podzim 2010 167 Univerzalita a robustnosť^Modifikácie Turingovho stroja ^ ^ Simu l ácia CP na TS čísla <— symboly hodnota kaZdej premennej je zapísaní ako postupnost! symbolov = číslic; jednotlive hodnoty su vzajomne oddelene specialnym symbolom (napr. *) instrukcie <— stavy kaZdej instrukcii programu zodpoveda skupina stav TS, vykonenie instrukcie je simulovane prechodom do príslusneho stavu a realizacia postupnosti krokov, ktoríe potrebníym spôosobom upravia obsah premennej IB110 Podzim 2010 168 Univerzalita a robustnost;g=-Modifikácie Turingovho stroja ^ ^ Simulácie ako redukcie Ak model A simúlúje model B, tak mame redúkčiú medzi týmito modelmi. Redúkčia prevedie program modelú A a jeho vstúp X na program modelú B a jeho vstúp Y. CT hýpoteza úkazúje, ze nase úvahý pri konstrúkčii redúkčií boli korektne. IB110 Podzim 2010 169 Univerzalita a robustnost;>Modifikácie Turingovho stroja ^ ^ Simulacie ako redukcie Ak modél A simulujé modél B, tak mamé rédukciu médzi tymito modélmi. Rédukcia prévédié program modélu A a jého vstup X na program modélu B a jého vstup Y. CT hypotéza ukazujé, Zé nasé uvahy pri konstrukcii rédukcií boli koréktné. Príklad nerozhodnutefnost problému zastavenia ^ formálne dokážeme nerozhodnutefnost problému pre TS ^ podía CT hypotázy problem zastavenia nemôže byt rozhodnutelný ani pre žiaden iná programovací jazyk vyššetj úrovne (je ekvivalenty TS!) Fénomén algoritmus, ktorého vstupom jé iny algoritmus IB110 Podzim 2010 169 Univerzalita a robustnost^Univerzólný Turingov stroj ^ ^ Univérzalita a robustnosť Výpočtový model Turingov stroj Churchova Turingova hypo Modifikace Turingovho str Univerzalny Turingov stroj IB110 Podzim 2010 170 Univerzalita a robustnostľ^Univerzálny Turingov stroj ^ ^ Univerzálny algoritmus jeden z najdôležitejších dôsledkov CT hypotézy Existencia univerzálneho algoritmu, ktorý ma schopnost choval! sa ako akykolvek iny algoritmus. ■ vstupom pre univerzýlny algoritmus je popis akehokolvek algoritmu A a akehokolvek jeho vstupu X ■ univerzýlny algoritmus simuluje vypocet A na X m vypocet univerzalneho algoritmu sa zastaví prýve ak vypocet A na X sa zastaví; ako vystup poskytne univerzalny algoritmus presne tý istu odpoved! ako poskytne A na X ak fixujeme algoritmus A a meníme X, tak univerzálny algoritmus sa chová presne ako algoritmus A IB110 Podzim 2010 171 Univerzalita a robustnosť^Univerzálny Turingov stroj ^ ^ Univerzálny algoritmus ■ moZe byt! vstupom univerzílneho algoritmu program v akomkoľvek programovacom jazyku? ■ vyuZijeme CT hypotezu a poznatok o ekvivalencii vsetkych znamych formalizmov pre popis algoritmov ■ ku konstrukcii univerzílneho algoritmu potrebujeme len jazyk L1, v ktorom napíšeme program U pre univerzalny algoritmus; program akceptuje ako vstup l'ubovol'ny program napísany vo fixovanom konkríetnom jazyku L2 i program U je nezívisly na víbere modelu, pretoZe podl'a CT hypotíezy | môZe byť napísaní v akomkoľvek jazyku ] dokaZe simulovat: akykol'vek algoritmus popísany v akomkoľvek jazyku Vhodným kandidátom pre jazyky L1 a L2 sú Turingove stroje. IB110 Podzim 2010 172 Univerzalita a robustnosť^Univerzálny Turingov stroj ^ ^ Univerzálny Turingov stroj ■ potrebujeme popísal! Turingov stroj ako linearny retazec nad konecnou abecedou symbolov ■ stací linearizovat prechodovy diagram ■ mark ** mark YES (#/#, L) * mark movea (a/#, R) * movea movea (a/a/, R) *... m linearizovany prechodovy diagram prevedieme standartnym spôsobom na retazec nad fixovanou abecedou (napr. binarnou) ■ podobne linearizujeme a kódujeme aj vstup simulovaneho TS ■ samotny program univerzalneho TS je jednoduchy svojim princípom: uchovava si aktualny stav simulovaneho TS, obsah jeho pasky a c ítany symbol; z linearizovaneho popisu simulovaneho TS odvod í, ake akcie sa maju realizoval! v d'alsom kroku vypoctu simulovaneho TS IB110 Podzim 2010 173 Univerzalita a robustnost^Univerzálný Turingov stroj ^ ^ Univérzalny program s počítadlami vstupom je dvojica c ísel; prvé c íslo je kódom nejakého programu s poc ítadlami, druhé c íslo je kodom jeho vstupu univerzalny program je mozné skonstruovat tak, aby vyuz íval len dve poc ítadla IB110 Podzim 2010 174 Univerzalita a robustnost;g=-Robustnost triedy prakticky riešiteľných problámov ^ ^ Univerzalita a robustnosť ■Výpočtový model MTúringov stroj Mchúrčhova Túringova hýpoteza Huniverzílný Túringov stroj Robústnost triedý praktičký riesitel'nýčh problemov IB110 Podzim 2010 175 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problémov ^ ^ Modifikované programý s počítadlami Motivacia ■ TS manipuluje jednom kroku výpoctu s jedným sýmbolom paský (s jednou číslicou čísla) ■ CP mení jednou instrukciou hodnotu premennej o 1 (exponencialne menej efektívne v porovnaní s TS) ■ narovnanie diskrepancie ■ CP musí mať moZnost k c íslu pridať alebo odobrať c íslicu v konstantnom case Modifikacia mnoZinu instrukci í CP rozsírime o 2 nove instruckie X — X/10 celoc íselne delenie IB110 Podzim 2010 176 Univerzalita a robustnost;g=-Robustnost triedy prakticky riešiteľných problámov ^ ^ Polýnomialna redukcia Existencia redukcií medzi programovacími jazykmi vyssej urovne (dostatocne silnymi vypoctovymi modelmi) ukazuje, ze trieda rozhodnutelnych problemov je invariantna voci vol'be jazyka (modelu). Otazka Aka je zlozitost redukcie? Fakt Ak oba modely manipuluju s císlami v inej nez unarnej sýstave, tak redukcia ma polynomiílnu casoví zlozitosl' . IB110 Podzim 2010 177 Univerzalita a robustnost;>Robustnost triedý praktický riešiteľných problámov ^ ^ ZloZitost rédukcií médzi TS a modifikovanými CP Zlozitost vypoctu TS pocet krokov vypoctu CP pocet vykonaných instrukci í Zlozitost vypoctu je funkciou d l zky vstupu; hodnota funkcie pre argument N zhora ohranicuje zlozitost vypoctov na vsetkyh vstupoch d l zky N. D l zkou vstupu pre TS je pocet znakov vstupného retazca, d l zkou vstupu pre CP je pocet c íslic pociatocnych hodot premennych. Redukcia TS —> modifikované CP krok vypoctu je simulovany zmenou hodnoty kazdého poc ítadla; zmena je realizovatelna konstantnym poctom instrukci í Redukcia modifikované CP —> TS kazda instrukcia je simulovana konstantnym poctom krokov TS a modifikované CP su polynomialne ekvivalentné IB110 Podzim 2010 178 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ Polynomiálna redukcia - dôsledky Nech vypočtove modely A a B sí polynomiílne ekvivalentne. Ak algoritmický problém P je riešiteľný na A s časovou zložitosťou 0(f(N)) ( f je funkcia dlžký vstupu), tak existuje program pre B, ktorý rieši problem P a jeho časova zloZitost je 0(p(f(N))), pričom p je nejaka (fixovana) polýnomialna funkcia. Naopak, ak P je riesitelný na B v čase 0(g(N)), tak existuje program pre A, ktorý riesi P s časovou zložitostou 0(q(f(N))), pričom q je nejaka (fixovana) polýnomialna funkčia. Ak TS riesi problem v polynomiálnom case, tak aj modifikový CP riesi tento problem v polynomiálnom case (a naopak). Ak neexistuje polynomialny TS pre daný problém, tak neexistuje ani polynomialny modifikoaný CP pre tento problem. IB110 Podzim 2010 179 Univerzalita a robustnost;g=-Robustnost triedy prakticky riesiteľných problámov ^ ^ Robustnosť triedy prakticky riešiteľných problemov CT hýpotíeza úkazúje robústnost' pojmú rozhodnútel'níý problíem. Polýnomialna ekvivalenčia zjemňúje toto pozorovanie na praktičký riesitelne problemý. Sekvenčna výpočtova hýpoteza Pojem praktičký riesitelneho problemú je robústný, tj. je nezavislý na konkretnej vol'be výpočtoveho modelú resp. programovačieho jazýka. Hypotéza sa nevztahuje na modely s neohraničeným zdrojom paralelizmu, preto sa označuje ako „sekvenčná". Triedý P, NP, PSPACE, EXPTIME sú robústne Triedy s lineárnou časovou zlozitostou nie sá robustne. IB110 Podzim 2010 180 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problémov ^ ^ Nedeterministické Turingove stroje pre rozhodovacie problemy ■ v prechodovom diagrame je povolene, aby s jedneho stavu vychýdzal ľubovoľný pocet hran oznacenych zhodym spínacom (symbolom, ktory sa číta) ■ stroj ma moznost výberu, ktory z prechodov pouzije i pre vstup X da TS odpoved' „/Áno" (akceptuje) prýve ak existuje taka postupnost vyberu prechodov, pre ktom vypocet skoncý v koncovom stave YES (stroj uvíazi vsetky mozníe víypocty na X a akceptuje X praíve ak aspon jeden z vypoctov skončí v stave YES) m v opacnom prípade, tj. ak ziaden vypocet neskoná v stave YES, da odpoved' „Nie" Nedeterministicke TS sý ekvivalentne (deterministickym) TS. IB110 Podzim 2010 181 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problámov ^ ^ P=NP? problém - revízia Formalna définícia triéd P a NP Triéda P (NP) obsahujé rozhodovacié problémy, ktoré su riésitél'né Turingovymi strojmi (nédétérministickymi TS) s polynomialnou casovou zlozitostou. P=NP? problém Sú détérministické a nédétérministické Turingové strojé polynomiálné ékvivaléntné? IB110 Podzim 2010 182 Univerzalita a robustnost;>Robustnost triedy prakticky riešiteľných problémov ^ ^ P=NP? problém - revízia Defin ícia NP-tažkého a NP-úplného probému Rozhodovac í problém sa nazýva NP-tažký ak každý problém ž triedy P je na ného polynomiainé rédukovatéľný. Rozhodovac í problém sa nazýva NP-úplný ak jé NP-tažký a naviac patrí do triédý NP. Faktý Ak nejaký NP-úplný problém patrí do triedy P, tak P = NP. Ak P = NP, tak žiaden NP-úplný problém nieje riešiteľný algoritmom polynomiainej zložitosti. IB110 Podzim 2010 183 Univerzalita a robustnost;>Robustnost triedý praktický riesiteľných problámov ^ ^ Turingové strojé a dolné odhady zloZitosti problémov ■ dôkaz nerozhodnutelnosti problému redukcia problému o ktorom je uz dokazané, zeje nerozhodnutelny, na problém o ktorom chceme dokízat, zeje nerozhodnutelny príklad redukcia problému zastavenia na problém domina ■ dôkaz vztahu medzi zlozitostnymi triedami metíoda diagonalizaície príklady P C EXPTIME, PSPACE c EXPSPACE ■ dokaz, ze problém nepatrí do zlozitostnej triedy doôsledok uíplnosti príklad ziaden EXPTIME-íplny problém nepatrí do triedy P pre dokaz horných odhadov zložitosti problémov nie sú TS vhodné; naopak je vhodné pouzit programovací jazýk výSSej úrovne IB110 Podzim 2010 184 Univerzalita a robustnost;g=-Robustnost triedy prakticky riesiteľnych problámov ^ ^ Redukcia problemu zastavenie na problem domina a ílohou je pokryt' horní polovicu nekonecnej plochy s podmienkou, ze prví dlazdica v T (nazveme ju t) je umiestnenía niekde v spodnom riadku a odpoved' „Ano" pre vstup (M, X) takí, ze vypocet M na X sa nezastaví IB110 Podzim 2010 185 Univerzalita a robustnost;>Robustnost triedy prakticky riesiteľných problámov ^ ^ Redukcia problemu zastavenie na problem domina Rédukcia Vstup dvojica (M, X) Vystup mnozina typov dlazdíc T a dlazdica t Princíp konstrukcié (T, t) pokrytié dlazdicami koréspondujé s vypoctom; pokrytié nékonécnéj plochy jé mozné lén v prípadé éxisténcié nékonécného vypoctu IB110 Podzim 2010 186 Univerzalita a robustnost^-Robustnost triedy prakticky riešiteľných problámov ^ ^ IB110 Podzim 2010 187 Univerzalita a robustnost^-Robustnost triedy prakticky riešiteľnych problémov ^ ^ IB110 Podzim 2010 1BB Formalne jazyky ;>Automaty ^ ^ Formalne jazýký 19 Automaty G IB110 Podzim 2010 189 Formalne jazyky ^Automaty ^ ^ Jednosmerne TS alebo konecne automaty i TS sí robústne voči modifikíčiam ■ existúje modifikačia, ktora zmení (zmensí) výpočtovú silú TS? ■ ano, modifikačia ale músí ohraničil' výpočtový zdroj Túringovho stroja polýnomialný čas trieda P polýnomialný priestor trieda PSPACE (triedý P a PSPACE sú mensie nez trieda rozhodnútel'nýčh problemov) jeden smer pohýbú na paske ohraničenie spočíva v tom, ze TS nema moznost vratiť sa k informačii, ktorú úz raz prečítal a ani nema moznost si o prečítanom úsekú účhovat kompletnú informačiú (riadiača jednotka máa len konečný počet stavov) = konečne aútomatý IB110 Podzim 2010 190 Formálne jazyky^Automaty ^ ^ Konečne automaty ■ vstupny ret!azec sa cíta zl'ava doprava, symbol po symbole ■ precítany symbol sa neprepisuje ■ vypocet sa zastaví po preataní posledneho symbolu alebo v situacii, ked' prechodovy diagram neumozňuje ziadny d'alsí krok ak sa vypocet zastaví po preataní celeho vstupu v stave YES, znamena to odpoved' „Áno" (konecny automat akceptuje vstup); ak sa vypocet zastaví v inom stave alebo sa zastaví a nieje precítany celíy vstup, znamenía to odpoved' Nie" (automat zamieta vstup) IB110 Podzim 2010 191 Formalne jazyky^Automaty ^ ^ Konecne automatý - dolne odhadý Problem rozhodnut', ci dany reťazec obsahuje rovnaky pocet symbolov a, Tvrdenie Neexistuje konecny automat, ktory riesi tento problem. Dôkaz Sporom. Predpokladajme, ze existuje automat F, ktory problem riesi. Oznacme N pocet stavov automatu F. Uvazme vstupny reťazec, ktory obsahuje presne N + 1 symbolov a, za ktorymi nasleduje presne N + 1 symbolov b. Pri cítaní uvodnej sekvencie a-cok musia byť dve polícka, ktore automat cíta v tom istom stave (počet políčok je N + 1, počet stavov je N). Vytvorme novy vstupny reťazec tak, ze odstranime vsetky symboly medzi tymito dvoma a-ckami (viz obrazok). Vypocet na novom vstupnom reťazci skoncí v tom istom stave a v tej istej pozícii ako vypocet na pôvodnom vstupnom reťazci. Ak automat akceptuje obidva reťazce dostavame spor (modifikovaný retazec nemý požadovanú vlastnost). Naopak, ak automat obidva reťazce zamieta - spor (pôvodný retazec mú požadovanú vlastnost). IB110 Podzim 2010 192 Formálne jazyky^Automaty ^ ^ slav s \a a a a a a i- fc b ŕ; "1 1 2 3 4 5 6 1 2 3 4 5 6 7 8 9 10 YES! (správne NO\) automat pocita presne ako na pôvodnej postupnosti IB110 Podzim 2010 193 Formálne jazyky^Automaty ^ ^ Konečné automaty ako model systému s udalosťami IB110 Podzim 2010 194 Formalne jazyky ^Automaty ^ ^ Konečne automaty - terminológia pojém jazyka ako ékvivaléntu pojmu rozhodovací problém régularny jazyk régularné vyrazy IB110 Podzim 2010 195 Formalne jazyky^Generatívne výpoctove modely ^ ^ Formalne jazyky Au 20 Génératívné vypoctové modély IB110 Podzim 2010 196 Formélne jazyky^Generatívne výpoCtové modely ^ ^ Generatívne vypoCtove modely Fixujme rozhodovaa problem P (resp. jazyk P/) e urát, ci pre dany vstup X je odpoved' „/Áno" alebo „Nie" (resp. urcit, Ci X patrí do jazyka Lx) e vymenoval! vsetky vstupy, pre ktore je odpoved' „Áno" (resp. vymenovat vsetky slová jazyka P/) Motivacia navod, ako vytvorit „sprývny" retazec formalna gramatika IB110 Podzim 2010 197 Formálne jazyky;>Generativne výpočtová modely ^ ^ Formaine gramatiky príklad IB110 Podzim 2010 198 Formalne jazyky^Generatívne výpoctové modely ^ ^ Formalne gramatiky - vlastnosti Fakt Trieda jazýkov generovaníýčh formíalnými gramatikami je príave trieda rozhodnútel'níýčh problíemov. Formalne gramatiký s obmedzeniami / retazeč na l'avej strane pravidla je nieje dlhsí nez ret'azeč na pravej strane pravidla ý na l'avej strane kazdeho pravidla je príve jeden neterminaílný sýmbol regúlíarne gramatiký IB110 Podzim 2010 199 Formalne jazyky^Generatívne výpoctove modely ^ ^ Formalne gramatiky - problem syntaktickej analýzy Pré danu formalnu gramatiku a rétazéc rozhodnut!, ci jé slovo sa gramatikou vygénérovat'. rozhodnut, ci program v programovacom jazyku (definovanom gramatikou) je syntakticky spraávny Problém syntaktickéj analyzy jé ciastocné rozhodnutélny pré formalné gramatiky rozhodnutélny pré kontéxtové gramatiky polynomialné riésitél'ny pré bézkontéxtové gramatiky je dolezitá, aby sme pre definíciu syntaxe programovacieho jazyka použili Co najjednoduchší typ gramatiky IB110 Podzim 2010 200 Alternatívne výpoCtová modely^ ^ Alternatívne vypoCtove modely Motivacia existencia veľkej triedy prakticky neriesiteľních (ale rozhodnutelných) problemov, ktore potrebujeme prakticky riesit! Idea využit! principiílne ine spôsoby počítania ■ paralelne počítanie ■ síbežnost ■ kvantove počítanie ■ molekularne počítanie ■ nahodnost! pomôže to ??? IB110 Podzim 2010 201 Alternatívne vypoctove modely^Paralelizmus ^ ^ Alternatívne vypoctove modely 21 Paralelizmus MKvantove po HMolekularne ^Nahodnostne IB110 Podzim 2010 202 Alternatívne výpoctove modelý^Paralelizmus ^ ^ Princíp paralélizmu Praktickí príklad A veza o zaklade 1m x 10 m a vysky 1 m; 1 murír vs 10 muraírov B veza o zaklade 1m x 1 m a vysky 10 m; 1 murír vs 10 muraírov Jednoduchí program A X — 3; Y — 4 Varianta B X — 3; Y — X paralelizovatel'ne problémy vs vnútorne sekvenčne problémy IB110 Podzim 2010 203 Alternatívne výpoctove modely^Paralelizmus ^ ^ Paralelne scitovanie IB110 Podzim 2010 204 Alternatívne vypoctové modely^Paralelizmus ^ ^ Paralelne scitovanie pre sčítanie 1 000 čísel potrebújeme v 1. krokú 500 pročesorov v 2. krokú 250 pročesorov v 3. krokú 125 pročesorov pri vhodne zvolenej díatovej strúktúíre a organizíačii komúnikaíčie mezdi pročesormi stačí na realizíčiú čeleho výpočtú príve 500 pročesorov pre sčítanie N čísel potrebújeme N/2 pročesorov a počet (paralelnýčh) výpočtovýčh krokov je O(log N) IB110 Podzim 2010 205 Alternatívne výpoctove modely^Paralelizmus ^ ^ Paralelizmus - počét procesorov pocet procesorov potrebných k realižacii paralelneho výpoctú ako funkcia veľkosti vstupnej inštancie (N/2 pre sčítanie N čísel) je to realisticke? indikator, ake vel'ke vstúpý môžeme riešil! s poctom procesorov, ktore mame k dispozícii (viz analógia s časovou a priestorovou zložitostou) ak pocet procesorov, ktore mame k dispozícii, je mensí, moZeme kombinovať paralelný a sekvencný prístup IB110 Podzim 2010 206 Alternatívne výpoCtové modely^Paralelizmus ^ ^ Paralelene triedenie sekvencne triedenie zoznamu L spájaným (mergesort) procedura sort-L (1) ak L ma len 1 prvok, je utriedeny (2) inak (2.1) rozdel' L na dve polovicky L1 a L2 (2.2) sort-L1 (2.3) sort-L2 (2.4) spoj dva utriedene zoznamy do jedneho utriedeneho zoznamu pocet vykonanych porovnaný je O(N log N) IB110 Podzim 2010 207 Alternatívne výpoCtove modely^Paralelizmus ^ ^ Paralelne triedenie paralelne triedenie žožnamu L spajaním procedUra parallel-sort-L (1) ak L ma len 1 prvok, je utriedeny (2) inak (2.1) roždel' L na dve polovičky L1 a L2 (2.2) subežne volaj parallel-sort-L1 a parallel-sort-L2 (2.3) spoj dva utriedene žožnamy do jedneho utriedeneho žožnamu počet (paralelnych) porovnaní je (predpokladáme, Ze N je mocninou 2) v 1. kroku N postupností dlžky 1; N/2 procesorov; spojenie dvoch postupností = 1 porovnanie v 2. kroku N/2 postupností dlžky 2; N/4 procesorov; spojenie dvoch postupností = 3 porovnania v 3. kroku N/4 postupností dlžky 4; N/8 procesorov; spojenie dvoch postupností = 7 porovnaní spolu 1 + 3 + 7 + 15+-----h (N - 1) < 2N porovnaní IB110 Podzim 2010 208 Alternatívne vypoctove modely^Paralelizmus ^ ^ Paralelizmus - cas x priestor konvencia: v kontexte paralelnych vypoctov sa pod priestorovou zlozitostou rozumie pocet procesorov potrebnych k realizacii vypoctu casova a priestorova zlozitosl' paralelnych vypoctov su spolu tesne zviazane zníženie jednej obvykle znamena zvýšenie druhej a naopak IB110 Podzim 2010 209 Alternatívne výpočtové modely^Paralelizmus ^ ^ Paralelizmus - cas x priestor SEQUENTIAL PARALLEL Name Size (no. of processors) Time (worst case) Product (time x size) Bubblesort 1 0(N2) Mergesort 1 0(Nx\ogN) 0(Nx logAO (optimal) Parallelized mergesort 0(N) SábeZnost ^ ^ SUbežnost situácie, ked' paralelizmus nevýúžívame k tomú, abý sme zefektívnili výpoctý, ale ked' paraleližmús vžnika v realných aplikaciach reaktívne a žapúždrene sýstemý Úloha navrhnut komunikacne protokolý pre komunikujuce objektý tak, abý splnali poZadovane vlastnosti Specifikum ílohou sýstemov nieje nájsť konkrétne riesenie, ale pocítat (být! funkcný) „donekonecna" IB110 Podzim 2010 220 Alternatívne výpoCtové modely;>Sébeznost ^ ^ Problem hotelovej sprchy ■ na poschodý je len jedna sprcha, na veľmi studenej chodbe ■ kazdy host sa chce osprchoval;, ale nemoze cakat na volnu sprchu na chodbe ak by z casu na cas kontroloval, ci je sprcha volna, moze nastat; situýcia, ze sa nikdy neosprchuje mozne riesenie ■ tabuľa pri vstupe do sprchy ■ host pri odchode zo sprchy zmaze z tabule oslo svojej izby a napíše na nu oslo nasledujucej izby (v nejakom fixovanom poradý) ■ kazdy hosť z casu na cas kontroluje, ci je na tabuli napýsane oslo jeho izby a ak ýano, osprchuje sa je to dobré riešenie? (prázdna izba, práve jedno sprchovanie v cykle, ...) IB110 Podzim 2010 221 Alternatívne výpočtové modely ^Súbežnost ^ ^ Distribuované súbežné systémy ■ (súbežné) komponenty systému sú fyzicky oddelené ■ komponenty vzájomne komunikujU ■ typicky od systemov nepožadujeme vstupno - výstupne chovanie, ale kontinuálnu (neprerusenu, neukončenu) funkcionalitu ■ doležite je chovanie systemu v case ■ okrem požiadavkov na jednotlive komponenty, kladieme na system globalne obmedzujuce podmienky ■ zdieľanie splocnych zdrojov ■ prevencia uviaznutia (vzajomne cakanie, deadlock) m prevencia starnutia procesov (starvation) (algoritmické) protokoly IB110 Podžim 2010 222 Alternatívne vypoCtová modely;>Sábeznost ^ ^ Problem vzajomneho vylúCenia žobecnenie problíemu hotelovej sprchy Problem vžajomneho vylíčenia: je danych N procesov, každy proces opakovane (v nekonečnom cykle) vykoníva ■ síkromne aktivity (proces ich môže vyznívat nežívisle na ostatnych procesoch) a ■ kritičke aktivity (žiadne dva procesy nemožu síčasne vykonavat svoje kritickíe aktivity) IB110 Podzim 2010 223 Alternatívne výpoCtová modely ;>Sábeznost ^ ^ Protokol pré problém vzajomného výlucénia pre dva procesy P1 a P2 protokol vyuzíva 3 premenne Z globalna premenna (vsetky procesy môžu menit jej hodnotu); nadobuda hodnoty 1 a 2 X1 lokalna premenna procesu P1; nadobuda hodnoty yes a no X2 lokalna premenna procesu P2; nadobuda hodnoty yes a no pociatocna hodnota premennych X1 a X2 je no, poáatocna hodnota Z je bud' 1 alebo 2 IB110 Podzim 2010 224 protokolvepré»problém vzajomnéno výlucénia (pré dva procésý) protokol pre proces P1 (1) opakuj v nekonecnom cýkle (1.1) výkonaj sukromne aktivitý (1.2) X1 — ýes (1.3) Z — 1 (1.4) cakaj kým bud' X2 nenadobudne hodnotu no alebo Z nenadobudne hodnotu 2 (1.5) výkonaj kritické aktivitý (1.6) X1 — no protokol pre proces P2 (1) opakuj v nekonecnom cýkle (1.1) výkonaj sýkromne aktivitý (1.2) X2 — ýes (1.3) Z — 2 (1.4) cakaj kým bud' X1 nenadobudne hodnotu no alebo Z nenadobudne hodnotu 1 (1.5) výkonaj kriticke aktivitý (1.6) X2 — no korektnost! protokolu vzájomne výlucenie OK starnutie procesu OK uviaZnutie OK IB110 Podzim 2010 225 Protokolvepre»problem vzajomneno vylúčenia (pre N procesov) protokol pre I-ty proces P\ (1) opakuj v nekonecnom cykle (1.1) vykonaj síukromníe aktivity (1.2) pre každe J od 1 do N — 1 urob (1.2.1) X[I] ^ J (1.2.2) Z[I] I (1.2.3) čakaj kym bud' X [K] < J pre nejake K = I alebo Z [J] = I (1.5) vykonaj kriticke aktivity (1.6) X [I ] ^ 0 IB110 Podzim 2010 226 Alternatívne výpoctove modely;>Sébeznost ^ ^ Vlastnosti distribuovaných sUbéZných sýstémov distribuovane síbeZne sýstemý sa odlisují od sekvencných sýstemov u nemôZeme pouZit! specifikaciu problemu prostredníctvom mnoZiný vstupných instancií a fukncnej zavislosti medzi vstupom a poZadovaným výstupom t nepostacuje dokaz konecnosti výpoctu a spravnosti vstupno-výstupneho vzťahu t nepostacuje výjadrenie efektivitý cez casovu (pocet krokov od začiatku do ukončenia) a priestoroví zloZitost aké vlastnosti požadujeme od súbežných procesov? IB110 Podzim 2010 227 Alternatívne výpočtové modely;>SábeZnost ^ ^ Vlastnosti živosti a bezpečnosti Vlastnosti, ktore požadujeme od protokolov pre súbežné procesy (najčastejšie) spadajú do dvoch kategórií: bežpeCnost a živost!. t nikdy nenastanú „spatne" udalosti resp. vždy sa stavajú len „dobre" udalosti určite „dobre" udalosti sa nakoniec stanú aby sme ukažali, že protokol porusuje vlastnost! bežpečnosti, stačí ukažat konkretnu postupnosť akcií, ktore vedú k žakážanej udalosti aby sme ukažali, že protokol porusuje vlastnosť živosti, musíme ukažat existenciu nekonecnej postupnosti akcií, ktore nevedú k požadovanej dobrej udalosti IB110 Podzim 2010 228 Alternatívne výpoctove modely;>Sábeznost ^ ^ Overovanie vlastností zivosti a bezpecnosti a mozu odhalit' chybu, ale nemozu dokízat platnosť pozadovanej vlastnosti; techniky suí jednoduchíe a matematickí metoda, ktorí dokaže platnosť pozadovanej vlastnosti; metída overovania modelov (model čhecking) narocne na implementaciu a samotne overenie vlastnosti; pre niektoríe systíemy je problíem nerozhodnutel'nyí IB110 Podzim 2010 229 Alternatívne výpoCtové modely;>Sébeznost ^ ^ Temporálna logika jazyk pre popis vlastnostýí sýubeoznýych systýemov formule logiky sa vyjadrujý o pravdivosti zýkladnych tvrdený v case (v priebehu vypočtu) zakladne konstrukcie: globalna platnost; (globally, G) a platnost; v buducnosti (future, F) príklady - protokol vzajomneho vylýcenia pre dva procesy P1-je-v-(1.4) F (P1-je-v-(1.5)) G (-[P1-je-v-(1.5) A P2-je-v-(1.5) ]) IB110 Podzim 2010 230 Alternatívne výpočtové modely;§=-Kvantové počítanie ^ ^ Alternatívne výpočtové modely Paralelizmus Kvantové počítanie Molekulárne počítan Nahodnostné algorit IB110 Podzim 2010 231 Alternatívne výpoctove modelý^Kvantove pocítanie ^ ^ Kvantové poďtanié zalozené na princípoch kvantovej mechaniky teoretickíy model: zíakladnou jednotkou reprezentaície informíacie je qubit, ktory (zjednodusene) moze nadobídat ľuboboľnó hodnotu z intervalu [0,1] kvantovíe algoritmy otízka konstrukcie kvantového pocítaca IB110 Podzim 2010 232 Alternatívne výpočtové modely^Molekulárne počítanie ^ ^ Alternatívne výpočtové modely ^Paralelizmus MKvantove počítanie 24 Molekularne počítanie HNahodnostné algoritmy IB110 Podzim 2010 233 Alternatívne vypoctove modely^Molekulárne pocítanie ^ ^ Molekularne (DNA) pocítanie ■ DNA == reťazce nad abededou A, C, T, G ■ vyvoj organizmu == manipulacia s retazcacmi: kopírovanie, rozdel'ovanie, spajanie ■ 1994: experiment, v ktorom pomocou manipulacie s molekulami bola vyriesena instancia problemu Hamiltonovskeho cyklu velkosti 7; experiment predstavoval niekoľko dní laboratórnej prace ■ pozitívum: vel'ka miera paralelizmu ■ negatívum: vel'ky objem biologickeho materialu potrebneho k rieseniu rozsiahlejsích instanci í buducnost: ??? IB110 Podzim 2010 234 Alternatívne vypoCtová modelyNáhodnostne algoritmy ^ ^ Altérnatívné výpoctové modélý Paralelizmus Subeznost Kvantove pocítanie Molekularne pocítanie Nahodnostne algoritmy IB110 Podzim 2010 235 Alternatívne výpoctove modelyNíhodnostne algoritmy ^ ^ nahodnostný protokol pre vecerajucich filoZofov IB110 Podzim 2010 236 Alternatívne výpoCtová modelyNáhodnostne algoritmy ^ ^ Porovnavanie reťazcov Na počítačoch A a B su uložene databažy x a y; nech x a y su binírne retažce dlžky n. Úlohou je rožhodnú1!, či x a y su žhodne. Zaujíma nas, kol'ko bitov si musia počítače A a B vymeniť, aby dokížali vyriesit problíem rovnosti. Dí sa dokažat, že neexistuje deterministicky komunikačny protokol, ktory by riesil problem rovnosti a pritom si A a B vymenili nanajvys n — 1 bitov. T.j. protokol, v ktorom A posle cely retažec x počítaču B je optimílny. IB110 Podzim 2010 237 Alternatívne výpočtové modelyNáhodnostné algoritmy ^ ^ Porovnávanie reťazcov Randomizovaný protokol pre problém rovnosti Vstup x = xiX2 ... xn, y = yiy2 ... y„ Krok 1 A vyberie náhodne prvočíslo p z intervalu [2, n2]. Krok 2 A vypočíta číslo s = x mod p a poSle čísla s, p počítaču B. Krok 3 B vypočíta číslo q = y mod p. Ak n = 1016, tak zlozitost deterministického protokolu je 1016, zatial' co zlozitost randomizovaného protokolu je 256. Pravděpodobnost, ze randomizovaný protokol vráti nesprávnu odopoved' Ak q = s, tak B vrati odpoved' x = y. Ak q = s, tak B vrati odpoved' x = y. n je < 0.36892 • 10-14. IB110 Podzim 2010 238 Alternatívne výpočtový modely Náhodnostne algoritmy ^ ^ Randomizovaný Quičksort Rand-Quicksort(A) Vstup žožnam prvkov A Krok 1 ak A ma jeden prvok, je utriedeny ak A ma viac prvkov, tak nahodne vyber prvok x ž A Krok 2 vytvor žožnam A< obsahujúci prvky ž A mensie než x vytvor žožnam A> obsahujúci prvky ž A väcsie než x Krok 3 vystup je Rand-Quicksort(A<), x, Rand-Quicksort(A>) ocakavana žložitost algoritmu je O(N log N) IB110 Podzim 2010 239 Alternatívne výpočtové modely^ Núhodnostné algoritmy ^ ^ Typy nahodnostnych algoritmov o s ohranicenou pravdepodobnostou je odpoved' nesprúvna príklad: randomizovany protokol pre problem rovnosti s odpoved' je vzdy spravna; ciel': ocakúvanú zlozitost Las Vegas algoritmu pre problem je lepsia nez zlozitosl! (deterministickeho) algorimtu príklad: randomizovany Quicksort IB110 Podžim 2010 240 Alternatívne vípoCtove modelyNíhodnostne algoritmy ^ ^ Náhodnostne zložitostne triedy Pravdepodobnostny Turingov stroj pracuje ako nedeterministicky TS s tym rozdielom, ze nedeterministický vyber kroku vypoctu interpretujeme ako nýhodnostný volbu Trieda RP obsahuje rozhodovacie problemy, pre ktore existuje polynomialne casovo ohraniceny pravdepodobnostny Turingov stroj s vlastnostou: ak odpoveďou pre vstup X je „Nie", tak s pravdepodobnostou 1 stroj da spraývnu odpoved ak odpovedou je „Ano", tak stroj s pravdepodobnostou > 1/2 dý yes. P C RP C NP náhodnostne algoritmy nemožu efektívne riesit problémy mimo NP; problémy z NP ale dokážu (často) riesit s väčšou efektivitou IB110 Podzim 2010 241