Egzamin 2025/26 (26.01.2026)#
Zadanie 1 [10 punktów]#
W tym zadaniu rozważamy tablicę a[1..n] zawierającą n parami różnych liczb całkowitych, gdzie n jest liczbą całkowitą większą od 1. Jeżeli \(a = [e_1, e_2, \ldots, e_n]\), to przez Revers(i), \(1 \le i \le n\), oznaczamy operację odwrócenia kolejności występowania pierwszych i elementów w tablicy a. Po wykonaniu Revers(i) mamy \(a = [e_i, e_{i-1}, \ldots, e_1,\ e_{i+1}, \ldots, e_n]\).
[2 punkty] Udowodnij, że tablicę a zawsze można posortować rosnąco za pomocą liniowej liczby (względem n) operacji Revers.
[3 punkty] Wiadomo, że na uporządkowanej rosnąco tablicy a wykonano dokładnie jedną operację Revers. Zaproponuj asymptotycznie optymalny ze względu na porównania algorytm sortujący rosnąco tablicę a.
[5 punktów] Zaproponuj efektywny algorytm, który dla danej tablicy a wyznaczy liniowy ciąg operacji Revers, po wykonaniu których tablica a zostanie posortowana rosnąco.
Podpowiedź
Indukcja: jak za pomocą co najwyżej dwóch operacji Revers ustawić największy element na ostatniej pozycji i już go nie ruszać?
Ile różnych tablic może dostać algorytm (dolne ograniczenie z drzewa decyzyjnego)? Jak wygląda para a[j], a[j+1] dla j < i, a jak dla \(j \ge i\)?
Strategia z a) symulowana naiwnie kosztuje \(\Theta(n^2)\). Przechowuj tablicę w zrównoważonym drzewie z niejawnymi kluczami (pozycjami) i leniwym znacznikiem odwrócenia; potrzebna jest też bieżąca pozycja danego elementu.
Zadanie 2 [10 punktów]#
DAG to graf skierowany bez cykli. Niech G = (V, E) będzie DAGiem. Ujściem w G nazywamy każdy wierzchołek bez wychodzących krawędzi, natomiast źródłem - każdy wierzchołek bez wchodzących krawędzi.
[2 punkty] Jaka może być najmniejsza a jaka największa liczba krawędzi w n-wierzchołkowym słabo spójnym DAGu o p źródłach i q ujściach, gdzie \(n > 1\) oraz \(p + q \le n\)?
[3 punkty] Zaproponuj wydajny algorytm, który dla danego słabo spójnego DAGu o n > 1 wierzchołkach i p źródłach oraz q ujściach, wyznaczy zbiór nie więcej niż p + q krawędzi, po dodaniu których dostaniemy graf silnie spójny (\(p + q \le n\)).
[5 punktów] Wiemy, że w DAGu G istnieje dokładnie jedno źródło s i dokładnie jedno ujście u. Zaproponuj wydajny algorytm, który wyznaczy ścieżkę z s do u (o ile istnieje), której długość jest podzielna przez 26.
Podpowiedź
Minimum: co wymusza słaba spójność? Maksimum: w porządku topologicznym - które pary wierzchołków na pewno nie mogą być połączone krawędzią?
Wystarczy, żeby wszystkie źródła i ujścia znalazły się w jednej silnie spójnej składowej (dlaczego?). Wybierz jedno źródło jako „centrum” i jedno ujście z niego osiągalne.
Rozważ graf stanów (wierzchołek, długość ścieżki mod 26) - on też jest DAGiem. Programowanie dynamiczne w porządku topologicznym.
Zadanie 3 [10 punktów]#
[2 punkty] Udowodnij, że dla każdego całkowitego n > 0 istnieje słowo nad alfabetem {a,b}, dla którego suma elementów odpowiadającej mu tablicy prefikso-sufiksów wynosi n.
[Bonus] Potrafisz skonstruować najkrótsze takie słowo?
[3 punkty] Słowo x nazywamy kwadratowym wtedy i tylko wtedy, gdy jest złączeniem dwóch takich samych słów. Dla przykładu słowo abbabb jest słowem kwadratowym, natomiast słowo abaabb już nie jest. Dla n = 4k, k > 0, podaj przykład słowa kwadratowego nad alfabetem {a,b} zawierającego obie litery a, b i o największej sumie wartości z odpowiadającej mu tablicy prefikso-sufiksów.
[5 punktów] Zaproponuj wydajny algorytm, który dla danego słowa x nad alfabetem {d,i,k,s} o długości co najmniej 2 i dodatniej liczby całkowitej \(k \le |x|/2\), znajdzie liczbę różnych słów kwadratowych o długości 2k występujących w słowie x.
Podpowiedź
Zacznij od krótkiego słowa i dopisuj fragment, który zwiększa sumę dokładnie o 1 - tak, żeby żaden dłuższy prefiks nie mógł pasować. Bonus: słowo \(a^k\) daje sumy trójkątne.
Kiedy \(P[i] = i - 1\)? Ile co najmniej „tracimy”, gdy pojawi się druga litera? Słowo o okresie p ma \(P[i] \ge i - p\).
Kiedy x[i..i+2k-1] jest kwadratem? Wystarczy porównywać x[j] z x[j+k] w przesuwanym oknie. Na koniec usuń powtórzenia: identyfikatory podsłów długości k (KMR / słownik podsłów bazowych albo haszowanie Karpa-Rabina).
Zadanie 4 [10 punktów]#
Niech n będzie dodatnią liczbą całkowitą. W tym zadaniu rozpatrujemy ustalone z góry n-węzłowe drzewo binarne T, którego węzły zostały ponumerowane w kolejności „preorder” (korzeń, lewe poddrzewo, prawe poddrzewo). Węzły utożsamiamy z ich numerami. W każdym węźle drzewa przechowujemy jedną z dwóch wartości – 0 lub 1. Każde maksymalne poddrzewo binarne drzewa T (bez możliwości rozszerzenia), w węzłach którego są same jedynki, nazywamy poddrzewem jedynkowym. Korzeniem poddrzewa jedynkowego jest zawsze węzeł o najmniejszym numerze w numeracji „preorder”.
[4 punkty] Zaprojektuj strukturę danych, która umożliwia wydajne wykonanie on-line ciągu co najmniej n następujących operacji na drzewie T, które na początku zawiera same zera:
Ini() :: zainicjuj strukturę danych;
Korzeń(i):: jeśli w węźle i jest jedynka („1”) podaj korzeń poddrzewa jedynkowego zawierającego ten węzeł;
DodajJedynkę(i):: zapisz jedynkę w węźle o numerze i.
[6 punktów] Zaprojektuj strukturę danych, która umożliwia wydajne wykonanie on-line ciągu co najmniej n następujących operacji na drzewie T, które na początku zawiera same jedynki:
Ini() :: zainicjuj strukturę danych;
Korzeń(i):: jeśli w węźle i jest jedynka („1”) podaj korzeń poddrzewa jedynkowego zawierającego ten węzeł;
UsuńJedynkę(i):: zapisz zero w węźle o numerze i.
Podpowiedź
Dodawanie jedynek tylko scala poddrzewa jedynkowe - Find-Union; przy zbiorze pamiętaj węzeł o najmniejszym numerze.
Korzeń(i) zależy od najgłębszego przodka i, w którym jest zero. W numeracji preorder poddrzewo węzła v to przedział \([v, v + \mbox{rozmiar}(v) - 1]\) - jak szybko znaleźć takiego przodka (np. drzewo przedziałowe)?
Uwaga: Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.