skanuj0003n

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) - 56178 (szukana wartość 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 (kO=l) -112345678 -> 23145678->456718 (znaleźliśmy ramy podzbioru czyli między 4 a 7; kontynuujemy metodą bisekcji)-45167 -> 617 - znaleźliśmy szukaną wartość. Metoda ta polega na tym że skaczemy jak pionek po planszy - tablicy; do tego co kolejny skok skaczemy 2 razy dalej; jak widać tworzą się coraz większe przedziały - ponieważ są one uporządkowane rosnącą wystarczy sprawdzić

czy w przedziale nie znajduje się nasza wartość - 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 końca 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^A0, 2^A1, 2^A2,~n po prostu sqrt(n) będzie „połową drogi" zarówno dla bisekcji, jak i dla "podwojonego kroku".

2. Przypuśćmy, że algorytm A ma złożoność pesymistyczną f(n), zaś algorytm B ma złożoność 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)=Q(f(n)logn) TAK

2.2. Czy w najgorszym przypadku danych A jest asymptotycznie szybszy od B, jeśli g(n)=0(f(n)logn) NIE WIADOMO

2.3. Czy w najgorszym przypadku danych A jest asymptotycznie szybszy od B, jeśli g(n)=0 (f(n)logn) TAK

2.4. Czy w najgorszym przypadku danych B jest asymptotycznie szybszy od A, jeśli g(n)=Q{f(n)logn) NIE

2.5. Czy w najgorszym przypadku danych B jest asymptotycznie szybszy od A, jeśli g(n)=0(f(n)logn) NIE WIADOMO

2.6. Czy w najgorszym przypadku danych B jest asymptotycznie szybszy od A, jeśli g(n)= 0 (f(n)logn) NIE

Dla uproszczenia można przyjąć, że f(n)=n to wtedy g(n)=nlogn , wtedy wszystko jest chyba oczywiste (i zgodne z rysunkiem).

5. Niepusty graf G, który ma n wierzchołków. Dla danego k sprawdzić „Czy graf G jest k-barwny?". Odpowiedzieć TRY jeśli 0(1), POL jeśli wielomianowo lub NPC.

	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

Dla k=l wszędzie mamy TRY, ponieważ przy reprezentacji w postaci pęków

3. Udowodnij redukcję 3-SAT alfa4-SAT

Wyrażenie 3-CNF ma postać: 0 = £* C₂* C₃*...* C_n, gdzie każda klauzula C-, wygląda następująco: (x_iX+Xj2+x_i3). Wprowadzamy n nowych zmiennych -^tworząc formułę 0 ' w postaci CNF, zastępując każdą starą klauzulę dwiema nowymi o 4 składnikach, tak że: 0 ' = ( ę+ q_a) * ( C_x+ !q_x) * ( C₂+ q₂) * (C₂+ Iq2) ( C_n+ !q_n) * (C_n+ !q_n). Widać, że jeżeli formuła 0 była spełnialna dla pewnego przypisania wartości logicznych, to dla dowolnych q nie zmieni to ogólnej wartości 0 ' przekształconego z 0 .

Przykład: 0 = (xl+x2+x3)(xl+!x2+!x3) => 0 ' =

(xl+x2+x3+x4)(xl+x2+x3+!x4)(xl+!x2+!x3+x4) (xl+!x2+!x3+!x4) Jak widać, zmienna x4 nie wpływa na spełnialność 0 ', jeżeli 0 było spełnione. Konkluzja: 3SATa4SAT, a to kończy dowód!

6. Ustal złożoność obliczeniową następujących problemów:

6.1.    Dany jest graf spójny G w postaci pęków wyjściowych; Czy G zawiera drzewo spinające T stopnia A(T)=<2?

A<=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 sprawdzić, 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).

wyjściowych wystarczy sprawdzić, czy tablica jest pusta (da się), czy nie (nie da się), a to zajmuje 0(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 K3 to powinien być 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 pokolorować 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-l problem jest TRYwialny we wszystkich 3 przypadkach. Moim

zdaniem dlatego, że w pękach wyjściowych wystarczy sprawdzić długość tablicy (jeśk graf jest petny ta 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 pokolorować tyloma kolorami ile ma wierzchołków.

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ść 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(i1[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ść 0(n^A2).