Vlevo je text písně tak, jak se zpívá — ale hláskované symboly („es“, „ó en na třetí“) jsou zapsané správnou notací (s, O(n³)): čteš symbol, zpíváš jeho jméno. Barevné podbarvení vlevo odpovídá stejně podbarvenému řádku v pravé tabulce, kde najdeš, co se přesně zpívá a co symbol znamená. Lekce označené „připravujeme“ zatím nejsou hotové — odkazy doplníme v další iteraci.
Metrický TSP. Christofides. Jedna a půl.
Najdi nejlevnější kostru, budem jí říkat T,
vrcholy lichého stupně hoď do množiny W.
Vždycky je jich sudý počet — to je jistá věc,
nejlevnější párování M na nich najdi přec!
Kostra! Liché! Párování!
Euler! Zkratka! Hotovo!
Jedna a půl krát optimum,
O(n³) — Christofidovo!
Kostra T plus matching M — všechny stupně sudé jsou,
Eulerův tah L tam projde každou hranou jedinou.
Zkratkou přeskoč vrcholy, cos viděl už dřív —
trojúhelník zaručí, že okruh H je kratší, div!
Čtyři nerovnosti, řetěz, co tě spasí:
optimum je víc než kostra — okruh bez hrany je kostra taky,
půl optima je víc než matching — okruh dá dvě párování,
T plus M se rovná L — a L je víc než H, bez ptaní!
Double-tree je chudší bratr: hrany kostry zdvojí,
faktor dva, O(n²) — s tím se nespokojíš.
Christofides místo zdvojení vezme matching M —
proto jedna a půl optima, a důkaz máme všem!
Kostra, liché, párování, Euler, zkratka…
O čem to je
Christofidesův algoritmus = nejlepší známá aproximace metrického TSP. 5 kroků: MST → vrcholy lichého stupně → min. párování → Eulerův tah → shortcutting. Bridge je celý důkaz faktoru 3/2 — u zkoušky nejčastější důkaz (žebříček #1).
Notace → význam
| TSP | problém obchodního cestujícího |
| W | vrcholy lichého stupně v MST |
| O(n³) | složitost Christofidese (kvůli matchingu) |
| M | min-weight perfect matching na W |
| O(n²) | složitost double-tree |
| c(H) ≤ 3/2·OPT | jedna a půl krát optimum |
| OPT ≥ c(T) | optimum je víc než kostra |
| OPT/2 ≥ c(M) | půl optima je víc než matching |
| c(T)+c(M) = c(L) ≥ c(H) | T plus M je L, a L je víc než H |
Materiály
- L3.10Christofides 3/2 — důkaz faktoru [FOTO]
- L3.8bMST jako dolní mez (OPT ≥ c(MST))
- L3.8cEulerovský tah a sudé stupně
- L3.9Double-tree (2-aproximace)
Co si vzít k testu
Text je postavený jako hotová osnova odpovědi. Refrén = pět kroků algoritmu v přesném pořadí (kostra → liché vrcholy → párování → Eulerův tah → zkratka) — když dostaneš „popište Christofidesův algoritmus“, vypiš refrén. Bridge = celý důkaz faktoru: čtyři nerovnosti se řetězí do c(H) ≤ c(L) = c(T)+c(M) ≤ OPT + OPT/2 = 3/2·OPT; každý řádek bridge je jedna nerovnost včetně zdůvodnění („okruh bez hrany je kostra“ = proč OPT ≥ c(T)). Verse 3 je pojistka proti záměně s double-tree: rozdíl je jen v kroku 3 (matching místo zdvojení hran) a právě ten zlepší faktor 2 na 3/2. Sudost množiny W („vždycky je jich sudý počet“) je drobnost, na kterou se zkoušející rád zeptá — bez ní by perfektní párování neexistovalo.
V s začni s nulou, všude jinde nekonečno,
množina R je prázdná — kdo v ní skončí, skončil věčně.
Vyber vrchol s nejmenším ℓ a zavři ho do R,
relaxuj hrany, co vedou ven — a znova, dokola.
Jednou zavřený, navždy zavřený — ℓ už se nezmění,
ℓ(v) ≤ ℓ(k),
a hrana nikdy záporná není —
proto přes otevřené to kratší nebude — bez vrácení!
Bellmanova rovnice chce minimum přes předchůdce k:
když k leží v R, tu hranu už jsem relaxoval já —
vnitřní smyčka prošla všechny hrany z R ven.
Když k leží venku? Tam se láme celý sen:
Kde by se důkaz zlomil? Kdyby váhy záporné byly —
levná hrana za otevřeným vrcholem by tvrzení zabily.
Proto Dijkstra jen s nezápornými, label setting, O(n²),
indukce přes velikost množiny R je mu zárukou.
Nezáporné váhy… jinak Bellman-Ford, příteli.
O čem to je
Důkaz korektnosti Dijkstry (žebříček #2): indukce přes rostoucí množinu uzavřených vrcholů R. Invariant: jakmile se vrchol zavře, jeho label je definitivní. Klíčové je místo, KDE se použije nezápornost hran — bez ní argument padá.
Notace → význam
| s | zdroj; ℓ(s) = 0, jinde ∞ |
| ℓ | label (délka cesty); vybírá se nejmenší mimo R |
| ℓ(v) ≤ ℓ(k) | zavíraný vrchol má nejmenší label ze všech otevřených |
| k | předchůdce; Bellman: ℓ(v) = mink{ℓ(k)+c(k,v)} |
| O(n²) | složitost, label setting |
| c(e) ≥ 0 | hrana nikdy záporná není — TADY se nezápornost použije |
Materiály
- L3.2Důkaz korektnosti Dijkstry [FOTO]
- L2.4Dijkstrův algoritmus (běh)
- L2.2Bellmanův princip + rovnice
Co si vzít k testu
Titulní fráze „jednou zavřený, navždy zavřený“ JE indukční invariant — věta, kterou odpověď na „dokažte korektnost Dijkstry“ začíná: label vrcholu se po uzavření do R už nezmění a je správný. Refrén dává obě ingredience zdůvodnění: zavíraný vrchol má nejmenší label ze všech otevřených (ℓ(v) ≤ ℓ(k)) a hrany jsou nezáporné, takže žádná cesta přes dosud otevřený vrchol nemůže být kratší. Verse 2 = rozbor Bellmanovy rovnice na dva případy předchůdce k: k ∈ R (hranu už vnitřní smyčka zrelaxovala) vs. k mimo R (tady se použije nezápornost). Bridge odpovídá na oblíbenou podotázku „KDE přesně důkaz potřebuje nezáporné váhy“ — levná hrana schovaná za otevřeným vrcholem by invariant zabila. Outro = poslední věta odpovědi: se zápornými hranami přepni na Bellman–Forda.
Hledej cestu z s do t, směr hran tě netrápí,
po směru ber hranu, když je tok pod kapacitou,
proti směru tehdy, když je tok nad dolní mezí —
augmentující cesta! Jiná pravda není!
Po směru: míň než kapacita!
Proti směru: víc než dolní mez!
γ je nejmenší rezerva z celé cesty —
po směru přičti, proti odečti — a běž!
Označkuj zdroj s a šiř tu zprávu dál:
po směru značkuj souseda, když f < u,
proti směru značkuj, když f > l,
a když označkuješ t — cestu jsi našel, námořníku!
Když už cesta není — stůj! Tok je maximální!
Složitost: hrany krát hodnota toku — f to škálu dální.
Iracionální kapacity? Nemusí to skončit, brachu —
Edmonds a Karp s BFS tě zbaví strachu!
Najdi tok, najdi cestu, spočti γ — a znova!
O čem to je
Ford–Fulkerson: opakovaně hledej augmentující cestu (neorientovaně!), spočti rezervu γ a pošli ji po cestě. Labeling = šíření značek od zdroje; když se označkuje t, cesta existuje. Když ne, tok je maximální.
Notace → význam
| s, t | zdroj a stok |
| f < u | po směru: tok pod kapacitou |
| f > l | proti směru: tok nad dolní mezí |
| γ | nejmenší rezerva na cestě; f ← f ± γ |
| f | hodnota toku; složitost O(m·|f*|) |
| BFS | Edmonds–Karp, O(n·m²) — skončí i pro iracionální kapacity |
Materiály
- L4.2Reziduální graf a augmentující cesta
- L4.3Ford–Fulkerson: iterativní augmentace (běh)
- L4.1Síť, tok, Kirchhoffův zákon
Co si vzít k testu
Píseň je návod na běhovou úlohu „proveďte iterace Ford–Fulkersona“. Verse 1 + refrén = definice augmentující cesty: jde se z s do t BEZ ohledu na orientaci hran, po směru smí hrana s f < u, proti směru s f > l — a pak update: γ je minimum rezerv přes celou cestu, po směru přičíst, proti směru odečíst. Verse 2 = labeling (jak se cesta hledá): značky se šíří od s, označkování t znamená nalezenou cestu. Bridge = zastavovací podmínka (žádná cesta → tok je maximální) plus dvě teoretické drobnosti na podotázky: složitost závisí na hodnotě toku (O(m·|f*|) — proto „pseudopolynomiální“) a s iracionálními kapacitami nemusí skončit, což řeší Edmonds–Karp s BFS. U každé iterace v testu si odzpívej refrén: najdi cestu, spočti γ, přičti/odečti.
Rozděl vrcholy na dva tábory: s patří do A,
t zůstává venku — a mezi nimi řez, δ(A).
Hrany ven, hrany dovnitř — δ⁺ a δ⁻,
kapacita řezu? Teď pozor na ten minus:
Kapacity VEN se sčítají,
dolní meze DOVNITŘ se ODEČTOU!
Maximální tok se rovná minimálnímu řezu —
Ford a Fulkerson, devatenáct set padesát šest!
Když labeling skončí a t zůstane bez značky,
označkované vrcholy tvoří A — bez hádky.
Hrany ven jsou plné: f = u,
hrany dovnitř na dolní mezi — minimální řez tu máš!
Celočíselné kapacity… celočíselný maximální tok existuje…
Dantzig a Fulkerson… integral flow theorem…
O čem to je
Věta max-flow = min-cut (Ford & Fulkerson 1956). Definice řezu a hlavně vzorec kapacity řezu s tím zrádným minusem. Druhá sloka: jak přečíst minimální řez z posledního (neúspěšného) labelingu.
Notace → význam
| s ∈ A, t ∉ A | rozdělení vrcholů: zdroj uvnitř, stok venku |
| δ(A) | řez = hrany mezi A a zbytkem |
| δ⁺(A), δ⁻(A) | hrany ven / hrany dovnitř |
| C(A) = Σu(δ⁺(A)) − Σl(δ⁻(A)) | kapacity ven sčítej, dolní meze dovnitř odečti |
| f = u | hrany ven z A jsou plné |
| f = l | hrany dovnitř na dolní mezi |
Materiály
Co si vzít k testu
Celá píseň krouží kolem jediného vzorce, ve kterém se nejvíc chybuje: kapacita řezu C(A) = Σu(δ⁺(A)) − Σl(δ⁻(A)). Refrén ti vtlouká to MINUS — dolní meze hran vedoucích DOVNITŘ se odečítají, ne sčítají ani neignorují. Verse 1 = definice řezu (s uvnitř A, t venku). Verse 2 je pracovní postup na úlohu „najděte minimální řez“: nech doběhnout labeling, označkované vrcholy tvoří A, a kontrola správnosti — hrany ven musí být plné (f = u), hrany dovnitř na dolní mezi (f = l). Letopočet v refrénu (Ford a Fulkerson 1956) je na otázku „jak se věta jmenuje a od koho je“. Šeptaný bridge = celočíselnost: s celočíselnými kapacitami existuje celočíselný maximální tok (integral flow theorem) — bývá to bonusová podotázka.
PS1. temp. Cmax. Time-indexed. Pět omezení. Jedem!
ait je jedna, když úloha i startuje v t,
binárka přes celý horizont, horní mez je strop, oukej.
Pět bloků staví model, žádný nesmíš vynechat —
kdo zapomene na zdroje, ten jde od zkoušky spát!
JEDNA: Σt ait = 1 — start právě jednou!
DVA: si = Σt t·ait — startovní čas!
TŘI: si + lij ≤ sj — temporální vazba!
ČTYŘI: v každém čase τ běží nejvýš jedna — zdroj nás hlídá zas!
PĚT: si + pi ≤ Cmax — a Cmax minimalizuj!
To okno v bloku čtyři, to je finta celá:
t ≤ τ, τ < t + pi — tak se to dělá.
Úloha, co startuje v t, zrovna běží v čase τ —
neostrá zleva, ostrá zprava — zapiš si to, čau!
Jednou startuješ, startem počítáš,
vazby ctíš, zdroj nepřetížíš,
konec pod Cmax — a Cmax tlačíš níž!
O čem to je
Time-indexed ILP pro projektové rozvrhování s temporálními vazbami — nejrecyklovanější ILP úloha rozvrhovacího slotu. Refrén = všech 5 omezení v pořadí.
Notace → význam
| PS1 | temp | Cmax | Grahamův zápis problému |
| ait ∈ {0,1} | binární proměnná: úloha i startuje v čase t |
| Σt ait = 1 | 1: každá úloha startuje právě jednou |
| si = Σt t·ait | 2: definice startovního času |
| si + lij ≤ sj | 3: temporální vazba |
| τ | 4: zdroj — Σi Σt≤τ<t+pi ait ≤ 1 |
| si + pi ≤ Cmax | 5: konec pod makespan; min Cmax |
| t ≤ τ < t + pi | okno „úloha startující v t právě běží v τ“ — neostrá zleva, ostrá zprava |
Materiály
- L5.3Time-indexed ILP pro PS1|temp|Cmax [FOTO](připravujeme)
- L5.2Precedence a temporální omezení(připravujeme)
- L1.15Časově indexované proměnné v ILP
Co si vzít k testu
Refrén je doslova šablona odpovědi na „napište time-indexed ILP model“: pět omezení v pořadí, v jakém je máš vypsat — (1) start právě jednou, (2) definice startovního času, (3) temporální vazby, (4) zdrojové omezení, (5) konec pod Cmax + minimalizace. Verse 1 ti připomíná začít definicí proměnné (ait binární přes celý horizont) — bez ní model nedává smysl a body padají. Verse 2 je nejčastější zdroj ztracených bodů: okno v omezení 4. Úloha startující v t právě běží v čase τ ⟺ t ≤ τ < t + pi — „neostrá zleva, ostrá zprava“; kdo otočí nerovnosti, počítá úlohu v čase, kdy už neběží. A jak píseň varuje: nejčastěji se zapomíná celý blok 4 (zdroje).
Level koncové úlohy? Prostě její p.
Jinak p plus maximum levelů následníků, jé!
Počítej to odzadu, od konce ke startu —
nejdelší cesta do cíle, tu měj v kartu.
Nejvyšší level bere procesory — to je zákon náš!
Když je úloh víc než strojů: β = h / |S|!
δ: někdo SKONČÍ, někdo KLESNE, někdo DOHÁNÍ —
a McNaughton to nakonec všechno srovná, yes!
Případ jedna: úloha doběhla — hotovo, šmik.
Případ dva: přiřazená klesla pod ready čekající — přepočti vmžik.
Případ tři: rychlejší s větší β dohnal pomalou —
sniž p i levely o δ·β, posuň čas, jedem dál!
C*max: vezmi MAXIMUM ze dvou —
nejdelší úloha, nebo Σp / R!
Namotávej úlohy přes okraj jako koberec,
každá se zlomí nejvýš jednou — McNaughton, O(n), věř!
Dva stroje, preempce, precedence — výsledek přesný!
Preempce a les — taky přesný, to je hezký.
Jinak aproximace: 2 − 2/R —
Muntz a Coffman, O(n²), tref se a ber!
O čem to je
Muntz & Coffman (P | pmtn, prec | Cmax): level = nejdelší cesta do konce, nejvyšší level dostává procesory, při remíze se výkon dělí (β). Tři události δ přepočítávají přiřazení; výsledný profil dokončí McNaughtonovo namotávání.
Notace → význam
| p | doba úlohy; level(i) = pi + max level následníků |
| β = h / |S| | díl procesoru na úlohu (h strojů, |S| úloh) |
| δ, δ·β | čas do další události; p i levely klesnou o δ·β |
| C*max = max(max pj, Σpj/R) | McNaughtonův optimální makespan |
| O(n) | McNaughton — každá úloha se zlomí nejvýš 1× |
| 2 − 2/R | aproximační faktor Muntz & Coffman |
| O(n²) | složitost Muntz & Coffman |
Materiály
- L5.10Muntz & Coffman [FOTO](připravujeme)
- L5.4McNaughton (P|pmtn|Cmax)(připravujeme)
Co si vzít k testu
Sloky jdou v pořadí, v jakém běhovou úlohu Muntz & Coffman počítáš. Verse 1: nejdřív levely, odzadu (level = p pro koncové, jinak p + max level následníků — tj. nejdelší cesta do cíle). Refrén: pravidlo přidělování — nejvyšší level dostává procesory, a když je ready úloh víc než strojů, dělí se výkon rovným dílem β = h/|S|. Verse 2: tři události, kdy se přepočítává (úloha skončí / přiřazená klesne pod čekající / pomalejší je dohnána) — mezi nimi odečítáš δ·β. Bridge: výsledný profil se dokončí McNaughtonem — vzorec C*max = max(max pj, Σpj/R) a namotávání „přes okraj“, každá úloha zlomená nejvýš jednou. Verse 3 na teoretickou podotázku: kdy je M&C přesný (2 stroje, nebo strom precedencí) a jinak faktor 2 − 2/R.
Hrana z xi do xj je konzistentní jenom tehdy,
když pro KAŽDOU hodnotu a z domény Di
EXISTUJE b v doméně Dj,
že spolu splní všechna omezení — tak zní ty věty!
Pro každé a existuje b —
kdo podporu nemá, z domény jde ven!
Mazal jsi v doméně k? Vrať do fronty hrany DO k —
jen tu od m ne! AC-3, krásný den!
A pozor: hrana má SMĚR, to si pamatuj —
(i,j) konzistentní neznamená (j,i), aleluj!
Fronta startuje se všemi orientovanými hranami,
vyber (k,m), zavolej REVISE — a co s mazáními?
Prázdná doména? Fail — jdi domů, konec hry.
Revize (k,m) nerozbije hranu (m,k) — ta klidně spí.
A závěr zrádný, ten si vryj do hlavy:
konzistence hran ti ŘEŠENÍ NEZARUČÍ — AC je neúplná, tak to ber!
O čem to je
Arc consistency + AC-3: definice s kvantifikátory, orientovanost hran, REVISE a pravidlo znovuzařazení do fronty. Pointa: AC je neúplná — i plně konzistentní CSP nemusí mít řešení (protipříklad: trojúhelník s ≠).
Notace → význam
| (xi, xj) | orientovaná hrana CSP |
| ∀a ∈ Di | každá hodnota domény proměnné i |
| ∃b ∈ Dj | „podpora“ hodnoty a |
| (i,j) ≠ (j,i), (k,m) | hrany mají směr; REVISE zpracovává (k,m) |
| Dk → (i,k), i ≠ m | po škrtu v doméně k vrať do fronty hrany do k, kromě té od m |
| AC-3 | algoritmus arc consistency (neúplný!) |
Materiály
Co si vzít k testu
Verse 1 je definice arc consistency tak, jak ji chtějí slyšet doslova — s oběma kvantifikátory: pro KAŽDÉ a ∈ Di EXISTUJE b ∈ Dj splňující omezení. Verse 2 dodává druhou půlku definice: hrana má SMĚR, (i,j) konzistentní neříká nic o (j,i) — proto fronta startuje se VŠEMI orientovanými hranami. Refrén = jediné pravidlo, kterým se AC-3 liší od naivního opakování: po škrtu v doméně k vrať do fronty hrany vedoucí DO k, kromě (m,k) — protože revize (k,m) konzistenci hrany (m,k) nemohla rozbít (bridge to říká explicitně, je to oblíbená „proč?“ podotázka). Bridge dává i dvě závěrečné věty každé odpovědi: prázdná doména = fail celé větve, a hlavně — arc consistency NEZARUČUJE řešení, AC je neúplná (protipříklad: trojúhelník s ≠ a doménami {1,2}).
Kdyby byla r-aproximace na obecný TSP,
rozhodl bych Hamiltonův okruh polynomiálně, jé!
Vezmi graf G, postav úplný graf na n vrcholech,
a teď ty váhy — ať nezůstaneš v koncích:
JEDNA — když hrana v grafu JE!
2 + (r−1)·n — když NENÍ!
Nejvýš r·n? Hamilton EXISTUJE!
Víc? Hamilton NENÍ! — Spor, pokud P ≠ NP!
Když okruh existuje, optimum je přesně n,
aproximace vrátí nejvýš r·n.
Když okruh neexistuje, jedna drahá hrana stačí:
n−1, + 2, + (r−1)·n —
r·n + 1 — to už nic nezamlží!
Dej váhy jedna a dva — trojúhelník platí dál…
proto i METRICKÝ TSP je NP-těžký král!
Optimum rovno n — právě když Hamilton žije…
O čem to je
Neexistence r-aproximace pro obecný TSP (žebříček #3). Důkaz sporem: kdyby existovala, rozhodla by NP-úplný Hamiltonův okruh v polynomiálním čase. Klíč = váhy, které mezi „okruh je“ a „okruh není“ udělají mezeru větší než faktor r.
Notace → význam
| r, r·n | faktor aproximace; rozhodovací mez |
| G, n, OPT = n | graf z HC; okruh existuje ⟺ optimum je přesně n |
| TSP | problém obchodního cestujícího |
| 2 + (r−1)·n, r·n + 1 | váha hran mimo G; bez HC je okruh aspoň r·n + 1 |
| P ≠ NP | předpoklad, se kterým je důkaz ve sporu |
| c ∈ {1,2} | váhy jedna a dva ⟹ i metrický TSP je NP-těžký |
Materiály
- L3.6Neexistence r-aproximace TSP [FOTO]
- L3.5TSP je silně NP-těžký (váhy 1/2)
- L3.3Hamiltonovská kružnice a NP-úplnost
Co si vzít k testu
Struktura písně = struktura důkazu sporem. Verse 1: předpoklad a konstrukce — kdyby existovala r-aproximace obecného TSP, vezmu instanci Hamiltonova okruhu (graf G na n vrcholech), doplním na úplný graf. Refrén: klíčová volba vah, kterou si musíš pamatovat přesně — 1 pro hrany z G, 2 + (r−1)·n pro ostatní — a rozhodovací pravidlo: výsledek aproximace ≤ r·n ⟺ Hamilton existuje. Verse 2 počítá, PROČ mezera funguje: s okruhem je OPT = n (aproximace vrátí ≤ r·n), bez okruhu i nejlepší okruh obsahuje aspoň jednu drahou hranu, takže (n−1)·1 + 2 + (r−1)·n = r·n + 1 — víc, než aproximace smí vrátit. Tím by polynomiální algoritmus rozhodl NP-úplný problém → spor s P ≠ NP. Bridge = navazující věta: s váhami 1 a 2 platí trojúhelníková nerovnost, takže i METRICKÝ TSP je NP-těžký (jen ne neaproximovatelný).
Nula v s, nekonečno všude jinde, jak to znáš,
n−1 kol — a v každém VŠECHNY hrany relaxuješ.
Label correcting, nic se nezavírá,
O(n·m) — a záporná hrana? Žádná díra!
n−1 kol, všechny hrany relaxuj!
Po k kolech máš cesty na nejvýš k hran!
Žádná cesta nemá víc než n−1 hran —
Bellman a Ford, O(n·m) — žádný klam!
Důkaz jede ve třech krocích, poslouchej ten ráj:
ALGORITMUS: ℓk je nejvýš ℓk−1 plus cena hrany,
INDUKCE: to je nejvýš cena cesty s k−1 hranami,
PRINCIP OPTIMALITY: dohromady cesta s k hranami — jaj!
Po konci projdi hrany ještě jednou, jen tak zkusmo:
když ℓ(t) > ℓ(v) + c(v,t) —
ZÁPORNÝ CYKLUS v grafu, pozor, kuš ho!
Nedosažitelné vrcholy? Nové s s nulovými hranami, jé!
O čem to je
Bellman–Ford (žebříček #4): label-correcting, zvládá záporné hrany. Důkaz korektnosti = věta o k-té iteraci (řetěz ALG → indukce → Bellmanův princip). Extra průchod po konci detekuje záporný cyklus. (Téma ústní zkoušky.)
Notace → význam
| s | zdroj; ℓ(s)=0, jinde ∞ |
| n−1 | počet kol (delší cesta neexistuje) |
| O(n·m) | složitost (n−1 kol × m hran) |
| k | věta o k-té iteraci: ℓk(v) ≤ délka nejkr. sledu o ≤ k hranách |
| ℓk(v) ≤ ℓk−1(u) + c(u,v) | krok ALGORITMUS v důkazu |
| ℓ(t) > ℓ(v) + c(v,t) | relaxace projde i po konci ⟹ záporný cyklus |
Materiály
- L3.7Korektnost Bellman–Forda (důkaz)
- L2.12Bellman–Ford + detekce záporného cyklu (běh)
- L2.18Teorie záporných cyklů / 5 výroků [FOTO]
Co si vzít k testu
Verse 1 = běh algoritmu (inicializace + n−1 kol přes všechny hrany, label correcting, žádné zavírání — kontrast k Dijkstrovi). Refrén = věta o k-té iteraci, jádro důkazu korektnosti: po k kolech je ℓk(v) nejvýš délka nejkratšího sledu o ≤ k hranách; a protože žádná cesta nemá víc než n−1 hran, po n−1 kolech je hotovo. Verse 2 ti dává tři kroky důkazu indukčního kroku v pořadí, v jakém je napsat: ALGORITMUS (relaxace dává ℓk(v) ≤ ℓk−1(u) + c(u,v)) → INDUKČNÍ PŘEDPOKLAD (ℓk−1 ohraničený sledy o k−1 hranách) → PRINCIP OPTIMALITY (spojením sled o k hranách). Bridge = dvě praktické podotázky: detekce záporného cyklu (jeden průchod navíc — jde-li ještě relaxovat, cyklus existuje) a trik na nedosažitelné vrcholy (nový zdroj s nulovými hranami).
α, to jsou STROJE: jednička je jeden stroj,
P jsou paralelní stejné, Q uniformní — rychlost hraje roli svou,
R jsou unrelated — tabulka časů, každý stroj svůj svět,
O, F, J: open shop, flow shop, job shop — a PS projekty hned!
α — β — γ!
Stroje — úlohy — kritérium!
Vlnka nad d je DEADLINE — tvrdá zeď,
bez vlnky d DUE DATE — lateness, no problém!
Cmax, Lmax, ΣCj —
α β γ — celé schéma, jé!
β, to jsou VLASTNOSTI: pmtn — smíš přerušit,
prec jsou předchůdci, temp: si + lij pod sj musíš ctít,
rj je release time — dřív se prostě nezačne,
pj = konstanta — všechno stejně dlouhé, vidíš, jak to jde snadně!
γ: Cmax je makespan — konec posledního z nás,
Lmax: maximum z Cj − dj — zpoždění hlas,
ΣCj, nebo s vahami ΣwjCj,
a prázdné γ? Jen rozhodni: jde to, nejde — oukej!
O čem to je
Grahamova notace α | β | γ — slovníček, kterým se zapisují všechny rozvrhovací problémy: stroje | vlastnosti úloh | kritérium. Nejzrádnější detail: deadline (d̃, tvrdý) vs. due date (d, měkký).
Notace → význam
| α | β | γ | stroje | úlohy | kritérium |
| P, Q, R, O/F/J, PS | identické, uniformní, unrelated, shopy, projekty |
| d̃j | deadline — vlnka, nesmí se překročit |
| dj | due date — bez vlnky, smí; měří se lateness |
| Cmax, Lmax = max(Cj−dj), ΣCj, ΣwjCj | kritéria: makespan, max lateness, součty dokončení |
| pmtn | preempce povolena |
| si + lij ≤ sj | temporální vazba (temp) |
| rj | release time — dřív se nezačne |
| pj = p | všechny úlohy stejně dlouhé |
Materiály
- L5.1Grahamova notace α|β|γ(připravujeme)
Co si vzít k testu
Píseň kopíruje tři pozice zápisu: Verse 1 = α (stroje), Verse 2 = β (vlastnosti úloh), Bridge = γ (kritérium). Když v testu čteš zadání typu 1 | pmtn, rj | Lmax, přehraj si příslušnou sloku a přelož každé písmeno — píseň je slovník. Refrén vtlouká rozdíl, na kterém se nejvíc chybuje: d̃ s vlnkou je DEADLINE (tvrdá zeď, nesmí se překročit — rozvrh jinak není přípustný), d bez vlnky je DUE DATE (smí se přejet, jen se měří zpoždění/lateness). Z γ si pamatuj definici Lmax = max(Cj − dj) a poslední řádek bridge: prázdné γ znamená čistě rozhodovací problém („existuje přípustný rozvrh?“), žádná optimalizace.
P2 a Cmax? NP-těžké — two partition to ví,
práh je půlka sumy p — tak zní redukce slovy.
P s preempcí a Cmax? McNaughton, O(n), easy!
Preempce, release, deadliny, jen rozhodnout? Maximální tok to jistí!
List scheduling: 2 − 1/R!
LPT: 4/3 − ⅓/R!
Muntz a Coffman: 2 − 2/R!
Tři zlomky pro zkoušku — tak si je pamatuj, věř!
Jeden stroj a Lmax? EDD — řaď podle due date!
Release a preempce k tomu? Horn — earliest deadline first, kamaráde!
Precedence navíc? Chetto, Silly, Bouchentouf — okna upraví,
release s tvrdým deadlinem bez preempce? Bratley — větve a meze — to tě zabaví!
P a Cmax bez preempce: LPT — nebo přesně Rothkopf, pseudopolynom!
PS1 s temp: time-indexed ILP — postav si dóm!
Jeden stroj, release, deadline: NP-těžké — three partition zvoní —
tahle mapa problém–algoritmus tě u zkoušky zachrání!
O čem to je
Mapa problém → algoritmus → faktor pro rozvrhovací slot. Tři aproximační zlomky, které se nejvíc pletou, plus kdo řeší co přesně (EDD, Horn, CSB, Bratley, McNaughton, Rothkopf).
Notace → význam
| P2 || Cmax, P | pmtn | Cmax, 1 || Lmax, PS1 | temp | Cmax | problémy zmíněné v písni (Grahamův zápis) |
| NP | NP-těžké (redukce z 2-partition / 3-partition) |
| 2 − 1/R | faktor list schedulingu |
| LPT: 4/3 − 1/(3R) | faktor LPT (longest processing time first) |
| 2 − 2/R | faktor Muntz & Coffman |
| EDD | earliest due date — řazení pro 1 || Lmax |
| O(n) | McNaughton |
| ½ Σpj | práh redukce z 2-partition |
| ILP | time-indexed model (viz píseň 5) |
Materiály
- L5.14Referenční tabulka: problém → algoritmus
- L5.12List scheduling (faktor)(připravujeme)
- L5.7EDD a Hornův algoritmus(připravujeme)
- L5.8Chetto–Silly–Bouchentouf(připravujeme)
- L5.9Bratleyho algoritmus (B&B)(připravujeme)
- L5.11Rothkopf DP(připravujeme)
Co si vzít k testu
Tohle je tahák „problém → algoritmus → záruka“ pro celý rozvrhovací slot. Refrén = tři aproximační zlomky, které se navzájem pletou; pamatuj si je jako trojici v tomhle pořadí: list scheduling 2 − 1/R, LPT 4/3 − 1/(3R), Muntz & Coffman 2 − 2/R. Sloky mapují, kdo řeší co PŘESNĚ a co je NP-těžké: P2||Cmax je NP-těžké redukcí z 2-partition (práh = půlka sumy p); s preempcí to McNaughton zvládne v O(n); rozhodovací verze s preempcí, release a deadliny jde přes maximální tok. Verse 2 = jednostrojové úlohy: EDD na 1||Lmax, Horn (EDF) když přibude release+preempce, Chetto–Silly–Bouchentouf upraví okna při precedencích, Bratley (B&B) bez preempce s tvrdými deadliny. U otázky „jakým algoritmem a s jakou zárukou“ odpověz přesně jedním řádkem téhle písně.
Tenhle batoh je jiný, než ho znáš ze školy:
stav NENÍ kapacita — stav je CENA, holky!
x(k,j): nejmenší váha, jak cenu k poskládat
z prvních j položek — tak se to má počítat!
Minimum ze dvou: NECH TO BÝT — x(k, j−1),
nebo PŘIDEJ j: x(k − cj), plus váha wj!
Na konci vem největší k s váhou nejvýš W —
O(n·C) — pseudopolynom — DP přes ceny, jé!
Nula nula je nula, jinak nekonečno na startu,
rozhodnutí si piš do s(k,j) — neztratíš mapu.
Zpátky pak: když s je jedna, položka j je v batohu,
sniž k o cj — a couvej až k prologu!
Bonus pro fajnšmekry: seřaď podle c / w,
h je PRVNÍ položka, co se nevejde —
vezmi LEPŠÍ z prefixu a h samotné:
dvojková aproximace — polovina optima jistá je!
O čem to je
Knapsack DP indexovaná CENOU — kurz učí neobvyklou variantu: stav je cena, hodnota tabulky je minimální váha. Bonus v bridgi: Dantzigův greedy a 2-aproximace.
Notace → význam
| x(k,j) | min. váha, jak cenu k poskládat z prvních j položek |
| x(k, j−1) | větev „položku j nepřidám“ |
| x(k−cj, j−1) + wj | větev „položku j přidám“ |
| W | kapacita; výsledek max{k : x(k,n) ≤ W} |
| O(n·C) | pseudopolynom, C = Σcj |
| DP | dynamické programování |
| s(k,j) | uložené rozhodnutí pro zpětnou rekonstrukci |
| cj, cj/wj | cena položky; Dantzig řadí podle poměru cena/váha |
| h | první nevejdoucí; max(Σ1..h−1cj, ch) ≥ OPT/2 |
Materiály
- L7.2Knapsack DP indexovaný cenou
- L7.1Knapsack DP (tabulka + backtracking)
- L3.11Knapsack: greedy + 2-aproximace (důkaz)
Co si vzít k testu
První věc, kterou v odpovědi řekni, je pointa Verse 1: tahle DP NENÍ školní tabulka přes kapacitu — stav je CENA k a hodnota x(k,j) je nejmenší váha, kterou cenu k poskládáš z prvních j položek. Refrén = rekurence (minimum z „nech být“ x(k, j−1) a „přidej j“ x(k−cj, j−1) + wj), čtení výsledku (největší k s váhou ≤ W) a složitost O(n·C) — pseudopolynom, protože C je suma cen, ne velikost vstupu. Verse 2 = detaily, bez kterých běhová úloha nestojí: inicializace (x(0,0)=0, jinak ∞) a rekonstrukce řešení zpětným průchodem přes uložená rozhodnutí s(k,j). Bridge je samostatná testová otázka „2-aproximace knapsacku“: seřaď podle c/w, h je první položka, co se nevejde, a lepší z {prefix 1..h−1} a {h samotná} má aspoň polovinu optima.