Egzamin 2000/01#

Zadanie 1 [10 punktów]#

Słowa kluczowe: najdłuższy podciąg rosnący

Podciągi rosnące. Oto algorytm, który w danym ciągu liczb całkowitych \(<a_1, a_2, \cdots, a_n>\) znajduje dla każdego \(i\), długość najdłuższego podciągu (ostro) rosnącego o początku w \(a_i\).

max_dl_o_pocz[n] := 1;
for i := n-1 downto 1 do
    max_dl_o_pocz[i] := max({max_dl_o_pocz[j] : (j > i) AND (a_j > a_i)}) + 1;

Zaproponuj efektywną implementację tego algorytmu. Uzasadnij poprawność swojego rozwiązania i przeanalizuj jego złożoność.

Zadanie 2 [10 punktów]#

Słowa kluczowe: struktury danych, kolejka, amortyzacja

Kolejka podwójna to lista, na której wykonywane są następujące operacje:

  • \(\textsf{Front}(q)\):: zwróć pierwszy element listy \(q\);

  • \(\textsf{Push}(q, x)\):: wstaw \(x\) na początek listy \(q\);

  • \(\textsf{Pop}(q)\):: usuń pierwszy element listy \(q\);

  • \(\textsf{Rear}(q)\):: zwróć ostatni element listy \(q\);

  • \(\textsf{Inject}(q, x)\):: wstaw \(x\) na koniec listy \(q\);

  • \(\textsf{Eject}(q)\):: usuń ostatni element listy \(q\).

Zaproponuj efektywną implementację kolejki podwójnej na trzech stosach. Przeanalizuj dokładnie koszt zamortyzowany poszczególnych operacji.

Zadanie 3 [10 punktów]#

Słowa kluczowe: grafy

Grafem trójkątnym nazywamy graf, w którym każda dwuspójna składowa jest trójkątem. Zaproponuj efektywny algorytm, który w danym grafie trójkątnym \(G = (V, E)\)

  1. znajdzie długość najdłuższej ścieżki elementarnej,

  2. policzy moc najliczniejszego skojarzenia

Zadanie 4 [10 punktów]#

Słowa kluczowe: wyszukiwanie; max, asymptotycznie optymalny

Rozważ zadanie znajdowania maximum za pomocą porównań w różnowartościowym \(n\)-elementowym ciągu liczbowym. Na co najwyżej jedno pytanie o wynik porównania możemy dostać błędną odpowiedź.

  1. Podaj efektywny algorytm na znajdowanie maximum w takim przypadku.

  2. Ile co najmniej pytań trzeba zadać w pesymistycznym przypadku? Uzasadnij formalnie swoją odpowiedź.