12. Základy programování

Programování, algoritmizace úloh

Programování je proces od návrhu řešení problému pomocí výpočetní techniky ke spustitelnému počítačovému programu. Zahrnuje analýzu problému, jeho pochopení, nalezení algoritmu a zápis zdrojového kódu v programovacím jazyce. Je třeba vytvořit takovou sekvenci příkazů, které počítač provede a automatizovaně tak vyřeší úlohu. S tvorbou programu souvisí i testování a ladění programu a jeho následná údržba (opravy případných chyb, dodatečné úpravy a přizpůsobení požadavkům uživatelů).

Algoritmizace úloh je převedení zadané úlohy do posloupnosti kroků, které je třeba udělat, aby byla úloha vyřešena. Jedna úloha může být řešena různými algoritmy (například výběr největšího čísla z několika postupně zadávaných čísel lze udělat až po načtení všech čísel, nebo již v průběhu načítání – program si pamatuje vždy jen největší ze zatím načtených čísel a porovnává ho s tím, které načítá jako poslední).

Vlastnosti algoritmů, zápis algoritmů, struktury, vývojové diagramy, složitost algoritmů

Různé algoritmy mohou řešit stejný problém, ale jejich časová nebo paměťová složitost se může lišit. Časová složitost algoritmu je dána dobou výpočtu potřebnou pro zpracování daného objemu dat. Paměťová složitost udává velikost paměti využívané při tomto výpočtu. Při určování složitosti se zpravidla pracuje s celými čísly. Algoritmu se přiřazuje funkce, která udává počet operací algoritmu (nebo velikost využité paměti) v závislosti na rozsahu vstupních dat. Jestliže počet zpracovávaných znaků nebo čísel je n, časová složitost algoritmu může být například konstantní, lineární - značí se O(n), kvadratická - O(n² ) apod.

Příklad: Nalezení zadaného čísla c ve vzestupně setříděné posloupnosti n čísel.

Algoritmus, který postupně projde všechna čísla v posloupnosti od nejmenšího po největší a zastaví se buď na konci, nebo ve chvíli, kdy narazil na hledané číslo, má složitost O(n) – v nejhorším případě totiž projde všechna čísla až na konec (hledané číslo je až na konci, nebo v posloupnosti vůbec není).

Jiný algoritmus neprochází čísla postupně, ale začne s číslem, které je v posloupnosti uprostřed. Pokud je hledané číslo menší (větší) než prostřední číslo, algoritmus dále pracuje pouze s levou (pravou) polovinou posloupnosti. Opět se podívá na prostřední číslo vybrané poloviny a vybere její polovinu (celkově tedy čtvrtinu), se kterou bude pokračovat. Tento algoritmus neprojde všechna čísla, ale pouze čísla v polovině, čtvrtině, osmině atd., dokud nenajde číslo c, nebo posloupnost už nelze rozpůlit (hledané číslo v posloupnosti není). Jeho složitost je O(log2n) – udělá nejvýše tolik kroků, kolikrát lze n rozdělit na polovinu.

Nevhodně navržený algoritmus může při velkém objemu vstupních dat počítat tak dlouho, že se uživatel výsledku nedočká, proto je výběr algoritmu velmi důležitý. Algoritmy lze zapisovat pomocí vývojového diagramu. Důležitými řídícími prvky algoritmů jsou různé cykly, podmínky a skoky.

Programovací jazyk, procedura, funkce

Programovací jazyk je prostředek pro zápis algoritmů pro počítač. Programátor pomocí programovacího jazyka formuluje postup řešení problému a počítač jednotlivé kroky postupu interpretuje technickými prostředky.

Existuje velké množství a mnoho typů programovacích jazyků. Podle filozofie fungování programovacího jazyka se dělí:

procedurální

strukturované (C, BASIC)
objektově orientované (Java), někdy navíc událostmi řízené (Scratch)
deklarativní
funkcionální (Lisp)
logické (Prolog)

Programovací jazyky jako C++, Python, Object Pascal kombinují strukturované i objektové programování.

Procedury a funkce jsou části programu, které se při běhu programu provádí vícekrát, někdy i s různými vstupními hodnotami (parametry). Proto se procedura nebo funkce napíše odděleně od hlavní části programu a při běhu programu se pouze opakovaně spouští (volá). Někdy program využívá procedury nebo funkce, které vůbec nejsou součástí jeho kódu (například má k dispozici tzv. vestavěnou knihovnu s již hotovými funkcemi). Procedura pouze vykoná uvedené příkazy, funkce ještě navíc vrací hodnotu (nebo více hodnot) na místo, ze kterého byla z programu zavolána. Vrácenou (vypočítanou) hodnotu lze například uložit do proměnné, nebo použít pro nějaký další výpočet. Příkladem procedury může být nakreslení kružnice s daným středem a poloměrem, příkladem funkce výpočet druhé mocniny daného čísla (vrací výsledek).

Datové struktury (integer, real, boolean, string, char), využití mod a div

Datové typy v programování definují typ hodnot, kterých smí nabývat proměnná nebo konstanta. S proměnnými jednotlivých datových typů lze provádět různé operace. Někdy jde o stejnou operaci, ale různé provedení (například + u proměnných typu integer nebo string).

Pomocí základních datových typů lze tvořit složené typy. Příklady datových typů:

Integer – celé číslo, rozsah závisí na šířce datové sběrnice (16 bitů umožňuje číslo od -32768 do

32767). Při překročení rozsahu dochází k přetečení: 32767 + 1 = -32768. Čísla typu integer lze

sčítat, odčítat, násobit, dělit, dělit se zbytkem (div – výsledkem je celočíselný podíl, zbytek se

neuvádí), získat zbytek po dělení (mod). Operace mod se používá například při převodech

mezi různými číselnými soustavami, při kontrole dělitelnosti (například správně zadané rodné

číslo je dělitelné 11) nebo při šifrování.

Real – reálné číslo, zapisuje se s desetinnou tečkou, má větší rozsah než číslo typu integer, je

reprezentováno pomocí dvou celých čísel ve tvaru mantisa * 2exponent.

Boolean – smí nabývat hodnot True nebo False (logické ANO/NE)

Char – znak, například a, A, @, ?, :

String – textový řetězec, skládá se z více znaků, lze s ním provádět různé operace, například zřetězení

(+), zjištění délky řetězce (length)

Složené datové typy: pole, seznam, záznam (může obsahovat různé datové typy)

Zvláštní datové typy: ukazatel, soubor, komplexní číslo

Rekurze a její využití

Situace, kdy funkce uvnitř svého těla volá sama sebe, se nazývá rekurzivní volání funkce. Používá se při implementaci metody "rozděl a panuj", kdy se složitější problém rozdělí na několik menších úloh stejného typu, jako byla ta původní.

Je vhodná například pro hledání nejkratší cesty, výherní strategie apod., kdy se zkouší různé možnosti pokračování. Metoda prohledávání s návratem se nazývá backtracking. Program se po prohledání možností do konce nebo do určité úrovně vrací zpět a zkouší jinou cestu. Rekurzi lze použít i k některým výpočtům, například výpočet faktoriálu, kde n! vypočítáme jako n-krát (n-1)! atd, až 1! = 1.

Rekurze může být časově náročná, proto je třeba toto řešení volit pouze v případě, kdy je k tomu skutečně důvod. Například při jejím použití pro backtracking se v praxi obvykle nezkouší všechny možnosti, ale pouze ty, kde zkoušení má smysl, a program je ještě nezkoušel (tzv. backtracking s ořezáváním, například hledáme umístění 8 dam na šachovnici tak, aby se neohrožovaly – nemá smysl zkoušet umístit další dámu na řádek nebo sloupec, kde už nějaká dáma je).

Ladění programů

Ladění programu je součást vývoje programu, kdy programátor zkouší, jak program funguje, a hledá případné chyby. Pokud program několikrát proběhne bez chyby, ještě to nemusí znamenat jeho bezchybnost. Proto je při ladění třeba vyzkoušet různé hodnoty vstupovaných dat, a zejména různé výjimky, ke kterým může dojít. Například pokud uživatel programu zadá nesmyslnou hodnotu na vstupu, program na to musí nějak vhodně zareagovat, a neprovádět nesmyslný výpočet. V případě aritmetických výpočtů je například vhodné hlídat velikost vstupovaných hodnot (přetečení), znaménka (nelze odmocnit záporné číslo), nulu (nulou nelze dělit) apod.

POJMY: Full-HD, PCI-E, torrent

Full-HD je rozlišení televize (nebo monitoru) 1920 x 1080 (poměr stran 16:9). Někdy je Full HD označena schopnost přijímat signál s rozlišením 1080p a zobrazovat ho v původním rozlišení, případně schopnost zvětšení obsahu o menším rozlišení na 1080p.

PCI-E = PCI Express je standard systémové sběrnice (náhrada za paralelní PCI a AGP). Používá sériový port, který umožňuje dále zvyšovat frekvenci, na které sběrnice pracuje (a tím i přenosovou rychlost). Rychlost posledních verzí je: PCI-E 4.0 nabízí 2 GB/s v obou směrech komunikace, celkem tedy PCI-E 4.0 x 16 umožňuje rychlost 64 GB/s, PCI-E 5.0 x 16 nabízí 64 GB/s v jednom směru, v obou je to dvojnásobek.

BitTorrent je nástroj pro P2P distribuci souborů. Datové přenosy jsou rozkládány mezi všechny klienty, kteří si data stahují. Název BitTorrent se používá jako název distribučního protokolu, originální klientské aplikace a typu souboru s příponou .torrent. Soubor s příponou .torrent obsahuje metadata o sdílených souborech. Torrent je také označení pro sdílená data. Torrent soubory jsou zveřejňovány na webových stránkách, tzv. tracker (PHP skript) udržuje seznamy klientů, kteří torrent aktuálně sdílejí.