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ů. má konečný počet kroků k řešení/výsledkům.
Algoritmus pracuje se vstupy, ty mají definované množiny hodnot, jichž mohou nabývat.
Algoritmus má alespoň jeden výstup - odpověď na problém, jenž algoritmus řeší.

Question 2

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

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

zápis pomocí: Programovací jazyk

Answer 4

Porgram je předpis pro provedení určitých akcí počítačem.

zapsaný v programovacím jazyku

Programovací jazyky mohou být kompilované (do strojového kódu) nebo interpretované pomocí jiného programu (například shell, JVM)

Question 5

zápis pomocí: Slovní popis

Answer 5

popsáno slovně

Question 6

zápis pomocí: Vývojový diagram

Answer 6

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

Question 7

zápis pomocí: Strukturogramy

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

zápis pomocí: Datově orientované diagramy HIPO

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

zápis pomocí: Rozhodovací tabulky

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

zápis pomocí: Pseudokód

Answer 10

Pseudokód je zápis algoritmu na papír aby tomu programátoři rozumněli, takový hybryd jazyka.

Příklady pseudokódu

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

Požadavky na Algoritmické konstrukce

Answer 11

Algoritmické konstrukce

Algoritmy lze teoreticky sestavovat libovolně, ale vzhledem k přehlednosti a úmyslně omezeným možnostem programovacích jazyků se musí dodržovat několik zásad:

Algoritmus

• má mít jeden začátek a jeden konec
• musí být složen pouze ze základních algoritmických konstrukcí

Question 12

základní konstrukce algorytmu

Answer 12

základní konstrukce algorytmu:

• Sekvence je posloupnost příkazů, které se postupně provedou
• Větvení umožňuje rozdělit program do 2 větví podle toho, zda je nebo není splněna podmínka
• Větvení s prázdnou akcí umožňuje provést příkaz jenom tehdy, když je splněna podmínka
• Cyklus s podmínkou na začátku Když podmínka není na počátku splněna, cyklus nemusí proběhnout ani jednou.
• Cyklus s podmínkou na konci Tento cyklus musí proběhnout aspoň jednou.
• Cyklus se známým počtem průchodů Cyklus proběhne n krát v obecném případě (pro i od m do n) proběhne (n-m+1) krát pokud m>n tak neproběhne ani jednou.

Question 13

Složitost algoritmu

Answer 13

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.

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ý.

Question 14

Typy algoritmů

Answer 14

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 15

Rekurzivní algoritmy

Answer 15

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

Question 16

Hladové algoritmy

Answer 16

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 17

Algoritmy typu rozděl a panuj

Answer 17

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 18

Algoritmy dynamického programování

Answer 18

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 19

Pravděpodobnostní algoritmy

Answer 19

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 20

Genetické algoritmy

Answer 20

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 21

Heuristické algoritmy

Answer 21

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 22

známé algoritmy

Answer 22

• 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 23

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

Answer 23

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 24

Rozhodovací problémy

Answer 24

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 25

Optimalizační problémy

Answer 25

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 26

Algoritmicky řešitelné problémy

Answer 26

máme problém P.

existuje li algoritmus, který P řeší, pak P je algoritmicky řešitelný.

Jestliže P je rozhodovací problém a existuje algoritmus, který 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 27

Třídy složitosti

Answer 27

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 28

Třídy složitosti

Answer 28

• 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 29

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

Answer 29

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 30

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

Answer 30

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 31

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

Answer 31

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).

Question 32

neřešitelné problémy

Answer 32

za neřešitelné považujeme takové ke kterým nelze najít algorytmus. nejznámější jsou:
Obracejte a přidávejte, dokud nevznikne palindrom
Problém zastavení - používá teoretický model algorytmického počítače
Wangovy dlaždice - domino čtyřstranné