Zadania dodatkowe niewymagające programowania¶
1. Problem plecakowy¶
Na podstawie modelu przedstawionego w notatniku należy przekształcić końcową funkcję celu
$$ A \left( \sum_{i=1}^{n} w_i x_i + \sum_{k=0}^{K} 2^k y_k - W \right)^2 - B \sum_{i=1}^{n} v_i x_i, $$
do jawnej postaci QUBO, tj. do postaci
$$ \sum_i Q_{ii} z_i + \sum_{(i,j)} Q_{ij} z_i z_j. $$
W szczególności należy:
- rozwinąć wyrażenie kwadratowe,
- uporządkować wyrazy liniowe oraz dwuliniowe,
- wyznaczyć współczynniki macierzy $Q$ odpowiadające otrzymanemu modelowi.
2. Problem podziału grafu¶
Rozważmy graf prosty $G = (V,E)$ o parzystej liczbie wierzchołków
$$ N = |V|. $$
Celem jest wyznaczenie takiego podziału zbioru wierzchołków $V$ na dwa rozłączne podzbiory o jednakowej liczności, tj. po $\frac{N}{2}$ wierzchołków każdy, aby liczba krawędzi łączących oba podzbiory była minimalna.
Należy:
- sformułować powyższy problem w postaci modelu QUBO lub modelu Isinga,
- uzasadnić wybór dogodniejszej reprezentacji,
- (opcjonalnie) sprowadzić otrzymany model do postaci jawnej.
3. Problem pełnego pokrycia¶
Rozważmy zbiór
$$ U = \{1, \ldots, n\}, $$
oraz rodzinę jego podzbiorów
$$ V_i \subseteq U, \qquad i = 1, \ldots, N, $$
spełniającą warunek
$$ U = \bigcup_{i=1}^{N} V_i. $$
Pytanie polega na rozstrzygnięciu, czy istnieje taki wybór podrodziny
$$ R \subseteq \{V_1, \ldots, V_N\}, $$
że:
- zbiory należące do $R$ są parami rozłączne, tzn. $$ V_i \cap V_j = \emptyset \qquad \text{dla } i \neq j, $$
- suma zbiorów należących do $R$ pokrywa cały zbiór $U$, tj. $$ \bigcup_{V \in R} V = U. $$
Innymi słowy, należy ustalić, czy istnieje wybór rozłącznych podzbiorów, które łącznie tworzą dokładnie zbiór $U$.
Należy:
- przedstawić ten problem w postaci modelu QUBO lub modelu Isinga oraz wskazać, która z tych reprezentacji jest bardziej naturalna w tym przypadku,
- rozszeżyć ten problem do problemu optymalizacyjnego. Znaleźć najmniejszy zbiór $R$ spełniający podane wymagania.
- (opcjonalnie) sprowadzić model do postaci jawnej.
4. Problem Max-Cut¶
Należy sformułować problem Max-Cut (notatnik) w postaci modelu Isinga.
--