Algoritmus

Z MiS
(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
(Zápis algoritmu: Oprava formátování)
(Algoritmus: Doplnění konečnosti.)
 
(Není zobrazena 1 mezilehlá verze od 1 uživatele.)
Řádka 21: Řádka 21:
 
#'''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ů.
 +
#*: ''Pro každou platnou vstupní posloupnost tedy lze nalézt konkrétní konečné číslo, které je nejzazším limitem počtu provedených kroků.'' (Algoritmus může skončit dříve.)
 +
#*: <div class="Priklad">Příklad: Pro desetiprvkovou posloupnost na vstupu skončí postup nejpozději po <tt>50&nbsp;000</tt>&nbsp;krocích. Pro posloupnost milionu prvků na vstupu skončí nejpozději po <tt>5.10<sup>9</sup></tt> krocích. Pro miliardu prvků nebo jakékoli jiné velké číslo bude výpočet trvat ještě déle, ale vždy lze nalézt konkrétní konečné číslo, které je limitem počtu kroků pro danou posloupnost. Pak postup je konečný.</div>
 
#'''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í) vstupní data správným výsledkem.
 
#'''Obecnost'''
 
#'''Obecnost'''
 
#* algoritmus řeší všechny úlohy daného typu.
 
#* algoritmus řeší všechny úlohy daného typu.
Řádka 63: Řádka 65:
 
* Viz série článků [http://programujte.com/clanek/2005080105-vyvojove-diagramy-1-dil/ Vývojové diagramy na Programujte.com].
 
* 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]].
 
* Viz stránka [[Vývojové diagramy]].
 +
 +
 +
=== Příklad zápisu algoritmu pseudokódem ===
 +
<div class="Priklad">
 +
Jako ukázku uvedeme algoritmus pro výběr nejmenšího prvku ze seznamu čísel.
 +
 +
Zápis pseudokódem by mohl vypadat třeba takto:
 +
 +
<pre>
 +
if seznam.isEmpty():
 +
print "Error"
 +
 +
vysledek := seznam[1]
 +
 +
for i := 2 to seznam.size():
 +
if vysledek > seznam[i]:
 +
vysledek := seznam[i]
 +
 +
return vysledek
 +
</pre>
 +
</div>
  
 
== Algoritmizace × programování ==
 
== Algoritmizace × programování ==

Aktuální verze z 18. 10. 2024, 08:01


Obsah

Úloha

Problém

Popis problému zahrnuje

Algoritmus

Schematický postup řešení určitého problému, 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ů.
      Pro každou platnou vstupní posloupnost tedy lze nalézt konkrétní konečné číslo, které je nejzazším limitem počtu provedených kroků. (Algoritmus může skončit dříve.)
      Příklad: Pro desetiprvkovou posloupnost na vstupu skončí postup nejpozději po 50 000 krocích. Pro posloupnost milionu prvků na vstupu skončí nejpozději po 5.109 krocích. Pro miliardu prvků nebo jakékoli jiné velké číslo bude výpočet trvat ještě déle, ale vždy lze nalézt konkrétní konečné číslo, které je limitem počtu kroků pro danou posloupnost. Pak postup je konečný.
  2. Určitost (determinovanost)
    • všechny kroky algoritmu jsou přesně definovány.
  3. Korektnost
    • algoritmus skončí pro libovolná (korektní) vstupní data správným výsledkem.
  4. Obecnost
    • algoritmus řeší všechny úlohy daného typu.
Někdy se jako vlastnosti uvádí také

Stav algoritmu

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

Zápis algoritmu

Algoritmus můžeme zapsat následujícími způsoby:

V přirozeném jazyce
Pseudokódem
V některém programovacím jazyce
Pomocí vývojových diagramů


Příklad zápisu algoritmu pseudokódem

Jako ukázku uvedeme algoritmus pro výběr nejmenšího prvku ze seznamu čísel.

Zápis pseudokódem by mohl vypadat třeba takto:

if seznam.isEmpty():
	print "Error"

vysledek := seznam[1]

for i := 2 to seznam.size():
	if vysledek > seznam[i]:
		vysledek := seznam[i]
		
return vysledek

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é

Osobní nástroje
Jmenné prostory
Varianty
Akce
Výuka
Navigace
Nástroje