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