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ócenie 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.
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.
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.
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ń drzewa 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ń drzewa jedynkowego zawierającego ten węzeł;
UsuńJedynkę(i):: zapisz zero w węźle o numerze i.
Uwaga: Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.