Kombinatorická optimalizace — příprava na zkoušku

Cíl: písemka + ústní 15. 6. 2026 · 6 úloh / 40 bodů · řazeno podle bodové návratnosti

Jak s učebnicí pracovat

Jdi shora dolů — kapitoly jsou seřazené podle očekávaných bodů ve zkoušce.
Každá lekce učí jednu novou věc. Otázky „🤔 Zkus sám" si vždy nejdřív zodpověz, pak rozklikni.
Úlohy s FOTO vyřeš celé na papír a pošli fotku ke kontrole.
Lekce s NICE jsou doplňkové — při časové tísni je můžeš odložit bez ztráty bodového slotu.
Zadání úloh jsou anglicky (jako v písemce), výklad česky (jako u ústní).
Plná osnova všech 93 lekcí: OSNOVA.md.

Co po nás chtějí u zkoušky — odškrtávací checklist

K0 — Základní jazyk grafů a ILP

prerekvizitní minikapitola · 8 lekcí · bez FOTO — projeď rychle, vracej se podle odkazů

Než se pustíš do zkouškových témat: tahle minikapitola tě naučí slovník, kterým je psaný celý zbytek webu — co je graf, strom, kostra, párování a co znamená „celočíselné lineární programování" (ILP). Sama se u zkoušky neptá, ale bez ní nebudeš rozumět zadáním ostatních slotů. Když na něco narazíš jinde, vracej se sem podle odkazů.

K1 — ILP modelování (Slot 1)

100 % výskyt × 7 bodů · 15 lekcí · FOTO: L1.9 Wedding, L1.12 Loot, L1.14 Toys

Dostaneš slovní úlohu („rozsaď svatební hosty tak, aby…") a tvým úkolem je přepsat ji do matematiky: zavést proměnné, napsat účelovou funkci (co minimalizovat/maximalizovat) a omezení (nerovnice). Nic se nepočítá do čísla — odevzdáváš jen model. Kapitola tě naučí typické „překladatelské triky": jak do nerovnic dostat logiku (když–pak, nebo, a), fixní náklady nebo volbu z více možností pomocí 0/1 proměnných a tzv. big-M.

L1.1Cílová funkce a základní omezení
L1.2Přiřazovací (assignment) struktura
L1.3Modelování logiky: implikace, XOR, AND
L1.4big-M: disjunkce omezení
L1.5Navázání binární na spojitou (aktivace)
L1.6Fixed-charge (fixní náklady)
L1.7Po částech konstantní funkce
L1.8Rozdíl / omezení rozptylu (max−min)
L1.9VYVRCHOLENÍ: Wedding planFOTO
L1.10Linearizace absolutní hodnoty
L1.11Poměrová a max-z-více podmínka
L1.12Implikace mezi skupinami (Loot)FOTO
L1.13„Worst-case" omezení přes kombinace
L1.14Sousednost a prostorová omezení (Toys)FOTO
L1.15Časově/pozičně indexované proměnné

K2 — Nejkratší cesty (Slot 2)

90 % × 7 bodů · 18 lekcí · FOTO: L2.5 Edge costs, L2.8 Dangerous adventure, L2.18 Negative cycles

Máš mapu (graf) s ohodnocenými spoji a hledáš nejlevnější trasu z bodu A do bodu B. Kapitola učí klasické algoritmy (Dijkstra, Bellman-Ford) — jak je ručně „odkrokovat" na papíře krok po kroku — a hlavně jak na nejkratší cestu chytře převést i úlohu, která tak na první pohled nevypadá (násobení pravděpodobností, plánování v čase apod.). Pozor je na záporné hrany a záporné cykly.

L2.1Záporné váhy ano, záporné cykly ne
L2.2Bellmanův princip optimality
L2.3Relaxace hrany
L2.4Dijkstrův algoritmus (běh)
L2.5Pořadí expanze a tie-breaking (Edge costs)FOTO
L2.6Split vrcholu (cena na vrcholu → na hraně)
L2.7Transformace součinu na součet: −log
L2.8VYVRCHOLENÍ: Dangerous adventureFOTO
L2.9Modelování reálné úlohy jako SP (DAG)
L2.10Stavový automat jako graf
L2.11Časově expandovaná síť (constrained SP)
L2.12Bellman-Ford + detekce záporného cyklu
L2.13SP v DAG v O(V+E)
L2.14Floyd-Warshall + nejdelší cestyNICE
L2.15Škálování vah a zachování nejkratší cesty
L2.16Dijkstra a počet hran cesty
L2.17Nejdelší cesta: kdy těžká a kdy snadná
L2.18VYVRCHOLENÍ: Teorie záporných cyklů / 5 výrokůFOTO

K3 — Důkaz / teorie (Slot 3)

95 % × 7 bodů · 16 lekcí · FOTO: L3.2 Dijkstra proof, L3.6 TSP r-aprox, L3.10 Christofides

Tady se nepočítá, ale dokazuje a argumentuje: proč nějaký algoritmus dává správný výsledek, proč je problém „těžký" (NP), nebo co přesně zaručuje aproximační algoritmus (řešení nanejvýš r-krát horší než optimum). Slot 3 chce souvislý důkaz nebo úvahu sepsanou vlastními slovy — kapitola tě provede těmi, co padají nejčastěji (korektnost Dijkstry/Bellman-Forda, těžkost TSP, Christofides 3/2).

L3.1Co je aproximační algoritmus a faktor r
L3.2Důkaz korektnosti DijkstryFOTO
L3.3Hamiltonovská kružnice a NP-úplnost
L3.4TSP jako ILP s eliminací podtras (MTZ)
L3.5TSP je silně NP-těžký (redukce z HC, váhy 1/2)
L3.6Neexistence r-aproximace pro obecný TSPFOTO
L3.7Korektnost Bellman-Forda
L3.8aMetrický TSP + trojúhelníková nerovnost + shortcutting
L3.8bMST jako dolní mez (OPT ≥ c(MST))
L3.8cEulerovský tah a zdvojení hran (sudý stupeň)
L3.9Double-tree algoritmus (2-aproximace metrického TSP)
L3.10VYVRCHOLENÍ: Christofides 3/2FOTO
L3.11Knapsack: fractional greedy + 2-aproximace
L3.12Teorie ILP/TUM (ústní opora)
L3.13Ekvivalence definic stromuNICE
L3.14k-OPT local searchNICE

K4 — Toky a řezy (Slot 4)

~100 % × 7 bodů · 15 lekcí · FOTO: L4.4 Ford-Fulkerson, L4.5 Residents & council

Představ si potrubní síť: kolik vody protlačíš ze zdroje do spotřebiče, když má každá trubka omezenou kapacitu? To je maximální tok. Kapitola učí algoritmus Ford-Fulkerson (jak ho odkrokovat hledáním „augmentujících cest"), klíčovou dualitu max-tok = min-řez a hlavně jak na tok převést úlohy, které s vodou nesouvisí (přiřazování lidí k úkolům, párování, zaokrouhlování tabulek).

L4.1Síť, tok, Kirchhoffův zákon
L4.2Reziduální graf a augmentující cesta
L4.3Ford-Fulkerson: iterativní augmentace (běh)
L4.4Řez a věta max-flow/min-cutFOTO
L4.5Modelování přiřazení jako tok (vrstvená síť)FOTO
L4.6Feasible flow with balances
L4.7Počáteční přípustný tok při nenulových dolních mezích
L4.8Matrix rounding přes toky
L4.9Bipartitní matching přes max flow
L4.10Minimum Cost Flow + reziduální graf s cenami
L4.11Cycle canceling (řešení MCF)
L4.12Assignment problem přes MCF + min-weight perfect matching
L4.13Directed Chinese Postman jako MCFNICE
L4.14Max flow s logickými omezeními (ILP)
L4.15Multikomoditní tok (ILP)NICE

K5 — Rozvrhování (Slot 5)

100 % × 6 bodů · 16 lekcí · FOTO: L5.0 toky-rozvrh, L5.3 time-indexed ILP, L5.5 B&B, L5.10 Muntz&Coffman

Máš úkoly (tasks) a stroje (procesory) a chceš je naplánovat v čase tak, aby něco vyšlo co nejlépe — typicky aby bylo vše hotové co nejdřív ($C_{max}$). Kapitola nejdřív naučí značení $\alpha|\beta|\gamma$, kterým se rozvrhovací problémy stručně pojmenovávají (stroje | podmínky | kritérium), a pak sadu konkrétních algoritmů — ke každému typu úlohy ten správný. Tahák „problém → algoritmus" je v poslední lekci.

L5.1Grahamova notace α|β|γ
L5.0Rozvrhování přes toky (P|pmtn,rj,dj|)FOTO
L5.2Precedence a temporální omezení; graf TC
L5.3Time-indexed ILP pro PS1|temp|CmaxFOTO
L5.4McNaughton (P|pmtn|Cmax)
L5.5Branch & Bound pro ILP (grafické řezání)FOTO
L5.6aRelative-order ILP pro 1|prec|Σw_jC_j
L5.6bLP relaxace jako dolní mez v B&B
L5.7EDD a Hornův algoritmus (1|pmtn,r_j|Lmax)
L5.8Chetto-Silly-Bouchentouf (prec → nezávislé, pak EDF)
L5.9Bratleyho algoritmus (1|r_j,d̃_j|Cmax, B&B)
L5.10Muntz & Coffman (P|pmtn,prec|Cmax)FOTO
L5.11Rothkopf DP pro P||Cmax
L5.12List scheduling pro P|prec|Cmax (faktor)
L5.13NP-těžkost rozvrhování (redukce)NICE
L5.14Referenční tabulka: problém → algoritmus (tahák)

K6 — CSP / AC-3 (Slot 6)

55 % × 6 bodů · 3 lekce · FOTO: L6.3 AC-3

Hlavolam typu sudoku: máš proměnné, každá s množinou možných hodnot („doménou"), a omezení mezi nimi (např. „tyhle dvě se musí lišit"). Než začneš zkoušet kombinace, vyplatí se domény pročistit — vyhodit hodnoty, které evidentně nemůžou vyjít, protože pro ně u souseda neexistuje žádný partner. Přesně to dělá algoritmus AC-3 (řetězová reakce škrtů řízená frontou hran) a Slot 6 chce jeho ruční odkrokování. AC-3 řešení nehledá — jen zmenší domény; to je celé.

K7 — Knapsack (doplňková)

doplňková · 2 lekce · foto volitelně

Batoh s omezenou nosností a věci, každá s nějakou cenou a vahou — co vzít, aby měl náklad největší hodnotu a nepřetížil se? Klasická úloha řešená dynamickým programováním (postupné vyplňování tabulky a zpětné dohledání, co se vzalo). Doplňková kapitola — ve zkoušce se objevuje spíš okrajově, ale technika tabulkového DP se hodí i jinde.