Zaawansowane algorytmy i struktury danych/Ćwiczenia 5

From Studia Informatyczne

Spis treści

Zadanie 1

Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego wierzchołka w DAG-u o dowolnych wagach krawędzi.

Rozwiązanie

Po pierwsze w DAG-u nie ma cykli, a więc także nie ma cykli o ujemnej wadze. Zauważmy, że wszystkie ścieżki w DAG-u idą zgodnie z porządkiem topologicznym, a więc także te najkrótsze. Odległości DAG-u można więc policzyć wykonując relaksację krawędzi w porządku topologicznym.

Zadanie 2

Układ ograniczeń różnicowych zadany jest poprzez zbiór zmiennych X=\{x_0, \ldots, x_n\} oraz zbiór nierówności liniowych O=\{x_{i_0} - x_{j_0} \le b_0, \ldots, x_{i_m} - x_{j_m} \le b_m\}, gdzie i_k, j_k \in X, b_k\in \mathcal{R} dla k = 0,\ldots, m. Rozwiązaniem układu ograniczeń różnicowych jest wartościowanie zmiennych X, dla którego spełnione są wszystkie nierówności z O. Zaproponuj efektywny algorytm znajdujący rozwiązanie układu ograniczeń liniowych.

Rozwiązanie

Problem ten można rozwiązać poprzez sprowadzenie do problemu najkrótszych ścieżek z jednym źródłem i wykorzystanie algorytmu Bellmana-Forda. Mając dane zbiory X i O, konstruujemy na ich podstawie graf G=(X,E) oraz funkcję wagową w:E \to \mathcal{R} w następujący

sposób:


E = \{(x_i, x_j) : x_{i} - x_{j} \le b \in O\},
w(x_i,x_j) = \min\{b : x_{i} - x_{j} \le b \in O\}.


Łatwo teraz pokazać, że w grafie G nie ma cyklu ujemnej długości, jeżeli układ ograniczeń różnicowych ma rozwiązanie, oraz odległości w grafie G zadają rozwiązanie tego układu.

Zadanie 3

Skrzynka d-wymiarowe o wymiarach (x_1, x_2, \ldots, x _d) mieści się w skrzynce o wymiarach (y_1, y_2,\ldots, y_d), jeżeli istnieje permutacja p zbioru \{1, 2,\ldots, d\} tak, że x_{p_1} < y_1, x_{p_2} < y_2, \ldots, x_{p_d} < y_d.

  1. Uzasadnij, że relacja mieszczenia się jest przechodnia.
  2. Opisz skuteczną metodę określania, czy jedna d-wymiarowa skrzynka zagnieżdża się w drugiej.
  3. Przypuścimy, że dany jest zbiór n d-wymiarowych skrzynek {B_1, B_2,\ldots, B_n}. Podaj skuteczny algorytm określający najdłuższy ciąg \{B_1,B_2,\ldots,B_n\} skrzynek mieszczących się w sobie nawzajem, tzn. takich, że B_{j} mieści się w B_{j+1} dla j = 1, 2,\ldots, n - 1. Podaj czas działania algorytmu ze względu na n i d.


Rozwiązanie

  1. Jeżeli p to permutacja pokazująca, że A mieści się w B, a p' pokazuje, że B mieści się w C, to złożenie permutacji p \cdot p' pokazuje, że A mieści się w C.
  2. W celu sprawdzenia, czy dwie skrzynki mieszczą się w sobie, można użyć metody zachłannej. Jeżeli chcemy sprawdzić czy skrzynka o wymiarach (x_1, x_2, \ldots, x_d) mieści się w skrzynce o wymiarach (y_1, y_2, \ldots, y_d) to sprawdzamy, czy po ich posortowaniu zachodzi x_i < y_i dla i = 1,\ldots, d.

Najpierw sortujemy wymiary skrzynek

Zadanie 4

Arbitraż walutowy polega na operacji jednoczesnego kupna i sprzedaży waluty na tym samym rynku w celu osiągnięcia zysku wynikającego z różnic kursowych. Na przykład: załóżmy, że kurs wymiany 1 USD wynosi 46.4 rupii, kurs rupii w jenach japońskich wynosi 2.5, natomiast 1 jen kosztuje 0.0091 USD. Poprzez wymianę walut, spekulant może rozpocząć transakcję kupna USD: 46.4 × 2.5 × 0.0091 = 1.0556 USD, osiągając korzyść finansową w wysokości 5.56 %. Przypuścimy, że mamy dane n walut c_1, c_2,\ldots, c_n i n \times n tabelę R kursów walutowych, tak że kurs 1 jednostki waluty c_i wynosi R[i,j] jednostek waluty c_j. Podaj skuteczny algorytm stwierdzający istnienie następującego ciągu walut, takich że:

  1. R[i_1, i_2] \cdots R[i_2, i_3] \cdot R[i_{k-1}, i_k] · R[i_k, i_1] > 1. Zanalizuj czas działania algorytmu.
  1. Podaj skuteczny algorytm drukowania takiego ciągu walut, jeżeli on istnieje. Ponadto, zanalizuj czas działania tego algorytmu.

Rozwiązanie