Algoritmus

Verze z 19. 9. 2013, 11:40 (zobrazit zdroj) Spravce (diskuse | příspěvky) (→Algoritmizace × programování: Přidána analýza zadání) ← Porovnání se starší verzí		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 6 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
	== Algoritmus ==		== Algoritmus ==
−		+	<div class="Definice">
−	Schematický postup řešení určitého problému, který je konečný, určitý, korektní a obecný.	+	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''' (determinovanost)		#'''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é:		; Někdy se jako vlastnosti uvádí také:
Řádka 35:		Řádka 36:
	== Stav algoritmu ==		== Stav algoritmu ==
−	*Nechť:	+	<div class="Definice">
−	** X={x1, x2, ...,xn} je množnina konfiguračních proměnných	+	* Nechť:
−	** Z={z1, z2, ...,zn} je množnia vnitřních proměnných algoritmu A řešícího I.	+	** X={x1, x2, ...,xn} je množina konfiguračních proměnných
−	*Pak každé ohodnocení s proměnných X a Z je stav algoritmu.	+	** 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 ==		== Zápis algoritmu ==
−	Algoritmy zapisujeme:	+	Algoritmus můžeme zapsat následujícími způsoby:
−	* v přirozeném jazyce (slovně)	+
−	* pseudokódem	+	; V&nbsp;přirozeném jazyce
−	** používáme jazyk podobný programovacím jazykům	+	* Česky, anglicky,...
−	** vynecháváme ale některé prvky, které člověk pro pochopení nepotřebuje (složené závorky tam, kde je dostačující odsazení apod.).	+	* Například napíšeme článek, kde se popisuje, jak problém řešit.
−	* v programovacím jazyce	+	* Tento popis by měl být srozumitelný každému člověku.
−	* 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].	+	; 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í ==
−	; Analýza zadání	+
−	* Slovní popis zadání formalizujeme tak, abychom získali problém.	+	Pojem ''programování'' v užším smyslu je synonymem ''kódování'', tedy přepisu algoritmu do zdrojového kódu.
−	* Vstupem je slovní zadání, výstupem je matematicky přesný popis problému.	+
−	; Algoritmizace	+	Pojem ''programování'' v širším slova smyslu je synonymem pro ''tvorbu software'' a zahrnuje: ''analýzu'' zadání, ''algoritmizaci'' a ''kódování''.
−	* Tvorba algoritmu pro daný problém.	+
−	* Vstupem je problém, výsledkem je algoritmus.	+	Viz [[Tvorba software]].
−	; Programování	+
−	* Zápis algoritmu v konkrétním prog. jazyce	+	== Viz také ==
−	* Vstupem je algoritmus, výsledkem je zdrojový kód.	+	* [[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