1. Algoritmus, Etapy tvorby programov. Algoritmické konštrukcie.
Algoritmus, vlastnosti algoritmu, spôsoby zápisu algoritmu, základné algoritmické konštrukcie
Etapy. Program, príkazy, premenná, konštanta, výraz, identifikátor, elementárne príkazy.
Algoritmus – postup alebo návod ako riešiť zadanú úlohu. Ide o presne stanovený postup ktorý
niekomu adresujeme (vykonávateľovi). V informatickej terminológii je adresátom procesor.
Algoritmus je postup, ktorého realizáciou získame zo zadaných vstupných údajov po konečnom
počte činností v konečnom čase správne výsledky.
Vlastnosti algoritmu:
 Elementárnosť – postup je zložený z jednoduchých krokov, ktoré sú pre vykonávateľa (človek,
procesor, nemysliace zariadenie) zrozumiteľné
 Determinovanosť (jednoznačnosť) - postup je zostavený tak, že v každom momente jeho
vykonávania je jednoznačne určené, aká činnosť má nasledovať, alebo či sa už postup skončil.
 Rezultatívnosť (opakovateľnosť) – postup dáva pre rovnaké vstupné údaje vždy rovnaké
výsledky.
 Konečnosť – postup skončí vždy v konečnom čase a po vykonaní konečného počtu činností.
 Hromadnosť (všeobecnosť) – postup je použiteľný na celú triedu prípustných vstupných
údajov. Algoritmus nepočíta 1 + 2 = 3, ale a + b = c.
 Efektívnosť – postup sa uskutočňuje v čo najkratšom čase a s využitím čo najmenšieho
množstva prostriedkov (príkazy, pamäť). (Ako kritériá efektívnosti slúžia časová a pamäťová
zložitosť algoritmu.)
V praxi sa doporučuje dodržiavať ešte dve ďalšie vlastnosti:
 zrozumiteľnosť a
 prehľadnosť algoritmu.
Zápis algoritmov:
 matematicky (vzťahom medzi veličinami, sústavou rovníc, maticami), rozhodovacie tabuľky
 graficky (vývojový diagram, štruktúrogram )
 slovne – v jazyku (prirodzenom alebo algoritmickom) alebo programovacím jazykom
(obrázkový - Baltík, Logo - Imagine, Pascal – TurboPascal, Lazarus, Delphi; ďalšie jazyky: C,
C++, C #, Java, PHP, ...)
Vývojový diagram – popisuje postupnosť činností pomocou normou definovaných grafických
značiek a textu v nich.
Štruktúrogram – zhustená obdoba vývojových diagramov, ktorá však nie je definovaná normou.
Základné značky používané vo vývojových diagramoch:
- počiatočná a koncová značka (medzná značka)
- vstup a výstup hodnôt
- priradenia; vykonanie [spracovanie (príkaz, operácia činnosť)]
- porovnanie, rozhodovanie a vetvenie
- poznámka, komentár
- spojka
značky spájame spojnicami, šípka musí byť ak
...
Základné algoritmické konštrukcie
1. sekvencia – postupnosť príkazov
2. vetvenie – členenie algoritmu na základe podmienky
1
3. cyklus – viacnásobné opakovanie časti algoritmu na základe podmienky (telo cyklu je to, čo sa
má opakovať, dokedy sa to má opakovať, to určuje podmienka cyklu)
začiatok
začiatok
príkaz 1
začiatok
vstup
príkaz 1
1
podmienka
príkaz 2
podmienka
koniec
......
príkaz n
príkaz 1
príkaz 2
vstup
koniec
príkaz 2
výstup
koniec
Etapy tvorby programov:
1. Zadanie úlohy a presné vymedzenie problému. Rozbor problému (čo ideme riešiť, presne
sformulujeme zadanie problému a samozrejme aj požiadavky kladené na program). Výsledkom
rozboru je popis vstupných a výstupných informácií a vzťahov medzi nimi.
2. Navrhneme postup riešenia – vytvoríme algoritmus – všeobecný zápis návodu riešenia (ako
riešiť, metódy a spôsoby riešenia). Výsledkom návrhu riešenia je zápis jednotlivých krokov
(príkazov) algoritmu a to buď v algoritmickom jazyku alebo graficky pomocou vývojového
diagramu alebo štruktúrogramu. Ak sa vyskytnú viaceré možnosti riešenia, snažíme sa zistiť,
ktorý je najefektívnejší. Pokúšame sa odhadnúť prácnosť naprogramovania každého z nich a po
zohľadnení oboch týchto kritérií si jeden spôsob vyberieme.
3. Realizácia (prepis algoritmu do programovacieho jazyka – tie majú rôznu syntax – súbor
príkazov a pravidiel, kými sa v ňom zapisujú programy)
Ladenie a testovanie – ladenie programu (oprava chýb syntaktických a logických, novšie
verzie, prispôsobenie softvéru požiadavkám používateľa)
4. Dokumentácia a údržba Ak je program dobrý a chceme ho ponúknuť aj iným ľuďom, je dobré,
ak sa k nemu vytvorí minimálne pomocník. Vhodná je aj dokumentácia, ktorú môžu využiť iní
programátori, kde opíšete, ako ste pristupovali k riešeniu jednotlivých problémov atď. Ak sa
program uchytí, postaráme sa o jeho údržbu (modifikácie, vylepšenia) a podporu (napríklad
možnosť napísať vám mail a opýtať sa na niečo).
problém
algoritmus
program
ALGORITMIZÁCIA
PROGRAMOVANIE
Vývojový diagram – popisuje postupnosť činností pomocou normou definovaných grafických
značiek a textu v nich.
2
Štruktúrogram – zhustená obdoba vývojových diagramov, ktorá však nie je definovaná normou.
Základné značky používané vo vývojových diagramoch:
- počiatočná a koncová značka (medzná značka)
- vstup a výstup hodnôt
- priradenia; vykonanie [spracovanie (príkaz, operácia činnosť)]
- porovnanie, rozhodovanie a vetvenie
- poznámka, komentár
- spojka
značky spájame spojnicami, šípka musí byť ak
...
Základné algoritmické konštrukcie
4. sekvencia – postupnosť príkazov
5. vetvenie – členenie algoritmu na základe podmienky
6. cyklus – viacnásobné opakovanie časti algoritmu na základe podmienky (telo cyklu je to, čo sa
má opakovať, dokedy sa to má opakovať, to určuje podmienka cyklu)
začiatok
začiatok
príkaz 1
začiatok
vstup
príkaz 1
1
podmienka
príkaz 2
podmienka
koniec
......
príkaz n
príkaz 1
príkaz 2
vstup
koniec
príkaz 2
výstup
koniec
Program – postupnosť príkazov (inštrukcií) programovacieho jazyka, ktorou popisujeme, ako má
počítač (procesor) riešiť určitú úlohu.
Príkazy – sú vety jazyka, ktoré prikazujú procesoru vykonať isté presne stanovené činnosti (napr.
príkaz vstupu, výstupu, priradenia). Príkazy spracovávajú nejaké objekty (premenné, konštanty,
výrazy).
Premenná je objekt (pomenované pamäťové miesto), ktorý obsahuje konkrétnu hodnotu (číslo,
znaky), ktorá sa počas behu programu môže meniť.
3
Konštanta je objekt, ktorý má počas realizácie programu jedinú konkrétnu hodnotu.
Výraz je predpis pre získanie hodnoty. Obsahuje operandy (premenné, konštanty, ...), operátoty (+,
-, *, /, <, >, ...) a zátvorky.
Identifikátor je názov objektu programu (premennej, konštanty, podprogramu, ...). Odporúča sa
voliť mnemotechnické identifikátory, t. j. také, ktoré približujú hodnotu, ktorá je v nich uložená.
Elementárne činnosti, ktoré vie počítač vykonávať sú:
 priraďovací príkaz
 príkaz vstupu
 príkaz výstupu
 podmienka
Priraďovací príkaz nariaďuje procesoru, aby vykonal na jeho pravej strane naznačené operácie
alebo funkcie a výsledok uložil do premennej, meno ktorej je na ľavej strane.
Príkaz vstupu umožňuje zadať procesoru konkrétne hodnotu údajov, ktoré má spracovávať. Tieto
hodnoty sa uložia do premenných
Príkaz výstupu umožňuje získať od procesora výsledky algoritmu alebo iné oznamy.
Podmienka je v programovacích jazykoch chápaná ako logický výraz.
Kocka
Čítaj a
V← a*a*a
Píš V
koniec
Otázky:
1. Čo rozumiete pod pojmom algoritmus?
2. Aké vlastnosti musí mať riešenie úlohy, aby to bol algoritmus (vlastnosti algoritmu)?
3. Popíšte vlastnosti algoritmu elementárnosť a determinovanosť.
4. Popíšte vlastnosti algoritmu rezultatívnosť a konečnosť.
5. Popíšte vlastnosti algoritmu hromadnosť a efektívnosť.
6. Akými spôsobmi môžeme zapísať algoritmus?
7. K čomu slúži vývojový diagram?
8. Vymenujte a nakreslite základné značky vývojového diagramu.
9. Popíšte spôsoby zápisu algoritmov a uveďte pomocou akých základných algoritmických
konštrukcií môžeme zapísať ľubovoľný výpočtový proces.
10. Vymenujte a stručne popíšte etapy tvorby programu?
11. Aký je rozdiel medzi chybou syntaktickou a logickou?
4
12. K čomu slúži vývojový diagram?
13. Vymenujte a nakreslite základné značky vývojového diagramu.
14. Čo rozumiete pod pojmom program a príkazy programu?
15. Čo je premenná a čo konštanta v programe a aký je medzi nimi rozdiel?
16. Čo rozumiete pod pojmom výraz a čo je identifikátor?
17. Vymenujte a popíšte činnosti, ktoré sú pre počítač elementárne.
18. Popíšte spôsoby zápisu algoritmov a uveďte pomocou akých základných algoritmických
konštrukcií môžeme zapísať ľubovoľný výpočtový proces.
Domáca úloha:
1. Napíšte do zošita program na výpočet obsahu a objemu hranola so stranami a, b, c:
 Urobte rozbor problému
 Navrhnite algoritmus riešenia aj v tvare vývojového diagramu
 Napíšte program a jazyku Logo v prostredí Imagine
Program odlaďte a otestujte na počítači, ak bude správny, zapíšte si ho do zošita.
5
Download

1. Algoritmus, Etapy tvorby programov. Algoritmické konštrukcie.