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?