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.
Kod:
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

(2009-02-09 12:14:34)
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.