Egzamin poprawkowy 2005/06

Zadanie 1

Słowa kluczowe: statystyki pozycyjne

Zaprojektuj drzewo decyzyjne znajdujące medianę z pięciu różnych elementów w co najwyżej sześciu porównaniach.

Zadanie 2

Słowa kluczowe: grafy

Trójkątowym kaktusem nazywamy spójny graf w którym każda dwuspójna składowa jest cyklem długości trzy (trójkątem). Niech \(G=(V, E)\) będzie \(n\)-wierzchołkowym trójkątowym kaktusem. Przyjmujemy, że \(G\) jest reprezentowany za pomocą list sąsiedztwa.

1. Podaj liczbę krawędzi \(G\) jako funkcję \(n\)?

2. Pokaż w jaki sposób zastosować przeszukiwanie w głąb do prawidłowego pokolorowania wierzchołków grafu \(3\) kolorami. Zapisz swój algorytm w pseudokodzie.

3. Zaproponuj efektywny algorytm znajdowania najliczniejszego skojarzenia w \(G\).

Zadanie 3

Słowa kluczowe: struktury danych, Find-Union

Tablica \(p[1..n]\) opisuje zbiór drzew z korzeniami (las), rozpiętych na zbiorze wierzchołków \(\{1, 2, \cdots, n\}\) - \(p[j]\) jest ojcem wierzchołka \(j\) w lesie, jeżeli tylko \(p[j] <> j\); jeżeli \(p[j] = j\), to \(j\) jest korzeniem drzewa.

Na lesie wykonujemy następujące operacje:

1. \(Parent(j) ::\) podaj wartość \(p[j]\);

2. \(Union(j, k) ::\) połącz dwa drzewa o korzeniach \(j\), \(k\) w jedno, czyniąc korzeń jednego z nich ojcem drugiego korzenia;

3. \(Contract(j) ::\) jeśli \(j\) nie jest korzeniem, to niech \(D\) będzie zbiorem wszystkich dzieci \(j\) lub \(p[j]\), z wyłączeniem \(j\); wybierz wierzchołek \(j\) lub \(p[j]\); niech \(x\) będzie wybranym wierzchołkiem, a \(y\) tym drugim; jeśli \(p[j]\) nie jest korzeniem, to uczyń ojcem \(x\) wierzchołek \(p[p[j]]\), w przeciwnym razie niech \(p[x] := x\); uczyń \(x\) ojcem wierzchołka \(y\), jak i wszystkich wierzchołków z \(D\).

Zaprojektuj sposób efektywnego wykonywania ciągu operacji \(Parent\), \(Union\) lub \(Contract\).

Zadanie 4

Słowa kluczowe: struktury danych, wzbogacanie

Zaprojektuj strukturę danych do przechowywania przedziałów domkniętych, która będzie umożliwiać wykonywanie następujących operacji, każdą w czasie \(O({\log n}^2)\):

1. \(Insert(x, y)\) - dodaj przedział \([x, y]\)

2. \(Remove(x, y)\) - usuń przedział \([x, y]\)

3. \(Count(x, y)\) - oblicz liczbę przedziałów w strukturze zawartych w przedziale \([x, y]\)

O liczbach \(x\), \(y\) wiadomo, że są liczbami całkowitymi z przedziału \([1,n]\) , dla pewnego, ustalonego całkowitego \(n > 1\).