Egzamin poprawkowy 2023/24 (19.02.2024)#
Zadanie 1 [14 punktów]#
W tym zadaniu rozważamy ciągi operacji na zmieniającym się grafie \(G=(V,E)\), w którym \(V = \{1, 2, \ldots, n\}\) dla pewnej, dodatniej liczby całkowitej n.
[6 punktów] Początkowo \(E = \{1-2, 2-3, \ldots, (n-1)-n\}\). Zaproponuj strukturę danych, która umożliwia efektywne wykonywanie operacji:
Ini(G):: zainicjuj strukturę danych;
Dodaj(i,j):: \(E := E \cup \{i-j\}\), \(2 \le i+1 < j \le n\);
Usuń(i,j):: \(E := E \setminus \{i-j\}\), \(2 \le i+1 < j \le n\);
PunktArtykulacji(i):: sprawdź, czy i jest punktem artykulacji, \(1 \le i \le n\).
[5 punktów] Początkowo graf G=(V,E) jest grafem spójnym zadanym przez listy sąsiedztwa. Dany jest z góry ciąg k > n operacji ze zbioru:
Usuń(i,j):: \(E := E \setminus \{i-j\}\), \(1 \le i < j \le n\),
LiczbaSpójnych(G):: podaj liczbę spójnych składowych w aktualnym grafie G.
Zaproponuj wydajny algorytm, który obliczy odpowiedź na każde zapytanie o liczbę spójnych składowych.
[3 punkty] Jaka jest najmniejsza możliwa wysokość DFS-drzewa w 16-wierzchołkowym grafie zawierającym cykl Hamiltona? Uwaga: wysokość mierzymy liczbą krawędzi.
Podpowiedź
Ścieżka 1-2-…-n jest zawsze w grafie. Kiedy usunięcie i rozspójnia graf - jaka krawędź musiałaby „przeskoczyć” nad i? Licz dla każdego i, ile krawędzi go przeskakuje: dodawanie na przedziale i zapytanie o punkt.
Cały ciąg operacji jest znany z góry. Odwróć czas: usuwanie krawędzi staje się dodawaniem. Jak utrzymywać liczbę składowych przy samych dodawaniach?
Każda krawędź grafu łączy przodka z potomkiem w drzewie DFS. Usuń ścieżkę od korzenia do wierzchołka na głębokości d (d+1 wierzchołków) - ile co najwyżej składowych może zostać w grafie z cyklem Hamiltona? Co to mówi o liczbie dzieci wierzchołków i o liczbie wierzchołków drzewa danej wysokości? Na koniec podaj konstrukcję.
Zadanie 2 [8 punktów]#
[3 punkty] Udowodnij, że każdą dodatnią liczbę całkowitą można przedstawić jako sumę różnych liczb Fibonacciego. Przypominamy, że \(F_0 = 0\), \(F_1 = 1\).
[5 punktów] Na początkowo wyzerowanym liczniku binarnym \(L[2,\ldots,+\infty]\) wykonujemy n operacji Inc() w taki sposób, że po wykonaniu k-tej operacji \(k=\sum_{i=2}^{+\infty} F_i \cdot L[i]\) gdzie \(F_i\) jest i-tą liczbą Fibonacciego. Zaproponuj takie wykonanie operacji Inc, aby jej zamortyzowany koszt był stały.
Podpowiedź
Indukcja: weź największe \(F_k \le m\). Dlaczego \(m - F_k < F_{k-1}\) i co to daje dla reszty?
Utrzymuj reprezentację bez dwóch sąsiednich jedynek. Inc dodaje jedynkę na najniższej pozycji (\(F_2 + F_2 = F_3\)), a parę sąsiednich jedynek zamieniaj na jedną wyżej (\(F_i + F_{i+1} = F_{i+2}\)). Potencjał: liczba jedynek.
Zadanie 3 [12 punktów]#
Niech \(a[1,\ldots,n]\) będzie tablicą n różnych liczb całkowitych. Dla dodatniego k < n, powiemy że a jest k-sortowalna, jeżeli można ją posortować wykonując co najwyżej k zamian par elementów.
[3 punkty] Udowodnij, że liczba porównań potrzebnych do posortowania ciągu zapisanego w 1-sortowalnej tablicy a[1..n] wynosi co najmniej n-1.
[3 punkty] Zaproponuj optymalny algorytm ze względu na porównania sortujący ciąg zapisany w 1-sortowalnej tablicy a[1..n].
[6 punktów] Zaproponuj algorytm, optymalny ze względu na porównania, sortujący ciągi zapisane w k-sortowalnej tablicy a[1..n] w czasie \(O(n \log k)\), dla danego dodatniego k < n.
Podpowiedź
Przeciwnik: jeśli algorytm nie porównał dwóch elementów sąsiednich w porządku posortowanym, to zamiana ich miejscami daje inną 1-sortowalną tablicę, zgodną ze wszystkimi wynikami porównań.
Porównaj każdą parę sąsiednich elementów tablicy. Jak wyglądają miejsca, w których a[i] > a[i+1], gdy tablica powstała z posortowanej przez jedną zamianę?
O ile jedna zamiana może zwiększyć liczbę miejsc a[i] > a[i+1]? Podziel tablicę na maksymalne rosnące fragmenty - ile ich jest? - i scal je.
Zadanie 4 [6 punktów]#
Dane jest słowo x nad alfabetem {d, i, k, s}, w którym litera s występuje co najmniej dwa razy. Zaprojektuj efektywny algorytm, który w słowie x znajduje najdłuższe dwa podsłowa (niekoniecznie różne), w których litera s występuje dokładnie na tych samych pozycjach.
Podpowiedź
Ważne jest tylko, na których pozycjach stoi s. Zamień x na słowo binarne (s na 1, pozostałe litery na 0). Czego wtedy szukasz? Najdłuższego podsłowa, które występuje co najmniej dwa razy - tablica sufiksowa z LCP albo drzewo sufiksowe.