Problémy, algoritmy a programovacie jazyky IB110 1 / 29 Algoritmický problém Problém čo je problém? 2/29 Algoritmický problém Problém čo je problém"; výpočtový problém • (nekonečná) množina vstupných inštancií prípustné vstupy • špecifikácia požadovaných výstupov funkcia vstupných inštancií 2/29 Algoritmický problém Riešenie problému Metóda riešenia problému popisuje efektívnu cestu, ktorá vedie k nájdeniu požadovaných výstupov. Popis pozostáva z postupnosti inštrukcií, ktoré môže ktokoľvek realizovať. existencia metódy riešenia problému znamená možnosť vypočítať riešenie automaticky v danom kontexte hovoríme o algoritme pre riešenie problému 3/29 Algoritmus — historický pohľad I koniec 19. storočia, priemyslová revolúcia, kauzálne chápanie sveta, zákony umožňujúce úplné pochopenie sveta program Davida Hilberta (a) celá matematika sa dá vybudovať z konečnej sady vhodných axióm (b) matematika vytvorená týmto spôsobom je kompletná v tom zmysle, že každé tvrdenie vyjádřitelné v jazyku matematiky sa dá dokázať alebo vyvrátiť v tejto teórii (z danej sady axiómov) (c) existuje metóda pre dokázanie resp. vyvrátenie každého tvrdenia. kľúčový pojem metódy Algoritmus — historický pohľad II • Kurt Gödel (1931) dokázal, že (a) neexistuje žiadna úplná (rozumná) matematická teória; v každej korektnej a dostatočne veíkej teórii je možné formulovať tvrdenia, ktoré nieje možné vnútri tejto teórie dokázať. Aby bolo možné dokázať správnosť týchto tvrdení, je nutné k teórii pridať nové axiómy a vybudovať tak novú, väčšiu teóriu (b) neexistuje metóda (algoritmus) pre dokazovanie matematických teorém • pre svoj dôkaz potreboval presnú definíciu pojmu metóda (algoritmus) (nie je možné dokázat neexistenciu algoritmu bez rigoróznej definície toho čo je a čo nieje algoritmus) • prvá formálna definícia pojmu algoritmu: Alan Turing (1936) • ďalšie definície a ich ekvivalencia Algoritmy Základné otázky Existujú problémy, ktoré nie sú riešiteľné automaticky (algoritmicky)? Ak áno, ktoré problémy sú algoritmicky riešiteľné a ktoré nie? 6/29 Programovacie jazyky Programovacie jazyky I • algoritmy musia byť zapísané jednoznačne a formálne • programovací jazyk -jazyk pre špecifikáciu algoritmov • program - zápis algoritmu v programovacom jazyku • strojový kód vs. programovací jazyk vyššej úrovne 7/29 Programovacie jazyky Programovacie jazyky II • ako prezentovať algoritmus reálnemu počítaču? • ako "prinútiť" počítač, aby realizoval výpočet tak, ako sme to zamýšľali? • programátori sú ľudia, uvažujú abstraktne a vyjadrujú sa pomocou slov a symbolov • počítače sú stroje, ktoré dokážu realizovať veľmi jednoduché úlohy • programovacie jazyky pomáhajú ľuďom komunikovať s počítačmi 8/29 Programovacie jazyky Vývojové diagramy 9/29 Programovacie jazyky Programovací jazyk vyššej úrovne jazyk pre popis algoritmov základné stavebné kamene • riadiace štruktúry • dátové štruktúry 10 / 29 Programovacie jazyky Riadiace štruktúry • postupnosť príkazov • podmienené vetvenie • ohraničená iterácia • podmienená iterácia kombinácia riadiacich štruktúr - vnorenie 11 / 29 Dátové typy • premenne • vektory, zoznamy • polia, tabuľky • zásobníky a fronty • stromy a hierarchie Programovacie jazyky 12 / 29 Programovacie jazyky Vlastnosti programovacích jazykov • presná syntax • presná sémantika 13 / 29 Programovacie jazyky Syntax • nejednoznačnosti; presný význam pre pojmy, ktoré sa používajú v bežnej komunikácii • Porovnanie "=" a priradenie "=" Java if (x==y) z = 3; else z = 4; FORTRAN IF (X .EQ. Y) THEN Z = 3 ELSE Z = 4 END FI Pascal if x = y then z := 3 else z:= 4 14 / 29 Programovacie jazyky Syntax - príklad • hypotetický programovací jazyk PL Príklad i input/V; 2 X :=0; 3 for Y from 1 to N do 4 X:=X+Y 5 od 6 OUtputX. 15 / 29 Programovacie jazyky Definícia syntaxe - syntaktické diagramy 16 / 29 Programovacie jazyky Definícia syntaxe — BNF (príkaz) ::= (for príkaz) | (priraďovací príkaz) | ... (for príkaz) ::= (premenná) from (hodnota) to {hodnota) BNF umožňuje generovať (syntakticky správne) programy 17 / 29 Programovacie jazyky Kontrola syntaktických chýb • program sa nedá vygenerovať použitím BNF • automatizovaný proces 18 / 29 Programovacie jazyky Sémantika for Y from 1 to N do • význam — odčítanie, príkaz pre tlačiareň, dnes je pekný deň 111 9 význam podľa použitých slov 111 • čo ak N = 3.14 111 • presná sémantika je nevyhnutná M! • manuál (dokumentácia) ako definícia sémantiky 111 19 / 29 Programovacie jazyky Sémantika - príklad Príklad procedúra P (s parametron V) (1) call V (s parametrom V), výsledok ulož do X (2) if X = 1 then return 0; else return 1 • procedúra, ktorá má ako svoj parameter názov procedúry • syntaktická korektnosť • call P(s parametrom P) - aká je návratová hodnota? • sémantika musí dať jednoznačnú odpoveď 20 / 29 Programovacie jazyky Výpočet programu • od programu v jazyku vyššej úrovne k manipulácii s bitmi • program je postupne transformovaný na strojovú úroveň • transformácia • kompilácia • interpretácia • kombinovaný prístup 21 / 29 Programovacie jazyky Kompilácia • program v jazyku vyššej úrovne je preložený do jazyka nižšej úrovne (jazyk symbolických adries) for Y from 1 to N do telo cyklu od LOOP: MOVE 0, Y CMP N, Y JEQ REST ADD 1, Y telo cyklu JMP LOOP do registra Y ulož 0 porovnaj hodnoty uložené v N a Y ak rovnosi, tak pokračuj príkazom REST pripočítaj 1 k Y prekladač 22 / 29 Programovacie jazyky Kompilácia - pokr. • preklad z jazyka symbolických adries do strojového kódu • assembler Optimalizácia kódu počas kompilácie 23 / 29 Programovacie jazyky Interpretácia • interpreter postupuje príkaz po príkaze • každý príkaz je okamžite preložený do strojového kódu a vykonaný Možnosť lepšie sledovať výpočet. Typicky jednoduchá tvorba interpretru. Nemožnosť optimalizácii. 24 / 29 Programovacie jazyky Programovacie esperanto • prečo rôzne programovacie jazyky? • programovací jayzk poskytuje programátorovi istú úroveň abstrakcie • potreba nových typov abstrakcií • vývoj hardwaru (paralelné počítače a programovanie vo vláknach) • nové aplikačné oblasti (mulimediálne aplikácie) • paradigmata - kategorizácia existujúcich programovacích jazykov 25 / 29 Programovacie jazyky Imperatívne programovanie • prístup blízky ľudskému uvažovaniu • imperatívne programovanie popisuje výpočet pomocou postupnosti príkazov a určuje presný postup, ako daný algoritmický problém riešiť • pamäť počítača je súborom pamäťových miest organizovaných do rôznych dátových štruktúr • program buduje, prechádza a modifikuje dátové štruktúry tak, že načíta dáta a mení hodnoty uložené v pamäti • príkazy, v závislosti na vyhodnotení podmienok, menia stav premenných • historicky najstaršie imperatívne programovacie jazyky: strojové jazyky • FORTRAN, ALGOL, COBOL, BASIC, Pascal, C, Ada • základné typy príkazov - priradenie, cykly, príkazy vetvenia 26 / 29 Programovacie jazyky Funkcionálně programovanie • výpočtom funkcionálneho programu je postupnosť vzájomne ekvivalentných výrazov, ktoré sa postupne zjednodušujú • výsledkom výpočtu je výraz v normálnej forme, ktorý sa nedá ďalej zjednodušiť • program je chápaný ako jedna funkcia, ktorá obsahuje vstupné parametry. Výpočet je vyhodnotením tejto funkcie. • imperatívny prístup: ako sa má vypočítať funkcionálny prístup: čo sa má vypočítať • Erlang, Haskell, Lisp, ML, Ozx, Scheme 27 / 29 Programovacie jazyky Logické programovanie • postavené na použití matematickej logiky • logický program je tvorený sadou pravidiel a jednoduchých logických tvrdení • dotaz sa rieši prehľadávaním množiny pravidiel. Hľadá sa dôkaz, ktorý poskytuje odpoveď na zadaný dotaz 28 / 29 Programovacie jazyky Objektovo orientované programovanie • pamäť počítača pozostáva z objektov • s každým objektom sú asociované operácie, ktoré môže objekt poskytovať (prístupné ako metódy volania) • program je súborom objektov, ktoré si posielajú správy obsahujúce požiadavky na realizáciu operácií a odpovede • Smalltalk, Java, C++, Python, Ruby. Lisp 29 / 29