1. W bardzo, bardzo długiej tablicy uporządkowanej rozmiaru n poszukujemy
pewnego elementu x. Mamy do wyboru klasyczną metodę bisekcji (1) lub
metodę podwajania kroku i bisekcji (2). Zakładając że poszukiwany element
znajduje się na pozycji k, określ dla jakich k metoda (1) jest szybsza od metody
(2).
*Bisekcja polega na dwupodziale zbioru na podzbiory - 12345678 -> 1234|5678 (następny krok
przy założeniu że szukamy 6tki) – 56|78 (szukana wartośd znajduje się w podzbiorze lewym) –
5|6 (znaleźliśmy nierozkładalne zbiory i nasz wynik).
*Podwajany krok - 12345678 (założenia podobne jak wyżej) i bisekcja (k0=1) – 1|2345678 ->
23|45678 ->4567|8 (znaleźliśmy ramy podzbioru czyli między 4 a 7; kontynuujemy metodą
bisekcji) – 45|67 -> 6|7 - znaleźliśmy szukaną wartośd. Metoda ta polega na tym że skaczemy
jak pionek po planszy - tablicy; do tego co kolejny skok skaczemy 2 razy dalej; jak widad tworzą
się coraz większe przedziały - ponieważ są one uporządkowane rosnącą wystarczy sprawdzid
czy w przedziale nie znajduje się nasza wartośd - załóżmy że przedział to a......b (<a,b>)
sprawdzamy czy k>=a && k<=b; jeżeli tak to stosujemy metodę bisekcji na przedziale <a,b>.
Odpowiedź: k > sqrt(n). Drugi sposób zaczyna od początku tablicy,
więc dla elementów z kooca tablicy będzie wolniejszy od sposobu
z samą bisekcją, który zaczyna od środka. Dlatego sqrt(n), bo jest
to środkowy element ciągu geometrycznym 2^0, 2^1, 2^2, ..., ~n
po prostu sqrt(n) będzie „połową drogi” zarówno dla bisekcji, jak i
dla "podwojonego kroku".
2. Przypuśdmy, że algorytm A ma złożonośd pesymistyczną f(n), zaś
algorytm B ma złożonośd pesymistyczną g(n). Na każde z poniższych
odpowiedz tak, nie, lub nie wiadomo, a odpowiedź uzasadnij:
2.1.Czy w najgorszym przypadku danych A jest asymptotycznie szybszy od B,
jeśli g(n)=Ω(f(n)logn)
TAK
2.2.Czy w najgorszym przypadku danych A jest asymptotycznie szybszy od B,
jeśli g(n)=O(f(n)logn
) NIE WIADOMO
2.3.Czy w najgorszym przypadku danych A jest asymptotycznie szybszy od B,
jeśli g(n)=Θ (f(n)logn
) TAK
2.4.Czy w najgorszym przypadku danych B jest asymptotycznie szybszy od A,
jeśli g(n)=Ω(f(n)logn
) NIE
2.5.Czy w najgorszym przypadku danych B jest asymptotycznie szybszy od A,
jeśli g(n)=O(f(n)logn
) NIE WIADOMO
2.6.Czy w najgorszym przypadku danych B jest asymptotycznie szybszy od A,
jeśli g(n)= Θ (f(n)logn
) NIE
Dla uproszczenia można przyjąd, że f(n)=n to wtedy g(n)=nlogn ,
wtedy wszystko jest chyba oczywiste (i zgodne z rysunkiem).
3. Udowodnij redukcję 3-SAT alfa 4-SAT
Wyrażenie 3-CNF ma postad: = C
1
* C
2
* C
3
*...* C
n
, gdzie każda klauzula C
i
wygląda następująco: (x
i1
+x
i2
+x
i3
). Wprowadzamy n nowych zmiennych
tworząc formułę ’ w postaci 4-CNF, zastępując każdą starą klauzulę
dwiema nowymi o 4 składnikach, tak że: ’ = ( C
1
+ q
1
) * ( C
1
+ !q
1
) * ( C
2
+
q
2
) * ( C
2
+ !q
2
) *…* ( C
n
+ !q
n
) * ( C
n
+ !q
n
). Widad, że jeżeli formuła była
spełnialna dla pewnego przypisania wartości logicznych, to dla dowolnych
q nie zmieni to ogólnej wartości ’ przekształconego z .
Przykład: = (x1+x2+x3)(x1+!x2+!x3) => ’ =
(x1+x2+x3+x4)(x1+x2+x3+!x4)(x1+!x2+!x3+x4) (x1+!x2+!x3+!x4) Jak widad,
zmienna x4 nie wpływa na spełnialnośd ’, jeżeli było spełnione.
Konkluzja: 3SATα4SAT, a to kooczy dowód!
6. Ustal złożonośd obliczeniową następujących problemów:
6.1. Dany jest graf spójny G w postaci pęków wyjściowych; Czy G zawier a
drzewo spinające T stopnia Δ(T)=<2?
Δ<=2 oznacza, że T jest ścieżką, a wiec problem sprowadza się do
znalezienia ścieżki Hamiltona w G. Jak wiadomo, jest to problem NPC.
6.2. Dany jest graf spójny G w postaci pęków wyjściowych; Czy G zawiera
drzewo spinające T stopnia DELTA(T)>2?
Można w czasie wielomianowym, wystarczy sprawdzid, czy graf jest
spójny i czy każdy wierzchołek ma co najmniej trzech sąsiadów, jest to
problem P o złożoności O(n).
4.Graf G zapisano w postaci macierzy sąsiedztwa wierzchołków. Napisz
program rozstrzygający, czy G jest cyklem i oszacuj jego złożonośd
obliczeniową.
1.
function czy_cyklem(G[n][n]:integer)
2.
var zlicz, ten, pop:integer;
3.
begin
4.
for i := 1 to n do
5.
if G[i][i] = 1 then return false;
6.
for i := 1 to n do
7.
begin
8.
zlicz := 0;
9.
for j := 1 to n do
10.
begin
11.
if G[i][j] = 1 then
12.
zlicz := zlicz + 1;
13.
end
14.
if zlicz != 2 then return false;
15.
end
16. for i := 1 to n do
17.
begin
18.
if G[1][i] = 1 then
19.
begin
20.
ten := i;
21.
break;
22.
end
23.
end
24.
pop := 1;
25. zlicz := 1;
26.
while ten != 1 do
27.
begin
28.
for i := 1 to n do
29.
if G[ten][i] = 1 and i != pop then
30.
begin
31.
pop := ten;
32.
ten := i;
33.
break;
34.
end
35.
zlicz := zlicz + 1;
36.
if zlicz > n then return false;
37.
end
38.
if zlicz = n then return true;
39.
return false;
40. end
Najpierw sprawdzam czy nie ma pętelek na wierzchołkach, czyli czy
wierzchołki nie prowadzą same do siebie. Potem czy wierzchołki są stopnia
drugiego. Po tym zostają nam dwa wyjścia: albo jest to nasz szukany cykl,
albo graf składa się z jakichś pomniejszych gówienek. No to jedziemy od
wierzchołka 1 aż nie wrócimy do niego i zliczamy przez ile przeszliśmy
wierzchołków. Jeżeli przez n to git, jak nie to false. Złożonośd O(n^2).
5. Niepusty graf G, który ma n wierzchołków. Dla danego k sprawdzid „Czy graf G
jest k-barwny?”. Odpowiedzied TRY jeśli O(1), POL jeśli wielomianowo lub NPC.
Dla k=1 wszędzie mamy TRY, ponieważ przy reprezentacji w postaci pęków
wyjściowych wystarczy sprawdzid, czy tablica jest pusta (da się), czy nie (nie da się),
a to zajmuje O(1). Dla k=2 gdy graf jest 2-dzielny problem jest TRY (bo każdy graf 2-
dzielny jest 2-barwny), a dla ogólnego i planarnego jest POL, istnieje wielomianowy
algorytm sprawdzania 2-dzielności grafu (jak nie ma podgrafów K
3
to powinien byd
2-barwny. Dla k=3 problem jest NPC dla grafów ogólnych i planarnych oraz
trywialny dla 2-dzielnych (one są zawsze 2-barwne). Dla k=k problem jest
TRYwialny dla grafów planarnych (je można zawsze pokolorowad za pomocą max 4
barw), o 2-dzielnych było wcześniej, a dla grafu ogólnego jest NPC tak samo jak
przy k=3. Dla k=n-1 problem jest TRYwialny we wszystkich 3 przypadkach.
Moim
zdaniem dlatego, że w pękach wyjściowych wystarczy sprawdzid długośd tablicy (jeśli graf jest pełny to nie da
się, jeśli nie jest to się da), ale tu przydałoby się potwierdzenie tej teorii.
Dla k=n problem jest
TRYwialny we wszystkich 3 przypadkach bo każdy graf można pokolorowad tyloma
kolorami ile ma wierzchołków.
__________1______2______3 _______k______n-1 ____ n___
ogólny: TRY POL NPC NPC TRY TRY
2-dzielny: TRY TRY TRY TRY TRY TRY
planarny: TRY POL NPC TRY TRY TRY