Egzamin 2020/21 (09.02.2021)

Zadanie 1 [14 punktów]

Słowa kluczowe: grafy

Grafem klik nazywamy graf spójny, w którym każda dwuspójna składowa jest kliką. W tym zadaniu zakładamy, że wierzchołkami grafu klik są kolejne liczby naturalne poczynając od 1 oraz kliki są ponumerowane kolejno \(1, 2, \ldots\).

1. [2 punkty] Podaj najmniejszą i największą liczbę klik w n-wierzchołkowym grafie klik.

2. [2 punkty] Jaka może być najmniejsza, a jaka największa liczba krawędzi w 2021-wierzchołkowym grafie klik o 100 klikach?

3. [3 punkty] Dokonaj analizy liczby możliwych numeracji DFS rozpoczynających się w wierzchołku 1 w zadanym grafie klik o dokładnie dwóch klikach, każda składająca się z 10 wierzchołków. Dwie numeracje uznajemy za różne, gdy istnieje wierzchołek, który ma różne numery w obu numeracjach.

Niech G będzie n-wierzchołkowym grafem klik o dokładnie k klikach. Zwartą reprezentacją grafu G nazwiemy graf dwudzielny Z(G) = (X,Y,F), w którym \(X = \{1, 2, \ldots, n\}\) oraz \(Y = \{1, 2, \ldots, k\}\) są odpowiednio zbiorami wierzchołków i klik w grafie G, natomiast zbiorem krawędzi jest \(F = \{x - y: x \in X, y \in Y\ \mbox{oraz wierzchołek}\ x\ \mbox{jest w klice}\ y\}\).

4. [7 punktów] Dana jest zwarta reprezentacja Z(G) grafu klik G. Zaproponuj wydajny algorytm, który obliczy długość najdłuższej ścieżki elementarnej w grafie G.

Zadanie 2 [7 punktów]

Słowa kluczowe: struktury danych, wzbogacanie

Na początkowo pustym n-wierzchołkowym grafie G, n>0, którego wszystkie wierzchołki są pokolorowane na biało, wykonujemy operacje:

• Kolor(v,c):: pokoloruj wierzchołek v na kolor c, gdzie \(c \in \{\textrm{biały}, \textrm{czerwony}\}\)

• Dodaj(v,u):: dodaj krawędź łączącą wierzchołki v, u do grafu G

• ZbalansowaneSkładowe():: podaj liczbę zbalansowanych spójnych składowych w grafie G, tzn. takich, w których liczby wierzchołków białych i czerwonych różnią się co najwyżej o 1.

Przyjmij, że wierzchołkami grafu są liczby \(1, 2, \ldots, n\). Zaproponuj strukturę danych, która umożliwi wykonanie ciągu m operacji Kolor, Dodaj, ZbalansowaneSkładowe, gdzie \(m \ge n\), w możliwie małym koszcie zamortyzowanym.

Zadanie 3 [12 punktów]

Słowa kluczowe: teksty

Dane jest słowo x o długości n nad alfabetem {d, i, k, s}.

1. [8 punktów] Zaproponuj wydajny algorytm, który obliczy liczbę wszystkich różnych podsłów, słowa x, z których każde zawiera wszystkie litery z alfabetu {d, i, k, s}. Dla przykładu, w słowie ababa liczb wszystkich różnych podsłów zawierających każdą z liter a i b wynosi 7.

2. [4 punkty] Podaj ile wynosi najmniejsza, a ile największa wartość sumy elementów tablicy prefiksów-sufiksów dla słowa x (tablica P z algorytmu Knutha-Morrisa-Pratta), gdy \(n = 4k\) i każda z liter d, i, k, s pojawia się w słowie x dokładnie k razy.

Zadanie 4 [7 punktów]

Słowa kluczowe: geometria

W tym zadaniu rozważamy tylko domknięte odcinki równoległe do osi współrzędnych na płaszczyźnie, zadane przez współrzędne końców. Danych jest n odcinków, z których tylko odcinki prostopadłe mogą mieć punkt wspólny. Zaproponuj wydajny algorytm, który obliczy największą liczbę punktów przecięć jednego odcinka z innymi i wyznaczy wszystkie odcinki, które przecinają właśnie tyle innych odcinków.