24. Teorie programování

Teorie programování, algoritmus a jeho vlastnosti, vývojový diagram, procedura, funkce, ukázka zápisu jednoduchého algoritmu pomocí VD

Předchozí okruh: 23. Komprese dat

Programování

• proces od návrhu řešení problému pomocí výpočetní techniky ke spustitelnému počítačovému programu
• cílem programování je nalezení takové sekvence příkazů (algoritmu), které může počítač provést, a zadaný úkol tak vyřešit

Programovací jazyk

• prostředek pro zápis algoritmů, jež mohou být provedeny na počítači
• zápis algoritmu v programovacím jazyku se nazývá program
• komunikační nástroj mezi programátorem a počítačem

1. generace – strojový kód, instrukce v šestnáctkové soustavě, pro člověka nečitelné
2. generace – assemblery, jde o strojový kód, kde mají instrukce slovní označení (kódy), pro člověka čitelnější
3. generace – dnešní jazyky, zaměřují se na čitelnost pro člověka, zdrojový kód připomíná matematický zápis

• dělení dle míry abstrakce
  • nižší programovací jazyky
    • zápisem se přibližuje tomu, jak funguje počítač
  • vyšší programovací jazyky
    • zápisem se přibližuje tomu, jak přemýšlí člověk

• dělení dle způsobu spuštění
  • kompilovaný
    • překládá zdrojový kód do strojových instrukcí najednou před vykonáním programu
    • výhody: jsou rychlejší, chyby se odhalí před spuštěním
    • nevýhody: závislost na platformě, program zkompilovaný v Linuxu pravděpodobně nebude fungovat ve Windows, bude nutné ho znovu zkompilovat ve Windows
    • C, C++, Pascal
  • interpretovaný
    • překládá zdrojový kód do strojových instrukcí postupně v průběhu vykonávání programu, proto jsou pomalejší
    • výhody: nezávislost na platformě, vyšší stabilita, jednodušší vývoj
    • nevýhody: nízká rychlost, obtížné hledání chyb
    • Python, PHP
  • s virtuálním strojem
    • kód je nejprve přeložen do jednoduchého mezikódu, který je poté interpretován
    • kombinuje výhody kompilovaných a interpretovaných jazyků a odstraňuje jejich nevýhody
    • C#, Java

Algoritmus

• přesný postup, jak vyřešit určitý problém (jak ze vstupních dat dostat požadovaná výstupní data)

• vlastnosti algoritmu:
  • elementárnost (jednoduchost)
    • skládá se z konečného počtu jednoduchých kroků
  • finitivnost (konečnost)
    • musí skončit v konečném počtu kroků
  • univerzálnost (obecnost)
    • 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 čísel“)
  • determinovanost
    • každý krok by měl být jednoznačný a přesně definovaný
    • výjimkou je vyžadovaná náhodnost (např. simulace hodu kostkou, generování hesla)
  • resultativnost (výstup)
    • má alespoň jeden výstup, tedy odpověď na problém

• příklady algoritmů
  • Euklidův algoritmus
    • jeden z nejstarších
    • umí určit největšího společného dělitele dvou přirozených čísel
  • Erathostenovo síto
    • nalezne všechna prvočísla menší než je zadaná horní mez
    • vezme prvočíslo a vyřadí jeho násobky, jako síto prosívá celou zadanou množinu čísel

• rekurzivní algoritmus
  • volá sám sebe
• různé řídící cykly
  • if
  • if, else
  • switch
  • while
  • do, while
  • for

• časová složitost algoritmu
  • závisí na velikosti vstupu, např.: množství čísel k setřídění
  • záleží na výkonu počítače i na použitém programovacím jazyce

Vývojové diagramy

• slouží ke grafickému znázornění jednotlivých kroků algoritmu
• značky
  • začátek – zelený ovál
  • konec – červený ovál
  • šipky určující směr zpracování, čáry (pravé úhly), kruh spojuje několik šipek
  • výkonný blok – obdélník
  • rozhodovací blok – kosočtverec
  • vstup – rovnoběžník
  • výstup
  • cyklování
• diagramy z vyučování semináře programování

Následující okruh: 25. Informační etika