Algoritmus
Z MiS
(Rozdíly mezi verzemi)
(Vytvoření stránky) |
m (→Algoritmus: Oprava vzhledu a překlepů) |
||
| Řádka 33: | Řádka 33: | ||
== Algoritmus == | == Algoritmus == | ||
| − | *Schematický postup řešení určitého | + | *Schematický postup řešení určitého problém, který je konečný, určitý, korektní a obecný. |
=== Vlastnosti algoritmu === | === 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''' |
#*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. | ||
Verze z 24. 5. 2012, 00:02
Obsah |
Úloha
- Zadání, které řešíme.
- Formálním popisem vznikne problém.
Problém
Definice problému
- vstupní proměnné
- výstupní proměnné
- konfigurační proměnné
- omezení
- optimalizační kritérium
Další pojmy týkající se problému
- instance problému — ohodnocení vstupních proměnných - I
- konfigurace — ohodnocení konfiguračních proměnných - Y
- řešení — konfigurace, která splňuje omezení
- optimální řešení — konfigurace, která splňuje omezení a má nejlepší hodnotu optimalizačního kritéria
- suboptimální řešení — konfigurace, která splňuje omezení a má vyhovující hodnotu optimalizačního kritéria (z hlediska aplikace)
Typy problémů
- Kombinatorické problémy
- Omezení - R(I,Y)
- Rozhodovací problém - Existuje Y takové, že R(I,Y)?
- Konstruktivní problém - Sestrojte nějaké Y takové, že R(I,Y).
- Enumerační problém - Sestrojte všechna Y taková, že R(I,Y).
- Optimalizační problémy
- C(Y) - optimalizační kritérium - cenová funkce
- Optimalizační rozhodovací problém - Existuje Y takové, že R(I,Y) a C(Y) je lepší než daná konstanta Q?
- Optimalizační konstruktivní problém - Sestrojte nějaké Y takové, že R(I,Y) a C(Y) je nejlepší možné.
- Optimalizační enumerační problém - Sestrojte všechna Y taková. že R(I,Y) a C(Y) je nejlepší mmmožné.
- Optimalizační evaluační problém - Zjistěte nejlepší možné C(Y) takové, že R(I,Y).
Algoritmus
- Schematický postup řešení určitého problém, 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
- 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.
Stav algoritmu
- Nechť:
- X={x1, x2, ...,xn} je množnina konfiguračních proměnných
- Z={z1, z2, ...,zn} je množnia vnitřních proměnných algoritmu A řešícího I.
- Pak každé ohodnocení s proměnných X a Z je stav algoritmu.
Algoritmizace × programování
- Algoritmizace
- tvorba algoritmu pro daný problém
- Výsledkem je algoritmus, může být zapsán vývojovým diagramem, pseudokódem nebo i slovně.
- Programování
- Zápis algoritmu v konkrétním prog. jazyce
- Výsledkem je zdrojový kód.
