Egzamin poprawkowy 2019/20 (19.02.2020)#
Zadanie 1 [10 punktów]#
Niech \(A = [a_1, a_2, \ldots,a_n]\) będzie ciągiem binarnym, n > 0.
[5 punktów] Zaprojektuj wydajny algorytm, który obliczy ile dokładnie porównań zostanie wykonanych w stabilnym algorytmie sortowania przez wstawianie zastosowanym do ciągu A.
[5 punktów] Ile wynosi dokładna średnia liczba porównań wykonywanych w stabilnym algorytmie sortowania przez wstawianie przy założeniu, że każdy ciąg binarny pojawia się na wejściu z jednakowym prawdopodobieństwem?
Podpowiedź
Niech \(Ile1(i) = |\{ j : a_j=1\ \mbox{oraz}\ j<i\}|\). Wynik to: \(n - 1 + \sum_{i=2}^n [a_i=0]\cdot Ile1(i) - [a_1=1 \mbox{ i } A \mbox{ zawiera } 0]\) (pierwsze zero w ciągu zaczynającym się od 1 dochodzi na początek tablicy bez porównania kończącego).
Z wzoru z punktu a): \(P(a_i=0)=\frac{1}{2}\), \(E[Ile1(i)]=\frac{i-1}{2}\), a ciąg zaczyna się od 1 i zawiera 0 z prawdopodobieństwem \(\frac{1}{2}(1-2^{-(n-1)})\). Stąd średnia liczba porównań to \(n-1 + \sum_{i=2}^{n}\frac{i-1}{4} - \frac{1}{2}(1-2^{-(n-1)}) = \frac{n(n-1)}{8} + n - \frac{3}{2} + 2^{-n}\).
Zadanie 2 [10 punktów]#
Niech A będzie dynamicznym zbiorem liczb całkowitych. Zaprojektuj strukturę danych umożliwiającą wydajne wykonywanie na zbiorze A następujących operacji:
[5 punktów]
Ini(A):: zainicjuj A jako pusty;
Insert(a):: wstaw a do A;
Delete(a):: usuń a z A;
Largest:: podaj rozmiar największego podzbioru A zbudowanego z kolejnych liczb całkowitych \(i, i+1, i+2, \ldots\), dla pewnej liczby całkowitej i.
[5 punktów]
Ini(A):: \(A := \{1,2, \ldots, n\}\)
Delete(a):: usuń a z A;
Largest:: podaj rozmiar największego podzbioru A zbudowanego z kolejnych liczb całkowitych \(i, i+1, i+2, \ldots\), dla pewnej liczby całkowitej i. W tym przypadku przyjmij, że ciąg operacji Delete, Largest jest dany off-line i chcemy znać odpowiedź na każde zapytanie Largest.
Podpowiedź
Dla uproszczenia, dobry ciąg to ciąg postaci \(i, i+1, i+2, \ldots\). Wzbogacamy drzewo o dodatkowe atrybuty: MaxDobryPrefiks, MaxDobrySufiks i MaxDobry (odpowiednio najdłuższy dobry prefiks, sufiks i dowolny spójny fragment).
W trybie off-line, możemy odwrócić kolejność operacji (to powoduje, że Delete zamienia się na Insert). Możemy użyć struktury Find-Union, każdy zbiór oznacza maksymalny dobry ciąg lub pojedynczy element, który nie należy do A.
Zadanie 3 [10 punktów]#
4-kaktusem nazywamy graf spójny, w którym każda dwuspójna składowa składa się z dokładnie 4 wierzchołków.
[2 punkty] Ile wierzchołków jest w 4-kaktusie o dokładnie n dwuspójnych składowych?
[2 punkty] Jaka jest maksymalna, a jaka minimalna wysokość DFS-drzewa w 4-kaktusie o n dwuspójnych składowych?
[6 punktów] Dany jest 4-kaktus (przez listy sąsiedztwa) z dodatnimi wagami na krawędziach. Zaprojektuj wydajny algorytm, który dla danej pary wierzchołków u i v znajduje najlżejszą ścieżkę między nimi.
Zadanie 4 [10 punktów]#
Zaprojektuj wydajny algorytm, który dla danych słów x, y nad alfabetem
{d, i , k, s} obliczy:
[6 punktów] długość najdłuższego wspólnego podsłowa zawierającego podciąg
d,i,k,s.[4 punkty] długość najkrótszego wspólnego podsłowa zawierającego podciąg
d,i,k,s.
Podpowiedź
Jak LCS tylko dodajmy trzeci wymiar ([0..4] – jak długi prefiks słowa diks już znaleziono). Złożoność czasowa \(O(n^2)\).
Niech e(i) będzie końcem zachłannego dopasowania podciągu diks w x od pozycji i (wartości e(i) liczymy w czasie \(O(n)\) za pomocą tablic następnych wystąpień liter). Najkrótsze szukane podsłowo ma postać x[i..e(i)]: jeśli wspólne podsłowo x[i..j] zawiera podciąg diks, to x[i..e(i)] jest jego prefiksem, więc też jest wspólnym podsłowem. Wynikiem jest najmniejsze \(e(i)-i+1\) po tych i, dla których x[i..e(i)] występuje w y. Sprawdzamy to w drzewie sufiksowym dla tekstu \(x\$y\#\): punkt na głębokości \(e(i)-i+1\) na ścieżce sufiksu i musi mieć w poddrzewie sufiks z y.
Złożoność czasowa \(O(n)\).
Uwaga: uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.