Vlastnosti, resp. požadavky na algoritmus

Algoritmus je přesný návod či postup, kterým lze vyřešit daný typ úlohy. Pojem algoritmu se nejčastěji objevuje při programování, kdy se jím myslí teoretický princip řešení problému (oproti přesnému zápisu v konkrétním programovacím jazyce). Obecně se ale algoritmus může objevit v jakémkoli jiném vědeckém odvětví. Jako jistý druh algoritmu se může chápat i např. kuchyňský recept. V užším smyslu se slovem algoritmus rozumí pouze takové postupy, které splňují některé silnější požadavky

Konečnost (finitnost)

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. Někteří autoři však mezi algoritmy zahrnují i takovéto postupy.

Obecnost (hromadnost, masovost, univerzálnost)

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 číšek), má širokou množinu možných vstupů.

Determinovanost

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, takže pro stejné vstupy dostaneme pokaždé stejné výsledky. 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. Některé algoritmy ale determinované nejsou, pravděpodobnostní algoritmy v sobě mají zahrnutu náhodu.

Výstup (resultativnost)

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 vede od zpracování hodnot k výstupu)

Elementámost

Algoritmus se skládá z konečného počtu jednoduchých (elementárních) kroků.

V praxi jsou proto předmětem zájmu hlavně takové algoritmy, které jsou v nějakém smyslu kvalitní. Takové algoritmy splňují různá kritéria, měřená např. počtem kroků potřebných pro běh algoritmu, jednoduchost, efektivitu či eleganci. Problematikou efektivity algoritmů, tzn. metodami, jak z několika známých algoritmů řešících konkrétní problém vybrat ten nej lepší, se zabývají odvětví informatiky nazývané algoritmická analýza a teorie složitosti.

Základní algoritmické konstrukce a jejich charakteristika

Algoritmus se navrhuje několika možnými způsoby:

  • Shora dolů – postup řešení rozkládáme na jednodušší operace, až dospějeme k elementárním krokům.
  • Zdola nahoru – z elementárních kroků vytváříme prostředky, které nakonec umožní zvládnout požadovaný problém.
  • Kombinace obou – obvyklý postup shora dolů doplníme „částečným krokem“ zdola nahoru tím, že se například použijí knihovny funkcí, vyšší programovací jazyk nebo systém pro vytváření programů (CASE).

Nejužívanější metody návrhů algoritmů jsou následující:

Rozděl a panuj

Klasický případ aplikace postupu odshora dolů. 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čí.

Zpracovává se množina V složená z n údajů. Tato množinu se rozdělí na k disjunktních podmnožin, které se zpracují každá zvlášť. Získané dílčí výsledky se pak spojí a odvodí se z nich řešení pro celou množinu V.

Klasickým případem je binární vyhledávání, nebo quicksort.

Hladový algoritmus

Velice přímočarý přístup k řešení určité třídy optimalizačních úloh.

Zpracovává se množina V složená z n údajů. Úkolem je najít podmnožinu W množiny V, která vyhovuje určitým podmínkám a přitom optimalizuje předepsanou účelovou funkci. Jakákoliv množina W, vyhovující daným podmínkám, se nazývá přípustné řešení. Přípustné řešení, pro které nabývá účelová funkce optimální hodnoty, se nazývá optimální řešení.

Hladový algoritmus se skládá z kroků, které budou procházet jednotlivé prvky z V, a v každém kroku rozhodne, zda se daný prvek hodí do optimálního řešení. Prvky V bude vybírat v pořadí určeném jistou výběrovou procedurou. Výběrová procedura bude založená na nějaké optimalizační míře – funkci, která může být odvozena od účelové funkce. V každém kroku ale musíme dostat přípustné řešení. Jakmile je učiněno takové rozhodnutí, už není dále revidováno. Příkladem je třeba hledání nejkratší cesty grafu.

Dynamické programování

Dynamické programování funguje obdobně jako hladový algoritmus, ale negeneruje se pouze jedna posloupnost. Zkoumají se všechny posloupnosti, které by mohly být optimální a vylučují se ty, které optimální nebudou. Používají se dílčí výsledky, které byly získané již dříve během výpočtu.

Nejjednodušší a nejméně účinnou je metoda hrubé síly – vygenerují se všechny možné posloupnosti a pak se vybere ta nejlepší. Za pomoci dynamického programování se automaticky negenerují ty možnosti, které určitě nejsou optimální.
Opírá se o princip optimality: Optimální posloupnost rozhodnutí má tu vlastnost, že ať je počáteční stav a rozhodnutí jakékoliv, musí být všechna následující rozhodnutí optimální vzhledem k výsledkům rozhodnutí prvního.

Typickým příkladem využití dynamického programování jsou grafové úlohy a a jejich příslušné grafové algoritmy.

Hledání s návratem (backtracking)

Hledání s návratem založené na prohledávání stavového prostoru problému. Též se nazývá metoda pokusů a oprav, metoda zpětného sledování, metoda prohledávání do hloubky.

Metodu je možné použít v případě, že řešením je vektor (x1,…,xn) jehož jednotlivé složky vybíráme z množiny Si, xiSi. Zpravidla je třeba najít n-tici, která optimalizuje nějakou účelovou funkci P(x1,…,xn). Můžou se ale také hledat všechny n-tice, které tuto podmínku splňují. Metoda vytváří n-tice jednu složku po druhé. Přitom používá účelovou funkci (nebo nějakou vhodnou pomocnou funkci) a pro každou nově vytvořenou složku testuje, zda by taková n-tice vůbec mohla být optimální nebo splňovat dané podmínky. Jestliže pro nějaké xi žádaný vektor (x1,…,xi) nemůže být optimální, není třeba už žádný takový vektor testovat a vezmeme další možnou hodnotu i-té složky. Pokud jsou vyčerpány všechny hodnoty i-té složky, vrátí se metoda zpět o jeden krok a zkouší další možnou hodnotu xi-1.

Příkladem je třeba chůze koně celou šachovnicí.

Způsoby vyjádření algoritmu

Algoritmus lze vyjádřit:

  • slovně: jednotlivé kroky postupu jsou vyjádřeny větami v přirozeném jazyce
  • graficky: jednotlivé kroky jsou popsány grafickými značkami se slovním popisem, například pomocí tzv. vývojových diagramů
  • matematicky: soustavou rovnic, vztahem mezi veličinami
  • programem: jednotlivé kroky jsou popsány instrukcemi určitého procesoru

Sekvence
je posloupnost příkazů, které se postupně provedou

  • Start a konec ovál
  • Jednotlivé příkazy (čti,piš) obdélníky

Větvení
umožňuje rozdělit program do 2 větví podle toho, zda je nebo není splněna podmínka

  • Podmínka IF kosočtverec

Větvení s prázdnou akcí
umožňuje provést příkaz jenom tehdy, když je splněna podmínka

  • Opět kosočtverec – jedna větev s akcí druhá bez – následně spojení

Cyklus s podmínkou na začátku
Když podmínka není na počátku splněna, cyklus nemusí proběhnout ani jednou.

Cyklus s podmínkou na konci
Tento cyklus musí proběhnout aspoň jednou.

Cyklus se známým počtem průchodů
Cyklus proběhne n krát
v obecném případě (pro i od m do n) proběhne (n-m+1) krát
pokud m>n tak neproběhne ani jednou.

Pojmy syntax a sémantika

Syntaxe definuje strukturu a způsob zápisu. V přirozeném jazyce hovoříme o gramatice.

Sémantika popisuje význam, a to nejčastěji pomocí přirozeného jazyka.

Program, programové konstrukce (vztah k algoritmickým konstrukcím)

Programování = zakódování algoritmu do zvoleného programovacího jazyka

Algoritmizace = proces vytváření a sestavování algoritmů

Efektivnost algoritmu

danou úlohu řeší více algoritmů, vybíráme efektivnějsší podle určitých kritérií:

  • časové: úloha vyřešena v kratším čase (uvažujeme strojový čas tj. počet instrukcí procesoru)
  • paměťové: spotřeba paměti
  • přehlednost, srozumitelnost: (důležité pro další vývoj a úpravy)

Programovací jazyk = umělý jazyk jenž se používá pro definování sekvence programových příkazů, které lze zpracovat na počítači. Algoritmus má obecnou povahu, zatímco implementace algoritmu v určitém programovacím jazyku je ryze konkrétní.

Dělení programovacích jazyků

Nižší programovací jazyky

jsou jazyky primitivní, jejichž instrukce odpovídají příkazům procesoru. To znamená, že procesor bude vykonávat ty instrukce, které programátor napíše. Jsou závislé na svém procesoru a nepřenositelné na jiný procesor.
V praxi to vypadá tak, že programátor musí vypisovat vše. Pak i jednoduchý program máneúměrně složitý zdrojový kód. Výhodou je, že programátor má takto přístup i k funkcím počítače, které by měl ve vyšším programovacím jazyce nedosažitelné. Lépe tedy využije jeho schopnosti.

Patří sem:

  • strojový kód (to, co uvidíte, když otevřete obsah „exe“ souboru v textovém editoru). Strojový kód = Soubor číslicových instrukcí, které je procesor počítače schopen rozpoznat a uskutečnit.
  • jazyk symbolických adres (Assembler) – je velice blízký strojovému kódu

Vyšší programovací jazyky

jsou podstatně srozumitelnější, jejich struktura je logická, nejsou závislé na strojových principech počítače. Do strojového kódu se převádějí kompilátorem (případně se rovnou spouštějí interpretrem). V praxi je vyšší programovací jazyk vše, co není Assembler (například jazyk C++, Pascal, Basic, Delphi..)

Programovací jazyky dále dělíme na :

  • kompilované
  • interpretované

Kompilované jazyky

jsou nejdříve celé přeloženy a až potom mohou být spuštěny. Jsou rychlejší, mají vyšší nároky na formální správnost kódu. Překládají se kompilátorem, výsledkem překladu je (většinou) .exe soubor. Patří sem většina klasických programovacích jazyků.
Teoreticky může mít jeden programovací jazyk verzi jak  interpretovanou, tak i kompilovanou.

Interpretované jazyky

jsou překládány až za běhu programu. Jsou pomalejší, ale nemají tak velké požadavky. Překládají se interpretem, ten instrukce zároveň při překladu provádí. Hlavní nevýhodou těchto jazyků je, že se musejí vždy spouštět v interpretu. Do této skupiny patří například Basic, skriptovací jazyky (PHP, Python, Perl …).

Další způsoby dělení programovacích jazyků

Programovací jazyky můžeme dále dělit na jazyky, které podporují:

  • programování strukturované (např. Pascal)
  • objektově orientované programování (OOP) – např. Visual Basic, Delphi

Specifika vývoje programů pro různé operační systémy