PaA. 1.2 HARVARDSKA ARCHITEKTURA - Pocitace s HA maju oddeleny adresovy priestir pre program a pre udaje. => situacia, aby program pisal sam od seba nemoze nastat. -tato architektura sa v sucastnosi pouziva pri niektorych JDNOCIPOVYCH MIKROPOCITACOCH. (jednocipovy mikropocitac -> vsetky strukturne prvky-procesor + pamat + I/O obvody -> su integrovane na jedinom polovodicovom cipe) - Procesor pouziva na adresaciu obidvoch pamati a na prenos udajov a instrukcii spolocne adresovane a udajove vodice. Rozlisenie medzi pristupom k pamati programu a k pamati udajov -> aktivaciou odlisnych riadiacich signalov. 1.3 POCITACE RIADENE TOKOM UDAJOV. (data-flow systemy) -Tieto pocitace nevykonavaju instrukcie postupne za sebou, tak ako su ulozene v pamati, vykona sa ta instrukcia, ktora ma pripravene udaje. - Ak ma, viac instrukcii pripravene udaje vykonaju sa paralelne -> ide o paralelne viacprocesorove pocitace. 2. POSTUP RIESENIA ULOHY NA POCITACI 2.1 Hlavne etapy postupu riesenia 1. Formulacia ulohy ~ definicia problemu 2. Analyza ulohy ~ navrh riesenia 3 Najdenie ALGORITMU vypoctu ~ zostavenie algoritmu 4. Overenie spravnosti algoritmu 5.Kodovanie programu a preklad 6. Overenie spravnosti programu ~ ladenie programu Pozn. Etapy 1-4 --> cvicenia dodrzia dany postup, ->priklady na samostatne riesenie, ->priklady na zadania pocas semestra, ->priklady na skusku (pisomna cast) ---------------------------------------------------------------------- 1.Formulacia ulohy ~ definicia problemu. --> definovat, co mame riesit --> podla zlozitosti problemu moze byt definicia problemu, SLOVNA alebo vyuzitim FORMALNEHO APARATU. ->formulacia ulohy,ktoru chceme riesit na pocitaci --> je jej uprava na taky tvar, ktory je vhodny pre pocitac. Formulacia ma splnat nasledujuce,podmienky: a)diskretnost udajov a operacii (+,-,*,/) b)konecnost udajov a operacii(pocet operacii je konecny) c)obmedzenia dane pocitacom 2. Analyza ulohy ~ navrh riesenia -> vykonavat dokladny rozbor ulohy(problem) ->specifikovat VSTUPY (struktura,formatovat mnozinu pristupnych dat) -> specifikovat VYSTUP ( struktura,format, funkcna zavislost na vstupnych hodnot dat) -> navrh riesenia obsahuje vyber metody dekompoziciu ulohy na ciastkove problemy 3.Najdenie algoritmu vypoctu ~ ALGORITMIZACIA Realizacia ulohy na pocitaci predpoklada poznat presny postup vypoctu ~ ALGORITMUS. ALGORITMUS --> je presny predpis definujuci vypoctovy proces, ktory vedie od menitelnych vychodzich udajov az k spravnym odpovedajucim vysledkom (MARKOV) Algoritmus sa sklada z jednolivych vypoctovych krokov, ktore su zapisane v presne urcenom poradi, ich pocet musi byt konecny. Kazdny algoritmus ma tri zakladane vlstnosti: ->Hromadnost - algoritmus definuje vypocet celej triedy uloh rovnakeho typu,pricom sa lisia od seba vstupnymi udajmi. ->Determinovanost - t.j. algoritmus je presny a jednoznacny -> vzdy je urceny nasledujuci krok jednoznacnym sposobom. Vypocet sa da vzdy opakovat -> pre rovnake vstupne udaje dostaneme vzdy rovnaky vysledok. -> Rezultativnost - udava, ze pre pripustne vstupne hodnoty ziskame vysledok po konecnom pocte vypoctovych krokov. Najdenie algoritmu riesiaceho dany problem, nazyvame ALGORITMIZACIA. pri algoritmizacii sa vyzaduje schopnostlogickeho myslenia. Pozn. Pojem ALGORITMUS pochadza od arabskeho matematika M.M Abdullah al Chorezmiho (8-9 st. n.l.) ->uzbekistan ->Traktat o vypoctoch v decimalnej pozicnej sustave. Vstup pojmu algoritmus do novodobej terminologie zaznamenala monograficka ruskeho matematika MARKOVA: Teoria algoritmov. Neformalne vymedzenie pojmu algoritmus: -> 1) mat problem, ktory chceme riesit : a) presne definovany, b) v priebehu riesenia nemenny c) rozpoznatelne riesenie -> 2) mat nastroj na riesenie problemu: a) nehmotny - matematicky aparat b) hmotny - pocitac 4.Overovanie spravnosti algoritmus Spociva v otestovani algoritmu na vhodnej mnozine vstupnych udajov. Vhodnym prostriedkom pre testovanie spravnosti je simulacna tabulka. 5. Kodovanie programu a preklad predstavuje prepis algoritmu do programovacieho zajyka (c-jazyk) ->Program v prislusnom jazyku nazyvame zdrojovy program; ktory tvori vstup pre prekladac (kompilator) -> Kompilator - subor programov pre pocitac, ktory prijima ako vstupne data programu v problemovo-orientovanom jazyku a ako vystup vytvara pocitacovo-orientovany kod;(lexikalna analyza,syntakticka analyza) odstranenie formalnych chyb ALGORITMUS VS PROGRAM Program = postupnost prikazov (chraneny autor. zakonom) L vypis programu algoritmus = postup prace(vypis - zapis algoritmu) L da sa patentovat Program realizuje algoritmus(algoritmy), algoritmus je jeho nutnou sucastou. 6. Overovanie spravnosti programu(a algoritmu) --> spociva v testovani programu na vhodnej mnozine vstupnych udajov, pre ktore pozname vysledky. (ladenie programu -> odstanenie logickych chyb)-> ladiace prostriedky(debuger) -> umoznuju sledovat priebeh vypoctu s medzivysledkami. 2.2 ALGORITMICKE JAZYKY -> pouzitie ludskej reci k jednoznacnemu a presnemu vyjadreniu algoritmu ->> v praxi robi problemy -> -> pre popis algoritmov(vypoctovych) boli vyvinute jazyky urcene k vyjadrovaniu vymedzeneho okruhu vybranych cinnosti Algoritmicke jazyky -> predstavuju suhrn prostriedkov a pravidiel, ktore umoznuju vyjadrovat vypoctove algoritmy a)Vyvojove diagramy; b)Strukturogramy; c)Rozhodovacie tabulky; d)Programovacie jazyky. a)Vyvojove diagramy-> predstavuju normau definovane symbolicke znacky a pravidla pre ich pouzivanie, ktore sluzia pre jednoznacne graficke vyjadrovanie vypoctovych operacii a postupov. -VD -> zobrazujeme postupnost krokov riesenia ulohy-> popis algoritmu ^ podklad pre zostavenie programu pre pocitac --> podrobnejsie dalej b)Strukturogram -> obdoba VD -> ni su definovane normou. Predstavovali pokus "zhutnit" graficku interpretaciu vypoctoveho postupu. Neujali sa v praxi -> prakticke vyuzitie bezvyznamne. c)Rozhodovacie tabulky-> boli definovane pre algoritmizaciu uloh so zlozitym rozhodavanim v oblasti hromadneho spracovania udajov. !d)Programovacie jazyky -> su dosledne formalizovane algoritmicke jazyky, urcene pre zapis algoritmu pre pocitac Zapis algoritmu v programovacom jazyku = PROGRAM Programovaci jazyk vyhovuje vzdy urcitym pravopisnym (syntaktickym) pravidlam s dopredu dohodnutym vyznamom (semantikou). /assemblery / Pocitacovo-orientovane< PROGRAMOVACIE jazyky < \strojovy kod \ makroprogramovacie ^ / \ (autokody) (vyssie programovacie jazyky) C-jazyk,Pascal, | | V Simulacne prog. jazyky [matlab,Simulink,...] [predmet]->simulacne <__________| systemy Vyssie programovacie jazyky -> vyrazne preparacovana syntax a semantika; ->zahrnuju v sebe zlozite programovane konstrukcie(struktury a objekty). ->koli vseobecnosti nie si tieto jazyky viazane na konkretny typ pocitaca. (jeben prikaz ~ 4-10 strojovym instrukciam) -vyvoj : prirodne vedy -> fortran,Algol 60) hromadnych udajov (RPG,COBOL)->zobecnenie(PL/1,Algol68,ada) programovacie jazyky vys. typu(Pascal-vyuka programovania,strukturovane programovanie, DELPHI,C,C++ | |___>objektove programovanie | (Systemove a aplikacny softver) Simulacne jazyky(SIMULA,CSMPVD VD--> je symbolicky algoritmicky jazyk,ktory sa pouziva pre nazorne zobrazenie algoritmu, t.j. znazornuje logicku stavku programu pre system spracovania informacii(tok udajov) Tento jazyk je tvoreni: -Znackami s presnym vyznamom (semantika ~slovnik) -Pravidlami ako znacky pouzivat vo vzajomnej suvislosti(syntax-gramatika) VD predstavuje graficke znazornenie logickej struktury rieseneho problemu. VD: a) VD riesi problem vo vseobecnej rovine bez zretela na vlastnosi pocitaca a program. jazyka b) VD riesi problem-> priamy vztah k pocitacu a klavne k moznostiam a vlastnostiam prog. jazyka. 2.3.1 SYMBOLY VYVOJOVYCH DIAGRAMOV 3. METODY ALGORITMIZACIE a ZAKLADNE ZLOZKY ALGORITMU 3.1 Metody algoritmizacie metoda "zdola nahor" metoda "zhora nadol" metoda "zhora nadol"->> Algoritmus je zapis postupu ktory je pouzitelny pre riesenie urcitej triedy problemov --> ak postup riesenia rozkladame na jednoduchsie operacie, az dospejeme k elementarnym krokom --> potom tento postup navrhu nazyvame metoda ZHORA NADOL.... Priklad: Kvadraticka rovnica -> budeme chciet na zaklade navrhnuteho algoritmu napisat program, ktory bude riesit rovnice, ktorych koeficienty su ulozene v subore A. Vysledok sa ma ulozit do suboru B. Najhrubsia formulacia moze mat tvar: Pokial nenarazite na KONIEC SUBORU A, rieste rovnice, urcene koeficientami ulozenymi v subore A a vysledky zapisujete do suboru B | V je nutne upresnit vyznam: "Rieste rovnice,urcene..."->rozklad na jednoduchsie koky: ALGORITMUS RUBEHO RIESENIA: 1)Vykonajuvodne operacie 2)pokial nenarazis na koniec suboru A,opakuj kroky 3-5,potom prejdi na krok 6. 3)precitaj zo suboru koefiicenty a,b,c 4Vyries kvadraticku rovnicu s koeficientmi a,b,c 5)zapis vysledok do suboru do B a vrat sa na krok 2. 6)vykonaj zaverecne operacie. kroky 1,4,6 sa daju sprasnit. 1,6 si spravime sami... Budeme sa zaoberat iba krok 4 na riesenie KR. 4a. Vypocitaj d=b^2-4ac 4b. Ak je d<0 pokracuj bodom 4f,inak pokracuj bodom 4c. ___ 4c. prirad d=V d 4d. Rovnica ma korene x1,2 = -b+-d/2a 4e. Pokracuj krokom 5. _____ 4f. Prirad d=V -d 4g.Rovnica ma korene x1,2 =-b+-id/2a i je imaginarna jednotka.. poz. upresnit postup,ak nastane chyba pri otvoreni suboru, pripadne obsahuje chybne udaje, ... format vstupnych a vystupnych udajov... Metoda "zdola nahor": postupujeme od elementarnych krokov --> vytvarame prostriedky,ktore umoznia vyriesit dany problem. Hybridna metoda --> kombinacia predoslich dvoch metod.(vytvaranie programov CASE) 3.2 Zakladne zlozky algoritmov --> zakladne riadiace struktury. V algoritmoch sa stretavame s troma zakladnymi konstrukciami, ktore oznacujeme: -POSTUPNOST(sekvencia) -VETVENIE(selekcia) -CYKLUS(iteracia) POSTUPNOST--> najjednoduchsia riadiaca struktura. Je tvorena jednym alebo niekolkymi krokmi, ktore sa vykonaju prave raz v danom poradi. So sekvenciou sa stretavame pri globalnom popise algoritmu --> pri upresneni --> zlozitejsie konstrukcie! VETVENIE --> je taka struktura,ktora v procese vykonavania algoritmu umoznuje vyberat rozne alternativy riesenia podla splnenia ci nesplnenia zadanych podmienok. a)preskok b) dvojcestne vetvenie c) prepinac - modifikacia viaccestneho vetvenia(je kazda vetva urcena na konkretnu hodnotu vyrazu uvedeneho v podmienke. CYKLY(iteracie)-->predstavuju cast algoritmu, ktora sa opakuje pokial je splnena podmienka opakovania. Cyklus sa sklada Z a) podmienky opakovania b) tela cyklu Pocet opakovani tela cyklu mozebyt dopredu zadany alebo jeodvodeny od splnenia podmienky. => a) cyklus s podmienkou na zaciatku (prikazy jazyka C: while , for) b) cyklus s podmienkou na konci =aritmeticky cyklus (prikaz jazyka C: do-while) c) cyklus s danym poctom opakovani =aritmeticky cyklus (prikaz jazyka c :for) a),b) su logicke cykly V priklade riesenia kvadratickej rovnicetvoria kroky 2-5 cyklus s podmienkou na zaciatku. Cyklus s podmienkou na zaciatku : 1, vyhodnotenie podmienky P 2, ak je splnena vykonajusa operacie dane strukturou Sa nasleduje navrat na zaciatku cyklu 3, ak podmienka nie je splnena cyklus sa ukonci Cyklus s podmienkou na konci : 1, cyklus zacinasvoju cinnost operaciami v sekvencii S 2, ak podmienka P je splnena navrat na bod 1 3, ak podmienka p nieje splnena vykonavanie cyklu je ukoncene Cyklus s danym poctom opakovani: a) aritmeticky cyklus (for) b) logicky cyklus (while)-obmena na system prace cyklu for 4.PREDNASKA ~~~~~~~~~~~~ Priklady zapisu algoritmov pomocou vyvojovych diagramov s vyuzitim riadiacich struktur: 1. Vypocitaj sucet cisel, ktorych pocet v subore je znamy. 2. Vypocet Aritmetickeho priemeru cisel zo suboru ukonceneho -99 __ 3. Vypocete druhej odmocniny x= v a kde a>0 podla Newtonovho iteracneho vzorca xi+1=1/2(xi + a/xi) i= 0,1,2....n xi su hodnoty postupnosti kt sa postupne priblizuju k hladanemu rieseniu. Vysledok urcte s presnostou E , tj. vypocet sa ma vykonat dovtedy,pokial nie je splnena podmienka |xi+1-xifile downloaded from nechodimnapprednasky.sk!