Problémy a algoritmy^Úvodne poznámky ^ ^ Problémy a algoritmy Úvodne poznámky Pi Pr IB110 Podzim 2010 1 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 2 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 3 Problémy a algoritmy^Úvodné poznémky ^ ^ Čo jé informatika (Computér Sciéncé)? previadajúce nazory ■ rozdielne schopnosti popúiacie v praci 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 4 Problémy a algoritmy^Úvodne poznámky ^ ^ základné pojmy problém a algoritmus IB110 Podzim 2010 5 Problémy a algoritmy^Problémy a algoritmy ^ ^ Problémy a algoritmy Úvodne poznámky Problémy a algoritmy Programovacie jazyky IB110 Podzim 2010 6 Problémy a algoritmy^Problémy a algoritmy ^ ^ Problém co je problém? IB110 Podzim 2010 7 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 7 Problémy a algoritmy^Problémy a algoritmy ^ ^ Riešenie problému Metoda riešenia problému popisuje efektívnu cestu, ktora vedie k nájdeniu požadovaných výstupov. Popis pozostáva z postupnosti inštrukcií, ktore môže ktokoľvek realizoval!. existencia metódý riesenia problemu znamena možnost! výpoCítat riesenie automaticky v danom kontexte hovoríme o algoritme pre riesenie problemu IB110 Podzim 2010 8 Problémy a algoritmy^Problémy 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 9 Problémy a algoritmy^Problémy a algoritmy ^ ^ Algoritmus — historický pohľad II ■ Kurt Godel (1931) dokázal, ze (a) neexistuje Žiadna Úplná (rozumná) matematická teoria; v každej korektnej a dostatoCne veľkej teorii je možne formulovat tvrdenia, ktore nieje možne vnútri tejto teórie dokazat. Aby bolo možne dokózat spravnost týchto tvrdení, je nutne k teórii pridal: nove axiomy a vybudovať 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 možné dokazat 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) ďalšie definície a ich ekvivalencia IB110 Podzim 2010 10 Problémy a algoritmy^Probiemy a algoritmy ^ ^ Základné otazky Existuju probiemy, ktore nie su rieSitel'ne automaticky (algoritmicky)? Ak ano, ktore probiemy sá algoritmicky riesitel'ne a ktore nie? IB110 Podzim 2010 11 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Problémy a algoritmy Ú Pr ^| Programovacie jazyky a paradigmata IB110 Podzim 2010 12 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 13 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Programovacie jazyky II ako prezentoval! algoritmus reúlnemu poCítaCu? ako "prinútil!" poCítaC, aby realizoval vypoCet tak, ako sme to zamýšľali? programatori sú l'udia, uvazují abstraktne a vyjadrujU sa pomoCou slov a symbolov poCítaCe sú stroje, ktore dokazu realizovat! vel'mi jednoduChe ulohy programovaCie jazyky pomúhaju l'ud'om komunikovat! s poCítaCmi IB110 Podzim 2010 14 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Vývojové diágrámy IB110 Podzim 2010 15 Problémy a algoritmy^Prograrnovacie jazyky a paradigmata ^ ^ Programovací jazyk vyššej úrovne jazyk pre popis algoritmov zíakladníe stavebníe kamene ■ riadiace struktury ■ datove struktííry IB110 Podzim 2010 16 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 17 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Dátové typy Dátové typy ■ premenne ■ vektory, zoznamy ■ polia, tabulky ■ zásobníky a fronty ■ stromy a hierarchie IB110 Podzim 2010 18 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Datové typy Vlastnosti programovacích jazykov ■ presná syntax ■ presna semantika IB110 Podzim 2010 19 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Dátové typy 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 IB110 Podzim 2010 20 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Datové typy Syntax - príklad ■ hypotetiCky programovad jazyk 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 21 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Datové typy Definícia syntaxe - syntaktické diagramy IB110 Podzim 2010 22 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Datove typy Definícia syntaxe — BNF (príkaz) ::= (for príkaz) | (priraďovací príkaz) | ... (for príkaz) ::= (premenná) from (hodnota) to (hodnota) BNF umoznuje generoval; (syntakticky spravne) programy IB110 Podzim 2010 23 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Datové typy Kontrola syntaktických chýb program sa neda vygeneroval! pouzitám BNF automatizovany proces IB110 Podzim 2010 24 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Datové 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 ??? ■ presná semantika je nevýhnutna !!! ■ manual (dokumentacia) ako definícia semantiký ??? IB110 Podzim 2010 25 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Datové typy Sémantika - príklad Príklad procedúra P (s parametron V) (1) call V (s parametrom V), výsledok úlož 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 odpoveď IB110 Podzim 2010 26 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Prekladače a intérprétry VypoCét programu ■ od programu v jazyku vyssej urovne k manipulaCii s bitmi ■ program je postupne transformovany na strojovu uroveň ■ transformaCia ■ kompilaCia ■ interpretada ■ kombinovany prístup IB110 Podzim 2010 27 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Prekladače a interpretry 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 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 cyklu JMP LOOP prekladaC IB110 Podzim 2010 28 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Prekladače a intérprétry Kompilácia - pokr. ■ preklad z jazýka symbolických adries do strojoveho kodu ■ assembler Optimalizacia kodu pocas kompilacie IB110 Podzim 2010 29 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Prekladače a interpretry Interpretácia ■ interpreter postupuje príkaz po príkaze ■ kaZdý príkaz je okamZite preloZený do strojoveho kodu a vykonaný MoZnost lepSie sledoval! výpočet. Typicky jednoducha tvorba interpretru. NemoZnost optimalizacii. IB110 Podzim 2010 30 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata Programovacie esperanto ■ preco rozne programovacie jazyky? ■ programovací jayzk poskytuje programatorovi istu uroven abstrakcie ■ potreba novych typov abstrakcií ■ vyvoj hardwaru (paralelné počítače a programovanie vo vláknach) ■ nove aplikacne oblasti (mulimediélne aplikécie) m paradigmata - kategorizacia existujucich programovacích jazykov IB110 Podzim 2010 31 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata imperatívne programovanie ■ prístup blízky l'udskemu uvaZovaniu ■ imperatívne programovanie popisuje vypocet pomocou postupnosti príkazov a urcuje presny postup, ako dany algoritmicky problem riesiť ■ pamat pocítaca je suborom pamatovych miest organizovaných do rôznych datovych struktur ■ program buduje, prechadza a modifikuje datove struktury tak, ze nacíta dáta a mení hodnoty ulozene v pamäti ■ príkazy, v zavislosti na vyhodnotení podmienok, menia stav premennych ■ historicky najstarsie imperatívne programovacie jazyky: strojove jazyky ■ FORTRAN, ALGOL, COBOL, BASIC, Pascal, C, Ada ■ zakladne typy príkazov - priradenie, cykly, príkazy vetvenia IB110 Podzim 2010 32 Problémy a algoritmy^Programovacié jazyky a paradigmata ^ ^ Paradigmata Funkcionálně programovanie ■ vypoctom funkcionalneho programuje postupnost vzajomne ekvivalentných vyrazov, ktore sa postupne zjednodusuju ■ vysledkom vypoctu je vyraz v normalnej forme, ktory sa neda d'alej zjednodusit ■ program je chapany ako jedna funkcia, ktora obsahuje vstupne parametry. Vypocet je vyhodnotením tejto funkcie. ■ imperatívny prístup: ako sa ma vypocítat funkcionalny prístup: ôo sa ma vypocítat ■ Erlang, Haskell, Lisp, ML, Ozx, Scheme IB110 Podzim 2010 33 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata Logické programovanie ■ postavene na pouZití matematickej logiky ■ logicky program je tvoreny sadou pravidiel a jednoduchych logickych tvrdení ■ dotaz sa riesi prehl'adavaním mnoZiny pravidiel. Hl'ada sa dokaz, ktory poskytuje odpoved' na zadany dotaz IB110 Podzim 2010 34 Problémy a algoritmy^Programovacie jazyky a paradigmata ^ ^ Paradigmata Objektovo orientované programovanie ■ pamat poC ítaCa pozostava z objektov ■ s kazdym 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 realizaciu operaci í a odpovede ■ Smalltalk, Java, C++, Python, Ruby. Lisp IB110 Podzim 2010 35