Egzamin 2019/20 (04.02.2020)#

Zadanie 1 [7 punktów]#

Słowa kluczowe: optymalne porównania

Zaproponuj optymalny ze względu na porównania algorytm sortujący 6 różnych liczb a, b, c, d, e, f, o których wiadomo, że a < b oraz c < d.

  1. [3 punkty] Wykaż, że każdy taki algorytm wymaga wykonania w pesymistycznym przypadku co najmniej 8 porównań.

  2. [4 punkty] Zaprojektuj algorytm, który sortuje liczby a, b, c, d, e, f wykonując w pesymistycznym przypadku co najwyżej 8 porównań.

Zadanie 2 [10 punktów]#

Słowa kluczowe: struktury danych, DFS

  1. [2 punkty] Podaj, ile wynosi największa wysokość DFS-drzewa, a ile BFS-drzewa, w n-wierzchołkowym grafie dwuspójnym, dla n > 2?

  2. [2 punkty] Podaj, ile wynosi najmniejsza wysokość DFS-drzewa, a ile BFS-drzewa, w n-wierzchołkowym grafie dwuspójnym, dla n > 2?

  3. [6 punktów] Zaproponuj wydajny algorytm, który sprawdza, czy w grafie silnie spójnym istnieje (skierowana) marszruta zamknięta o długości nieparzystej [3 punkty], a następnie znajduje jedną z takich marszrut [3 punkty].

Zadanie 3 [6 punktów]#

Słowa kluczowe: teksty

Powiemy, że dwa ciągi liczb całkowitych \(a_1, a_2, \ldots, a_n\) i \(b_1, b_2, \ldots, b_n\) są podobne, gdy istnieje takie c, że \(b_i = c*a_i\), dla każdego \(i = 1, 2, \ldots, n\).

Zaprojektuj wydajny algorytm, który dla danych dwóch ciągów dodatnich liczb całkowitych \(x_1, x_2, \ldots, x_n\) oraz \(y_1, y_2, \ldots, y_m\), \(n \le m\), wyznacza w ciągu y wszystkie pozycje i takie, że podciąg \(y_i, y_{i+1}, \ldots, y_{i+n-1}\) oraz ciąg x są podobne.

Zadanie 4 [17 punktów]#

Rozważmy następujący algorytm sortowania n różnych liczb \(x_1, x_2, \ldots, x_n\) w porządku malejącym.

Algorytm Szymka R.
X := {x1, x2, ..., xn};
Zainicjuj stos S jako pusty;
while Not Empty(X) do{
    weź dowolny element x ze zbioru X;
    X := X \ {x};
    Usuń ze stosu S wszystkie elementy większe od x i wstaw je z powrotem do zbioru X;
    Umieść x na wierzchołku stosu S;
}
Wypisz kolejno elementy ze stosu S;

Przyjmijmy, że operacjami dominującymi są operacje stosowe Top, Push, Pop.

  1. [6 punktów] Jaka jest pesymistyczna złożoność sortowania algorytmem Szymka R.?

Załóżmy teraz. że element x wybieramy losowo ze zbioru X z rozkładem jednostajnym - każdy element może zostać wylosowany z prawdopodobieństwem \(1/|X|\).

  1. [6 punktów] Udowodnij, że oczekiwana liczba losowań w algorytmie elementu x ze zbioru X wynosi \(O(n^2)\).

  2. [5 punktów] Dokonaj analizy oczekiwanej liczby operacji dominujących w algorytmie Szymka R. w opisanym wyżej modelu probabilistycznym.

Uwaga: w każdym zadaniu uzasadnij poprawność swojego rozwiązania i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.