Damiánova zahrádka :3

Základy algoritmizace

4 min read

Algoritmizace

Algoritmus

  • Přesný návod či postup, kterým lze vyřešit daný typ úlohy.
  • Měl by být co nejednoduší
  • Pojem algoritmus se nejčastěji objevuje při programování, kdy se jím myslí teoretický princip řešení problému
  • 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ř. kuchařský recept. Zpravidla však na algoritmy klademe určitá omezení.

Vlastnosti

  1. Jednoduchost (elementárnost)
    • Skládá se z konečného počtu jednoduchých kroků
  2. Konečnost (rezultativnost)
    • Každý algoritmus musí skončit v konečném počtu kroků.
    • Počet kroků může být libovolně velký, ale musí být vždy konečný
    • Postupy, které tuto podmínku nesplňují se mohou nazývat výpočetní metody (např. reaktivní proces, který průběžně reaguje s okolním prostředím)
  3. Obecnost
    • algoritmus řeší všechny úlohy daného typu
    • má širokou množinu možných vstupů
  4. Určitost (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.
  5. Korektnost
    • algoritmus skončí pro libovolná (korektní) data správným výsledkem v konečném množství kroků.
  6. Výstup
    • 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ší

Základní konstrukce

  • kroky jdou za sebou
a = 5
b = 6
c = a + b //před c vždy musí být už definované a a b

větvení algoritmu

  • if, ifelse
if(vek>18){
print("vstup povolen");
}

Cykly

  • bez podmínky - for
    • 3 parametry - int i = 0; i<5;i++
    • prvním parametrem je deklarace řídící proměnné cyklu, nastavena na hodnotu 0. druhý parametr je podmínka, po jakou dobu bude cyklus běžet. třetí parametr je jakým způsobem se bude řídící proměnná měnit po každém cyklu
  • s podmínkou na začátku - while
  • s podmínkou na konci - do

Způsoby zapsání algoritmu

  1. Písemně
    • Postup se napíše slovně na kus papíru
  2. Diagramem
    • Grafické znázornění jednotlivých kroků, pracovního postupu nebo nějakého procesu
  3. Programovacím jazykem
    • Zápis algoritmů, jež mohou být provedeny na počítači
    • Nazývá se program

tady končila šmídova přednáška pro nás, ale předchozí ročníky tam měli ještě tohle

Metody návrhu

  • Shora dolů – postup řešení rozkládáme na jednodušší operace
  • 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ů.

Dělení algoritmů

Iterativní a rekurzivní algoritmy

  1. Iterativní algoritmy
    • Iterativní algoritmus je takový, který spočívá v opakování určité své části (bloku).
  2. Rekurzivní algoritmy
    • Rekurzivní algoritmus naproti tomu opakuje kód prostřednictvím volání sebe sama
    • Každý rekurzivní algoritmus lze převést do iterativní podoby.
    • Výhoda rekurzivních algoritmů je v jejich snadno čitelném a kompaktním zápisu. Nevýhodou je spotřeba dodatečných systémových prostředků pro udržení jednotlivých rekurzivních volání.

Deterministické a nedeterministické algoritmy

  • Deterministický algoritmus – Algoritmus, který má v každém svém kroku právě jednu možnost, jak pokračovat. Nedeterministický jich má více.

Sériové, paralelní a distribuované algoritmy

  • Sériový algoritmus vykonává všechny kroky v sérii (jeden po druhém)
  • Paralelní algoritmus tyto kroky vykonává zároveň (ve více vláknech)
  • Distribuovaný algoritmus kroky vykovává zároveň na více strojích

Asymptotická složitost algoritmu

  • Charakterizuje počet provedených operací v závislosti na velikosti dat

Typy programovacích jazyků

Dle míry abstrakce

  1. Vyšší programovací jazyky (většina jazyků)
    • Procedurální (imperativní)
    • Strukturované (např. C, BASIC, Cobol)
    • Objektově orientované (např. Smalltalk, Java)
    • Neprocedurální (deklarativní)
    • Funkcionální (např. Lisp, Haskell)
    • Logické (např. Prolog, Gödel)
  2. Nižší programovací jazyky (např. jazyk symbolických adres, částečně VHDL)

Dle způsobu překladu a spuštění

  1. Kompilované programovací jazyky (např. Pascal, C, Java, Cobol)

    • Před spuštěním jsou nejprve kompletně přeloženy kompilátorem
    • Výsledkem je větší rychlost, ale také větší náročnost na správně zapsaný kód

  2. Interpretované programovací jazyky (např. BASIC, Perl, Python, shell, Ruby)

    • Pouze interpretované (z toho důvodu jsou pomalejší – proto většina jazyků má alespoň nějakou jinou možnost, pokud nejsou stejně zpomalované něčím jiným, jako třeba shell)
    • Překládané do mezikódu, nikoli do strojového kódu počítače (např. Java, Python)
    • Překládané do strojového kódu - po spuštění za běhu programu počítače (např. Java, pokud se použije systém JIT)

    Toto členění není absolutní, řada programovacích jazyků existuje v implementaci jak interpretované, tak kompilované (například zmíněná Java). Navíc jsou oba postupy někdy kombinovány, zdrojový kód je nejprve kompilován do mezikódu, který je poté interpretován.

Graph View

Backlinks