Egzamin poprawkowy 2010/11#
Zadanie 1#
Dany jest (przez listy sąsiedztwa) zorientowany graf \(G=(V,E)\). Zaprojektuj efektywny algorytm, który znajduje podgraf \(H=(V,F)\) grafu \(G\) zawierający \(O(|V|)\) krawędzi i którego silnie spójne składowe dają taki sam podział zbioru wierzchołków \(V\), co silnie spójne składowe grafu \(G\).
Zadanie 2#
Dany jest (przez listy sąsiedztwa) słabo spójny zorientowany graf bez cykli \(G=(V,E)\). Ponieważ graf jest słabo spójny, to pomiędzy każdą parą wierzchołków istnieje ścieżka, choć pewne krawędzie na takiej ścieżce należy przechodzić przeciwnie do ich orientacji. Zaproponuj efektywny algorytm, który dla pary wierzchołków \(u\), \(v\) znajdzie ścieżkę elementarną z \(u\) do \(v\), na której znajdzie się możliwie najmniejsza liczba krawędzi, które trzeba będzie pokonać w kierunku przeciwnym do ich orientacji.
Zadanie 3#
Zaproponuj implementację struktury danych udostępniającej operacje struktury Find-Union dla elementów \(1..n\) z przypisanymi całkowitoliczbowymi wartościami (początkowo same zera) oraz dwie nowe operacje:
\(Add(i, a) ::\) do wartości wszystkich elementów ze zbioru zawierającego element \(i\) dodaj wartość \(a\)
\(Value(i) ::\) podaj aktualną wartość przypisaną elementowi \(i\)
Zadanie 4#
Zaproponuj strukturę danych, który implementuje dynamiczny, skończony ciąg liczbowy z następującymi operacjami:
\(Podaj(i) ::\) podaj wartość elementu z pozycji \(i\)-tej,
\(Wstaw(i,a) ::\) wstaw \(a\) na pozycje \(i\)-tą w ciągu (tzn. pomiędzy elementami na pozycjach \(i - 1\) oraz \(i\)),
\(Usun(i) ::\) usuń \(i\)-ty element z ciągu,
\(MinLuka ::\) podaj co do wartości bezwzględnej wartość najmniejszej różnicy pomiędzy dwoma kolejnymi elementami ciągu.
Możesz przyjąć, że wynik wywołania każdej z powyższych operacji jest dobrze określony.