{{ :courses:b4m35ko:master_zkouska_ko-1.pdf | Sborník zkoušek }}

Materiály zpracované od Fable5:
[[https://knapejar.github.io/CVUT-FEL-KO-materials-2026/pisnicky.html|Vibe písničky]]
[[https://knapejar.github.io/CVUT-FEL-KO-materials-2026/|Vibe materiály]]

===== Zkouška - řešené příklady =====

++++ Tučnáci|
  * $P = \{1, \dots, n\}$: tučňáci
  * $C = \{ (x,y) \mid 1 \le x \le w, 1 \le y \le h \}$: kry
  * $T = \{0, 1, \dots, T_{max}\}$: diskrétní čas
  * $N(c)$: okolí políčka $c$
  * $c_s(i) \in C$: startovní pozice tučňáka $i$
  * $c_e(i) \in C$: konečná pozice tučňáka $i$

$$
\begin{align*}
\min \quad & 0 \\
\text{s. t.:} \quad & \\
% Initial and final positions
x_{i, c_s(i), 0} &= 1 && \forall i \in P \rightarrow \text{starts at cell}\ i\\
x_{i, c_e(i), T_{max}} &= 1 && \forall i \in P \rightarrow \text{ends at cell}\ i \\
e_{i, c_s(i), 0} &= 1 && \forall i \in P \rightarrow \text{enters cell}\ \text{at time}\ 0 \\
% One position per penguin
\sum_{c \in C} x_{i, c, t} &= 1 && \forall i \in P, \forall t \in T \rightarrow \text{the penguin is at exactly one position every tick}\\
% At most one penguin per cell (collision prevention)
\sum_{i \in P} x_{i, c, t} &\le 1 && \forall c \in C, \forall t \in T \rightarrow \text{one cell occupied by max one penguin at a time}\\
% Valid moves to 4-neighborhood
x_{i, c, t-1} &\le x_{i, c, t} + \sum_{d \in N(c)} x_{i, d, t} && \forall i \in P, \forall c \in C, \forall t \in \{1 \dots T_{max}\} \rightarrow \text{the penguin can stay or move to a neighbourhood} \\
% Entry variable triggers
e_{i, c, t} &\ge x_{i, c, t} - x_{i, c, t-1} && \forall i \in P, \forall c \in C, \forall t \in \{1 \dots T_{max}\} \rightarrow \text{the entry is triggered by a move between two time ticks}\\
% Sinking ice cubes (max one entry overall)
\sum_{i \in P} \sum_{t=0}^{T_{max}} e_{i, c, t} &\le 1 && \forall c \in C \rightarrow \text{each cube can be entered at most one time}\\
% Variables
\text{variables:} \quad & \\
x_{i, c, t} &\in \{0, 1\} && \forall i \in P, \forall c \in C, \forall t \in T \rightarrow = 1\ \text{if penguin present at time and cell}\\
e_{i, c, t} &\in \{0, 1\} && \forall i \in P, \forall c \in C, \forall t \in T \rightarrow = 1\ \text{if penguin entered at time and cell}
\end{align*}
$$

++++

===== Zkouška 2026 =====
{{ :courses:b4m35ko:ko-25-5-2026.pdf_2-6.pdf | První termín}}

===== Zkouška 2025 =====

==== První termín ====
  - ILP formulace - maximalizace součtu absolutních hodnot
  - SPT formulace problému s pravděpodobností na hranách grafu (podobný jako SPT.dioid.reliability v přednášce)
  - Christofides algorithm - derivovat aproximační faktor 
  - Ford-Fulkerson - iterace na grafu se zadaným initial fessible flow, určit upper bound na počet iterací 
  - AC3 arc consistency 
  - ILP formulace time-indexed PS1|temp|Cmax


===== Zkouška 2023 =====

{{ :courses:b4m35ko:2023_zkouska.pdf |Zkouška}}