Bakalářská státnice - Informatika - Základy informatiky - ISPS - Algoritmy a datové struktury
Z ωικι.matfyz.cz
zpět: Bakalářská státnice - Informatika - Základy informatiky - obor Správa počítačových systémů
zdroje:
- Algoritmy a datové struktury
- Slajdy k ADS I a ADS II (Čepek)
- Prezentace k přednášce Programování (Töpfer)
literatura:
- Pavel Töpfer: Algoritmy a programovací techniky
- Matoušek, Nešetřil: Kapitoly z diskrétní matematiky
Obsah
- 1 Časová složitost algoritmů, složitost v nejhorším a průměrném případě
- 2 Třídy složitosti P a NP, převoditelnost, NP-úplnost
- 3 Binární vyhledávací stromy, vyvažování, haldy
- 4 Hašování
- 5 Sekvenční třídění, porovnávací algoritmy
- 6 Grafové algoritmy - prohledávání do hloubky a do šířky, souvislost, topologické třídění, nejkratší cesta, kostra grafu
- 7 Tranzitivní uzávěr
- 8 Algoritmy vyhledávání v textu
- 9 Algebraické algoritmy - DFT, Euklidův algoritmus
- 10 Základy kryptografie, RSA, DES
Časová složitost algoritmů, složitost v nejhorším a průměrném případě[editovat | editovat zdroj]
- časová složitost, paměťová složitost
- asymptotická složitost - polynomální, exponenciální, "O" notace
- asymptoticky menší nebo rovna, asymptoticky větší nebo rovna, asymptoticky stejná
- časová složitost algoritmu
- v nejhorším případě = maximální počet operací pro nějaká data
- v nejlepším případě = minimální počet operací pro nějaká data
- v průměrném případě = očekávaný počet operací, průměr pro všechna možná vstupní data
- složitost problému = složitost nejlepšího algoritmu, který řeší daný problém
Třídy složitosti P a NP, převoditelnost, NP-úplnost[editovat | editovat zdroj]
Typy úloh:
- optimalizační úloha = hledání optimální struktury s danými vlastnostmi
- rozhodovací problém = pro dané zadání odpovědět ANO/NE
- třída P rozhodovacích problémů = existuje (deterministický sekvenční) algoritmus běžící v polynomiálním čase, který správně rozhodne ANO/NE
- třída NP rozhodovacích problémů = existuje NEdeterministický sekvenční algoritmus běžící v polynomiálním čase, který řeší daný problém
Příklady problémů NP:
- KLIKA - existence úplného podgrafu velikosti alespoň k
- HK - existence Hamiltonovské kružnice v grafu
- TSP - obchodní cestující
- SP - součet podmnožiny
- DNF 3SAT - splnitelnost Booleovských formulí
- problém A je polynomiálně převoditelný (redukovatelný) na problém B, pokud existuje zobrazení zadání problému A do zadání problému B, že:
- zadání problému A je kladné <=> zadání problému B je kladné (tj. odpověď je ANO)
- zadání problému převoditelné v polynomiálním čase
- NP-těžký problém = je na něj polynomiálně převoditelný libovolný problém třídy NP
- NP-úplný problém = patří do třídy NP a je NP-těžký
Binární vyhledávací stromy, vyvažování, haldy[editovat | editovat zdroj]
- binární strom, binární vyhledávací strom obecně
- popis operací search, insert, delete (několik možných situací), min, max - jejich složitost
- červeno-černé stromy - každý uzel má barvu (červená, černá) a typ (interní, externí), vlastnosti, výška uzlu, černá výška uzlu, rotace (levá, pravá), vkládání a odebírání uzlu - složitost všech operací O(log n) v nejhorším případě
- AVL stromy - definice, modifikace operací Insert a Delete (dodatečné vyvážení pomocí rotací) - složitost všech operací O(log n) v nejhorším případě
- halda (heap) - obecná halda, binární halda, zarovnání hladin, otec < syn, složitost O(log n)
- haldové operace: přidání prvku, odebrání minima
- realizace haldy v poli
- heapsort - třídění haldou - postavení haldy + rozebírání hlady (odebírání minima z kořene)
Hašování[editovat | editovat zdroj]
- hašovací funkce - transformace klíče na index do tabulky, požadavek rovnoměrného rozložení (popř. nějaký předpoklad o vstupních datech)
- hašovací tabulka - přímo adresovatelné buňky
- pouze operace insert, delete, search
- řešení kolizí
- řetězením prvků - spojový seznam kolidujících prvků
- otevřené adresování = hledání náhradní buňky pro umístění položky, komplikovanější Delete
- lineární zkoušení - umístění na první volnou pozici za
- kvadratické zkoušení
- dvojité hašování - druhá hašovací funkce pro případ kolizí
Pokročilejší techniky:
- hašování do stránek - hašovací funkce vrací číslo stránky, do které se vejde více záznamů
- perfektní hašování - složitější hašovací funkce, přidání prvků může h.f. změnit a způsobit přehašování dat, vhodné pro intenzivní vyhledávání a méně časté vkládání
- perfektní hašování Cormacka - adresář (informace o kolidujících prvcích, umístění v primárním souboru, rozlišující hašovací funkce)
- Larson a Kalja - data umístěna do M stránek, 2 sady hašovacích funkcí (stránka, signatura záznamu), separátor stránek
- rozšiřitelné hašování - adresář pro lokalizaci stránek, některé stránky splývají, dle potřeby se rozdělují, 1-2 přístupy na disk (adresář lze mít v paměti)
- lineární hašování (Litwin) - stránky se štěpí po pevném počtu vložení
Sekvenční třídění, porovnávací algoritmy[editovat | editovat zdroj]
Vnitřní třídění[editovat | editovat zdroj]
= všechna data se vejdou do operační paměti
- select sort (přímý výběr) - O($ N^2 $) - stále dokola procházíme celé pole, vždy vybereme nejmenší prvek
- insert sort (třídění vkládáním) - O($ N^2 $) - prvky jeden po druhém zatřiďujeme na správné místo
- bubble sort (bublinkové třídění) - O($ N^2 $) - procházíme pole jedním směrem, dle potřeby prohazujeme sousední prvky
- vylepšení: procházet střídavě oběma směry, posouvat hranice zkoumané části
- heapsort (třídění haldou) - O(N log N) - z tříděných čísel sestavíme haldu, poté odebíráme minimální prvky z vrcholu, lze implementovat v poli
- radix sort (přihrádkové třídění) - O(N) - nutný předpoklad o rozsahu tříděných čísel a možnost indexovat cílové "přihrádky" klíči tříděných prvků
- obecně třídění vícemístných čísel - třídí se podle jednotlivých cifer od nejméně k nejvíce významným
Následující algoritmy jsou typu "rozděl a panuj":
- merge sort (slevání) - O(N log N) - dělí tříděné pole na poloviny, každou setřídí stejným postupem a pak je slévá
- quicksort - rozdělení pole na 2 části podle pivota, nalevo od pivota menší nebo stejné prvky, napravo větší (provádí se průchodem z obou stran a vzájemnou výměnou prvků, které podmínku nesplňují), dále rekurzivně každá část zvlášť
- časová složitost v nejhorším případě O($ N^2 $), v průměrném a nejlepším O(N log N), paměťová náročnost (zásobník pro rekurzi) až O(N)
Vnější třídění[editovat | editovat zdroj]
= všechna data se do operační paměti nevejdou, musíme pracovat s částmi dat na disku (výrazně pomalejší přístup)
- pracuje se se setříděnými částmi dat (běhy), které se postupně slévají ve větší
- předtřídění - na začátku lze dle velikosti paměti připravit běhy vnitřním tříděním, bez předtřídění musíme začít běhy délky 1
- slévání - z několika vstupních běhů se vytváří sléváním jeden výstupní běh
- jednofázové třídění - při slučování jsou setříděné úseky rovnou ukládány střídavě do dvou souborů (odpadne rozdělování)
Grafové algoritmy - prohledávání do hloubky a do šířky, souvislost, topologické třídění, nejkratší cesta, kostra grafu[editovat | editovat zdroj]
- prohledávání do hloubky (DFS, backtracking) - rekurze, zásobník pro uložení dalších uzlů k prohledání
- ořezávání - průběžné vyhodnocování situace - podstromy, které nemohou vést k řešení, neprohledáváme
- heurestiky - odhad, kde je asi větší šance na nalezení řešení, podle toho volba pořadí prohledávání podstromů
- prohledávání do šířky (BFS, algoritmus "vlny") - po vrstvách dle vzdálenosti od vrcholu, strom nejkratších cest, fronta pro uložení dalších uzlů k prohledání
- souvislost grafu - pomocí prohledávání do šířky, začínáme v náhodném vrcholu, obarvujeme navštívené; podobně počítání počtu komponent souvislosti (spouštíme z neobarvených vrcholů, dokud nějaké jsou)
- topologické třídění
- pouze pro orientované acyklické grafy
- setřídění vrcholů grafu tak, že pro každou hranu (i,j) platí t(i) < t(j) - aneb máme očíslovat vrcholy grafu přirozenými čísly tak, aby hrany vedly jen z vrcholu s nižším číslem do vrcholu s vyšším číslem
- algoritmus: mírná modifikace DFS - očíslování vrcholů podle klesajících časů jich opouštění je topologické
- nejkratší cesta
- Dijkstrův algoritmus - pro nezáporná ohodnocení hran
- vrcholy rozděleny do 2 množin (dokončené, nedokončení)
- v každém kroku bereme nedokončený vrchol s nejkratší dočasnou cestou, prohlásíme za dokončený a přepočítáme sousedy (nedokončené)
- Bellman-Fordův algoritmus - obecnější, umí záporná ohodnocení hran
- Floyd-Warshallův algoritmus - nejkratší cesty pro všechny páry vrcholů
- Dijkstrův algoritmus - pro nezáporná ohodnocení hran
- kostra grafu
- Prim (Jarník) - buduje strom, vybírá hranu, která má nejmenší váhu ze všech hran, které vedou mezi budovaným stromem a jeho okolím
- Kruskalův algoritmus (hladový) - buduje les, fragmenty se spojí do stromu, hrany do kostry zařazuje podle jejich ohodnocení vzestupně, přeskakuje ty, které by vytvořily cyklus
- Borůvkův algoritmus
Tranzitivní uzávěr[editovat | editovat zdroj]
- Tranzitivní uzávěr orientovaného grafu je orientovaný graf s původními vrcholy a platí, že existuje hrana z uzlu u do uzlu v právě tehdy, když v původním orientovaném grafu existuje libovolná orientovaná cesta z uzlu u do uzlu v.
- matice dosažitelnosti grafu = tranzitivní uzávěr grafu reprezentovaný maticí sousednosti
- matici lze získat v čase O(n(n+m)) pomocí n použití DFS
Algoritmy vyhledávání v textu[editovat | editovat zdroj]
- Aho-Corasick
- samotné prohledávání probíhá pomocí vyhledávacího automatu, který je nejprve třeba vytvořit podle hledaných vzorků (překladač)
- vyhledávací stroj - množina stavů, přechodová funkce, zpětná funkce, výstupní funkce
- automat lze znázornit stromem, který znázorňuje prefixy hledaných vzorků a odkazuje se na nejdelší kratší prefix, který je sufixem již prohledaného textu (zpětná funkce)
- složitost: výroba automatu O(h.p), vyhledávání O(N), celkově O(N + h.p), kde h=délka vzorů, p=počet znaků abecedy, N=délka prohledávaného textu
- Knuth-Morris-Pratt (KMP)
- zjednodušená verze pro hledání pouze jednoho vzorku
- zpětná (prefixová) funkce udává délku kratšího prefixu
Algebraické algoritmy - DFT, Euklidův algoritmus[editovat | editovat zdroj]
- Diskrétní Fourierova transformace (DFT)
- obecně převod mezi 2 reprezentacemi polynomu - vektorem koeficientů a funkčními hodnotami v bodech (dvojice)
- evaluace = převod koeficienty -> dvojice
- interpolace = převod dvojice -> koeficienty
- obojí lze provést v čase O(N log N), pokud se "chytře" vyberou body či funkční hodnoty
- chytře vybranými body budou n-té komplexní odmocniny čísla 1
- Vandermondova matice
- diskrétní = transformace jen v několika bodech (Fourierovy body)
- inverzní DFT
- Euklidův algoritmus
- algoritmus na spočítání největšího společného dělitele dvou přirozených čísel
- Rozšířený Euklidův algoritmus
- pro zkoumaná čísla A a B navíc spočítá čísla X a Y tak, že D=NSD(A,B)=A*X+B*Y
Základy kryptografie, RSA, DES[editovat | editovat zdroj]
- Základy kryptografie:
- šifrování, dešifrování, kryptosystém, symetrické vs. asymetrické šifry
- proudové šifry vs. blokové šifry
- S-box (substituční box)
- Feistelovy sítě
- hybridní šifrování
- hašovací funkce (typu MAC, MDC) - MD5, SHA-1
- časové známky
- digitální podpis
- key management
- certifikát, certifikační autority, standard X.500
- inicializační vektory
- pseudonáhodné generátory, HW generátory
- DES
- symetrická šifra
- šifruje 64-bitové bloky, délka klíče 64 bitů (efektivně pouze 56 bitů), 16 šifrovacích kol
- příliš krátký klíč, nevhodná volba S-boxů, těžká implementace v SW
- 3DES
- AES (Rijndael)
- RSA
- asymetrická šifra - veřejný a privátní klíč (vzájemně inverzní)
- použití: šifrování, elektronický podpis, výměna klíčů pro symetrické algoritmy
- Euklidův algoritmus, Malá Fermatova věta