1. Klasówka 2022/23 (24.11.2022)#

Zadanie 1 [11 punktów]#

Słowa kluczowe: struktury danych

Dla dodatniej liczby całkowitej n, w tablicy a[1..n] zapisano n różnych elementów z pewnego liniowo uporządkowanego uniwersum. Rangą elementu a[i], oznaczanego przez R(i), nazywamy pozycję tego elementu w tablicy a po jej uporządkowaniu rosnąco.

Przykład

Dla a = [2, 5, 3, 4], rangami elementów a[1], a[2], a[3] i a[4] są odpowiednio 1, 4, 2, 3.

Dla nieujemnej liczby całkowitej k powiemy, że tablica jest k-zaburzona wtedy i tylko wtedy, gdy dla każdego \(i = 1, 2, \ldots, n\), \(|R(i) - i| \le k\). Dana jest liczba całkowita k, \(0 \le k < n\), oraz k-zaburzona tablica a[1..n].

  1. [4 punkty] Zaproponuj wydajny algorytm, który zbuduje w tablicy a kopiec zupełny typu MIN.

  2. [3 punkty] Zaproponuj algorytm, optymalny ze względu na liczbę porównań, sortowania 1-zaburzonej tablicy a.

  3. [4 punktów] Zaproponuj asymptotycznie optymalny algorytm sortowania tablicy a.

Podpowiedź

Obserwacja: w ciągu k-zaburzonym dowolne dwa elementy a oddalone o więcej niż 2k pozycji są już dobrze uporządkowane.

  1. zbuduj kopiec na 4k-pierwszych elementach (cała reszta jest już w porządku kopcowym)

  2. W ciągu 1-uporządkowanym na \(R(i)\in\{i-1, i, i+1\}\). Stąd jedyne inwersje mogą wynikać z zamiany sąsiednich elementów.

    i = 1
while i < n do:
    if a[i] > a[i+1]
        a[i], a[i+1] = a[i + 1], a[i]
        i += 2
    else:
        i += 1

  3. posortuj bloki długości 4(k+1) z krokiem co 2(k+1) (A[1..4(k+1)], A[2(k+1)..6(k+1)], ..) używając algorytmu HeapSort. Złożoność \(O(n\log k)\).

Zadanie 2 [4 punkty]#

Słowa kluczowe: teksty

W tym zadaniu rozważamy skończone słowa nad alfabetem {d,i,k,s}. Niech s będzie słowem i niech s[j] będzie j-tym znakiem w tym słowie. Blokiem znaku s[j] nazywamy maksymalne podsłowo s zawierające znak s[j], w którym wszystkie znaki są takie same, równe s[j]. Taki blok oznaczamy przez B(s,j).

Przykład

W słowie s = abbaac mamy B(s,3) = bb, B(s,4) = aa.

O dwóch słowach \(s_1\) i \(s_2\) powiemy, ze są podobne wtedy i tylko wtedy, gdy \(|s_1| = |s_2|\) oraz dla każdego \(j = 1, \ldots, |s_1|\), bloki \(B(s_1,j)\) i \(B(s_2,j)\) są tej samej długości.

Zaprojektuj wydajny algorytm, który dla danego zbioru Q złożonego z n skończonych słów nad alfabetem {d,i,k,s}, wyznaczy wszystkie jego maksymalne (nie dające się rozszerzyć) podzbiory słów podobnych.

Podpowiedź

Niech \(C(s)=\{i : 1\le i < |s|\ \mbox{oraz}\ s[i]\not=s[i+1]\}\). Dwa słowa są podobne jeśli \(|s_1| = |s_2|\) oraz \(C(s_1)=C(s_2)\).

Posortuj słowa wg sekwencji \(C(s_i)\) i wyznacz grupy z tymi samymi kodami.

Zadanie 3 [5 punków]#

Słowa kluczowe: amortyzacja

Dane są trzy, początkowo puste stosy \(S_1, S_2, S_3\). Operacja PołóżŻeton(i) polega na położeniu nowego żetonu na stos \(S_i\). Jeśli po dołożeniu żetonu liczba żetonów na stosie \(S_i\) jest 3 razy większa od łącznej liczby żetonów na dwóch pozostałych stosach, 2/3 wszystkich żetonów ze stosu \(S_i\) zostaje przeniesionych na dwa pozostałe stosy, po tyle samo żetonów na każdy z nich. Operacjami elementarnymi w procedurze PołóżŻeton są operacje stosowe Push i Pop. Dokonaj analizy kosztu zamortyzowanego operacji PołóżŻeton. Za prawidłową analizę otrzymasz 3 punkty. Za prawidłową analizę metodą funkcji potencjału - 5 punktów.

Podpowiedź

Funkcja potencjału \(\Phi(S_1,S_2,S_3)=4\max(|S_1|,|S_2|,|S_3|)\). Zauważmy, że gdy dokonujemy przenosin stosu \(S_i\) to potrzebujemy \(2\frac{2|S_i}{3}\) operacji, przed wykonaniem operacji potencjał wynosi \(\Phi=4|S_i|\), po wykonaniu operacji potencjał \(\Phi' \le \frac{8|S_i|}{3}\) (przed wykonaniem operacji \(\frac{|S_i|}{3} \ge \max_{j\not=i}|S_j|\)).

Uwaga: W każdym zadaniu uzasadnij poprawność swoich rozwiązań i dokonaj analizy złożoności obliczeniowej zaproponowanych algorytmów.