Základy algoritmizace

Algoritmus

• Toto je sice na první pohled pravdivá, ale při bližším prozkoumání nepřesná definice. Například některé matematické postupy by této definici vyhovovaly, ale nejsou algoritmy.

• Přesné znění definice algoritmu zní: „Algoritmus je procedura proveditelná Turingovým strojem.“

• Turingův stroj (1937) je teoretický model počítače popsaný matematikem Alanem Turingem. Skládá se z procesorové jednotky, tvořené konečným automatem a programu ve tvaru pravidel přechodové funkce a potenciálně nekonečné pásky pro zápis mezivýsledků a vstupů dat. Využívá se pro modelování algoritmů v teorii vyčíslitelnosti.

Základy algoritmizace

Algoritmus

• Algoritmus je schematický postup pro řešení určitého druhu problémů, který je prováděn pomocí konečného množství přesně definovaných kroků.

nebo

• Algoritmus lze definovat jako jednoznačně určenou posloupnost konečného počtu elementárních kroků vedoucí k řešení daného problému (úlohy), přičemž musí být splněny základní vlastnosti každého algoritmu.

• Ačkoliv se dnes tento pojem používá především v informatice a přírodních vědách obecně, tak je jeho působnost daleko širší (kuchyňské recepty, návody a postupy...). Samotné slovo „algoritmus“ pochází ze jména perského matematika 9. století Abu Jafar Muhammada ibn Mūsā al-Chwārizmího, který ve svých dílech položil základy algebry (arabské číslice, řešení lineárních a kvadratických rovnic).

Základy algoritmizace

Vlastnosti algoritmů (1)

1) Konečnost – Algoritmus má konečné množství kroků (musí mít začátek konec).

– Po konečném počtu kroků musí dojít od počátku do konce.

2) Korektnost (správnost) – Algoritmus skončí pro libovolná (korektní) data správným výsledkem v konečném

množství kroků.

– Jinak řečeno: algoritmus je správný tehdy, když pro všechny údaje splňující vstupní podmínku se proces zastaví a výstupní údaje splňuji výstupní podmínku.

3) Obecnost (hromadnost, univerzálnost) – Algoritmus neřeší jeden konkrétní problém (např. výpočet 9 + 3), ale řeší obecnou třídu

obdobných problémů (např. výpočet součet dvou čísel).

4) Rezultativnost – Algoritmus při zadání vstupních dat vždy vrátí výsledek (může se jednat i o chybové

hlášení).

Základy algoritmizace

Vlastnosti algoritmů (2)

5) Jednoznačnost (Determinovanost) – Každý krok algoritmu musí být jednoznačně a přesně definován.

– V každé situaci musí být naprosto zřejmé, co a jak se má provést, jak má provádění algoritmu pokračovat.

– Protože běžný jazyk neposkytuje naprostou přesnost a jednoznačnost vyjadřování, byly pro zápis algoritmů navženy programovací jazyky, ve kterých má každý příkaz jasně definovaný.

6) Opakovatelnost – Při stejných vstupních hodnotách musíme dostat vždy stejný výsledek.

7) Srozumitelnost – Algoritmus musí být srozumitelný i pro uživatele, který daný algoritmus nevytvářel.

Základy algoritmizace

Jak sestavit algoritmus?

• Popsat všechny operace, pomocí kterých transformujeme vstupní data na požadovaná data výstupní. – Počáteční údaje = vstupní data – Požadovaný výsledek = výstupní data

• Možnosti reprezentace algoritmů:

– slovní popis,

– matematický zápis,

– strukturogramy,

– rozhodovací tabulky,

– vývojové diagramy,

– počítačové programy.

Základy algoritmizace

Vývojové diagramy

Vý vojový diagram je graficke zna zorne ní jednotlivý ch kroků (pr í kazů ), ze který ch se skla da , a jejich

na vazností pomocí normalizovaný ch znac ek.

Základní značky pro tvorbu vývojových diagramů

Kvadratická rovnice Mezní značka (začátek a konec programu)

d = b2 - 4*a*c Zpracování (příkaz, operace, činnost)

Podmínka

D < 0 Větvení

Načti a, b, c Vstup a výstup hodnot (dat)

Výpočet kořenů

kvadratické rovnice Podprogram, funkce, procedura

1 Spojka

Cyklus i = 1, n Příprava (např. příprava cyklu)

Ano Ne

Vývojové diagramy

Základní algoritmizační úloha: výměna obsahu dvou proměnných

Jedna se o c astoů operaci, ktera je soůc a stí mnoha dals í ch algoritmů .

Výměna proměnných

Načti a, b

pom = a

a = b

b = pom

Zobraz a, b

Konec

Vývojové diagramy

Výpočet kořenů kvadratické rovnice

Kvadratická rovnice

Načti a, b, c

D = b2 - 4*a*c

D < 0

Ne

Ano

D == 0 Ano

x = -b/(2*a)

„Rovnice má

jedno řešení:“ x

Ne

x1 = (-b+√(D))/(2*a)

x2 = (-b-√(D))/(2*a)

„Rovnice má řešení:“ x1, x2

„Rovnice nemá

řešení v R“

Konec programu

Vývojové diagramy

Součet číslic v čísle

Součet číslic v celém čísle

Načti a

suma = 0

Sestavte algoritmůs, který zjistí soůc et cifer v zadane m cele m c í sle. Vý stůpem algoritmů bůde zadane

c í slo a jeho ciferný soůc et.

a >= 10

cislo = a % (10)

a = (a-cislo)/10

suma = suma + cislo

zaloha = a

+

-

suma = suma + a

„Zadali jste číslo:“ zaloha

„Součet číslic čísla“ zaloha

„je:“ suma

Konec programu

Poznámka:

Algoritmus využívá toho, že většina programovacích

jazyků má operaci modulo - tedy zjištění zbytku po

celočíselném dělení.

V PHP, Javě, C # a dalších jazycích se pro operaci

modulo používá operátor %.

Zdroje

• Roubal, Pavel. Informatika a výpočetní technika pro střední školy – praktická učebnice. ISBN: 978-80-251-3227-2.

Základy algoritmizace

jméno autora Tomáš Žižka

název projektu Informatika a digitální technika

číslo projektu CZ.1.07/1.5.00/34.0158

číslo šablony III/2 Inovace výuky pomocí ICT

předmět/ třída (ročník) Informatika/oktáva

pořadové číslo DUM 20

datum 22. 4. 2013

název DUM Základy algoritmizace

metodická poznámka k využití

Výuková prezentace, která je zaměřena na problematiku

algoritmizace a programování. Určeno pro frontální výuku s celou

třídou.