Algoritmus

Algoritmy jsou starší než počítače. Lidé po staletí sní o strojích, které za člověka odvedou práci, a to i duševní.

Jeden z nejstarších algoritmů, které dnes v programech používáme je euklidův algoritmus. Můžeme jít však ještě dále do minulosti - čtyři tisíce let stará sumerská hliněná tabulka nalezena poblíž Bagdádu popisuje schéma nezkráceného dělení.

Slovo algoritmus je odvozené od perského matematika Al-Chorezmího žijícího v 9. století, autora spisu Hisáb al-džabr wal-l-mugábala obsahující postupy pro ruční výpočty.

Algoritmus je omezená sekvence kroků k řešení určitého problému.

Pojmy

Invariant

invariant, neboli tvrzení, které platí po celou dobu výpočtu. Důkaz: Obvyklý způsob důkazu invariantů je indukce podle počtu kroků výpočtu.


Analýza algoritmů

Inkrementální: řeší jak se změní výstup, když na konec vstupu přidáme další prvek.

Stabilní: pokud kdykoliv jsou si prvky s1 a s2 rovny, tak jejich vzájemné pořadí na výstupu se shoduje s jejich pořadím na vstupu.

Na místě (In-place): Paměť O(1)

Rychlost algoritmu

Asymptotická složitost.

Volba algoritmů

Při volbě algoritmu nutno zohlednit:

  • Jaké jsou požadavky na vstupní / výstupní data?
  • Jaká je velikost vstupních / výstupních dat, tj. pro jaká n problém řeším?
  • Požaduji exaktní / přibližné řešení? Jak jsem schopen ověřit kvalitu přibližného řešení?
  • Je problém řešitelný pro libovolnou konfiguraci vstupních dat?
  • Existují speciální případy, které musí být řešeny zvlášt’ nebo je lze zanedbat?
  • Lze problém efektivně převést na jiný problém?
  • Jak má být problém rychle vyřešen, tj. on-line, nebo mohu čekat sekundy, minuty, hodiny či dny?
  • Jak dlouho má vývoj aplikace trvat, tj. kolik času a financí je do řešení problému možno investovat?
  • O jaký typ problému se jedná, nepatří mezi NP problémy?
  • Lze urychlit / vylepšit řešení volbou vhodných datových struktur? Lze urychlit / vylepšit řešení předzpracováním dat?


Související