zpět: Bakalářská státnice - Informatika - Základy informatiky - obor Správa počítačových systémů

zdroje:

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(N2N^2) - stále dokola procházíme celé pole, vždy vybereme nejmenší prvek

  • insert sort (třídění vkládáním) - O(N2N^2) - prvky jeden po druhém zatřiďujeme na správné místo

  • bubble sort (bublinkové třídění) - O(N2N^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(N2N^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)=AX+BY

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