Egzamin poprawkowy 2024/25 (20.02.2025)#
Zadanie 1 [12 punktów]#
Dla dodatniej liczby całkowitej n, zygzakiem rzędu n nazywamy każdy ciąg \(x_1, x_2, \ldots, x_n\) parami różnych liczb całkowitych spełniający warunek: dla każdego \(1 \le i < n\):
\(x_i > \max(x_{i+1}, \ldots, x_n)\) lub \(x_i < \min(x_{i+1}, \ldots. x_n)\).
Niech \(x[1,\ldots,n]\) będzie tablicą, w której zapisano pewien zygzak rzędu n, tzn. \(x[i]=x_i\).
[3 punkty] Zaproponuj wydajny algorytm, który obliczy liczbę wszystkich inwersji w tablicy x.
[5 punktów] Zaprojektuj wydajny, działający w miejscu algorytm, który w zygzaku zapisanym w tablicy \(x[1,\ldots,n]\) znajdzie dwa najbliższe sobie elementy, tzn. wartość bezwzględna ich różnicy jest najmniejsza.
[4 punkty] Niech \(P_n\) będzie zbiorem wszystkich permutacji liczb \(1, 2, \ldots, n\), które są zygzakami. Dokonaj analizy oczekiwanej liczby porównań wykonywanych podczas sortowania przez wstawianie losowego zygzaka z \(P_n\).
Zadanie 2 [8 punktów]#
W tym zadaniu rozważamy grafy dwudzielne.
[3 punkty] Jaka może być minimalna, a jaka maksymalna wysokość DFS-drzewa w n-wierzchołkowym dwudzielnym grafie dwuspójnym, dla \(n > 3\).
[5 punktów] Zaprojektuj strukturę danych umożliwiającą wydajne wykonanie \(m > n\) on-line operacji na dynamicznie rozrastającym się dwudzielnym multigrafie \(G=(\{1, 2, \ldots,n\}, E)\):
Ini:: \(E:= \emptyset\) // tylko raz na samym początku
Dodaj(u-v):: sprawdź, czy \(G=(V,E \cup \{u-v\})\) jest nadal dwudzielny i jeśli tak, dodaj krawędź u-v do grafu,
Ile():: podaj liczbę spójnych składowych w grafie G zawierających wierzchołek stopnia 1.
Zadanie 3 [6 punktów]#
Dany jest acykliczny graf skierowany (dag) G=(V,E). Wierzchołek \(w\in V\) jest przodkiem wierzchołka \(u\in V\), gdy istnieje skierowana ścieżka z u do w. Najbliższym wspólnym przodkiem wierzchołków \(u\in V\) i \(v \in V\) nazywamy wierzchołek \(w \in V\), który jest przodkiem u i v oraz nie istnieje inny przodek u i v, którego przodkiem jest w. Najbliższy wspólny przodek dla pary wierzchołków nie musi być jednoznacznie wyznaczony. Zaproponuj wydajny algorytm znajdujący w danym dagu G=(V,E) najbliższego wspólnego przodka dla danych wierzchołków \(u,v\in V\).
Zadanie 4 [14 punktów]#
W tym zadaniu rozważmy skończone słowa nad alfabetem {a, b}. Zaproponuj wydajne algorytmy rozwiązujące następujące problemy.
[3 punkty] Dla danego słowa \(s[1,\ldots,n]\), \(n > 1\), oblicz liczbę pozycji \(1 \le i < j \le n\) takich, że podsłowo \(s[i,\ldots,j]\) zawiera tyle samo liter a co liter b.
[7 punktów] Znajdź w słowie s podsłowo długości 2k, gdzie \(2 \le 2k < n\), które zawiera taką samą liczbę liter a i b oraz występuje w s najczęściej.
[4 punkty] Zaprojektuj strukturę danych umożliwiającą wykonanie na dynamicznym słowie s wydajne wykonanie następujących operacji w trybie on-line:
Ini:: s=[] // słowo puste,
Ins(x,i):: dodaj symbol \(x\in \{a, b\}\) na i-tą pozycję w słowie,
Del(x,i):: usuń symbol z pozycji i-tej w słowie,
a-Strings():: podaj liczbę różnych podsłów zbudowanych tylko z liter a.