Kolokwium nr 1 (12.2008)

Zadanie 2.

Na płaszczyznę rzucono n prostych. Niech R(n) oznacza największą możliwą liczbę regionów (ograniczonych lub nie) powstałych w ten sposób, np. R(0)=1, R(1)=2. Wiadomo, że R(n)=xR(n-1)+ym. Ustal wartość x i y. Oszacuj tempo wzrostu R(n). Podaj wartość R(4).

R(2) = 4 = 2x+2y

R(3) = 7 = 4x+3y

Rozwiazujemy uklad, wychodzi x=1, y=1.

R(n) = R(n-1) + n

R(4) = 7+4 = 11

Tempo wzrostu:

d(n) = n

a^n = 1^n = 1

d(n) = ω(a^n), wiec R(n) = O(n^2)

Zadanie 3. (str. 90 skryptu Kubale zad 3.28)

W historii problemu przydziału (LSAP) dla ważonych grafow dwudzielnych znane są następujące coraz szybsze algorytmy:

(1946) Easterfielda

(1955) Khuna

(1969) Dinica-Kronroda

(1985) Gabowa

(1988) Bertsejasa-Ecksteina

(1989) Gabowa-Tarjana

(2001) Kao i in.

o złożonościach O(sqrt(n)Wlog(C^2/W)/logn), O(sqrt(n)mlog(nC)), O(n^(3/4)mlogC), ? , O(nmlog(nC)), O(n^4), O(n^3), gdzie C jest największą wagą krawędzi, zaś W - sumą wag. Zakładając, że C=O(1), przypisz złożoności do algorytmów.

Odpowiedź na 99% poprawna:

(1946) Easterfielda ?

(1955) Khuna O(n^4)

(1969) Dinica-Kronroda O(n^3)

(1985) Gabowa O(nmlog(nC))

(1988) Bertsejasa-Ecksteina O(n^(3/4)mlogC)

(1989) Gabowa-Tarjana O(sqrt(n)mlog(nC))

(2001) Kao i in. O(sqrt(n)Wlog(C^2/W)/logn)

Zadanie 5.

Napisz procedurę obliczająca sumę kwadratów liczb, oblicz czas wykonania i złożoność oblicz.

procedure T(n)

begin

if n = 1 return 1;

else return T(n-1) + n*n

end

nasza zajebista procedura wykona się n razy, czyli czas wykonania = teta(n)

na wejście dostajemy liczbę, czyli N to rozmiar danych wejsciowych, ktory rowny jest liczbie bitow za pomoca ktorych mozemy wyrazic liczbe n, czyli N = podłoga(log2n) + 1 // dwa przy podstawie

co z dokładnością do 1 : N = log2n

Więc procedura o czasie działania n pobierająca na wejściu liczbe będzie wykładnicza bo n = 2^N stąd złożoność obliczeniowa = teta(2^N)

Zadanie 6.

function kwadraty (n : word) : boolean

var i, j, k : word

begin

k := 1, n := n - 1

while (n > 0) do

begin

j := 0

while (j < n) do

begin

j := j + 1

if (n == j * j) return true

end

n = n - 2 * (k - 1)

k = k + 1

end

return false

end

Rozwiązanie:

Najpierw rozważymy ilość wykonań pętli

Kod:

while (n > 0) do

begin

(...)

[b]n = n - 2 * (k - 1)

k = k + 1[/b]

end

jak widać n maleje o kolejne liczby parzyste, czyli n = n - (0 + 2 + 4 + 6 + 8 +2(k-1))

czyli n = n - k(k + 1)

więc:

ilosc wykonan petli bedzie rowna najmniejszemu takiemu k dla którego: k(k+1) >= n

czyli k = sufit(sqrt(n)) + coś co nie wnosi nic do tego tempa

Pętla

Kod:

while (j < n) do

begin

j := j + 1

if (n == j * j) return true

end

wykonuje się n razy

Więc mamy 2 pętle: jedna leci n razy, druga sufit(sqrt(n)) czyli czas działania procedury wynosi teta(n*sqrt(n)) czyli teta(n^3/2). Jest to czas pesymistyczny

Pillow napisał(a):

Optymistyczna wynosi sqrt(n). Przypadek optymistyczny jest gdy znajdziemy rozwiazanie w pierwszym obiegu zewnetrznej petli, a wewnetrzna wykona sie dokladnie sqrt(n) razy.

Z 29.01.2009:

1.Dany jest zbiór n różnych liczb naturalnych A={a1,...,an} Wiadomo że problem polegający na sprawdzeniu "czy zbiór można rozbić na sume dwóch rozłącznych zbiorów B : C o równych sumach elementów" jest NP-zupełne. Czy pozostanie on Np-zupelny, czy tez stanie sie wieloomainowe przy nastepujacych modyfikacjach:

a) n jest podzielne

b) wszystkie liczby ai =< 33

c) wszystkie liczby ai są podzielne przez 3

d) sumy elementów zbiorów B i C nie muszą buc równe lecz mogą różnić się co najwyżej o 3

e) sumy te muszą się różnić o wiecej niz 3

f) 2 zbiory B i C zastepujemu trzema B,C i D o równych sumach elementów

Uzupłelnij graf redukcji pomiedzy tymi podproblemami

a). NPC(?

b). NPC - nie upraszcza to problemu

c). NPC - podzielność przez trzy niczego nam nie zmienia, weźmy dowolny zbiór liczb A danych dla podproblemu bazowego, i każdą z nich pomnóżmy przez 3 - otrzymujemy zbiór liczb A' podzielny przez 3. Zatem, jeśli P nie jest równe NP, to problem ten też musi być NP-zupełny.
d). NPC - nie jest to dowód, ale można wnioskować, że problem 2-podziału to szczególny przypadek danego w tym podpunkcie problemu (czyli: sumy elementów zbiorów B i C mogą się różnic co najwyżej o k elementów, dla 2-podziału k = 0 )
e). P, wystarczy jako B wziąć zbiór pusty, a jako C zbiór wszystkich liczb ze zbioru A. Jeśli ich różnica jest >= 3, to znaczy, że zbiór da się tak podzielić, jeśli nie, to się nie da.
f). NPC, problem można alfa-zredukować do problemu bazowego, dodając do zbioru wejściowego liczbę naturalna K równą połowie sumy wszystkich liczb ze zbioru ( będzie musiała stanowić osobny zbiór D, a pozostałe liczby z A będą i tak musiały się rozdzielić na B i C ).