Algoritmus
Z MiS
(Rozdíly mezi verzemi)
(→Problém: Vypuštěny typy problémů a další pojmy) |
(→Zápis algoritmu: Oprava formátování) |
||
(Není zobrazeno 8 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''' | + | #'''Určitost''' (determinovanost) |
− | #*všechny kroky algoritmu jsou přesně definovány. | + | #* všechny kroky algoritmu jsou přesně definovány. |
#'''Korektnost''' | #'''Korektnost''' | ||
− | #*algoritmus skončí pro libovolná (korektní) data správným výsledkem. | + | #* algoritmus skončí pro libovolná (korektní) data správným výsledkem. |
#'''Obecnost''' | #'''Obecnost''' | ||
− | #*algoritmus řeší všechny úlohy daného typu. | + | #* 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]]. | ||
== 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 22. 9. 2021, 12:40
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ů.
- Určitost (determinovanost)
- všechny kroky algoritmu jsou přesně definovány.
- Korektnost
- algoritmus skončí pro libovolná (korektní) 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.
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.