www.manualy.net
logo
Originální stránky pro originální lidi. Výrobky chráněných dílen
Google

Algoritmy: Teoretický úvod

25.2. 2006 Vebloud Algoritmy

Co je to vlastně algoritmus. Lze vymyslet algoritmus na cokoliv? Jak poznám, který algoritmus je rychlejší nebo lepší? Vlastnosti algoritmů. Druhy algoritmů.

Historie pojmu algoritmus a jeho původ

Slovo algoritmus pochází ze jména významného perského matematika žijícího v první polovině 9. století (cca 780–840 n. l.), kterým byl Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī (أبو عبد الله محمد بن موسى الخوارزمي) (doslova „Otec Abdulláha, Mohameda, syn Mojžíšův, pocházející z města Khwārizm.“ Region Khwārizm se nachází jižně od Aralského moře). Tento učenec ve svém díle prakticky vytvořil systém arabských číslic a základy algebry (konkrétně metody řešení lineárních a kvadratických rovnic), jejíž název pochází přímo z titulu tohoto díla (Kitūb al-jabr waāl-muqūbala). Jeho jméno bylo do latiny převedeno jako algorismus, a původně znamenalo: „provádění aritmetiky pomocí arabských číslic.“

Postupem času se kvůli neznalosti původu slova jeho podoba měnila, záměnou arabského kořene s kořenem řeckého slova αριθμός (arithmos) se z algorismu stal algoritmus. (Později bylo v některých jazycích včetně češtiny th změněno na t, v katalánštině se vrátilo s.). Toto slovo se používalo jako označení různých matematických postupů. Slovo algoritmus v dnešním významu se používá až zhruba od 20. století.

Algoritmus bývá často definován jako: „přesný návod či postup, kterým lze vyřešit daný typ úlohy.“ Toto je sice na první pohled pravdivá, ale při bližším prozkoumání nepřesná definice. Například některé matematické postupy by této definici vyhovovaly, ale nejsou algoritmy. Přesné znění definice algoritmu zní: „Algoritmus je procedura proveditelná Turingovým strojem.“

Turingův stroj je teoretický model počítače popsaný matematikem Alanem Turingem. Skládá se z procesorové jednotky, tvořené konečným automatem a programu ve tvaru pravidel přechodové funkce a potenciálně nekonečné pásky pro zápis mezivýsledků a vstupů dat.

Tímto končím historický a etymologický úvod a začínám se věnovat vlastnostem algoritmů.

Vlastnosti algoritmů:

Algoritmus obvykle pracuje s nějakými vstupy, veličinami, které jsou mu předány před započetím jeho provádění, nebo v průběhu jeho činnosti. Vstupy mají definované množiny hodnot, jichž mohou nabývat. Algoritmus má alespoň jeden výstup, veličinu, která je v požadovaném vztahu k zadaným vstupům, a tím tvoří odpověď na problém, který algoritmus řeší.

Algoritmus musí být:

  • Konečný – Každý algoritmus musí skončit v konečném počtu kroků. Tento počet kroků může být libovolně velký (podle rozsahu a hodnot vstupních údajů), ale pro každý jednotlivý vstup musí být konečný. Postupy, které tuto podmínku nesplňují, se mohou nazývat výpočetní metody. Speciálním příkladem nekonečné výpočetní metody je reaktivní proces, který průběžně reaguje s okolním prostředím.
  • Deterministický – Každý krok algoritmu musí být jednoznačně a přesně definován; v každé situaci musí být naprosto zřejmé, co a jak se má provést, jak má provádění algoritmu pokračovat. Protože běžný jazyk obvykle neposkytuje naprostou přesnost a jednoznačnost vyjadřování, byly pro zápis algoritmů navrženy programovací jazyky, ve kterých má každý příkaz jasně definovaný význam. Vyjádření výpočetní metody v programovacím jazyce se nazývá program.
  • Efektivní – Obecně požadujeme, aby algoritmus byl efektivní, v tom smyslu, že požadujeme, aby každá operace požadovaná algoritmem, byla dostatečně jednoduchá na to, aby mohla být alespoň v principu provedena v konečném čase pouze s použitím tužky a papíru.
  • Obecný – Algoritmus neřeší jeden konkrétní problém (např. „jak spočítat 3×7“), ale obecnou třídu obdobných problémů (např. „jak spočítat součin dvou celých čísel“).
  • Rezultativní – Algoritmus při zadání vstupních dat vždy vrátí nějaký výsledek (může se jednat i jen o chybové hlášení).

Správnost algoritmu

Algoritmus je správný tehdy, když pro všechny údaje splňující vstupní podmínku se proces zastaví a výstupní údaje splňují výstupní podmínku. K ověření správnosti algoritmu nestačí vyzkoušet reakci algoritmu na konečný počet vstupních dat, i když se to tak v praxi často dělá a takové ověření o správnosti algoritmu leccos vypoví. Není ovšem dokázáno, že se algoritmus při neočekávané kombinaci vstupních dat nezhroutí. Pro ověřování správnosti algoritmu neexistuje univerzální metoda, algoritmus by měl být matematicky dokázán sledem předem známých kroků (operací), které nevyvratitelně vedou pro všechna přípustná data ke správnému výsledku úlohy. Je zřejmé, že takový algoritmus je pak korektním řešením úlohy. Algoritmus můžeme považovat za korektní, pokud není opomenuta žádná z možností zpracování dat při průchodu algoritmem. Algoritmus je částečně (parciálně) správný, právě když platí, že pokud skončí, vydá správný výsledek. K dokázání částečné správnosti výpočtu můžeme použít tzv. invariant – tvrzení, které platí po celou dobu výpočtu. Nutné je také ověřit konečnost algoritmu (pro všechna přípustná data algoritmus po konečném počtu kroků skončí).

Konečnost algoritmu

Konečnost algoritmu je často intuitivně zřejmá tím, že se pro vstupní data nemůže algoritmus zacyklit. Matematicky lze dokázat konečnost algoritmu takto: Pokud najdeme způsob, který každý stav výpočtu ohodnotí přirozeným číslem, a ukážeme, že provedením jednoho kroku algoritmu se tato hodnota zmenší, je jasné, že algoritmus po konečném počtu kroků skončí, neboť interval počtu průchodů algoritmem je konečný.

Druhy algoritmů

Algoritmy můžeme klasifikovat různými způsoby. Mezi důležité druhy algoritmů patří:

  • Rekurzivní algoritmy, které využívají (volají) samy sebe.
  • Hladové algoritmy se k řešení propracovávají po jednotlivých rozhodnutích, která, jakmile jsou jednou učiněna, už nejsou dále revidována.
  • Algoritmy typu rozděl a panuj dělí problém na menší podproblémy, na něž se rekurzivně aplikují (až po triviální podproblémy, které lze vyřešit přímo), po čemž se dílčí řešení vhodným způsobem sloučí.
  • Algoritmy dynamického programování pracují tak, že postupně řeší části problému od nejjednodušších po složitější s tím, že využívají výsledky již vyřešených jednodušších podproblémů. Mnoho úloh se řeší převedením na grafovou úlohu a aplikací příslušného grafového algoritmu.
  • Pravděpodobnostní algoritmy (někdy též probabilistické) provádějí některá rozhodnutí náhodně či pseudonáhodně.
  • V případě, že máme k dispozici více počítačů (procesorů nebo jader), můžeme úlohu mezi ně rozdělit, což nám umožní ji vyřešit rychleji; tomuto cíli se věnují paralelní algoritmy.
  • Genetické algoritmy pracují na základě napodobování biologických evolučních procesů, postupným „pěstováním“ nejlepších řešení pomocí mutací a křížení. V genetickém programování se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápany jako možná řešení daného problému.
  • Heuristické algoritmy si za cíl nekladou nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používají se v situacích, kdy dostupné zdroje (např. čas) nepostačují na využití exaktních algoritmů (nebo pokud nejsou žádné vhodné exaktní algoritmy vůbec známy).

Přitom jeden algoritmus může patřit zároveň do více skupin; například může být zároveň rekurzivní a typu rozděl a panuj.

Reprezentace a zápis algoritmů:

  • Slovním popisem – slovní popis v přirozeném jazyce
  • Vývojovým diagramem (blokové schéma) – grafické znázornění algoritmu řešení úlohy jednotnými značkami a zkratkami (tento způsob kombinovaný se slovním popisem zde budu používat, tudíž přibude i článek na toto téma).
  • Strukturogramy – používá obdobné symboly ale přesnější, tento systém přesně splňuje podmínky důležité pro strukturované programování
  • Datově orientované diagramy HIPO – (z angl. Hierarchy plus Input- Process- Output), je grafickým vyjádřením funkčního členění problému, struktury dat a postupu řešení problému při různém stupni podrobnosti.
  • Rozhodovací tabulky – používané při velmi složitých větveních.

Dalším kritériem pro algoritmy je jejich efektivita, respektive rychlost nebo naopak složitost. Složitost algoritmů je ovšem téma na celý článek a to hned na ten příští.

Zdroje:

Napište váš názor na článek.