ALGORITMIZACE

Question 1

ALGORITMUS

Answer 1

• Algoritmus je přesný postup, který se využívá pro řešení nějaké úlohy.
• Algoritmus obecně splňuje různé požadavky:
• Konečnost - Každá algoritmus musí skončit v konečném počtu kroků (dle většiny autorů, můžou existovat I tzv. Reaktivní algoritmy). Tento počet může být libovolně vysoký (podle rozsahu a hodnot vstupních údajů), ale pro daný jednotlivý vstup musí být konečný.
• Obecnost - Algoritmus neřeší jeden konkrétní problém, ale obecnou třídu obdobných problémů
• Determinovanost - Každý krok algoritmu musí být jednoznačně a přesně definován. V každé situaci musí být naprosto jasné, co a jak se má provést, jak má po provedení algoritmus pokračovat atd. Stejný vstup by u algoritmu vždy měl vrátit stejný výsledek. Některé algoritmy determinované nejsou - např. pravděpodobnostní algoritmy mají ve svém výpočtu zahrnut náhodný faktor.
• Výstup - Algoritmus má alespoň jeden výstup, která je v požadovaném vztahu k zadaným vstupům. Vrácením tohoto výstupu je vytvořena odpoveď na problém, jež daný algoritmus řeší.

Question 2

VLASTNOSTI ALGORITMU

Answer 2

• Algoritmus obecně splňuje různé požadavky:
  
  • Konečnost - Každá algoritmus musí skončit v konečném počtu kroků (dle většiny autorů, můžou existovat I tzv. Reaktivní algoritmy). Tento počet může být libovolně vysoký (podle rozsahu a hodnot vstupních údajů), ale pro daný jednotlivý vstup musí být konečný.
  • Obecnost - Algoritmus neřeší jeden konkrétní problém, ale obecnou třídu obdobných problémů
  • Determinovanost - Každý krok algoritmu musí být jednoznačně a přesně definován. V každé situaci musí být naprosto jasné, co a jak se má provést, jak má po provedení algoritmus pokračovat atd. Stejný vstup by u algoritmu vždy měl vrátit stejný výsledek. Některé algoritmy determinované nejsou - např. pravděpodobnostní algoritmy mají ve svém výpočtu zahrnut náhodný faktor.
  • Výstup - Algoritmus má alespoň jeden výstup, která je v požadovaném vztahu k zadaným vstupům. Vrácením tohoto výstupu je vytvořena odpoveď na problém, jež daný algoritmus řeší.
  • Dále se uvádí:
    
    • Elementárnost
    • Výstup - Algoritmus má alespoň jeden výstup, který tvoří odpověď na problém
    • Srozumitelnost
    • Kvalitativní vlastnosti
      
      • Přehlednost
      • Časová složitost
        Prostorová složitost

Question 3

ZPŮSOBY VYJÁDŘENÍ ALGORITMU

Answer 3

• Základní způsoby vyjádření algoritmu jsou:
  - Slovně - přirozeným jazykem (může vést k nejasnostem)
  - Matematicky
  - Graficky
  - Pomocí vývojového diagramu
  - Počítačově - např. programovacím jazykme
  • Vývojový diagram:

Question 4

ALGORITMIZACE ZÁKLADNÍCH TYPŮ ÚLOH

Answer 4

• Algoritmizace je postup tvorby algoritmu pro řešení nějakého problému.
• Algoritmizaci lze rozdělit do několika etap:
  
  • Formulace problému — V této etapě je nutné přesně formulovat:
    
    • Výchozí hodnoty
    • Požadované výsledky, jejich formu a přesnost řešení
  • Analýza úlohy
    
    • Při analýze úlohy ověřujeme, zda je úloha vůbec řešitelná
    • Dále je nutné určit, zda k řešení úlohy stačí dostupné výchozí hodnoty
    • Identifikujeme možná řešení, a pokud jich má úloha více, vybereme to nejlepší
  • Vytvoření algoritmu úlohy
    
    • Sestavíme jednotlivé kroky, jež je nutné pro úspěšné vyřešení úlohy
  • Sestavení programu
    
    • Dle určených kroků, algoritmus sestavíme ve vybraném programovacím jazyku
    • Kompilací vytvoříme spustitelný program
  • Odladění programu
    
    • Cílem odladění je odstranění chyb z programu
      Syntaktické chyby jsou odhaleny překladačem, ty logické musíme odhalit testováním

Question 5

ZPRACOVÁNÍ ŘADY DAT

Answer 5

• Je nutné zvolit vhodný algoritmus
  Složitost my měla být maximálně lineárně logaritmická

Question 6

ZPRACOVÁNÍ SOUBORU DAT

Answer 6

• Je nutné mít ukazatel na soubor
  Je nutné soubor otevřít a zavřít

Question 7

ALGORITMIZACE ŘAZENÍ

Answer 7

• Kvadratické metody
  - Přímý výběr - selection sort
  - Bublinkové řazení - bubble sort
  - Přímé vkládání - insertion sort
  
  • Lineárně logaritmické metody
    
    • Řazení haldou - heapsort
    • Quick sort
    • Stromové řazení
    • Řazení slučováním - merge sort
  • Lineární metody
    
    • Řazení množinou (multimnožinou)
      Hašování

Question 8

ALGORITMIZACE ROZVOJŮ NEKONEČNÝCH ŘAD

Answer 8

• Aproximací Tayolorovým polynomem
  
  • Předpokladem je existence bodu, v němž známe jeho funkčí hodnota a hodnoty všech derivací
    Funkcí aproximujeme konstantou, pak přímkou, následně parabolou atd. Dokud nedostaneme požadovanou přesnost