I. Algoritmus, prostředky pro zápis algoritmu, algoritmické konstrukce. Složitost algoritmu, příklady algoritmů, algoritmicky neřešitelné problémy.

Question 1

Co je to algoritmus?

Answer 1

Postup při řešení určité třídy úloh, který je tvořen seznamem jednoznačně definovaných příkazů a zaručuje, že pro každou přípustnou kombinaci vstupních dat se po provedení konečného počtu kroků dospějě k požadovaným výsledkům.
Algoritmus pracuje se vstupy, veličinami, které jsou mu předány před započetím jeho provádění nebo v průběhu jeho činnosti. Vstupy mají definované množiny hodnot, jichž mohou nabývat.
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, jenž algoritmus řeší.

Question 2

Jaké jsou vlastnosti algoritmu?

Answer 2

Vlastnosti:
● Hromadnost - měnitelná vstupní data
● Determinovanost - každý krok je jednoznačně definován
● Konečnost a resultativnost - pro přípustná vstupní data se po provedení konečného počtu kroků dojde k požadovaným výsledkům

Question 3

Jaké jsou prostředky pro zápis algoritmu?

Answer 3

Prostředky pro zápis algoritmu:
● Programovací jazyk
● Slovní popis
● Vývojový diagram
● UML action diagram
● Strukturogramy
● Datově orientované diagramy HIPO
● Rozhodovací tabulky
● Pseudokód

Question 4

Programovací jazyk (podotázka Jaké jsou prostředky pro zápis algoritmu?)

Answer 4

Porgram je předpis pro provedení určitých akcí počítačem zapsaný v programovacím jazyku (formální jazyk s definovanou syntaxí a sémantikou, který je zcela jednoznačný). Programovací jazyky mohou být kompilované (do strojového kódu) nebo interpretované pomocí jiného programu (například shell, JVM)

Question 5

Slovní popis (podotázka Jaké jsou prostředky pro zápis algoritmu?)

Answer 5

Slovní popis - slovní popis v přirozeném jazyce

Question 6

Vývojový diagram (podotázka Jaké jsou prostředky pro zápis algoritmu?)

Answer 6

Vývojový diagram - grafické znázornění algoritmu řešení úlohy jednotnými značkami a zkratkami

Question 7

Strukturogramy (podotázka Jaké jsou prostředky pro zápis algoritmu?)

Answer 7

Strukturogramy - strukturogram je grafické znázornění algoritmu pomocí 3 základních programových struktur (posloupnost, opakování a větvení).

Question 8

Datově orientované diagramy HIPO (podotázka Jaké jsou prostředky pro zápis algoritmu?)

Answer 8

Datově orientované diagramy HIPO - (z angl. hierarchical input process output model) je grafickým vyjádřením funkčního členění problému, struktury dat a postupu řešení problému při různém stupni podrobnosti.

Question 9

Rozhodovací tabulky (podotázka Jaké jsou prostředky pro zápis algoritmu?)

Answer 9

Rozhodovací tabulky - používané při složitých větveních. Např. obrázek - Rozhodovací tabulka se smíšenou volbou

Question 10

Pseudokód (podotázka Jaké jsou prostředky pro zápis algoritmu?)

Answer 10

Pseudokód je neformální způsob zápisu algoritmu, který používá strukturní konvence programovacích jazyků, avšak nezahrnuje detailní syntaxi, jako jsou deklarace proměnných, podprocedury nebo jiné konstrukce specifické pro konkrétní programovací jazyk. Zápis je pro srozumitelnost částečně doplněn popisy podrobností v přirozeném jazyce nebo kompaktně vyjádřeným matematickým zápisem.

Příklady pseudokódu
Následující příklad ilustruje rozdíl mezi pseudokódem a programovacím jazykem:
Programovací jazyk PHP:

if(je_platne($cislo_kk)) { spust_prenos($cislo_kk, $objednavka);

} else { zobraz_chybu();

}

?>

• Pseudokód:*
• *pokud** je číslo kreditní karty platné

proveď přenos, založený na číslech kreditní karty a objednávky
jinak

zobraz chybové hlášení
konec podmínky

Question 11

Základní konstrukce algoritmu

Answer 11

1. Strukturované programování
2. Rekurze
3. Princip seznamů

Question 12

Popište strukturováné kédování (podotázka základní konstrukce algoritmu)

Answer 12

Strukturované programování

Podstatou je to, že rozklad úlohy na podúlohy se omezuje pouze na tři konstrukce, na sekvenci, selekci a iteraci - a žádné jiné konstrukce rozkladu nejsou použity.

Selekce = úloha se rozloží na dvě (nebo několik) podúloh, úloha se vyřeší tím, že se provede právě jedna podúloha (v závislosti na nějaké podmínce). Příklad: v závislosti na hodnotě diskriminantu počítám buď reálné, nebo komplexní kořeny.

Sekvence = úloha se rozloží na podúlohy, které se provádějí postupně za sebou. Příklad: kvadratickou rovnici vyřeším, když nejdříve vypočtu diskriminant a pak vypočtu kořeny.

Iterace = řešení úlohy sestává z opakovaného provádění podúlohy. Příklad: chůze je iterace kroků.

Tento koncept je vhodný pro větší kompaktní programy. Konstrukce rozkladu odpovídají řídicím konstrukcím programovacích jazyků, takže syntéza je jednoduchá - těžiště práce leží na tom, kdo provádí rozklad.

Question 13

Rekurze (podotázka základní konstrukce algoritmu)

Answer 13

V programování rekurze představuje opakované vnořené volání stejné funkce (podprogramu), v takovém případě se hovoří o rekurzivní funkci (funkce volá sama sebe). Nedílnou součástí rekurzivní funkce musí být ukončující podmínka určující, kdy se má vnořování zastavit. Jelikož bývá nejčastějším zdrojem chyb, je třeba ji navrhnout dostatečně robustním způsobem a prověřit veškeré možné stavy. Pro uplatnění rekurzivních algoritmů je zapotřebí, aby programovací jazyk umožňoval volání podprogramu ještě před ukončením jeho předchozího volání. Po každém kroku volání sebe sama musí dojít ke zjednodušení problému. Pokud nenastane koncová situace, provede se rekurzivní krok. Každý algoritmus využívající rekurzi lze přepsat do nerekurzivního tvaru při použití zásobníku nebo jiné paměťové struktury.

Nepřímá rekurze -> Alespoň 2 podprogramy R a S. Podprogram R volá S a ten opět volá R.

Přímá rekurze -> Např. Výpočet faktoriálu nebo nejvyššího spol. Dělitele (NSD) => podprogram volá sám sebe

Rekurzi používáme

• Prohledávání do hloubky (backtracking) – řešení grafových úloh Metoda „rozděl a panuj“
• Některé třídící algoritmy (quicksort, mergesort), Hanojské věže
• Aritmetické výrazy

Question 14

Princip seznamů (podotázka základní konstrukce algoritmu)

Answer 14

Princip seznamů

Seznam je základní dynamická datová struktura. Je to posloupnost záznamů stejného typu, které jsou navzájem lineárně provázány vzájemnými odkazy pomocí ukazatelůnebo referencí.Aby byl seznam lineární, nesmí existovat cykly ve vzájemných odkazech. Lineární seznamy mohou existovat jednosměrné a obousměrné. V jednosměrném seznamu odkazuje každá položka na položku následující a v obousměrném seznamu odkazuje položka na následující i předcházející položky. Zavádí se také ukazatel nebo reference na aktuální (vybraný) prvek seznamu. Na konci (a začátku) seznamu musí být definována zarážka označující konec seznamu.

Question 15

Lineárně spojové seznamy

Answer 15

Lineární spojové seznamy

Základní dynamickou datovou strukturou je lineární spojový seznam. Je to posloupnost záznamů stejného typu seřazených za sebe. V programech zastává často podobnou funkci jako jednorozměrné pole. Na rozdíl od pole nám neumožňuje přímý přístup k jednotlivým položkám pomocí indexů, LSS musíme vždy procházet sekvenčně od začátku.

Question 16

Druhy lineárně spojových seznamů

Answer 16

Druhy:

• Jednosměrný
  
  • Do každého uzlu seznamu je uložena hodnota a jeden ukazatel ukazuje na následující uzel.
  • Poslední ukazatel ukazuje na hodnotu nil, která signalizuje konec seznamu.
• Obousměrný
  
  • Každý ukazatel obsahuje dva ukazatele – na svého předchůdce a na následníka v seznamu.
  • Paměťově náročnější, ale umožňuje zato procházet seznamem oběma směry a snáze se také provádí některé další akce (vypouštění prvků).

Nejčastěji používanými spojovými seznamy jsou tzv. zásobníky, fronty a uspořádané seznamy. Liší se především způsobem rozšiřování (přidávání prvků) a zkracování (odebírání prvků).

Přidání prvku do zásobníku -> na začátek, do fronty -> na konec.
Nelineární jsou pak stromy a grafy

Question 17

Kódování

Answer 17

Kódování je způsob reprezentace textu a jiných dat pomocí binární abecedy {0,1}.

Na základě použitého kódování je určena délka jednoho znaku (ASCII - 1B, UTF-8 - až 4B) a význam všech hodnot, jichž může daná jednotka nabývat - tj. všech znaků. Obdobně je nutné postupovat při kódování jiných (například obrazových a zvukových) dat. V tom případě lze použít jednoduchá kódování bez komprese (BMP, WAV) nebo komprimované formáty (MP4, JPEG, HEVC).

Question 18

Kódování vstupu a výstupu

Answer 18

Většinou předpokládáme, že vstupy i výstupy jsou kódovány jako slova v nějaké abecedě Σ.

Příklad: Například u problému tříděníbychom mohli zvolit jako abecedu Σ = {0,1, 2, 3, 4, 5, 6, 7, 8, 9, ,}.

Vstupem by pak mohlo být například slovo:826, 13, 3901, 101, 128, 562A výstupem slovo:13, 101, 128, 562, 826, 3901

Poznámka: Ne každé slovo ze Σ* musí reprezentovat nějaký vstup. Kódování bychom ale měli volit tak, abychom byli schopni snadno poznat ta slova, která nějaký vstup reprezentují.

Question 19

Binární programování

Answer 19

Můžeme se omezit na případ, kdy jsou vstupy i výstupy kódovány jako slova v abecedě {0, 1} (tj. jako sekvence bitů). Symboly jakékoli jiné abecedy lze reprezentovat jako sekvence bitů.

Příklad: Abeceda {a, b, c, d, e, f, g}:

a 001, b 010, c 011,

d 100, e 101, f 110, g 111

Slovo ‘defb’ pak můžeme reprezentovat jako ‘100101110010’

Question 20

Příkaz goto

Answer 20

Příkaz typu „go to“ – tedy „jdi na (řádek)“ se používal v nestrukturovaných programovacích jazycích. V raných jazycích tohoto stylu byly navíc všechny řádky programu číslované a skoky šlo realizovat pouze uvedením konkrétního čísla řádku, což bylo velmi nepraktické. Později se objevily jazyky využívající tzv. návěští, tedy textová označení míst, kam má program skočit. Typickými zástupci byly například rané verze jazyků FORTRAN a COBOL.

Kvůli nepraktičnosti příkazu skoku „go to“ (ta vězí zejména v tom, že struktura programu nedává prakticky žádnou informaci o jeho vykonávání, což velmi komplikuje jeho ladění) vznikly strukturované jazyky (nebo obecněji – strukturovaný způsob zápisu programů). Jeho hlavním přínosem je fakt, že nahrazuje příkazy skoku pomocí podmíněných cyklů („opakuj, dokud platí podmínka“) a jiných strukturovaných instrukcí, které se do sebe vnořují. Typickými zástupci jsou jazyky C a Pascal.

Question 21

Definice algoritmu

Answer 21

Postup při řešení určité třídy úloh, který je tvořen seznamem jednoznačně definovaných příkazů a zaručuje, že pro každou přípustnou kombinaci vstupních dat se po provedení konečného počtu kroků dospěje k požadovaným výsledkům.

Algoritmus pracuje se vstupy, veličinami, které jsou mu předány před započetím jeho provádění nebo v průběhu jeho činnosti. Vstupy mají definované množiny hodnot, jichž mohou nabývat. 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ší.

Algoritmus může být realizován:

• slovním popisem v přirozeném jazyce
• pseudokódem
• jako počítačový program v nějakém programovacím jazyce
• jako hardwarový obvod

Question 22

Složitost algoritmu

Answer 22

Pod složitostí algoritmu rozumíme dobu prováděného algoritmu (časovou složitost) a rozsah použité operační paměti (prostorovou složitost). Složitost závisí na velikosti vstupních dat, proto ji můžeme popsat jako funkci f(n), kde číslo n udává velikost vstupních dat. Například f(n) = an + b, kde a, b jsou nějaké konstanty, je zápis lineární časové složitosti (složitost roste lineárně s rostoucí velikostí vstupů). Pro porovnání složitostí algoritmů se používá tzv. asymptotická složitost f(n)=O(g(n)), kde pro všechna čísla n od určitého čísla n0 a konstantu c>0 platí: f(n)<=c*g(n). Obdobně lze určit i spodní asymptotickou složitost f(n)=Ω(g(n)).

Za efektivní algoritmy považujeme takové postupy, jejichž složitost je nejvýše polynomiální (tedy n^k [n^127], nikoliv exponenciální k^n [2^n]). Provádění exponenciálních algoritmů či dokonce algoritmů o složitosti O(n!) může už jen při malém navýšení velikosti vstupních dat trvat příliš dlouho na to, aby v době ukončení výpočtu byl výsledek využitelný. Praktickým příkladem využití algoritmů, které jsou za určitých podmínek relativně rychle proveditelné, zatímco za jiných podmínek jsou proveditelné pouze za dlouhou dobu, je moderní kryptografie. Čím je algoritmus složitější, tím menší je vliv navýšení výkonu procesoru při větších vstupních datech.

Question 23

Typy algoritmů

Answer 23

Typy algoritmů

1. Rekurzivní algoritmy
2. Hladové algoritmy
3. Algoritmy typu rozděl a panuj
4. Algoritmy dynamického programování
5. Pravděpodobnostní algoritmy
6. Genetické algoritmy
7. Heuristické algoritmy

Přitom jeden algoritmus může patřit do více skupin; například může být zároveň rekurzivní a typu rozděl a panuj

Question 24

Rekurzivní algoritmy

Answer 24

• Rekurzivní algoritmy – které využívají (volají) samy sebe.

Question 25

Hladové algoritmy

Answer 25

Hladové algoritmy se k řešení propracovávají po jednotlivých rozhodnutích, která už nejsou dále revidována, jakmile jsou jednou učiněna.

Question 26

Algoritmy typu rozděl a panuj

Answer 26

Algoritmy typu rozděl a panuj dělí problém na menší podproblémy, na než se rekurzivně aplikují ( až po triviální podproblémy, které lze vyřešit přímo), po čemž se dílčí řešení vhodným způsobem sloučí.

Question 27

Algoritmy dynamického programování

Answer 27

Algoritmy dynamického programování pracují tak, že postupně řeší části problému od nejjednodušších po složitější s tím, že využívají výsledky již vyřešených jednodušších podproblémů. Moho úloh se řeší převedením na grafovou úlohu a aplikací příslušného grafového algoritmu.

Question 28

Pravděpodobnostní algoritmy

Answer 28

Pravděpodobnostní algoritmy (někdy též probabilistické) provádějí některá rozhodnutí náhodně či pseudonáhodně. V případě, že máme k dispozici více počítačů (procesorů nebo jader), můžeme úlohu mezi ně rozdělit, což nám umožní ji vyřešit rychleji; tomuto cíli se věnují paralelní algoritmy.

Question 29

Genetické algoritmy

Answer 29

Genetické algoritmy - pracují na základě napodobování biologických evolučních procesů, postupným “pěstováním” nejlepších řešení pomocí mutací a křížení. V genetickém programování se tento postup aplikuje přímo na algoritmy (resp. programy), které jsou zde chápány jako možná řešení daného problému.

Question 30

Heuristické algoritmy

Answer 30

Heurisitické algoritmy - si za cíl nekladou nalézt přesné řešení, ale pouze nějaké vhodné přiblížení; používají se v situacích, kdy dostupné zdroje (např. čas) nepostačují na využití exaktních algoritmů (nebo pokud nejsou žádné vhodné exaktní algoritmy známy).

Question 31

známé algoritmy

Answer 31

• Eratosthenovo síto – algoritmus pro nalezení všech prvočísel menších než zadaná horní mez
• Euklidův algoritmus – algoritmus, kterým lze určit největšího společného dělitele dvou přirozených čísel
• Dijkstrův algoritmus – algoritmus sloužící k nalezení nejkratší cesty v grafu.

Question 32

Problém - Co musí být v zadání problému určeno?

Answer 32

Problém

V zadání problému musí být určeno:

• co je množinou možných vstupů
• co je množinou možných výstupů
• jaký je vztah mezi vstupy a výstupy

Question 33

Problém třídění

Answer 33

• Příklad:*
• Vstup: 8, 13, 3, 10, 1, 4*
• Výstup: 1, 3, 4, 8, 10, 13*

Question 34

Rozhodovací problémy

Answer 34

Rozhodovací problémy

Situace, kdy množina výstupů je {Ano,Ne} je poměrně častá. Takovým problémům se říká rozhodovací problémy. Rozhodovací problémy většinou specifikujeme tak, že místo popisu toho, co je výstupem, uvedeme otázku.

Příklad:

Problém „Prvočíselnosti“

• Vstup: Přirozené číslo n.
• Otázka: Je n prvočíslo?

Question 35

Optimalizační problémy

Answer 35

Optimalizační problémy

Dalším speciálním případem jsou tzv. optimalizační problémy. Optimalizační problém je problém, kde je úkolem vybrat z nějaké množiny přípustných řešení takové řešení, které je v nějakém ohledu optimální.

Question 36

Řešení problémů

Answer 36

Algoritmus korektně řeší daný problém, když:

• se pro libovolný vstup daného problému (libovolnou vstupní instanci) po konečném počtu kroků zastaví,
• vyprodukuje výstup z množiny možných výstupů, který vyhovuje podmínkám uvedeným v zadání problému.

Pro jeden problém může existovat celá řada algoritmů, které jej korektně řeší.

Poznámka: Množina vstupních instancí bývá typicky nekonečná.

Question 37

Algoritmicky řešitelné problémy

Answer 37

Předpokládejme, že máme dán nějaký problém P. Jestliže existuje nějaký algoritmus, který řeší problém P, pak říkáme, že problém P je algoritmicky řešitelný. Jestliže P je rozhodovací problém a jestliže existuje nějaký algoritmus, který problém P řeší, pak říkáme, že problém P je rozhodnutelný. Když chceme ukázat, že problém P je algoritmicky řešitelný, stačí ukázat nějaký algoritmus, který ho řeší (a případně ukázat, že daný algoritmus problém P skutečně řeší).

Question 38

Třídy složitosti

Answer 38

Algoritmy můžeme podle f(N) rozřadit do tříd.

• P - polynomiální algoritmus.
• NP - nedeterministicky polynomiálních problémy.
• NP-Complete
• NP-Hard

Question 39

Třídy složitosti

Answer 39

• P - Pokud je rozhodovací problém řešitelný algoritmem o složitosti O(N), pak se jedná o polynomiální algoritmus.
• NP - Pokud pro daný rozhodovací problém neexistuje polynomiální algoritmus, který řešení nalezne, ale existuje polynomiální algoritmus, který řešení ověří, hovoříme o nedeterministicky polynomiálních problémech. Problémy, které patří do této třídy jsou například problém obchodního cestujícího a splnitelnost formule výrokové logiky. Jednou z největších současných otevřených otázek teoretické informatiky je, zda se třídy P a NP rovnají. Vše nasvědčuje tomu, že to pravda není (viz NP-úplnost).
• NP-Complete - Taková podmnožina NP problémů, na jejíž prvky (=NPC problémy) lze převést všechny NP problémy. Patří sem například problém obchodního cestujícího, Hamiltonovy cesty, hledání kliky grafu a obarvení grafu.
• NP-Hard - Obchodní cestující je NP-Hard problém, který je zároveň i NP-C a tedy i NP. NPH problém nemusí být NP, protože nemusí být rozhodovacím problémem. Příkladem takového problému je Halting problém, který je NPH, ale není NPC. Je to považováno za algoritmicky neřešitelný problém.

Question 40

Některé asymptotické složitosti mají i své triviální pojmenování (jsou seřazeny od nejrychlejších k nejpomalejším):

Answer 40

Některé asymptotické složitosti mají i své triviální pojmenování (jsou seřazeny od nejrychlejších k nejpomalejším):

O(1) – konstantní

O(log N) – logaritmická

O(N) – lineární

O(N log N) – lineárně logaritmická

O(N^2) – kvadratická

O(N^3) – kubická

obecně O(N^k) – polynomiální

obecně O(k^N) – exponenciální

O(N!) – faktoriálová

Question 41

Typické příklady časové složitosti

Answer 41

Typické příklady časové složitosti

• O(1) přístup k prvku pole pomocí indexu
• O(log 2 N) vyhledání prvku v seřazeném poli metodou půlení intervalu
• O(N) vyhledání prvku v neseřazeném poli lineárním (sekvenčním) vyhledáváním
• O(N log N) seřazení pole čísel podle velikosti algoritmem Mergesort
• O(N2) diskrétní Fourierova transformace (DFT)
• O(2^N) přesné řešení problému obchodního cestujícího (či jiného NP-úplného problému hrubou silou)

Existují i funkce, u nichž nelze složitost vůbec shora rozumně omezit. Příkladem budiž Ackermannova funkce.

Question 42

Snižování výpočetní složitosti algoritmů

Answer 42

Snahou programátorů je asymptotickou složitost dostat alespoň na polynomiální úroveň, horší složitosti jsou v reálných aplikacích (tedy u vyšších N) nepoužitelné. Typickým příkladem je diskrétní Fourierova transformace (DFT), která v obecném tvaru má asymptotickou složitost O(N2), proto je nevhodná pro transformaci vektorů větších délek. Existuje rychlá verze této transformace označovaná jako FFT (Fast Fourier Transform), která využívá skutečnosti, že pro délky vektorů N=KM (kde K je určeno tzv. radixem transformace 2,4,8,… a M je přirozené číslo), lze tento problém zjednodušit na složitost O(N log N).