1. Klasówka 2006/07 (01.12.2006)#

Zadanie 1 (6 punktów)#

Słowa kluczowe: sortowanie, optymalne porównania

Zaproponuj optymalny algorytm sortujący przez porównania różnowartościowe ciągi 7-elementowe \(x_1,x_2,\ldots,x_7\), dla których zachodzi warunek kopca. Uwodonij poprawność swojego rozwiązania

Zadanie 2 (6 punktów)#

Słowa kluczowe: grafy

Niech G=(V, E) będzie grafem spójnym i nich u będzie wierzchołkiem w G. W grafie G obliczamy z wierzchołka u drzewo poszukiwania w głąb D i drzewo poszukiwania wszerz B. Udowodnij, że D=B wtedy i tylko wtedy, gdy G jest drzewem.

Podpowiedź

Jeśli graf posiada cykl, to możemy wyznaczyć 3 wierzchołki leżące na tym cyklu (u, v, w), takie, że:

  • w drzewie DFS znajdziemy ścieżkę \(u \righarrow v \rightarrow w\)

  • w drzewie BFS znajdziemy ścieżki \(u \righarrow v\) i \(u \rightarrow w\) ale bez \(v \rightarrow w\).

Zadanie 3 (8 punktów)#

Słowa kluczowe: sortowanie, amortyzacja

Rozważmy następujący dynamiczny problem sortowania.

Na początku mamy:

a[1..n] = [1,2,…,n] b[1..n] = [0,0,…,0] S = {};

Następnie wykonujemy ciąg operacji, z których każda to Exchange (zamiana dwóch sąsiednich elementów) lub Sort (posortowanie tablicy a). Tablica b to wektor inwersji dla tablicy a, natomiast zbiór S zawiera pozycje niezerowych elementów z b. Przyjmyjemy, że operacje na zbiorze S wykonywane są w czasie stałym. Dokonaj analizy kosztu zamortyzowanego operacji Exchange i Sort.

procedure Exchange(i);
{ 1 < i <= n }
begin
    S := S - [i-1, i];
    a[i] := A[i-1]; // zamiana
    x := b[i];
    if a[i] > a[i-1] then begin
       b[i] := b[i-1];
       b[i-1] := x-1;
    end else begin
       b[i] : = b[i-1] + 1;
       b[i-1] : = x;
    end;
    if b[i] > 0 then S := S + [i];
    if b[i-1] > 0 then S : = S + [i-1];
end;

procedure Sort():
begin
    while not empty(S) do begin
        // niech i będzie dowolnym element z S;
        S : = S - [i];
        j := i; v := a[i]; x := b[i];
        repeat
            j := j-1; w := a[j]; y := b[j]; S := S - [j];
            a[j] := v; b[j]:= x-1;
            if b[j] > 0 then S := S + [j];
            v := w; x := y;
        until v > a[i];
        a[i] := v; b[i] := x;
        if b[i] > 0 then S := S + [i];
    end;
end;