Praktický test practise

ko_test_painting.pdf

• $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*} $$

Psaný na přednášce v 10. týdnu. Rok ze kterého je toto PDF bohužel neznám.

ko_test_2.pdf

Test 2 nevyplněný $\LaTeX$ source (ko_test2.tex)

Níže si můžete vyzkoušet otázky a odpovědi bez řešení, vyberte si kolik chcete otázek a odstartujte test.

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

Zkouška