Egzamin 2015/16 (29.01.2016)#
Zadanie 1 [22 punkty]#
Skierowany graf G=({1,2, …, n}, E) nazywamy grafem przedziałowym, jeżeli dla każdego wierzchołka v, zbór wierzchołków, do których prowadzą krawędzie wychodzące z v, tworzą kolejne wierzchołki od l[v] do r[v], dla pewnych \(1 \le l[v] \le r[v] \le n\). Graf może zawierać pętle. Jeżeli z wierzchołka nie wychodzi żadna krawędź, to l[v] = r[v] = 0. Liczba n oraz ciąg par l[v], r[v] nazywamy zwartą reprezentacją G, a n rozmiarem tej reprezentacji. Dana jest zwarta reprezentacja pewnego przedziałowego grafu G o rozmiarze n.
[5 punków] Ułóż algorytm sprawdzający, czy po usunięciu wszystkich pętli, graf G jest ukorzenionym drzewem, w którym krawędzie są skierowane od korzenia do liści.
[9 punktów] Ułóż algorytm sprawdzający, czy G jest słabo-spójny (po usunięciu orientacji na krawędziach jest spójny).
[8 punktów] Ułóż algorytm, który sprawdzi, czy G jest eulerowski.
Zadanie 2 [9 punktów]#
Różnowartościowy ciąg liczbowy nazwiemy k-ciągiem, jeżeli zawiera co najwyżej k inwersji.
[5 punków] Zaproponuj algorytm, optymalny ze względu na pesymistyczną liczbę wykonywanych porównań, który sortuje 2-ciągi o długościach równych 2016.
[4 punkty] Zaproponuj algorytm, optymalny ze względu na pesymistyczną liczbę wykonywanych porównań, który w 2016-ciągu o długości n > 2016 znajduje element najmniejszy.
Udowodnij optymalność swoich rozwiązań.
Zadanie 3 [9 punktów]#
W tym zadaniu rozważamy słowa nad alfabetem {d,i,k,s}. Przesunięciem cyklicznym słowa x[0..m-1] nazywamy słowo z takie, że dla pewnego k ze zbioru {0,.., m-1} i każdego i ze zbioru {0,.., m-1} zachodzi z[i]=x[(i+k) mod m]. Zaprojektuj algorytm sprawdzający, czy w słowie y[0.. n-1], \(1 \le m \le n\), znajduje się podsłowo będące przesunięciem cyklicznym danego słowa x.
Uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.