Egzamin poprawkowy 2014/15 (luty 2015)#
Zadanie 1 (21 punktów)#
W tym zadaniu rozważamy liczbowe ciągi różnowartościowe o długości n > 0. Niech T będzie n wierzchołkowym drzewem binarnym. Powiemy, że ciąg \(\alpha = \langle a_1, a_2,\ldots,a_n \rangle\) jest zgodny z T, jeśli po wykonaniu ciągu operacji Wstaw(\(a_1\)), Wstaw (\(a_2\)),…, Wstaw (\(a_n\)), do początkowo pustego drzewa wyszukiwań binarnych, otrzymamy drzewo izomorficzne z T.
Przykład
Permutacja \(\langle 4, 6, 5, 2, 3, 1, 7 \rangle\) jest zgodna z pełnym drzewem binarnym o wysokości 2.
(4 punktów) Dana jest dodatnia liczba całkowita \(n \ge 3\) oraz ciąg \(\alpha = <a_1, a_2,\ldots,a_n>\), zgodny z pewnym drzewem binarnym o wysokości n-2. Zaprojektuj algorytm, który w czasie liniowym posortuje ciąg \(\alpha\).
(4 punktów) Udowodnij, że sortowanie przez porównania ciągu zgodnego z pełnym drzewem binarnym wymaga w pesymistycznym przypadku \(\Omega(n \log n)\) porównań.
(4 punktów) Zaproponuj algorytm, który w n-elementowym ciągu \(\alpha\), \(n \ge 3\), zgodnym z pełnym drzewem binarnym, znajduje element maksymalny w mniej niż n-1 porównań.
[2 punkty] Rozwiąż (asymptotycznie) równanie rekurencyjne:
\(T[1] = 0\)
\(T[n] = T[n\ \textrm{div}\ 2] + n\).
(7 punktów) Zaproponuj algorytm, który w czasie liniowym sprawdzi, czy dana permutacja \(\alpha\) liczb naturalnych 1, 2, … , n jest zgodna z pełnym drzewem binarnym.
Uwaga: przez pełne drzewo binarne rozumiemy drzewo w którym wszystkie poziomy są w pełni zapełnione wierzchołkami, od poziomu 0 do poziomu h, gdzie h to wysokość drzewa.
Zadanie 2 (10 punktów)#
Niech G=(V,E) będzie n-wierzchołkowym grafem spójnym, zadanym przez listy sąsiedztwa. Z każdą krawędzią grafu G jest związana dodatnia, całkowitoliczbowa waga.
[4 punkty] Przy założeniu, że graf G zawiera co najwyżej n+4 krawędzie zaproponuj efektywny algorytm obliczający jego minimalne drzewo rozpinające.
[2 punkty] Uzasadnij, że liczba wierzchołków w G o nieparzystych stopniach jest parzysta.
[4 punkty] Zaproponuj efektywny algorytm, który połączy wierzchołki o nieparzystym stopniu w G w pary i wyznaczy zbiór parami krawędziowo rozłącznych ścieżek łączących wierzchołki w parach.
Zadanie 3 (9 punktów)#
W tym zadaniu rozważamy skończone słowa nad alfabetem {a,b,c}. Dla słowa długości n i liczby k, \(0 \le k \le n\), zaproponuj efektywne algorytmy obliczania:
[3 punkty] liczby wszystkich podsłów zawierających dokładnie k wystąpień litery a;
[6 punktów] liczby wszystkich różnych podsłów (różniących się długościami lub co najmniej jedną literą) zawierających dokładnie k wystąpień litery a.
Uwaga: w każdym zadaniu wykaż poprawność swojego rozwiązania i dokonaj analizy złożoności obliczeniowej zaproponowanego algorytmu.