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×🎓)

Zážitky ze zkoušek

Aproximacní algoritmy (2015) - Definice, chtel pomerovou i relativni chybu. Ukazal jsem algoritmus pro BIN PACKING, ktery je nejhure 2x horsi nez optimalni algoritmus. Pak definice aproximacniho schematu, polynomialniho apr. sch. i uplnepolynomialniho apr. schematu. Byl jsem dotazan, zda znam nejake schema (Batoh podle poznmek pana Kucery) a jake schema to je (uplne polynomialni nebo jen polynomialni). Aproximacni schemata (2014, konzultace) - definice Aproximační algoritmy a schémata a jejich souvislost s pseudopolynom. algoritmy, příklad schémata pro batoh nebo soucet podmnozin Aproximacni schemata (2014, Kučera) - definicia optimalizacnej ulohy, definicia aproximacneho algoritmu, aproximacneho pomeru, aproximacneho schema, PAS a UPAS, - schema pre BATOH Aproximacne alg a schemy (2009, Fiala) - Pripraveny papier posluzil na prvu minutu, kedy si to skusajuci precital. Mal som tam plus minus vsetko. Este sa opytal preco nemozem TSP aproximovat s lubovolne malou chybou (v nejakom rozumnom case). Nevedel som , tak mi pomohol otazkou: Co sa stane, ak mi niekto da graf na 100 vrcholoch a povoli chybu pod 1%? Musel by som najst optimalne riesenie. Velmi rychla odpoved. Aproximacne algoritmy (2009, Loebl?) - Pripravil som si 2 a4 s definiciami AA, pom. rel. chyba, AS, PAS, UPAS. Nakoniec som dal priklad vrch.pokrytie s dokazom ze pom.chyba je 2. Skusajuci to asi za 5s preletel ocami a spytal sa ci viem zlozitejsi algortimus, na co som odpovedal ze nie a on ze ok a koniec. Odhad:2 Aproximační algoritmy a schémata (2009, Majerech) - Definice AA, poměrová a relativní chyba, AS, PAS, ÚPAS, ÚPAS pro SP (pozor na písmena v popisu PROŘEŽ (1-d)z < y < z), AA pro TSP Pseudopolynomiální algoritmy a aproximační schémata (2008, Trpělivý teoretik) - Napsal jsem špatnou definici pseudopolynomiálních algoritmů, aproximací, AS, a ÚPAS. Na dotaz jestli znám nějaké AS jsem zmínil UPAS pro SP, a to že patrně obsahuje nějakou proceduru co cosi prořezává. Posléze se mi podařilo přijít na správnou definici pseudopolynomiálních algoritmů, a to jak by zhruba měl vypadat pseudopolynomiální algoritmus pro problém batohu. Tou dobou ale už všichni ze zkoušky odešli tak mě nechal jít :-)

Optimalizační úloha A je buď maximalizační nebo minimalizační a skládá se z těchto tří částí:

1. Množina instancí D_A ⊆ {0, 1}*
2. Množina přípustných řešení S_A(I) ⊆ {0, 1}* , ∀I ∈ D_A
3. Hodnota řešení σ je fce μ_A(I, σ) , která ∀I ∈ D_A a ∀přípustnému řešení σ ∈ S_A(I) přiřadí kladné racionální číslo μ_A(I, σ)

• Optimální řešení σ ∈ S_A(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, σ) | σ ∈ S_A(I) }
  • 💡 tj. pro minimalizační: μ_A(I, σ) = min{ μ_A(I, σ) | σ ∈ S_A(I) }
  • OPT_A(I) je hodnota optimálního řešení instance I ∈ D_A
    • 💡 tj. OPT_A(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 ∈ D_A vrátí řešení σ ∈ S_A(I)
  • 💡 pro S_A(I) = ∅ ohlásí že přípustné řešení neexistuje
• ALG(I) je hodnota řešení ALG na instanci I ∈ D_A
  • 💡 v tj. ALG(I) = μ_A(I, σ), kde σ ∈ S_A(I) je přípustné řešení vrácené algoritmem ALG
• Aproximační poměr ε ≥ 1 algoritmu ALG pokud ∀I ∈ D_A 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

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·OPT_BP(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 $. Pokud $ FF-BP(I) > 1 $, pak z toho plyne, že: $ FF-BP(I) < ⌈2 Σ_{i = 1}^n s(u_i)⌉ ≤ 2⌈Σ_{i = 1}^n s(u_i)⌉ $, kde první nerovnost plyne z toho, že po zdvojnásobení obsahu jsou všechny koše plné až na jeden, který může být zaplněn jen částečně. Rovnosti bychom přitom dosáhli jedině ve chvíli, kdy by byly všechny koše zaplněné právě z poloviny, což není podle našeho předpokladu možné. Druhá nerovnost plyne z vlastností zaokrouhlování. Na druhou stranu musí platit, že $ OPT(I) ≥ ⌈Σ_{i = 1}^n s(u_i)⌉ $. Dohromady tedy dostaneme, že $ FF-BP(I) < 2.OPT(I) $. Pokud $ FF-BP(I) = 1 $, pak i $ OPT(I) = 1 $ a i v tomto případě platí ostrá nerovnost.

Aproximační schémata (🎓)

ALG(I, ε) je aproximačním schématem pro úlohu A, pokud pro I ∈ D_A a racionální číslo ε > 0 vydá řešení σ ∈ S_A(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(n^1/ϵ)) ale ÚPAS nesmí

💡 př. použití aprox.schématu: I je moc složitá pro přímé nalezení OPT , zjednodušíme jí tedy a získáme řešení ALG_ε(I) to ještě můžeme přeložit zpět na řešení odpovídající původní instanci I (u BAPX to ani není nutné)

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, ε)

1. urči v[m] největší cenu
2. if (1 + ε ≥ n) return {m} //nemá cenu pokračovat, zaokrouhlili bysme moc
3. t = ⌊log₂( ε·v[m] / n )⌋ - 1
4. c je nové pole délky n
5. for (i = 1; i ≤ n; i++) c[i] = ⌊v[i] / 2ᵗ⌋
6. 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