Egzamin 2014/15 (29.01.2015)#
Zadanie 1 [6 pkt]#
Zaproponuj efektywny algorytm, który w słowie s o długości \(n \ge 3\) nad alfabetem {a,b} znajdzie dwa najdłuższe, takie same podsłowa nie zachodzące na siebie.
Przykład
W słowie aaaaaa takie dwa najdłuższe podsłowa to aaa zaczynające się na pozycji 1 i aaa zaczynające się na pozycji 4. W słowie abbabbbab takie słowa, to np. bbab zaczynające się na pozycji 2 i bbab zaczynające się na pozycji 6.
Zadanie 2 [9 pkt]#
Zaproponuj strukturę danych, która umożliwi efektywne wykonywanie następujących operacji na dynamicznym, skończonym ciągu \(\alpha\) o wartościach 0-1:
Ini(\(\alpha\)):: \(\alpha\) := [];
Wstaw(\(\alpha\), e, i):: wstaw element e na pozycję i w ciągu (przesuwając elementy od pozycji i o jedną pozycję w prawo), :math:1 le i le |alpha|+1;
Usuń(\(\alpha\), i):: usuń i-ty element ciągu, \(1 \le i \le |\alpha|\);
Wartość(\(\alpha\), i):: podaj wartość i-tego element ciągu, \(1 \le i \le |\alpha|\);
Zamień(i, j):: zamień wartości elementów na pozycjach od i do j na przeciwne \((0 \rightarrow 1,\, 1 \rightarrow 0)\), \(1 \le i \le j \le |\alpha|\);
Pozycja(\(\alpha\)):: podaj pozycję środkowej jedynki w ciągu, licząc od początku; jeśli w ciągu nie ma jedynek odpowiedzią jest 0; jeśli w ciągu jest k > 0 jedynek, to odpowiedzią jest pozycja jedynki podłoga(k/2), licząc od początku ciągu.
Bez operacji Zamień - max 3 punkty.
Zadanie 3 [20 pkt]#
W tym zadaniu rozważamy n-wierzchołkowe grafy nieskierowane, których wierzchołki są ponumerowane liczbami od 1 do n i które zadane są przez listy sąsiedztwa. Krawędziom grafu są przypisane wagi całkowitoliczbowe z przedziału [1..m], gdzie m jest liczbą krawędzi w grafie. Wartością ścieżki nazywamy najmniejszą wagę krawędzi z tej ścieżki.
[8 pkt] Zaproponuj efektywny algorytm, który dla danego, co najmniej 3-wierzchołkowego, dwuspójnego grafu G=(V,E) i dwóch jego różnych wierzchołków x i y, znajdzie cykl elementarny zawierający te dwa wierzchołki.
[12 pkt] Zaproponuj efektywny algorytm, który dla danego, spójnego grafu G=(V,E) i dwóch jego różnych wierzchołków x i y, znajdzie ścieżkę o największej wartości pomiędzy x i y.
Za poprawne rozwiązanie w czasie \(\Theta(m \log n)\) - max 3 pkt. Za poprawne rozwiązanie w czasie \(o(m \log n)\), ale nie liniowe - max 6 pkt. Za poprawne rozwiązanie w czasie liniowym - max 12 pkt.
Zadanie 4 [5 pkt]#
W tym zadaniu rozważamy rekurencyjny algorytm sortowania przez scalanie, w którym scalanie dwóch posortowanych ciągów odbywa się w sposób klasyczny: na swoją docelową pozycję trafia mniejszy z początkowych elementów scalanych ciągów.
Przykład
Podczas scalania ciągów [2, 4, 5, 8] oraz [1, 3, 6, 7] porównywane są kolejno 2 z 1, 2 z 3, 4 z 3, 4 z 6, 5 z 6, 8 z 6 oraz 8 z 7.
Zaprojektuj liniowy algorytm, który sprawdzi, czy w wyniku wykonania algorytmu sortowania przez scalanie na danej permutacji p[1..n] liczb naturalnych \(1, \ldots, n\), porównane zostaną ze sobą zadane, dwie różne liczby a i b ze zbioru \(\{1,\ldots,n\}\).