Algoritmus

Z MiS

Verze z 24. 5. 2012, 00:02; Spravce (diskuse | příspěvky)

Přejít na: navigace, hledání

Obsah

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)

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).

Schematický postup řešení určitého problém, který je konečný, určitý, korektní a obecný.

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.

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.

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ě.