PAA 1 i 2 koło pyt+odp


DRUGI TERMIN:

1. Uogólniony problem podziału (UPP) zdefiniowany jest następująco: dany jest uporządkowany zbiór
A={a­1,a2,...,an­} n liczb naturalnych takich, że a1≥a2≥...≥an. Zadaniem jest takie podzielenie zbioru A na 2 podzbiory A1 i A2, że 0x01 graphic
Pokaż, że algorytm zachłanny dla UPP, który dla każdego ai, 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.: 0x01 graphic
0x01 graphic

0x08 graphic

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 H0x01 graphic
G wraz z k-pokolorowaniem C. Pytanie czy
k-pokolorowanie Ck 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.:

0x08 graphic
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={a1,a2,...,an}. 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. 0x01 graphic
) 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 ai 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. 0x01 graphic

  2. 0x01 graphic
    C jest wagą krawędzi,

  3. 0x01 graphic
    W jest sumą wag,

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

  5. 0x01 graphic

  6. 0x01 graphic

  7. 0x01 graphic

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.

0x08 graphic
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.

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

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

0x08 graphic
4xy-1≠ (4x-1)*(4y-1)

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

0x08 graphic

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

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

0x08 graphic
0x08 graphic
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

0x08 graphic

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)= (n2) => θ(n2)

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(0x01 graphic
) + 2 · x); // 5*f(n/2)

j := 0;

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

j := j+1;

if n ≤ j3 then return x · j; // wykona się 0x01 graphic

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 => θ(nlog25)

2. T(n)=0(n)

3. T(n)=0(0x01 graphic
)

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

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 : n3 (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

0x01 graphic

0x01 graphic

0x01 graphic



Wyszukiwarka

Podobne podstrony:
kolo pyt i odp wszystko id 2372 Nieznany
PAA 3 termin pyt+odp
Zakazy 1 koło pyt i odp, Studia, IV ROK, Bydło, Zakaźne, ZAKAZY, kolos I, zakaz zakazany na 1 kolo n
word, giełda mikro kolo II , 97 pyt z odp., 1
pyt. bota koło III z odp, farmacja, BOTANIKA FARMACEUTYCZNA, Koła
,technika satelitarna,pyt&odp
pyt i odp andragogika 1
NERKI I FIZ STOSOWANA pyt odp
pyt odp
Socjologia pyt i odp
wyklad pyt i odp v1 1
Pedagogika Społeczna pyt. i odp., PEDAGOGIKA SPOŁECZ
pyt i odp, Audyt Wewnętrzny
WYZNANIOWE - pyt. i odp, Politologia
socjologia pyt i odp
mikro pyt i odp

więcej podobnych podstron