Algoritmus

Verze z 24. 5. 2012, 00:02 (zobrazit zdroj) Spravce (diskuse | příspěvky) m (→Algoritmus: Oprava vzhledu a překlepů) ← Porovnání se starší verzí		Verze z 24. 5. 2012, 00:03 (zobrazit zdroj) Spravce (diskuse | příspěvky) (→Problém: Vypuštěny typy problémů a další pojmy) Porovnání s novější verzí →
Řádka 6:		Řádka 6:
	== Problém ==		== Problém ==
−	=== Definice problému ===	+	; Definice problému
	*vstupní proměnné		*vstupní proměnné
	*výstupní proměnné		*výstupní proměnné
Řádka 12:		Řádka 12:
	*omezení		*omezení
	*optimalizační kritérium		*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 ==		== Algoritmus ==

---

Verze z 24. 5. 2012, 00:03

Obsah 1 Úloha 2 Problém 3 Algoritmus 3.1 Vlastnosti algoritmu 3.2 Stav algoritmu 4 Algoritmizace × programování

Ú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

Algoritmus

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

Vlastnosti algoritmu

1. Konečnost
   • algoritmus skončí pro libovolná (korektní) data v konečném množství kroků.
2. Určitost
   • všechny kroky algoritmu jsou přesně definovány.
3. Korektnost
   • algoritmus skončí pro libovolná (korektní) data správným výsledkem.
4. 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.