V první kapitole jsme si neformálně zavedli pojmy problém a algoritmus pro jeho řešení, které jsme na počítači prováděli pomocí programů.
Jako příklad uveďme problém řazení. Pro tento problém známe algoritmy řazení
- výběrem
- vkládáním
- bublinkové
- Shellovo
- haldou
- slučováním
- dělením
Programy mohly množinu řazených prvků uchovávat pomocí
- pole
- spojového seznamu
Jednotlivé algoritmy a jejich programové realizace jsme analyzovali z pohledu jejich časové případně paměťové náročnosti.
Položme jsme si otázku jak je to s problémem samotným. Na to musíme přesněji odpovědět na otázku co je to problém. Další přirozenou otázkou je, zda-li každý problém má algoritmus pro svoje řešení, jinými slovy je-li algoritmicky řešitelný. Víme-li, že tomu tak je, zřejmě má smysl se ptát jaký algoritmus je optimální.
Předpokládejme, že bychom pro problém řazení znali jenom první tři z uvedených algoritmů. To by mohlo vést k domněnce, že nejlepší algoritmus řazení je O(n2). Víme však, že všechny další uvedené algoritmy pro porovnávací řazení jsou efektivnější. Neexistuje však další, dosud neznámý, algoritmus pro problém řazení n prvků, který je ještě efektivnější? Jak je to s jinými problémy? Jak jsou „těžké“, rozumíme-li tím množství „práce“ potřebné na jejich vyřešení? A exituje vůbec pro daný problém nějaký algoritmus? Abychom mohli studovat naznačené otázky musíme pojem problému formalizovat.
Problém Q definujeme jako binární relaci nad množinou instancí problému I a množinou řešení S.
Pro problém řazení například přirozených čísel je množina instancí množina všech jednoprvkových, dvouprvkových, ... posloupností a množina řešení je množina těch posloupností, které jsou seřazeny. Uvedené zobrazení potom můžeme obvyklým způsobem vyjádřit jak je uvedeno na obr
.
Vidíme, že různé instance problému řazení mohou mít stejné řešení, ale ne více řešení a v tomto případě je problém vyjádřen funkcí.
Uvažujme však problém nalezení nejkratší cesty v grafu. Instancí problému je konkrétní graf a dva jeho vrcholy. Pro každou takovou trojici je řešením posloupnost vrcholů na nejkratší cestě, včetně prázdné posloupnosti, označující neexistenci cesty mezi zadanými vrcholy. Nyní jde obecně o zobrazení, protože nejkratších, stejně dlouhých, cest mezi dvěma vrcholy v grafu může být více.