Algoritmy

Algoritmem budeme nazývat jakýkoliv postup (návod, soupis kroků), který bude splňovat následující kritéria:

1. Elementárnost
   algoritmus se skládá z jednoduchých, tzv. elementárních, kroků.
2. Hromadnost, obecnost, univerzálnost
   algoritmus slouží k řešení celé třídy (skupiny) navzájem si podobných úloh. Úlohy jsou si podobné, ale liší se vstupními daty. Tzn. neřeší „jak spočítat 3x7“, ale řeší, „jak spočítat součin dvou celých čísel“.
3. Konečnost
   pro každá přípustná data algoritmus po konečném počtu kroků (může být libovolně velký) skončí.
4. Determinovanost algoritmu
   každý krok uvedený v algoritmu musí být jednoznačně a přesně definován. V každé situaci musí být napřosto zřejmé, co a jak se má provést a jak má provádění algoritmu pokračovat.
5. Částečná (parciální) správnost
   jestliže algoritmus skončí, pak výsledek je správný (tj. nestane se, že pro nějaká přípustná vstupní data algoritmus skončí se špatným výsledkem).
6. Výstup, resultativnost
   algoritmus musí mít alespoň jeden výstup. Říkáme, že algoritmus vede od zpracování hodnot k výstupu. Můžeme algoritmus chápat také jako funkci, která nám ke vstupu přiřadí příslušný výstup.
7. Mechanické provádění
   algoritmus může provádět každý bez hlubší znalosti řešené úlohy, např. procesor (umí jen základní sadu příkazů) nebo ten kdo bude vykonávat algoritmus (nemusí to být nutně počítač).

Druhy algoritmů

Algoritmů dnes existuje celá řada a proto existuje klasifikace (roztřídění) do skupin. Rozdělení ale neplatí direktivně, a je běžné, že jeden algoritmus může patřit současně i do více skupin. Mezi důležité skupiny algoritmů patří:

1. Rekurzivní algoritmy, které v rámci cyklu volají samy sebe.
2. Pravděpodobnostní algoritmy provádějí některá rozhodnutí náhodně.
3. Paralelní algoritmy lze využít v případě, kdy můžeme algoritmus rozdělit na více samostatných úloh a zpracovávat je odděleně na více strojích. Výhodou je časová úspora.
4. Genetické algoritmy, které pracují na základě napodobování biologických evolučních procesů. Pro vědu jsou přirozené procesy probíhající v přírodě velkým vzorem, protože mohou být chápány a aplikovány i jako možná řešení daného problému.
5. Heuristické algoritmy, jejichž cílem není nalézt přesné řešení daného problému. Tyto algoritmy se používají v situacích, kdy dostupné zdroje nepostačují na využití exaktních algoritmů.

Ověřování správnosti algoritmu

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 k 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čí).

Dokazování konečnosti 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ý.

Kvantitativní ukazatele kvality algoritmů

Mezi dva nejdůležitější kvantitativní ukazatele kvality algoritmů patří:

• operační složitost
• paměťová složitost

Příklady:

Zadání: Pole S obsahuje n vzestupně seřazených prvků. Je třeba nalézt funkci typu Boolean, která vrátí hodnotu true, pokud zadaný prvek v poli S existuje, a hodnotu false v opačném případě.

Řešení

Řešení hrubou silou - sekvenční hledání

function sekvencni_hledani(hodnota, pole) {

    var existuje = false;

    var i = 0;

    while(i<pole.lenght && !existuje) {

          if(pole[i] === hodnota) {

                existuje = true;

          }

          i++;

    }

    return existuje;

}

Nejhorší případ: prvek v poli není, pak tělo cyklu proběhne (n-1) krát a bude provedeno n porovnání.

 

Cvičení: Je-li pole uspořádáno, lze využít efektivnější binární půlení, napište tento algoritmus.

function binarni_hledani(hodnota, pole) {

    var existuje = false;

    var i = l = 0;

    var r = pole.length;

    while(!ret && r >= 1) {

          i = Math.round((l+r)/2);

          if(hodnota === pole[i]) {

                existuje = true;

          } else {

                if(hodnota > pole[i]) {

                      l = i+1;

                } else {

                      r = i-1;

                }

          }

    }

    return existuje;

}

Opět časově nejnáročnější při neexistenci prvku v poli. Cyklus while však proběhne jen (log₂ n) krát. Algoritmus je však mírně paměťově náročnější.

 

Důležitost analýzy složitosti algoritmů

Ukážeme na dvou příkladech tisku Fibonacciho posloupnosti:  Fibonacci (Leonardo z Pisa) řešil reprodukční problém - kolik párů králíků může vzniknout za rok z jednoho páru, jestliže budeme předpokládat, že každý pár každý měsíc plodí nový pár, který se začne množit od druhého měsíce?

f₀ = 0; f₁ = 1 a f_n = f_n-1 + f_n-2 pro n > 1.

 

Varianta 1: Rekurzivní výpočet n-tého Fibonacciho čísla:

function fib(n) {

    return (n == 0) ? 0:((n == 1) ? 1 : fib(n-1) + fib(n-2));

}

 

function printFib(n) {

    for(var i = 1; i <= n; i++) {

          console.log(i + " " + fib(i));    

    }

}

 

Varianta 2: Fibonaccioho posloupnost bez rekurze:

function prinFib2(n) {

    var p0 = p1 = p = 1;

    for (var i = 1; i <= n; i++) {

          console.log(i + " " + p0);

          p = p1;

          p1 = p0 + p1;

          p0 = p;

    }

}

Pod složitostí algoritmu rozumíme tedy dobu prováděného algoritmu - časovou složitost a rozsah použité operační paměti - paměťovou náročnost (složitost).