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, tvorba algoritmu, vývojový diagram, strukturogram
Algoritmus „Algoritmus je účelně zvolený postup výpočtu.“ (španělsko-arabský matematika Al-Chváriamí)
Poprvé slovo algoritmus použil asi před 1000 let perský matematik Abú Abdallah Muhammad. Algoritmus = předpis konečného počtu kroků, kterými je možno řešit stejnorodé úkoly, např. výpočty, programy ro počítač = obdobný postup pro řešení třídy úloh konečným počtem úkolů, z nichž každý je přesně definován (Slovník cizích slov, [online]28.8.2013, dostupné na slovnik-ciczich-slov.abz.cz/slovo/)
Algoritmus je postup, pomocí kterého můžeme vyřešit zadaný problém.
Algoritmus je předpis kroků pro zadanou množinu problém, které vedou k řešení problém
Schématický postup řešení problému
Řešení pomocí konečného množství přesně definovaných kroků
Pro řešení jednoho problém můžeme najít více 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ě
5/5/2014
Algoritmus
1/12
Vstup:
Činnost:
Výstup:
problém
algoritmizace
Algoritmus = jak to řešit
Efektivnost algoritmu:
Jedná s o důležitou výkonnostní charakteristiku algoritmu.
Efektivní algoritmus řeší problém s minimálními nároky na hardware a v co nejkratší době.
Nejjednodušší řešení většinou nejdéle trvá, ale je jednoduché na implementaci.
Nejrychlejší řešení bývá náročné na implementaci, nemusí být však stabilní.
Optimální řešení = pomalejší než nejrychlejší, ale stabilní!!!!!
Analýza efektivnosti – např. empiricky, srovnáním doby běhu různých algoritmů
Vlastnosti algoritmu:
Hromadnost o Algoritmus slouží k řešení celé skupiny navzájem si podobných úloh. Úlohy jsou si podobné, ale liší se vstupními daty. Pro jejich libovolnou kombinaci obdržíme jednoznačné řešení.
Konečnost (rezultativnost) o Pro každá přípustná data algoritmus po konečném počtu kroku skončí nám požadovaném čase. Tento počet kroků může být libovolně velký (podle složitosti úlohy), ale pro každý jednotlivý vstup musí být konečný.
Částečná (parciální) správnost o 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í o Algoritmus muže provádět každý bez hlubší znalosti řešené úlohy.
Opakovatelný o Při opakovaném použití stejných vstupních údajů získáme tentýž výsledek.
Jednoznačnost(determinovanost) o 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. 5/5/2014
Algoritmus
2/12
Vlastnosti dobrého algoritmu:
Je jednoznačný (detministický)
Konečný = k výsledku dospějeme v konečném čase
Obecný/hromadný = je použitelný pro libovolná přípustná data
Opakovatelný = vede pro stejná data vždy ke stejnému výsledku
Srozumitelný
Přehledný
Postup při vytváření algoritmu: 1) Formulace problému 2) Stanovení cíle 3) Volba strategie 4) Navržení postupu 5) Zápis vytvořených postupů 6) Ověření správnosti a) definice vstupních dat b) definice výstupních dat
Možné přístupy k návrhu algoritmu: 1. Shora dolů
Řešení rozkládáme na jednodušší operace až k dílčím krokům
Postupujeme od obecného ke konkrétnímu
2. Zdola nahoru
Z dílčích kroků vytváříme prostředky pro zvládnutí celkového problému
Postupujeme od konkrétního k obecnému
Nejdříve vytváříme nejjednodušší komponenty, ty spojujeme do větších až dospějeme k vytvoření hlavního programu
3. Kombinace
5/5/2014
Nejčastější varianta
Algoritmus
3/12
Reprezentace a zápis algoritmu:
Slovní popis o popis v přirozeném jazyce, programovacích jazycích
formálním
jazykem
Vývojový diagram
Strukturogramy
Datově orientované diagramy
Rozhodovací tabulky
Matematický zápis
Programovacím jazykem = jediný způsob srozumitelný počítači
nebo
ve
vyšších
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č
Grafické vyjádření algoritmu Výhody:
Přehlednost
Názornost
Znázornění struktury problému a postup řešení
Nevýhody:
Náročná konstrukce grafických symbolů a jejich vzájemných vztahů
Obtížná možnost dodatečných úprav
Není vhodné pro rozsáhlé a složitější problémy
5/5/2014
Algoritmus
4/12
Strukturogram
Jedná se o úspornější znázornění algoritmu pomocí kombinace grafického a textového popisu.
Je tvořen obdélníkovou tabulkou, do řádků zapisujeme postup kroků symbolickou či slovní formou v pořadí, v jakém budou prováděny.
Záhlaví tabulky obsahuje název algoritmu či dílčího kroku.
Výhody: o Přehlednější způsob znázornění o Lze jej aplikovat i na složitější problémy o Jednoznačný a snadný přepis do formálního jazyka
Nevýhody: o Pracnost konstrukce o Složité strukturogramy se nevejdou na jednu stranu o Malé možnosti pozdějších úprav
Řešení kvadratické rovnice Čti a,b,c Spočti diskriminant D=b*b – 4*a*c Je D >0? Ano
Ne
x1=( -b+sqrt(D))/(2*a)
Je D = 0?
x2=( -b-sqrt(D))/(2*a)
Ano
Ne
Tisk:
x1=( -b+sqrt(D))/(2*a)
Tisk:
2 kořeny: x1, x2
Tisk:
Nemá řešení
1 kořen : x1
5/5/2014
Algoritmus
5/12
Vývojový diagram
Znázorňuje průběh a stavbu programu
Skládá se z jednotlivých grafických značek ve formě uzavřených rovinných obrazců, do kterých jsou vepisovány slovní či symbolickou formou jednotlivé operace
Tvary a velikosti značek jsou dány normami
Každá značka má svůj význam
Spojovací čáry – pokud směřuje dolů, není nutné znázorňovat šipku
Výhody: názornost, přehlednost
Nevýhody: pracnost a složitost konstrukce, složitější se nevejdou na jednu stranu a stávají se méně přehlednými
5/5/2014
Algoritmus
6/12
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
5/5/2014
Algoritmus
7/12
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é
5/5/2014
Algoritmus
8/12
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
5/5/2014
Algoritmus
9/12
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
5/5/2014
Algoritmus
10/12
ŽÁ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.
5/5/2014
Algoritmus
11/12
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
5/5/2014
Algoritmus
12/12
