Algoritmus Cílem kapitoly je seznámit žáky se základy algoritmu, s jeho tvorbou a způsoby zápisu.
Klíčové pojmy: Algoritmus, vlastnosti algoritmu, vývojový diagram
Algoritmus •
Algoritmus je postup, pomocí kterého můžeme vyřešit zadaný problem.
•
Algoritmus je předpis kroků pro zadanou množinu problem, které vedou k řešení problem
•
Schématický postup řešení problému
•
Řešení pomocí konečného množství přesně definovaných kroků
•
Pro řešení jednoho problem můžeme najít vice postupů, vždy však musí vést ke stejnému výsledku
•
Příklad z života: o Recepty o Návody a postupy o Popis trasy na mapě
Vstup:
Činnost:
Výstup:
problém
algoritmizace
Algoritmus = jak to řešit
Vlastnosti algoritmu: •
Hromadnost – algoritmus slouží k řešení celé skupiny navzájem si podobných úloh. Úlohy jsou si podobné, ale liší se vstupními daty.
•
Konečnost – pro každá přípustná data algoritmus po konečném počtu kroku skončí v name požadovaném čase. Tento počet kroků může být libovolně velký(podle složitosti úlohy), ale pro každý jednotlivý vstup msí být konečný.
•
Částečná (parciální) správnost – jestliže algoritmus skončí, pak výsledek je správný (tj. nestane se, že pro nějaká přípustná vstupní data algoritmus skončí se špatným výsledkem). Pro stejný vstup musí vždy vyjít stejný výsledek.
•
Mechanické provádění – algoritmus muže provádět každý bez hlubší znalosti řešené úlohy.
•
Opakovatelný
•
Jednoznačnost(determinovanost) – algoritmus se skládá z jednoduchých kroků (příkazů), po splnění jednoho kroku musí být jednoznačně řečeno, jaký krok bude následovat
Pokud neni splněna jakákoliv vlastnost, nejedná se o algoritmus.
Vlastnosti dobrého algoritmu: •
Je jednoznačný (detministický)
•
Konečný = k výsledku dospějeme v konečném case
•
Obecný/hrnomadný = je použitelný pro libovolná přípustná data
•
Opakovatelný = vede pro stejná data vždy ke stejnému výsledku
•
Srozumitelný
•
Přehledný
Reprezentace a zápis algoritmu: •
Slovní popis – popis v přirozeném jazyce nebo ve vyšších programovacích jazycích
•
Vývojový diagram
•
Strukturogramy
•
Datově orientované diagramy
•
Rozhodovací tabulky
•
Matematický zápis
•
Programovacím jazykem = jedinný způsob srozumitelný počítači o Program = algoritmus vyjádřený programovacím jazykem
Interpret – zápis algoritmu
Kompilátor – překlad jazyka tak, aby mu rozuměl počítač
Vývojový diagram: •
Znázorňuje průběh a stavbu programu
•
Skládá se z jednotlivých grafických značek
•
Každá značka má svůj význam
•
Spojovací čáry – pokud směřuje dolů, není nutné znázorňovat šipku
Jednotlivé části diagramu a jejich význam (výběr):
Konec a začátek algoritmu
Běžný příkaz
Podmíněný výraz
Cyklus s určeným počtem opakování
Cyklus s podmínkou na konci
Cyklus s podmínkou na začátku
Spojovací čára
Struktury vývojových diagramů Sekvence Jedná se o příkazy jdoucí po sobě. Je to řada příkazů, které se postupně vykonají.
Obr. 1: Sekvence
Větvení Program se skládá z několika částí. Další krok závisí na podmínce, zda je splněna či ne.
Větvení - úplná alternativa Podmínka nám větví program na dvě části. Jedna část programu se vykonává, pokud je podmínka splněna, a druhá, pokud podmínka není splněna. Program pak v určitém místě pokračuje stejně. + podmínka je splněna - podmínka neni splněna
Obr. 2: Větvení - úplné
Větvení - neúplná alternativa Podobné jako úplný, ovšem jedna větev je prázdná. Program nám jen některé části programu přeskočí.
Obr. 3: Větvení - neúplné
11/9/2012
Algoritmus
5/9
Větvení - několikanásobná alternativa Podmínka je zde složitější, dělí nám program na více větví.
Obr. 4: Větvení - několikanásovné
Cykly se vstupní podmínkou Cyklus se provádí do doby, dokud není podmínka splněna. Pokud jsou podmínky již na začátku splněny, cyklus se neprovede ani jednou.
Obr. 5: Cykly se vstupní podmínkou
Cykly s výstupní podmínkou Podmínka je až ke konci programu.
Obr. 6: Cyklus s výstupní podmínkou
JIŘÍ CHYTIL, VÝVOJOVÉ DIAGRAMY 1. – 6. DÍL ,[ ONLINE] 21.7. 2011 Z WEBU: http://programujte.com
11/9/2012
Algoritmus
6/9
PŘÍKLADY ALGORITMŮ
ZATLUČENÍ HŘEBÍKU PROBLÉM :
Máme zatlouct hřebík.
Předpokládáme, že máme k dispozici hřebík, místo na zatlučení a kladivo.
ALBORITMUS:
Start
Vezmeme kladivo a hřebík
Přiložíme hřebík k desce
Uhodíme kladivem na hlavičku hřebíku
NE Je hřebík zatlučen? ANO Konec
11/9/2012
Algoritmus
7/9
ŽÁROVKA: PROBLÉM: Nesvítí žárovka. Jak budeme postupovat? Musíme si položit několik otázek: •
Opravdu nesvítí?
•
Je připojene ke zdruji el. Energie?
•
Neni polámaná?
Předpokládáme, že vice problem nemůže nastat.
11/9/2012
Algoritmus
8/9
Vývojový diagram: Start
Zapneme vypínač
ANO Svítí žárovka?
NE NE Je žárovka zapojena
Připoj žárovku ke zdorji el.en..
ke zdroji el.en.?
ANO NE Svítí žárovka?
Zkus vyměnit žárovku.
ANO
Konec
11/9/2012
Algoritmus
9/9
