Egzamin poprawkowy 2017/18 (17.02.2018)#

Zadanie 1 [11 punktów]#

Słowa kluczowe: teksty

W tym zadaniu rozważamy słowa na alfabetem binarnym.

  1. [2 punkty] Ile wynosi suma elementów tablicy P dla słowa \((01)^{2018}\)?

  2. [2 punkty] Ile wynosi wysokość drzewa sufiksowego (liczona liczbą krawędzi) dla słowa \((01)^{2018}\$\)?

  3. [7 punktów] Zaprojektuj efektywny algorytm, który dla dodatniej liczby całkowitej k oraz słów x, y takich, że \(|x| = k\), \(|y| = k^2\) sprawdzi, ile jest w y podsłów o długości k, z których każde różni się od x na dokładnie jednej pozycji.

Zadanie 2 [18 punktów]#

Słowa kluczowe: grafy

Niech n będzie liczbą całkowitą większą od 2 i niech J będzie rodziną co najwyżej n różnych, domkniętych przedziałów liczb całkowitych zawartych w przedziale [1,n]. Grafem G(n,J) nazywamy graf ({1,2, …, n}, {i-j: istnieje przedział w J, do którego wpadają obie liczby (oba wierzchołki) i oraz j}).

  1. [6 punktów] Rozważmy rodziny przedziałów:

    \(J_1\) = {[2,23], [1,19], [6,25], [11,29]} \(J_2\) = {[1,13], [10,17], [11,15], [17,27], [25,29]} \(J_3\) = {[4,17], [2,29], [1,11]} \(J_4\) = {[1,15], [12,29], [9,19]}

Wskaż, dla których i graf \(G(29, J_i)\) posiada cykl Eulera oraz dla których i graf \(G(29, J_i)\) posiada cykl Hamiltona. Odpowiedź uzasadnij.

  1. [4 punkty] Zaprojektuj algorytm, który w czasie liniowym (O(n)) sprawdzi, czy w danym grafie G(n,J) istnieje cykl Hamiltona.

  2. [8 punktów] Zaprojektuj algorytm, który w czasie liniowym (O(n)) sprawdzi, czy w danym grafie G(n,J) istnieje cykl Eulera.

Zadanie 3 [11 punktów]#

Słowa kluczowe: sortowanie, Bubble Sort

Rozważmy następująca wersję algorytmu sortowania bąbelkowego dla tablicy a[1..n] różnych liczb całkowitych z przedziału [1,n]. Interesuje nas wartość zmiennej i po zakończeniu wykonywania algorytmu.

i := 0;
repeat
    i := i + 1; brak_zamiany := TRUE;
    j := 2;
    while j <= n-i+1 do begin
        if a[j] < a[j-1] then begin
            a[j] :=: a[j-1]; brak_zamiany := FALSE;
        end;
        j := j + 1:
    end;
until brak_zamiany;

  1. [3 punkty] Jaka jest minimalna, a jaka maksymalna wartość zmiennej i po zakończeniu wykonywania algorytmu dla tablicy a z liczbą inwersji n-1?

  2. [8 punktów] Zaprojektuj pesymistycznie efektywny algorytm, który dla danej tablicy a obliczy wartość zmiennej i po zakończeniu wykonywania algorytmu.

Uzasadnij poprawność swoich rozwiązań oraz dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.