Pocitace a Algoritmizacia, suhrn vsetkeho co treba vediet na skusku

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,CSMP<MaHab/Simulink)
---------------------------------------------------------------------

2.3   VYVOJOVE DIAGRAMY   ->VD

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-xi