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).

Wyszukiwarka

Podobne podstrony:
36433 skanuj0105 (17) 108 JOANNA PRZYBYŚ Współcześni turyści poszukują nowości przez powrót do trady
skanuj0037 3 - Bardzo podejrzane sq fundusze na zbudowanie tej psiej budki
Natomiast przykład d) to kolejny opis, który ma formę potoku składniowego, a więc jest to jedno bard
P1510725 waty, będący wynikiem bardzo długiego tułowia. Uszy, zarówno pod dem wielkości, jak i kszta
skanuj0022 6 krowa .........Ucho słonia Posłuchaj uważnie czytanych słów. Słowa te są do siebie bard
grv 004 b bardzo długie zawiesia 1 orawiłator kierunek ruchu 1 [. - . olei miedziany
79017 skanuj0143 Bardzo lubię mieć pieniądze i bardzo lubię ich nie mieć. Dla mnie wydawanie pienięd
SŁUŻBA w CODZIENNOŚCI opowiadanie Pewien ksiądz mówił bardzo długie kazania, a potem sapał jak kroko
cXolakcja szalików Do wyboru, do koloru 44 - szale bardzo długie, czyli obecnie modne. 1 bardzo
CCF20090318001 (2) OZNAKI MOBBINGU WEWNĄTRZ KLASY 28 Oznaki mobbingu bywają bardzo różne. Bez uporz
23025 skanuj0034 Bardzo rnnic cieszy, kiedy moja praca staje się niepotrzebna! Po co miałabym pragną

więcej podobnych podstron