5. Egzamin - [2002]

Egzamin z AA - 5 sem. (2002-01-29)

Zadanie l Na rysunku przedstawiono graf skierowany z określonymi wagami krawędzi. Czy dla tego grafu istnieją najkrótsze drogi między wszystkimi parami wierzchołków? Zaproponować taką modyfikację algorytmu Floyda-Wshalla. Która poza znajdowaniem najkrótszych dróg pozwoli wykryć sytuacje, w których takie drogi nie istnieją. Zastosować ten algorytm do przedstawionego grafu, tzn. znaleźć długości najkrótszych dróg między wszystkimi parami jego wierzchołków lub pokazać, na którym etapie obliczeń algorytm wykryje brak możliwości znalezienia dróg.

Zadanie 2 Dany jest zbiór liczb 5 = {2,6,14,15,17,18,19,21,27,29,40.49}. Wykorzystując, przedstawiony na ćwiczeniach. zachłanny algorytm kolorowania grafu, podziel zbiór 5 na rozłączne zbiory A, B.... zawierające liczby parami względnie pierwsze. (Dwie liczby są względnie pierwsze jeśli ich NWD wynosi l.)

Zadanie 3 Wyznaczyć pesymistyczną złożoność obliczeniową następującego algorytmu obliczania wartości x". 1 2 3 4 5 6 7 8 9 10 11 12

function potega(x, n); begin potęga:=1;, while N<>O do if odd(n) then potęga := potęga * x; end if; n := n div 2; x:=x*x; end while: return potęga; end.

.

Jako operację dominującą przyjąć mnożenie liczb, (n > O, n należy do Z).