Algoritmus
Z MiS
(Rozdíly mezi verzemi)
(Vytvoření stránky) |
(→Algoritmus: Doplnění konečnosti.) |
||
| (Není zobrazeno 12 mezilehlých verzí od 1 uživatele.) | |||
| Řádka 3: | Řádka 3: | ||
== Úloha == | == Úloha == | ||
* Zadání, které řešíme. | * Zadání, které řešíme. | ||
| − | * | + | * Pokud ''úlohu'' popíšeme formálně (matematicky), vznikne ''problém''. |
== Problém == | == Problém == | ||
| − | + | ; Popis problému zahrnuje: | |
| − | *vstupní proměnné | + | * vstupní proměnné |
| − | *výstupní proměnné | + | * výstupní proměnné |
| − | *konfigurační proměnné | + | * konfigurační proměnné |
| − | *omezení | + | * omezení |
| − | *optimalizační kritérium | + | * optimalizační kritérium |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
== Algoritmus == | == Algoritmus == | ||
| − | + | <div class="Definice"> | |
| + | Schematický postup řešení určitého problému, který je konečný, určitý, korektní a obecný. | ||
| + | </div> | ||
| − | + | ; Vlastnosti algoritmu | |
| − | #Konečnost | + | #'''Konečnost''' |
| − | #*algoritmus skončí pro libovolná (korektní) data v konečném množství kroků. | + | #* algoritmus skončí pro libovolná (korektní) data v konečném množství kroků. |
| − | #Určitost | + | #*: ''Pro každou platnou vstupní posloupnost tedy lze nalézt konkrétní konečné číslo, které je nejzazším limitem počtu provedených kroků.'' (Algoritmus může skončit dříve.) |
| − | #*všechny kroky algoritmu jsou přesně definovány. | + | #*: <div class="Priklad">Příklad: Pro desetiprvkovou posloupnost na vstupu skončí postup nejpozději po <tt>50 000</tt> krocích. Pro posloupnost milionu prvků na vstupu skončí nejpozději po <tt>5.10<sup>9</sup></tt> krocích. Pro miliardu prvků nebo jakékoli jiné velké číslo bude výpočet trvat ještě déle, ale vždy lze nalézt konkrétní konečné číslo, které je limitem počtu kroků pro danou posloupnost. Pak postup je konečný.</div> |
| − | #Korektnost | + | #'''Určitost''' (determinovanost) |
| − | #*algoritmus skončí pro libovolná (korektní) data správným výsledkem. | + | #* všechny kroky algoritmu jsou přesně definovány. |
| − | #Obecnost | + | #'''Korektnost''' |
| − | #*algoritmus řeší všechny úlohy daného typu. | + | #* algoritmus skončí pro libovolná (korektní) vstupní data správným výsledkem. |
| + | #'''Obecnost''' | ||
| + | #* algoritmus řeší všechny úlohy daného typu. | ||
| − | + | ; Někdy se jako vlastnosti uvádí také: | |
| − | *Nechť: | + | * resultativnost — konečnost a korektnost dohromady |
| − | ** X={x1, x2, ...,xn} je | + | ** Algoritmus skončí pro libovolná (korektní) data v konečném množství kroků správným výsledkem. |
| − | ** Z={z1, z2, ...,zn} je | + | * elementárnost |
| − | *Pak každé ohodnocení s proměnných X a Z je stav algoritmu. | + | ** Základní kroky algoritmu jsou dostatečně jednoduché, aby jim rozuměl vykonávající stroj. |
| + | ** Chápeme to jako součást určitosti algoritmu. | ||
| + | |||
| + | == Stav algoritmu == | ||
| + | <div class="Definice"> | ||
| + | * Nechť: | ||
| + | ** X={x1, x2, ...,xn} je množina konfiguračních proměnných | ||
| + | ** Z={z1, z2, ...,zn} je množina vnitřních proměnných algoritmu A řešícího problém I. | ||
| + | * Pak každé ohodnocení s proměnných X a Z je stav algoritmu. | ||
| + | </div> | ||
| + | |||
| + | == Zápis algoritmu == | ||
| + | Algoritmus můžeme zapsat následujícími způsoby: | ||
| + | |||
| + | ; V přirozeném jazyce | ||
| + | * Česky, anglicky,... | ||
| + | * Například napíšeme článek, kde se popisuje, jak problém řešit. | ||
| + | * Tento popis by měl být srozumitelný každému člověku. | ||
| + | |||
| + | ; Pseudokódem | ||
| + | * Používáme jazyk podobný programovacím jazykům, ale zjednodušený. | ||
| + | * Vynecháváme prvky, které člověk pro pochopení nepotřebuje (složené závorky tam, kde je dostačující odsazení apod.). | ||
| + | |||
| + | ; V některém programovacím jazyce | ||
| + | * Například v Javě. | ||
| + | * Oproti pseudokódu už je zde větší množství řádků, které nesouvisí s vysvětlením principu, ale jsou nutné pro spuštění. | ||
| + | * Výhoda je, že tento postup lze v počítači přímo spustit. | ||
| + | |||
| + | ; Pomocí vývojových diagramů | ||
| + | * Viz série článků [http://programujte.com/clanek/2005080105-vyvojove-diagramy-1-dil/ Vývojové diagramy na Programujte.com]. | ||
| + | * Viz stránka [[Vývojové diagramy]]. | ||
| + | |||
| + | |||
| + | === Příklad zápisu algoritmu pseudokódem === | ||
| + | <div class="Priklad"> | ||
| + | Jako ukázku uvedeme algoritmus pro výběr nejmenšího prvku ze seznamu čísel. | ||
| + | |||
| + | Zápis pseudokódem by mohl vypadat třeba takto: | ||
| + | |||
| + | <pre> | ||
| + | if seznam.isEmpty(): | ||
| + | print "Error" | ||
| + | |||
| + | vysledek := seznam[1] | ||
| + | |||
| + | for i := 2 to seznam.size(): | ||
| + | if vysledek > seznam[i]: | ||
| + | vysledek := seznam[i] | ||
| + | |||
| + | return vysledek | ||
| + | </pre> | ||
| + | </div> | ||
== Algoritmizace × programování == | == Algoritmizace × programování == | ||
| − | + | ||
| − | + | Pojem ''programování'' v užším smyslu je synonymem ''kódování'', tedy přepisu algoritmu do zdrojového kódu. | |
| − | + | ||
| − | + | Pojem ''programování'' v širším slova smyslu je synonymem pro ''tvorbu software'' a zahrnuje: ''analýzu'' zadání, ''algoritmizaci'' a ''kódování''. | |
| − | * | + | |
| − | * | + | Viz [[Tvorba software]]. |
| + | |||
| + | == Viz také == | ||
| + | * [[Tvorba software]] | ||
| + | * [[Složitost algoritmu]] | ||
Aktuální verze z 18. 10. 2024, 08:01
Obsah |
Úloha
- Zadání, které řešíme.
- Pokud úlohu popíšeme formálně (matematicky), vznikne problém.
Problém
- Popis problému zahrnuje
- vstupní proměnné
- výstupní proměnné
- konfigurační proměnné
- omezení
- optimalizační kritérium
Algoritmus
Schematický postup řešení určitého problému, který je konečný, určitý, korektní a obecný.
- Vlastnosti algoritmu
- Konečnost
- algoritmus skončí pro libovolná (korektní) data v konečném množství kroků.
- Pro každou platnou vstupní posloupnost tedy lze nalézt konkrétní konečné číslo, které je nejzazším limitem počtu provedených kroků. (Algoritmus může skončit dříve.)
- Příklad: Pro desetiprvkovou posloupnost na vstupu skončí postup nejpozději po 50 000 krocích. Pro posloupnost milionu prvků na vstupu skončí nejpozději po 5.109 krocích. Pro miliardu prvků nebo jakékoli jiné velké číslo bude výpočet trvat ještě déle, ale vždy lze nalézt konkrétní konečné číslo, které je limitem počtu kroků pro danou posloupnost. Pak postup je konečný.
- algoritmus skončí pro libovolná (korektní) data v konečném množství kroků.
- Určitost (determinovanost)
- všechny kroky algoritmu jsou přesně definovány.
- Korektnost
- algoritmus skončí pro libovolná (korektní) vstupní data správným výsledkem.
- Obecnost
- algoritmus řeší všechny úlohy daného typu.
- Někdy se jako vlastnosti uvádí také
- resultativnost — konečnost a korektnost dohromady
- Algoritmus skončí pro libovolná (korektní) data v konečném množství kroků správným výsledkem.
- elementárnost
- Základní kroky algoritmu jsou dostatečně jednoduché, aby jim rozuměl vykonávající stroj.
- Chápeme to jako součást určitosti algoritmu.
Stav algoritmu
- Nechť:
- X={x1, x2, ...,xn} je množina konfiguračních proměnných
- Z={z1, z2, ...,zn} je množina vnitřních proměnných algoritmu A řešícího problém I.
- Pak každé ohodnocení s proměnných X a Z je stav algoritmu.
Zápis algoritmu
Algoritmus můžeme zapsat následujícími způsoby:
- V přirozeném jazyce
- Česky, anglicky,...
- Například napíšeme článek, kde se popisuje, jak problém řešit.
- Tento popis by měl být srozumitelný každému člověku.
- Pseudokódem
- Používáme jazyk podobný programovacím jazykům, ale zjednodušený.
- Vynecháváme prvky, které člověk pro pochopení nepotřebuje (složené závorky tam, kde je dostačující odsazení apod.).
- V některém programovacím jazyce
- Například v Javě.
- Oproti pseudokódu už je zde větší množství řádků, které nesouvisí s vysvětlením principu, ale jsou nutné pro spuštění.
- Výhoda je, že tento postup lze v počítači přímo spustit.
- Pomocí vývojových diagramů
- Viz série článků Vývojové diagramy na Programujte.com.
- Viz stránka Vývojové diagramy.
Příklad zápisu algoritmu pseudokódem
Jako ukázku uvedeme algoritmus pro výběr nejmenšího prvku ze seznamu čísel.
Zápis pseudokódem by mohl vypadat třeba takto:
if seznam.isEmpty(): print "Error" vysledek := seznam[1] for i := 2 to seznam.size(): if vysledek > seznam[i]: vysledek := seznam[i] return vysledek
Algoritmizace × programování
Pojem programování v užším smyslu je synonymem kódování, tedy přepisu algoritmu do zdrojového kódu.
Pojem programování v širším slova smyslu je synonymem pro tvorbu software a zahrnuje: analýzu zadání, algoritmizaci a kódování.
Viz Tvorba software.
