DRUGI TERMIN:

1. Uogólniony problem podziału (UPP) zdefiniowany jest następująco: dany jest uporządkowany zbiór
A={a_­1,a₂,...,a_n­} n liczb naturalnych takich, że a₁≥a₂≥...≥a_n. Zadaniem jest takie podzielenie zbioru A na 2 podzbiory A₁ i A₂, że
Pokaż, że algorytm zachłanny dla UPP, który dla każdego a_i, i=1,..., n wybiera ten podzbiór, który ma aktualnie mniejszą sumę, jest optymalny dla n≤4 i suboptymalny dla n ≥ 5.

Odp.: Aby udowodnić, że ten algorytm jest suboptymalny dla n ≥ 5 należy podać chociaż jeden przykład dla którego ten algorytm jest nie optymalny. Pierwsza musi być sumą 2 ostatnich, a dwie środkowe takie same.

Dla liczb:86644 algorytm podzieli na 844 66 , a optymalne rozwiązanie to 86 644.

Dla liczb a ≥ b ≥ c ≥ d ten algorytm nigdy nie poda odpowiedzi ab cd , a tylko takie rozwiązanie byłoby nieoptymalne.

2. Czy pamiętasz zadanie z mostem? Dotarłeś do brzegu rzeki i w celu znalezienia mostu stosujesz następujący algorytm A: dopóki nie znajdziesz mostu robisz krok w prawo, następnie 2 kroki w lewo, potem 3 kroki
w prawo, itd. Utożsamiając skuteczność algorytmu z długością przebytej drogi pokaż, że nie istnieje stała k taka, że A jest k-aproksymacyjny.

Odp.:

3. Problem PE (Precoloring Extension) zdefiniowany jest następująco: Dane są: liczba naturalna k ≥ 2, graf (może być niespójny) G, jego podgraf H
G wraz z k-pokolorowaniem C_k­. Pytanie czy
k-pokolorowanie C_k daje się rozszerzyć na k-pokolorowanie całego grafu G? Pokaż, że PE jest NP-zupełny.

Odp.: Jeżeli graf G jest niespójny i składa się z podgrafu H i reszty, czyli podgrafu J, to graf H i J są rozłączne. Optymalne pokolorowanie podgrafu H nie daje się rozszerzyć na graf J. Podgraf J możemy potraktować jako oddzielny graf, a wówczas PE jest problemem kolorowania grafu, a to znaczy, że jest on NP-zupełny.

4. Udowodnij, że jeżeli P≠NP, to nie istnieje wielomianowy algorytm 1-absolutnie aproksymacyjny dla problemu minimalnego pokrycia wierzchołkowego grafu.

Odp.:

Założenie główne P ≠ NP
Zakładamy że alg 1 abs aproksymacyjny faktycznie istnieje. Dla dowolnego grafu G wiec może zwrócić minimalne pokrycie lub pomylić się o jeden, czyli opt lub opt+1.
Skonstruujmy graf składający się z 2ch grafów G i oznaczmy G*
W Grafie G* alg 1abs aprox może się pomylić co najwyżej o 1. a skoro G* składa się z 2ch grafów G wiec optymalnym w G* jest pokrycie rozmiaru 2*opt ( w grafie G).
Skoro alg może się pomylić o 1 wtedy dla jednej składowej grafu obliczy opt a dla drugiej opt +1. Lub nie pomylić się wcale dla G* zwrócić 2*opt ( gdzie opt jest optimum w grafie G).
Jeżeli się pomylił o co najwyżej 1 to znaczy ze albo znalazł rozwiązanie optymalne albo w jednej ze składowych znalazł optymalne. Co więcej znalazł optymalne w czasie wielomianowym ( nawet jak nie jest napisane ze aproksymacyjny wielomianowy to tak go trzeba traktować u Kubale ). Rozwiązaliśmy problem npc w czasie wielomianowym wiec P=NP i mamy milion dolarów. Wszystko fajnie gdyby nie założenie główne, które mówi, że mamy sprzeczność i taki alg nie może istnieć.

5. Problem Pokrycie Wierzchołkowe (Dany jest graf G i liczba naturalna k; czy G ma pokrycie wierzchołkowe mocy ≤ k ?) jest NP-zupełny. Udowodnij, że ten problem radykalnie zmienia status, gdy k = 2. Wskazówka: Przyjmij, że G zapisany jest w postaci macierzy sąsiedztwa wierzchołków.

Odp.: Jeżeli k=2 to jesteśmy w stanie w wielomianowy sposób sprawdzić, czy istnieje pokrycie wierzchołkowe o mocy k, na podstawie macierzy sąsiedztwa wierzchołków. W macierzy sąsiedztwa wybieramy 2 wiersze zawierające największą liczbę jedynek, wykreślamy je, a następnie sprawdzamy ich lustrzane odbicie i również wykreślamy. Jeżeli w macierzy nie pozostały już żadne jedynki to znaleźliśmy pokrycie wierzchołkowe dla k=2.

6. Dany jest zbiór n różnych liczb naturalnych A={a₁,a₂,...,a_n}. Wiadomo, że problem polegający na sprawdzeniu, „czy zbiór ten można rozbić na sumę dwóch rozłącznych zbiorów B i C
(tzn.
) o równych sumach elementów?” jest NP-zupełny. Czy pozostanie on
NP-zupełny, czy też stanie się wielomianowy przy następujących modyfikacjach:

1. n jest podzielne przez 3

2. liczby są 33. Kolejnymi wyrazami ciągu Fibonacciego

3. wszystkie liczby a_i są podzielne przez 3

4. sumy B i C mogą się różnić o maksymalnie 3

5. sumy B i C muszą się różnić o co najmniej 3

6. zamiast podziału na zbiory B i C, mamy podział na zbiory B, C i D o równych sumach elementów

Odp.: a) NPC. Sama podzielność ilości liczb przez 3 nic nie wnosi, wiec nie zmienia statusu problemu.

b) P. Zmienia, bo wystarczy sprawdzić, czy liczba elementów jest podzielna przez 3, ponieważ dla dowolnej liczby Fibonacciego dwie poprzedni ją równoważą.

c) NPC. Sama podzielność każdej liczby ciągu nic nie wnosi bo nie da się zrównoważyć poprzednimi.

d) NPC. Nic to nie wnosi bo nie wpływa znacząco na uproszczenie problemu.

e) P. Zmienia to znacząco problem, ponieważ wystarczy wszystkie liczby wrzucić na jedną z szalek.

f) NPC. Podział na trzy podzbiory o równych sumach elementów jest znanym problemem NPC.PIERWSZY TERMIN:

1. Uporządkuj następujące złożoności malejąco:

1. 
   

2. 
   C jest wagą krawędzi,

3. 
   W jest sumą wag,

4. 
   Zakładając, że graf jest planarny, zaś C=O(1).

5. 
   

6. 
   

7. 
   

Odp.: d,f,g,e,c,b,a. Łatwo je uporządkować znając zależność że najpierw „?”, bo na początku nie liczono złożoności. Następnie według potęgi n, od największej. Na koniec ten najbardziej przekombinowany, bo nie wiele już mogli wymyślić żeby był lepszy od poprzedniego. Logarytm jest zawsze mniej ważny od potęgi, nawet pierwszej.

2. Ułóż równanie rekurancyjne na T(n) i rozwiąż w terminach symbolu Θ(.). T(n) liczba kroków, aby spenetrować teren ≤ n. Dopóki nie znajdziesz mostu robisz krok w prawo, następnie 2 kroki w lewo, potem 3 kroki w prawo, itd.

Odp.: wzór: wzór na postać iloczynową d(n):

d(xy) = d(x) * d(y)

4xy-1≠ (4x-1)*(4y-1)

0(4n+1)= 0(4n)

a=1 d(n)=4n-1 => d(n)=4n , ponieważ d(n) musi mieć postać iloczynową.

Z wzorów w książce: d(n)=ω(1ⁿ)= ω(1) => T(n)=0(n*d(n)) => T(n)=0(n*4n)=0(4n²)=0(n²)

3. Dany jest graf G, zapisany w postaci macierzy sąsiedztwa wierzchołków G[1..n][1..n]. Napisz algortym lgs(G), który zwraca liczbę gwiazd spinających zawartych w G. Oszacuj złożoność.

	A	B	C	D	E
A	0	1	0	1	0
B	1	0	1	1	0
C	0	1	0	1	0
D	1	1	1	0	1
E	0	0	0	1	0

Odp.: Dla G(n) jeżeli jest gwiazda to w wierszu/kolumnie znajduje się (n-1) jedynek.

procedure gwiazda(S [1..n] [1..n]:integer):integer;

begin

gwiazd=0;

for i=0 to n do

begin

jedynek=0;

for j=0 to n do

begin

if S[i][j] ==1 then jedynek++;

if jedynek == n-1 gwiazda++;

end;

end;

return gwiazda;

end.

T(n)= (n²) => θ(n²)

4. Dane są 3 pudełka w których znajdują się po 2 kulki; 2 czarne, 2 białe lub 1 biała-1 czarna. Etykiety na pudełkach zostały tak pomieszane, żeby napewno nie wskazywały prawidłowej zawartości. Ile trzeba wyjąć kulek aby rozróżnić pudełka wyciągając po kolei po jednej z każdego? Odpowiedz swoją uzasadnij opisem algorytmu postępowania i dowodem optymalności.

Odp.: Algorytm:

Wyciągamy 1 kulę z pudełka oznaczonego BC. Jeżeli jest biała to wewnątrz są 2 białe kule, a jeżeli czarna to 2 czarne. Jeżeli w BC była biała to w BB jest CC(bo nie może być CC w CC), a w CC jest BC. Jeżeli w BC była czarna to w CC jest BB (bo nie może być BB w BB), a w BB jest BC.

5. Ułóż równanie rekurencyjne, za pomocą θ(.) oszacuj asymptotyczną liczbę kroków wykonywaną przez f(n). Podaj klasę złożoności obliczeniowej.

function f(n : integer) : real;

begin

x := 1;

if n>1 then for i := 1 to 5 do x :=3 · f(
) + 2 · x); // 5*f(n/2)

j := 0;

while j < n do begin // wykona się n razy

j := j+1;

if n ≤ j³ then return x · j; // wykona się

end;

end;

Odp.: Wszystkie składowe liczymy oddzielnie.

1. T(n)= 0(5T(n/2))

a=5 b=2 d(n)=0 d(b)=0

z książki: a>d(b) => 5>0 => θ(n^log₂⁵)

2. T(n)=0(n)

3. T(n)=0(
)

Wybieramy największą złożoność z 3 przypadków 0(
) < 0(n) < θ(n^log₂⁵) , a więc złożoność całości jest T(n)=θ(n^log₂⁵).

6. Podaj optymistyczną i pesymistyczną liczbę kroków oraz optymistyczna i pesymistyczną złożoność obliczeniową podanego algorytmu używając symboli Θ:

procedure sort(A [1..n] : wektor; n : int);

begin

i := 1;

while i < n do begin

if A[i] > A[i+1] then begin

A[i] :=: A[i+1]; //zamiana

i := 1;

end

else i := i+1;

end;

end;

Odp.: Algorytm sortuje liczby rosnąco.

Liczba kroków:

- optymistyczna : n (ponieważ przejdzie tylko raz po wszystkim, gdyż wszystko jest poukładane)

- pesymistyczna : n³ (ponieważ musi dla każdego niepoprawnego elementu musi zaczynać od początku, więc n*n i jeszcze przejść po wszystkich i sprawdzić czy są poukładane, wiec jeszcze razy n)

niespójne

G

J

H

G

---