Zaawansowane algorytmy i struktury danych/Ćwiczenia 5

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

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

Rozwiązanie

Zadanie 2

Układ ograniczeń różnicowych zadany jest poprzez zbiór zmiennych oraz zbiór nierówności liniowych , gdzie , dla . Rozwiązaniem układu ograniczeń różnicowych jest wartościowanie zmiennych , dla którego spełnione są wszystkie nierówności z . Zaproponuj efektywny algorytm znajdujący rozwiązanie układu ograniczeń liniowych.

Rozwiązanie

Zadanie 3

Skrzynka -wymiarowe o wymiarach mieści się w skrzynce o wymiarach , jeżeli istnieje permutacja zbioru tak, że .

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


Rozwiązanie

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 walut i tabelę kursów walutowych, tak że kurs 1 jednostki waluty wynosi jednostek waluty . Podaj skuteczny algorytm stwierdzający istnienie następującego ciągu walut, takich że:

  1. Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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