Algoritmizace
Co je to algoritmus?
Algoritmus je posloupnost operací, která řeší daný úkol v konečném počtu kroků. Je to přesný postup jednotlivých kroků, který je potřeba vykonat, aby se splnila určitá činnost.
Příklad algoritmu si můžeme ukázat na úloze vaření čaje. Zde si dovolím předpokládat, že každý z Vás již alespoň párkrát v životě čaj vařil, a tak by neměl být problém se znalostí správného postupu.
Vstupy jsou jasné: voda, pytlík čaje nebo lžička sypaného čaje, prázdný hrnek, varná konvice, případně sítko.
Výstupem je hrnek s horkým čajem.
Postup tedy bude: 1) nalít vodu do varné konvice, 2) zapnout varnou konvici, 3) máme-li pytlík s čajem, vložit jej do hrnku, 4) máme-li sypaný čaj, nasypat čaj do sítka a sítko umístit do hrnku, 5) počkat, dokud se voda ve varné konvici nebude vařit, 6) zalít čaj vodou, 7) počkat dvě až tři minuty, 8) vyhodit sáček s čajem nebo vyprázdnit čaj ze sítka, 9) konec algoritmu
Zde vidíte, jak i tak zdánlivě jednoduchý postup, jakým je vaření čaje, se skládá z množství jednotlivých kroků. A to jsme zdaleka nešli do úrovně, kterou by potřeboval robot, aby tento postup mohl bez potíží udělat. Zcela jsme například opominuli zkontrolovat, zda-li je varná konvice v elektřině, jestli funguje zásuvka, co budeme dělat, když nemáme pytlík čaje, jestli je hrnek čistý, jaký typ čaje máme (některé se zalévají vroucí vodou a některé pouze 80 stupňovou), jestli máme kam sáček vyhodit, atd.
Vlastnosti algoritmu
Každý algoritmus musí splňovat tyto minimální vlastnosti, abychom vůbec mohli hovořit o algoritmu:
- konečný – má jasně definovaný začátek i konec
- věcně správný – má možnost dojít ke správnému řešení
- jednoznačný – jsou ošetřeny všechny situace, které mohou při procházení algoritmem nastat
- obecný – algoritmus řeší co možná nejširší množinu zadání
- opakovatelný – za stejných podmínek musí dojít vždy ke stejnému řešení
- srozumitelný – srozumitelný jak pro programátora, tak i pro ne-programátora
V hodině si ukážeme konkrétní příklady nesprávně navržených algoritmů, které porušují jednotlivá pravidla.
jsou ošetřeny všechny situace, které mohou při procházení algoritmem nastat
obecný
konečný
algoritmus má začátek i konec
algoritmus je srozumitelný pro programátora i ne-programátora
má možnost dojít ke správnému řešení
opakovatelný
za stejných podmínek musí algoritmus dojít vždy ke stejnému řešení
jednoznačný
Znázornění algoritmu
Máme několik způsobů, jak algoritmus znázornit. Dopředu je důležité říci, že žádný není univerzálně nejlepší ani nejhorší – každý z nich má svá pro a svá proti. Budeme rozlišovat následujících šest způsobů znázornění:
- Slovní vyjádření
- Rozhodovací tabulky
- Vývojové diagramy
- Matematické zápisy
- Strukturogramy
- Programovací jazyk
| Slovní vyjádření | Rozhodovací tabulky | Vývojové diagramy | |
|---|---|---|---|
| Klady | rozumí tomu i laik poslední možnost, když nic jiného nezbývá | jednoznačný zápis přehlednost snadná pochopitelnost | přehlednost názornost |
| Zápory | nejméně přehledné bez nástroje, jak uhlídat zmapování všech možných stavů | nehodí se pro každý typ úlohy nehodí se pro delší vysvětlování | v případě složitých algoritmů ztrácí přehlednost |
| Matematické zápisy | Strukturogramy | Programovací jazyk | |
|---|---|---|---|
| Klady | jednoznačnost přehlednost | úsporný zápis podobnost se zápisem pomocí programovacího jazyka | přímý převod do spustitelného kódu |
| Zápory | srozumitelné pouze pro matematicky znalé většinou příliš stručný | méně se používá malé možnosti pozdějších úprav | obtížně čitelný pro ne-autory programovacího kódu |
Slovní vyjádření
„…Žáci jsou povinni chodit do školy slušně a čistě oblečeni, řádně upraveni a učesáni…“
(§ ze školního řádu)
Napadá Vás nějaké výhody a nevýhody tohoto způsobu vyjádření postupu?
Rozhodovací tabulky
Mějme tři spínače (spínač 1, 2 a 3) a jednu žárovku. Požadované zapojení je dle následující tabulky:
| Spínač 1 | Spínač 2 | Spínač 3 | Žárovka |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Vše jasné, že? Napadají Vás nějaké výhody a nevýhody tohoto způsobu vyjádření algoritmu?
Vývojové diagramy
Vývojové diagramy (flowcharty) se používají v programování velmi často a my je budeme taktéž chvíli probírat. Skládají se z několika málo základních tvarů:
- kruh pro začátek a konec (pozor – musí být definován, jinak bychom porušili vlastnost algoritmu)
- obdélník pro znázornění interního kroku
- rovnoběžník pro znázornění vstupu nebo výstupu
- kosočtverec pro znázornění podmínky (má vždy jeden vstup a dva výstupy)
Například:
Matematický zápis
Použijeme jednoduchou rovnici pro výpočet dvou kořenů kvadratické rovnice:
Napadají Vás zde výhody a nevýhody tohoto způsobu znázornění?
Strukturogram
Zkusíme tedy ten samý postup znázornit pomocí strukturogramu:
Programovací jazyk
Ukážeme si úplně jednoduchý program, který má na vstupu znak (načítá z klávesnice) a na výstupu vypíše daný znak včetně jeho číselné hodnoty v ASCII tabulce.
#include <stdio.h>
int main() {
char c;
printf("Enter a character: ");
scanf("%c", &c);
printf("ASCII value of %c = %d", c, c);
return 0;
}
Podcast
Generovaný podcast o algoritmech si můžete pustit zde:
Podcast byl automaticky generován na základě této stránky a na základě videa z YouTube https://youtu.be/kaGpgiXExS0?si=hX2Vh51eth1fUhH0.