Požadavky ke zkoušce z ADS2
Seznam všech definic, algoritmů, vět a důležitých příkladů z přednášky, které požaduji u zkoušky. K algoritmu vždy patří rozbor korektnosti a časové a prostorové složitosti. K větám patří důkaz.
Vyhledávání v textu
Terminologie okolo řetězců (podslova, prefixy, suffixy)
Knuth-Morris-Pratt (jedna jehla v seně)
Aho-Corasicková (více jehel v seně)
Rabin-Karp (okénkové hešování)
Počet kolizí u okénkového hešování
Toky v sítích
Síť, tok, přebytek, velikost toku
Řez, kapacita řezu
Velikost toku se dá měřit na každém řezu
Rezerva hrany, nasycená hrana
Ford-Fulkerson (zlepšující cesty)
Minimální řez je stejně velký jako maximální tok
Čistý tok
Celočíselná síť má celočíselný maximální tok
Největší párování v bipartitním grafu
Blokující tok, vrstevnatá síť
Dinicův algoritmus (zlepšující toky)
Vlna, převedení přebytku po hraně
Goldbergův algoritmus (výšky a přebytky)
Goldbergův algoritmus s výběrem nejvyššího vrcholu
Algebraické algoritmy
Reprezentace polynomu grafem
Primitivní n-tá odmocnina z jedničky
Rychlá Fourierova transformace a její inverze
Násobení polynomů pomocí Fourierovy transformace
Paralelní algoritmy
Hradlová síť
Sčítání přirozených čísel hradlovou sítí
Komparátorová síť
Bitonické třídění komparátorovou sítí
Geometrické algoritmy
Konvexní obal
Průsečíky úseček
Voroného diagram
Lokalizace bodu v mnohoúhelníkové síti
Semipersistentní binární vyhledávací strom
Převody problémů
Rozhodovací problém
Bipartitní párování jako rozhodovací problém, kódování vstupu
Převod mezi problémy
Vlastnosti převoditelnosti (reflexivita, tranzitivita apod.)
Problémy: klika, nezávislá množina, SAT, 3-SAT, 3,3-SAT, 3D-párování
Převod klika ↔ nezávislá množina
Převod SAT → 3-SAT → 3,3-SAT
Převod 3-SAT → nezávislá množina
Převod nezávislá množina → SAT
Převod 3,3-SAT → 3D-párování
NP-úplnost
Třídy složitosti P a NP
NP-těžké a NP-úplné problémy
Pokud A→B a B∈P, pak A∈P
Pokud A→B, B∈NP a A je NP-úplný, pak B je NP-úplný
Cookova věta: SAT je NP-úplný (náznak důkazu)
Převod obvodového SATu na SAT
Klasické NP-úplné problémy
Jak zvládnout těžký problém
Nezávislá množina ve stromu
Barvení intervalového grafu
Pseudopolynomiální algoritmus pro problém batohu
Aproximační algoritmus
2-aproximace obchodního cestujícího v metrickém prostoru
Neaproximovatelnost obchodního cestujícího bez trojúhelníkové nerovnosti
Polynomiální aproximační schéma (PTAS)
Plně polynomiální aproximační schéma (FPTAS)
FPTAS pro problém batohu