I. Algoritmus, prostředky pro zápis algoritmu, algoritmické konstrukce. Složitost algoritmu, příklady algoritmů, algoritmicky neřešitelné problémy. Flashcards
Co je to algoritmus?
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ší.
vlastnosti algoritmu?
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
prostředky pro zápis algoritmu?
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
zápis pomocí: Programovací jazyk
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)
zápis pomocí: Slovní popis
popsáno slovně
zápis pomocí: Vývojový diagram
Vývojový diagram je grafické znázornění algoritmu řešení úlohy jednotnými značkami a zkratkami
zápis pomocí: Strukturogramy
Strukturogramy - strukturogram je grafické znázornění algoritmu pomocí 3 základních programových struktur (posloupnost, opakování a větvení).
zápis pomocí: Datově orientované diagramy HIPO
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.
zápis pomocí: Rozhodovací tabulky
Rozhodovací tabulky - používané při složitých větveních. Např. obrázek - Rozhodovací tabulka se smíšenou volbou
zápis pomocí: Pseudokód
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
Požadavky na Algoritmické konstrukce
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í
základní konstrukce algorytmu
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.
Složitost algoritmu
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ý.
Typy algoritmů
Typy algoritmů
- Rekurzivní algoritmy
- Hladové algoritmy
- Algoritmy typu rozděl a panuj
- Algoritmy dynamického programování
- Pravděpodobnostní algoritmy
- Genetické algoritmy
- 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
Rekurzivní algoritmy
- Rekurzivní algoritmy – které využívají (volají) samy sebe.
Hladové algoritmy
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.
Algoritmy typu rozděl a panuj
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čí.
Algoritmy dynamického programování
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.
Pravděpodobnostní algoritmy
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.
Genetické algoritmy
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.
Heuristické algoritmy
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).
známé algoritmy
- 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.
Problém - Co musí být v zadání problému určeno?
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
Rozhodovací problémy
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?
Optimalizační problémy
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í.
Algoritmicky řešitelné problémy
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ší).
Třídy složitosti
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
Třídy složitosti
- 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.
Některé asymptotické složitosti mají i své triviální pojmenování (jsou seřazeny od nejrychlejších k nejpomalejším):
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á
Typické příklady časové složitosti
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.
Snižování výpočetní složitosti algoritmů
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).
neřešitelné problémy
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é
