Algoritmus, algoritmická složitost

 

Otázka: Algoritmus, algoritmická složitost

Předmět: Programování, Informatika

Přidal(a): Ondřej Rethy

 

Algoritmus

• Z obecného hlediska se jedná o „přesný návod nebo postup pro vyřešení konkrétní úlohy“
• Název je od perského matematika Al-Chorezmí (9. století)
• Teoretický princip řešení programu (nejen programu, ale i například skládání rubikovy kostky)
• Například kuchařka je též algoritmus pro kuchaře na přípravu jídla
• Základní vlastnosti algoritmu
  • Elementárnost
    • Rozložit problém na co nejmenší prvky a ty poté řešit
    • Například úklid pokoje
      • Nejdříve sebrat oblečení, poté utřít prach, poté vyluxuovat, přemístit věci atd.
  • Konečnost
    • Algoritmus musí končit
    • Například úklid pokoje
      • Algoritmus musí někdy dojít k závěru, že je pokoj uklizen
  • Obecnost
    • Algoritmus by měl být obecný, tzn. Aby šel použít na více podobných řešení.
    • Například úklid pokoje
      • Musí jít tedy na všechny typy a rozměry pokojů
  • Determinovanost
    • Stejné úkony udělají za stejný čas
    • Například úklid pokoje
      • Necháme 2 roboty uklízet identický pokoj s identickým nepořádkem => Výsledek bude naprosto identický a za stejný čas
  • Determinismus
    • Každá část znamená přesně danou věc
    • V programování se s tím nemusíme tolik často setkávat
    • Například úklid pokoje
      • Sebrat oblečení musí přesně znamenat sebrat oblečení tím a tím způsobem.
  • Výstup
    • Každý algoritmus by měl být výsledek
    • Například úklid pokoje
      • Chceme aby tento algoritmus měl jako výsledek uklizený pokoj
• Metody návrhu
  • Shora dolů (X->x)
    • postup řešení rozkládáme na jednodušší operace, až dospějeme k elementárním krokům.
  • Zdola nahoru (x->X)
    • 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í nebo vyšší programovací jazyk

 

Algoritmická složitost

• Udává rychlost algoritmu vzhledem k množině vstupních dat
• Dvě hlavní zaměření
  • Paměť
  • Čas
• Faktorialová, exponenciální, kubická, kvadratická, lineární, logaritmická

 

Rekurze

• Je volání funkce z funkce, která ještě nedokončila svůj průběh
• Z důvodu konečnosti musí být volání podmíněné (memory overflow)
• Funkci můžeme volat:
  • Přímo
  • Nepřímo
• Podprogram může být volán jednou nebo vícekrát
  • Lineární rekurze
  • Stromová struktura (zakořeněný strom, binární)

 

Náhodnost

• Náhodné algoritmy se snaží nalézt řešení problému náhodným rozhodováním o svém postupu
• Při vytváření musíme dokončit všechny, směry, kterými se může program vydat
• Program se rozhoduje několika způsoby:
  • V každém uzlu rozhodne postup náhodně
  • Na začátku vybere jeden z deterministických algoritmů
• Generování pseudonáhodných čísel – Kongurentní generátor