Algoritmus, vlastnosti, zápis, algoritmická složitost
Algoritmus je konečná posloupnost přesně definovaných kroků (instrukcí), které vedou k vyřešení určitého problému. Popisuje postup tak, aby ho mohl provést člověk i počítač, nezávisle na konkrétním programovacím jazyce.
Slovo "algoritmus" pochází z přepisu jména perského matematika al-Chvárizmí (cca 780–850 n. l.), který napsal knihu o aritmetických postupech. Z arabského "al-Khwarizmi" se latinizací stal "Algorismi", a odtud dnešní "algoritmus".
Moderní teorii algoritmů formalizoval ve 20. století Alan Turing (Turingův stroj) a později Donald Knuth ve své monumentální sérii The Art of Computer Programming.
| Algoritmus | Program | |
|---|---|---|
| Co je | Abstraktní postup | Konkrétní implementace |
| Forma | Pseudokód, diagram, slova | Zdrojový kód v jazyce |
| Závisí na | Logice problému | Jazyce, prostředí, knihovnách |
| Příklad | "Najdi nejmenší prvek pole" | Math.min(...arr) v JavaScriptu |
Algoritmus je něco jako recept: program je konkrétní vaření podle něj.
| Algoritmus | Heuristika | |
|---|---|---|
| Garance | Vrátí správný výsledek | Pravděpodobně blízko správného |
| Použití | Když máš čas a chceš přesnost | Když potřebuješ rychlost |
| Příklad | Dijkstra: nejkratší cesta | A*: rychlá ale ne vždy optimální |
Klasické vlastnosti, kterými musí každý algoritmus splňovat (7):
| Vlastnost | Popis |
|---|---|
| Konečnost (finitnost) | Musí skončit po konečném počtu kroků. Nesmí běžet věčně. |
| Resultativnost (výslednost) | Musí vrátit výsledek, nebo oznámit, že řešení neexistuje. |
| Jednoznačnost (determinismus) | Každý krok je přesně definován. Stejný vstup = stejný výstup. |
| Vstupnost | Má jasně definované vstupy, žádné skryté/externí proměnné. |
| Obecnost | Řeší celou třídu problémů, ne jen jeden konkrétní případ. |
| Správnost | Prokazatelně dává správný výsledek pro všechny vstupy. |
| Efektivnost | Co nejméně kroků a paměti. Doběhne v rozumném čase. |
Některé algoritmy záměrně používají pseudonáhodnost (Quicksort s náhodným pivotem, hashing). Stále jsou deterministické: pokud zafixuješ random seed, dostaneš stejný výsledek. Při různých seedech ale různé pořadí operací.