Co po nás chtějí u zkoušky

Odškrtávací seznam dovedností · stav se ukládá v prohlížeči · u každé položky odkaz, kde je vyložená

Slot 1 — ILP modelování ~100 %

• Ze slovní úlohy sestavit kompletní ILP: proměnné, účelová funkce, omezení✍️ napsat

  → [L1.1] Cílová funkce a omezení · [L1.9] Wedding · [L1.14] Toys · [L1.12] Loot
• big-M: disjunkce omezení, „buď–anebo"✍️ napsat

  → [L1.4] big-M · [L1.3] logika přes 0/1
• Linearizace absolutní hodnoty a „max z více"✍️ napsat

  → [L1.10] abs. hodnota · [L1.11] poměr a max · [L1.8] rozptyl max−min

Slot 2 — Nejkratší cesty ~90 %

• Odkrokovat Dijkstru + pořadí expanze / tie-breaking🔁 odkrokovat

  → [L2.4] Dijkstra (běh) · [L2.8] Dangerous adventure · [L2.5] Edge costs
• Bellman-Ford + detekce záporného cyklu🔁 odkrokovat💬 ústní

  → [L2.12] Bellman-Ford + záporný cyklus · [L2.18] teorie záporných cyklů
• Převést úlohu na SP: −log součinu, časová expanze, DAG✍️ napsat

  → [L2.7] −log: součin → součet · [L2.11] časově expandovaná síť · [L2.9] reálná úloha jako SP

Slot 3 — Důkaz / teorie ~95 %

• Důkaz korektnosti Dijkstry✍️ dokázat

  → [L3.2] Důkaz Dijkstry
• Neexistence r-aproximace pro obecný TSP✍️ dokázat

  → [L3.6] r-aprox TSP · [L3.5] TSP silně NP-těžký
• Christofides 3/2: dokázat faktor (pseudokód bývá zadaný)✍️ dokázat

  → [L3.10] Christofides 3/2 · [L3.8a] metrický TSP + Δ-nerovnost · [L3.9] double-tree 2-aprox
• Korektnost Bellman-Forda✍️ dokázat

  → [L3.7] Korektnost Bellman-Forda

Slot 4 — Toky a řezy ~100 %

• Odkrokovat Ford-Fulkerson + najít minimální řez🔁 odkrokovat

  → [L4.3] Ford-Fulkerson (běh) · [L4.4] řez a max-flow/min-cut
• Modelovat přiřazení / párování jako tok (vrstvená síť)✍️ napsat

  → [L4.5] přiřazení jako tok · [L4.9] bipartitní matching
• Initial feasible flow při nenulových dolních mezích / balancech✍️ napsat💬 ústní

  → [L4.7] počáteční přípustný tok · [L4.6] feasible flow s balancy
• Rozvrhování / matrix rounding jako max-flow (úkoly → intervaly → stok)✍️ napsat🔁 odkrokovat

  → [L5.0] rozvrhování přes toky · [L4.8] matrix rounding
• Min-cost flow + reziduální graf s cenami, cycle canceling🔁 odkrokovat

  → [L4.10] Min-cost flow · [L4.11] cycle canceling
• Assignment problem / min-weight perfect matching přes MCF (Hungarian)✍️ napsat

  → [L4.12] assignment přes MCF

Slot 5 — Rozvrhování ~100 %

• Číst a zapsat Grahamovu notaci $\alpha|\beta|\gamma$✍️ napsat

  → [L5.1] notace α|β|γ · [L5.14] tahák problém → algoritmus
• Muntz & Coffman: odkrokovat úrovně + Gantt🔁 odkrokovat

  → [L5.10] Muntz & Coffman
• Time-indexed ILP pro $PS1|temp|C_{max}$✍️ napsat

  → [L5.3] time-indexed ILP · [L5.2] precedence a graf TC
• Branch & Bound (grafické řezání) a Bratley🔁 odkrokovat💬 ústní

  → [L5.5] B&B pro ILP · [L5.9] Bratley
• McNaughton (wrap-around) pro $P|pmtn|C_{max}$🔁 odkrokovat

  → [L5.4] McNaughton
• EDD a Hornův algoritmus pro $1|pmtn,r_j|L_{max}$🔁 odkrokovat

  → [L5.7] EDD a Horn · [L5.8] Chetto-Silly-Bouchentouf

Slot 6 — CSP / AC-3 ~55 % (rotuje)

• Odkrokovat AC-3: zredukovat domény, zapsat frontu před každou revizí🔁 odkrokovat

  → [L6.3] AC-3 + oditerování · [L6.1] CSP a arc consistency · [L6.2] REVISE
• Slovně popsat, jak AC-3 funguje (fronta, REVISE, neúplnost)💬 ústní

  → [L6.3] Key takeaways

Doplňkové & rotující sloty

• Knapsack DP: tabulka + zpětná rekonstrukce + složitost🔁 odkrokovat💬 ústní

  → [L7.1] Knapsack DP · [L7.2] cost-indexed
• TUM → celočíselnost (jak z LP zaručit integer řešení)💬 ústní

  → [L3.12] Teorie ILP / TUM
• List scheduling: pseudokód + faktor aproximace (i pro LPT)✍️ napsat

  → [L5.12] List scheduling (faktor)
• SP v DAG v $O(V+E)$ (výroba topologického pořadí)💬 ústní

  → [L2.13] SP v DAG v O(V+E)
• Knapsack: fractional greedy + důkaz 2-aproximace✍️ dokázat

  → [L3.11] Knapsack 2-aproximace