Bakalářská státnice - Informatika - Základy informatiky - ISPS - Algoritmy a datové struktury

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

Časová složitost algoritmů, složitost v nejhorším a průměrném případě

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

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

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

• 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

Vnitřní třídění

= 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í

= 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

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

• 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

• 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

• 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

• 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