Ctrl+K

Egzamin 2016/17 (31.01.2017)

Egzamin 2016/17 (31.01.2017)#

Zadanie 1 [24 punkty]#

Słowa kluczowe: grafy

Niech n będzie dodatnia liczbą całkowitą. Grafem Ln nazywamy graf \(({1,2, ..., n}, {i─j: 0 < |i-j| < 3})\).

  1. [3 punkty] Ile jest różnych BFS-drzew w grafie Ln zakorzenionych w wierzchołku 1.

  2. [3 punkty] Ile jest różnych DFS-drzew w grafie L10 zakorzenionych w wierzchołku 1.

Uwaga: dwa drzewa są różne, jeśli istnieje wierzchołek, który w tych drzewach ma różnych ojców.

W podzadaniach (c) i (d) przyjmujemy, że każda krawędź w grafie Ln ma przypisaną całkowitoliczbową wagę.

  1. [8 punktów] Zaprojektuj algorytm, który w czasie liniowym obliczy minimalne drzewo rozpinające w danym grafie Ln.

  2. [10 punktów] Zaprojektuj strukturę danych, która umożliwia efektywne wykonywanie następujących operacji dla dynamicznie modyfikowanych wagach krawędzi w grafie Ln:

  • Ini:: inicjacja struktury danych dla zadanych początkowo wag (tylko raz);

  • Zmiana(e,w):: zmień wagę krawędzi e na nową wagę w;

  • WMDR:: podaj wagę minimalnego drzewa rozpinającego w bieżącym grafie Ln.

Zadanie 2 [8 punktów]#

Słowa kluczowe: amortyzacja

Gracz ma do dyspozycji planszę w kształcie nieograniczonego pasa podzielonego na kwadratowe pola. Jedno pole wypełnia całą szerokość pasa. Możliwe są następujące posunięcia:

  • położenie pionka na wskazanym, wolnym polu,

  • zdjęcie wskazanego pionka i uczynienie pola zajętego przez ten pion wolnym,

  • wielokrotny skok w prawo (symetrycznie w lewo) od wskazanego pionka.

Pojedynczy skok w prawo odnosi się zawsze do pola zajętego (z pionkiem), dla którego pierwsze pole na prawo jest zajęte, ale następne pole z prawej strony jest puste. Skok polega na ustawieniu nowego pionka na tym pustym polu. Wielokrotny skok w prawo polega na wykonywaniu pojedynczych skoków w prawo tak długo, jak to możliwe, poczynając od wskazanego zajętego pola. Tzn. wykonujemy pojedynczy skok w prawo, następnie pojedynczy skok w prawo od pola, na którym postawiliśmy nowy pionek o ile to możliwe, itd.

Przykład:

Niech O oznacza pole zajęte, a _ pole wolne. Rozważmy pas

_ _ O O O _ O _ O _ O O _

Po wykonaniu wielokrotnego skoku w prawo dla pionka O dostajemy konfigurację

_ _ O O O O O O O O O O _

Dokonaj analizy kosztu zamortyzowanego jednego posunięcia gracza. Za operację elementarną przyjmujemy postawienie lub usunięcie pionka.

Zadanie 3 [8 punktów]#

Słowa kluczowe: teksty, drzewo sufiksowe

Zaprojektuj efektywny algorytm, który dla danych słów x, y nad alfabetem {d,i,k,s} obliczy ile różnych słów będących cyklicznymi przesunięciami słowa x jest podsłowami słowa y.

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

Zawartość