Algoritmus

Verze z 23. 5. 2012, 23:58 (zobrazit zdroj) Spravce (diskuse | příspěvky) (Vytvoření stránky)		Aktuální verze z 22. 9. 2021, 12:40 (zobrazit zdroj) Spravce (diskuse | příspěvky) (→Zápis algoritmu: Oprava formátování)
(Není zobrazeno 10 mezilehlých verzí od 1 uživatele.)
Řádka 3:		Řádka 3:
	== Úloha ==		== Úloha ==
	* Zadání, které řešíme.		* Zadání, které řešíme.
−	*Formálním popisem vznikne problém.	+	* Pokud ''úlohu'' popíšeme formálně (matematicky), vznikne ''problém''.
	== Problém ==		== Problém ==
−	=== Definice problému ===	+	; 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
−	=== 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 ==
−	*Schematický postup řešení určitého problémů, který je konečný, určitý, korektní a obecný.	+	<div class="Definice">
		+	Schematický postup řešení určitého problému, který je konečný, určitý, korektní a&nbsp;obecný.
		+	</div>
−	=== 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''' (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.
−	=== Stav algoritmu ===	+	; Někdy se jako vlastnosti uvádí také:
−	*Nechť:	+	* resultativnost &mdash; konečnost a korektnost dohromady
−	** X={x1, x2, ...,xn} je množnina konfiguračních proměnných	+	** Algoritmus skončí pro libovolná (korektní) data v konečném množství kroků správným výsledkem.
−	** Z={z1, z2, ...,zn} je množnia vnitřních proměnných algoritmu A řešícího I.	+	* 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&nbsp;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&nbsp;některém programovacím jazyce
		+	* Například v&nbsp;Javě.
		+	* Oproti pseudokódu už je zde větší množství řádků, které nesouvisí s&nbsp;vysvětlením principu, ale jsou nutné pro spuštění.
		+	* Výhoda je, že tento postup lze v&nbsp;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í ==
−	; Algoritmizace	+
−	* tvorba algoritmu pro daný problém	+	Pojem ''programování'' v užším smyslu je synonymem ''kódování'', tedy přepisu algoritmu do zdrojového kódu.
−	* Výsledkem je algoritmus, může být zapsán [[Vývojový diagram|vývojovým diagramem]], pseudokódem nebo i slovně.	+
−	; Programování	+	Pojem ''programování'' v širším slova smyslu je synonymem pro ''tvorbu software'' a zahrnuje: ''analýzu'' zadání, ''algoritmizaci'' a ''kódování''.
−	* Zápis algoritmu v konkrétním prog. jazyce	+
−	* Výsledkem je zdrojový kód.	+	Viz [[Tvorba software]].
		+
		+	== Viz také ==
		+	* [[Tvorba software]]
		+	* [[Složitost algoritmu]]

---

Aktuální verze z 22. 9. 2021, 12:40

Obsah 1 Úloha 2 Problém 3 Algoritmus 4 Stav algoritmu 5 Zápis algoritmu 6 Algoritmizace × programování 7 Viz také

Ú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

Vlastnosti algoritmu

1. Konečnost
   • algoritmus skončí pro libovolná (korektní) data v konečném množství kroků.
2. Určitost (determinovanost)
   • 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.

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

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.

Viz také

• Tvorba software
• Složitost algoritmu