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

Prů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í

Násobení 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

Stránku spravuje Martin Mareš