Státnice - Aproximační algoritmy a schémata I2
Ze zápisků k zkoušce z ZSV
09/10, 14/15: Aproximacní algoritmy a schémata.
Aproximační algoritmy - definice a příklad (6×🎓)[editovat | editovat zdroj]
Zážitky ze zkoušek |
---|
|
Optimalizační úloha A je buď maximalizační nebo minimalizační a skládá se z těchto tří částí:
- Množina instancí DA ⊆ {0, 1}*
- Množina přípustných řešení SA(I) ⊆ {0, 1}* , ∀I ∈ DA
- Hodnota řešení σ je fce μA(I, σ) , která ∀I ∈ DA a ∀přípustnému řešení σ ∈ SA(I) přiřadí kladné racionální číslo μA(I, σ)
- Optimální řešení σ ∈ SA(I), pro něž je μA(I, σ) maximální (pro maximalizační úlohu A) nebo minimální (pro minimalizační A)
- 💡 tj. pro maximalizační: μA(I, σ) = max{ μA(I, σ) | σ ∈ SA(I) }
- 💡 tj. pro minimalizační: μA(I, σ) = min{ μA(I, σ) | σ ∈ SA(I) }
- OPTA(I) je hodnota optimálního řešení instance I ∈ DA
- 💡 tj. OPTA(I) = μA(I, σ), kde σ je optimální řešení intance I
- ALG je aproximačním algoritmem pro optimalizační úlohu A, pokud ∀vstup I ∈ DA vrátí řešení σ ∈ SA(I)
- 💡 pro SA(I) = ∅ ohlásí že přípustné řešení neexistuje
- ALG(I) je hodnota řešení ALG na instanci I ∈ DA
- 💡 v tj. ALG(I) = μA(I, σ), kde σ ∈ SA(I) je přípustné řešení vrácené algoritmem ALG
- Aproximační poměr ε ≥ 1 algoritmu ALG pokud ∀I ∈ DA platí: $ ε ≥ max\left\{ \frac{OPT(I)}{ALG(I)}, \frac{ALG(I)}{OPT(I)} \right\} $
- tj. OPT(I) ≤ ε·ALG(I) (maximalizační úlohy)
- ALG(I) ≤ ε·OPT(I) (minimalizační úlohy)
- 💡 nekdy se nazývá také poměrová chyba a značí se ρ(n)
- $ \text{"relativní chyba"} ≥ \frac{|ALG(I)-OPT(I)|}{OPT(I)} $
Příklad aproximačního algoritmu pro Bin Packing[editovat | editovat zdroj]
- Bin Packing – BP, úloha
- Instance : Konečná množina předmětů U = {u₁, .., uₙ}, s každým předmětem asociovaná velikost 0 ≤ s(u) ≤ 1, což je racionální číslo.
- Cíl : Najít rozdělení všech předmětů do co nejmenšího počtu po dvou disjunktních množin U₁, .., Uₘ takové, že každá množina může mít velikost max 1.
- 💡 Naším cílem je tedy minimalizovat m.
- Algoritmus (First Fit pro Bin Packing – FF-BP - 💡 zřejmě polynomiální)
- Ber jeden předmět po druhém,
- ∀ předmět u najdi první koš, do nějž se tento předmět ještě vejde,
- pokud takový koš neexistuje, přidej nový koš obsahující jen předmět u
Věta ( Aproximační poměr FF-BP je 2 - tj. max 2x horší než optimum ): ∀ instanci I ∈ DBP platí, že FF-BP(I) < 2·OPTBP(I)
Dk: |
---|
: V řešení, které vrátí $ FF-BP $ je nejvýš jeden koš, který je zaplněn nejvýš z poloviny. Kdyby totiž existovaly dva koše $ U_i $ a $ U_j $ pro $ i < j $, které jsou zaplněny nejvýš z poloviny, tak by $ FF-BP $ nepotřeboval zakládat nový koš pro předměty z $ U_j $, všechny by se vešly do $ U_i $.
|
Aproximační schémata (🎓)[editovat | editovat zdroj]
ALG(I, ε) je aproximačním schématem pro úlohu A, pokud pro I ∈ DA a racionální číslo ε > 0 vydá řešení σ ∈ SA(I), jehož hodnota se od optimální liší s aproximačním poměrem $ (1 + ε) ≥ max\left\{ \frac{OPT(I)}{ALG(I, ε)}, \frac{ALG(I, ε)}{OPT(I)} \right\} $
- Tj. pro maximalizační úlohu platí, že: OPT(I) ≤ (1 + ε) ALG(I, ε)
- a pro minimalizační úlohu platí, že: ALG(I, ε) ≤ (1 + ε) OPT(I)
ALGε je instance algoritmu ALG se zafixovanou ε
- ALG je polynomiální aproximační schéma (PAS), pokud ALGε má časovou složitost polynomiální v len(I) (💡 tj. délce vstupu n, ∀ε)
- ALG je úplně polynomiální aproximační schéma (ÚPAS), pokud ALG má časovou složitost polynomiální v len(I) a 1/ϵ
- 💡 tj. PAS může mít 1/ϵ v exponentu čas.složitosti (např. O(n1/ϵ)) ale ÚPAS nesmí
- Příklad ÚPAS pro Batoh - BAPX
- Vstup: Velikost batohu B, pole 0 < s[1..n] ≤ B velikostí předmětů a pole v[1..n] cen předmětů, racionální číslo ε > 0.
- Otázka: Množina M předmětů, jejichž souhrnná velikost nepřesahuje B, maximalizujeme celkovou cenu.
BAPX(s, v, B, ε)
- urči v[m] největší cenu
- if (1 + ε ≥ n) return {m} //nemá cenu pokračovat, zaokrouhlili bysme moc
- t = ⌊log₂( ε·v[m] / n )⌋ - 1
- c je nové pole délky n
- for (i = 1; i ≤ n; i++) c[i] = ⌊v[i] / 2ᵗ⌋
- return Batoh(s, c, B) //volání původního pseudopolynomiálního algoritmu iterující přes V = Σv
💡 není nutné znát všechny logaritmy v algoritmu, jenom nějak stručně vysvětlit myšlenku
💡 snažíme se omezit celkovou cenu V = Σv, algoritmus přeškáluje (normalizuje) ceny předmětů pomocí ε a v[m] a zaokrouhlí na ⌊⌋
💡 Předpokládáme, že (∀i ∈ {1, ..., n}) [0 < s[i] ≤ B]
- Schéma BAPX pracuje v čase O(n³ / ε)
Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓) Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3) Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita
🎓 - znamená kolikrát byla otázka u státnic