Ctrl+K

Egzamin poprawkowy 2023/24 (19.02.2024)

Egzamin poprawkowy 2023/24 (19.02.2024)#

Zadanie 1 [14 punktów]#

W tym zadaniu rozważamy ciągi operacji na zmieniającym się grafie \(G=(V,E)\), w którym \(V = \{1, 2, \ldots, n\}\) dla pewnej, dodatniej liczby całkowitej n.

  1. [6 punktów] Początkowo E = {1—2, 2—3, …, (n-1)—n}. Zaproponuj strukturę danych, która umożliwia efektywne wykonywanie operacji:

    • Ini(G):: zainicjuj strukturę danych;

    • Dodaj(i,j):: E := E ∪ {i—j}, 2 ≤ i+1 < j ≤ n;

    • Usuń(i,j):: E := E {i—j}, 2 ≤ i+1 < j ≤ n;

    • PunktArtykulacji(i):: sprawdź, czy i jest punktem artykulacji, 1 ≤ i ≤ n.

  2. [5 punktów] Początkowo graf G=(V,E) jest grafem spójnym zadanym przez listy sąsiedztwa. Dany jest z góry ciąg k > n operacji ze zbioru:

    • Usuń(i,j):: E := E {i—j}, 1 ≤ i < j ≤ n,

    • LiczbaSpójnych(G):: podaj liczbę spójnych składowych w aktualnym grafie G.

    Zaproponuj wydajny algorytm, który obliczy odpowiedź na każde zapytanie o liczbę spójnych składowych.

  3. [3 punkty] Jaka jest najmniejsza możliwa wysokość DFS-drzewa w 16-wierzchołkowym grafie zawierającym cykl Hamiltona? Uwaga: wysokość mierzymy liczbą krawędzi.

Zadanie 2 [8 punktów]#

  1. [3 punkty] Udowodnij, że każdą dodatnią liczbę całkowitą można przedstawić jako sumę różnych liczb Fibonacciego. Przypominamy, że \(F_0 = 0\), \(F_1 = 1\).

  2. [5 punktów] Na początkowo wyzerowanym liczniku binarnym \(L[2,\ldots,+\infty]\) wykonujemy n operacji Inc() w taki sposób, że po wykonaniu k-tej operacji \(k=\sum_{i=2}^{+\infty} F_i \cdot L[i]\) gdzie \(F_i\) jest i-tą liczbą Fibonacciego. Zaproponuj takie wykonanie operacji Inc, aby jej zamortyzowany koszt był stały.

Zadanie 3 [12 punktów]#

Niech \(a[1,\ldots,n]\) będzie tablicą n różnych liczb całkowitych. Dla dodatniego k < n, powiemy że a jest k-sortowalna, jeżeli można ją posortować wykonując co najwyżej k zamian par elementów.

  1. [3 punkty] Udowodnij, że liczba porównań potrzebnych do posortowania ciągu zapisanego w 1-sortowalnej tablicy a[1..n] wynosi co najmniej n-1.

  2. [3 punkty] Zaproponuj optymalny algorytm ze względu na porównania sortujący ciąg zapisany 1-sortowalnej tablicy a[1..n].

  3. [6 punktów] Zaproponuj algorytm ze względu na porównania sortujący ciągi zapisane w k-sortowalnej tablicy a[1..n] czasie \(O(n \log k)\), dla danego nieujemnego k < n.

Zadanie 4 [6 punktów]#

Dane jest słowo x nad alfabetem {d, i, k, s}, w którym litera s występuje co najmniej dwa razy. Zaprojektuj efektywny algorytm, który w słowie x znajduje najdłuższe dwa podsłowa (niekoniecznie różne), w których litera s występuje dokładnie na tych samych pozycjach.

Zawartość