PTO cz 1

To taki zbiór wolnych myśli, ja, stosując właściwie tylko je zdałem PTO i to z rezerwą, może komuś pomoże

1. Warto znać i czuć wzorek na oszacowanie złożoności piszą tak, jeśli d(b) jest funkcją iloczynową to dla funkcji w postaci :

zachodzą oszacowania

iloczynowa =
dla pewnego k >0

a co jak nie jest iloczynowa?

Np.:

F(n)=2F(n/3)+5*n^2

To tak:

G(n)=0,2*F(n) => G(n)=2G(n,3)+n^2 szacujemy G(n) wiemy, że F(n)=
(G(n))

I mamy oszacowanie na F(x)

F(n)=2F(n/3)+n^2+3*n

G(n)=2F(n/3)+n^2

H(n)=2F(n/3)+2*n/2 ;

H(n)>F(n)>G(n)

Z poprzedniego punktu mamy H(n)=
(G(n))

To F(n)=
(G(n))

G(n) umiemy oszacować

Za te liczby możemy podstawić sobie cokolwiek

Jeszcze ostatni przykład ale tu ostrożnie stosowalność silnie ograniczona!!!!!!

F(n)=10F(n/2)+3*(log^5 n)*n^2+n^2+logn

G(n)=10F(n/2)+100*(log^5 n)*n^2

H(n)=10F(n/2)+(log^5 n)*n^2

H(n)=
(G(n))

H(n)<F(n)<G(n)

Było kiedyś powiedziane tak (log^1000 n)=(n^0,0000001)

I(n)=10F(n/2)+n^2

J(n)=10F(n/2)+n^2,0000000(tu tyle zer ile się chce)1

Jeśli I(n)=
(J(n)) to jesteśmy w domu bo F(n)=
(J(n))

Nie będą jeśli d(b)=a gdzie d(b) to ta część wielomianowa (w przykładzie n^2) wtedy jest zonk ale to chyba mimo wszystko lepiej niż na początku

2. Warto zdać sobie sprawę że te wszystkie
,O itp. To dopiero w nieskończoności

tak więc jak mamy

function A(n)

{

if(n<10000)

{for i=1 to n^n ;

return 3};

else

return(A(n/2))

};

to ma złożoność log n T(n)=T(n/2)+1 (jak w czasie stałym to na końcu trzeba pisać 1)

jak się napisze 2 to już oszacowania nie wyjdą bo funkcja f(n)=2 nie jest iloczynowa

pomimo że dla n=50 to to na żadnym kompie nie pójdzie w rozsądnym czasie (tj do skończenia świata)

3. co to złożoność obliczeniowa, czasowa, asymptotyczne tempo wzrostu funkcji

zagadka (n)

{if (n=1)

return(1)

else

return(3*zagadka(n/2))}

złożoność czasowa liczymy ile czasu będzie się wykonywać, więc by policzyć zagadka(n) funkcja musi obliczyć raz wartość dla n/2 i wykonać pewne obliczenia w czasie stałym (sprawdzić IF pomnożyć przez 3 itp.)

więc

T(n)=T(n/2)+1 więc T(n)=
(log(n)) (patrz oszacowania)

Złożoność obliczeniową liczymy wprost z czasowej podstawiając za n 2^N

T(N)=
(log(2^N))=
(N)

Asymptotyczne tempo wzrostu funkcji, to jak zmieniają się wartości zagadka(n) w zależności od n, u nas

Z(n)=3*Z(n/2)+1 więc z oszacowań Z=

UWAGA!!!

zagadka (n)

{if (n=1)

return(1)

else

return(zagadka(n/2)+zagadka(n/2)+zagadka(n/2))}

i

zagadka (n)

{if (n=1)

return(1)

else

return(3zagadka(n/2))}

mają różną złożoność czasową/obliczeniową pierwsza liczy wyrażenie zagadka(n/2) trzy razy a druga raz złożonośc czasowa drugiej to log n ;

jeśli chodzi o złożoność pamięciową to zawsze liczy się wysokość drzewa rekursji a ta dla funkcji F(n)=aF(n/b)+d(n) jest zawsze logarytmiczna (gdy b>1 rzecz jasna), ale inaczej to wzór rekurencyjny robi się nieskończony, więc niealgorytmiczny .

4. Sufity, podłogi i inne takie

to jest dość niewygodne badziewie ale pozbyć można się tego tak, że najpierw sprawdzamy czy funkcja jest monotoniczna zwykle wystarczy napisać „monotoniczność tej funkcji jest oczywista” (dla funk . typu F(n)=aF(n/b)+d(n) jest to zawsze prawda gdy d(n) monotoniczna (oczywiście dla n>0))

następnie znaleźć taką postać n że sufity i podłogi znikają np.

to będzie n=3^k gdzie k naturalne

liczymy więc złożoność dla

jak wychodzi nam wielomianowa to piszemy

dla każdego n istnieje k takie że

F(3^k)<F(n)<F(3^(k+1))

F(3^k)<F(n)<F(3*3^k) jak nam wyszła złożoność wielomianowa (n^w)to możemy napisać

F(3^k)<F(n)<3^w *F(3^k)

Ponieważ 3^w jest stałą niezależną od doboru n więc oszacowanie jest prawdziwe dla każdego n nie będzie działać ta metoda gdy dla n w szczególnej postaci wyjdzie złożoność wykładnicza (a przynajmniej niekoniecznie będzie działać)no cóż wtedy właściwie robi się kłopot ale nie sądzę by coś takiego się pojawiło (jeden przykład tego jest w skrypcie str.17, ale uogólnić tego nie potrafię, a przepisywać nie chcę)

No to teraz parę przykładów z egzaminu Janczewskiego

A(m,n)

{if((n=0)or(m=0)) A=0 ;

else

{i=0;j=0;

while (2*i<n)i++ ;

while(2*j<m)j++ ;

A(i-1,j-1)};}

Podaj pesymistyczną/optymistyczną złożoność obliczeniową/pamięciową podanej procedury

W zależności od rozmiaru danych wejściowych r

No więc po pierwsze

W każdym wywołaniu pętle wykonuje się ½(n+m) razy a wysokość drzewa rekursji jest min{m,n} więc złożoność wynosi min{m^2,n^2} jak np. m=1 to bez względu na n funkcja wykonuje się w czasie stałym więc optymistyczna złożoność obliczeniowa jest TETA(1)

Lecz pesymistyczna (gdy n=m to r=log n) wynosi

Pamięciowa zaś to optymistycznie TETA(r) (gdy jedno wywołanie bez rekursji)

Zaś pesymistycznie r2^r

Słowo wyjaśnienia czemu to r , jak daną wejściową jest jedna liczba (albo stała liczba liczb) to nie taktujemy jej jako zapisanej w jednej komórce pamięci tylko rozważamy ile ma bitów

A teraz coś lepszego

B(n,m)

{for k=1 to n do

for l=1 to m do

{i=m/n; j=m mod n;

while(i*j>0)

{i--;j--;}

};

podanie złożoności pamięciowej jest banalne, nie ma rekursji, więc TETA(r)

zarówno optymistyczna jak i pesymistyczna,

podanie optymistycznej złożoności obliczeniowej też nie jest trudne jak m jest wielokrotnością n, lub m<n to i*j=0 więc złożoność determinują te dwa for-y czyli TETA(m*n) a względem rozmiaru danych wejściowych to jest to TETA((2^r)*(2^r))=TETA(4^r)

z pesymistyczną nieco trudniej, ale pętla while nie wykona się więcej niż n razy (j<=n)

to wtedy mamy O(n*n*m) =O(8^r) teraz wypadałoby udowodnić że to jest TETA

niech m=n^2-1

to i=n-1 j=n-1 to pętla wykona się TETA(n*n*m)=teta(2^r*2^r*2^r)=TETA(8^r)

to jest ogólna metoda ograniczyć z góry a potem znaleźć jeden przypadek który wykonuje się dokładnie w tym czasie

i trzeci przykład

C(n)

{if(n=0)

C:=0;

Else

{i=n/4;j=n/2;

C=C(i)+C(j) ;};

No więc tu jest rekurencja więc wypadałoby zapisać równanie

T(n)=T(n/2)+T(n/4)+1 funkcja monotoniczna, co chyba widać

Tu jest trudniej ale rozpiszmy kilka wyrazów

T(n)=T(n/4)+T(n/8)+T(n/4)+2

T(n)=2T(n/4)+T(n/8)+2

T(n)=2T(n/8)+2T(n/16)+T(n/8)+4

T(n)=3T(n/8)+2T(n/16)+4

T(n)=3T(n/16)+3T(n/32)+2T(n/16)+7

T(n)=5T(n/16)+3T(n/32)+7

Widać tu już ciąg fibonacciego

1,1,2,3,5 (od prawej do lewej wpółczynniki w równaniu)

Suma jegi elem to

1,2,4,7,11 (wyrazy wolne)

Teraz kongo po log2 n kroków dojdziemy do jedynki wtedy współczynnik przy T będzie Fib(log2 n) (gdzie Fib(i) ita liczba fibonnaciego)

T(n)=
wiem że hardcore ale jak ktoś zrozumie to na prawde równania rekurencyjne to się pikuś zrobi, ogólnie warto stosować metodę rozwijania równań

NP. i cały ten stuff

Problem decyzyjny (czyli z odpowiedzią TAK/NIE) należy do NP. gdy istnieje niedeterministyczny algorytm, który go rozwiązuje w czasie wielomianowym, po ludzku

i bardziej przystępnie, gdy jesteśmy w stanie sprawdzić w czasie wielomianowym poprawność wygenerowanego rozwiązania np.

CYKL HAMILTONA

Mamy wektor VEC[1..n] zweryfikować czy jest to cykl hamiltona

1. Najpierw czy nie powtarzają się wierzchołki

For i=1 to n-1

For j=i+1 to n

if(VEC[i]=VEC[j])

return 0;

2. teraz czy w macierzy sąsiedztwa są odpowiednie krawędzie

For i=1 to n-1

if(A[VEC[i],VEC[i+1]]=0)

return 0 ;

if(A[VEC[n],VEC[1]]=0)

return 0;

return 1 ;

KLIKA (podobnie tyle że w drugim kroku będzie podwójny for)-sprawdzenie czy i-ty wierzchołek łączy się z każdym j-ty jeśli i!=j

ZBIÓR NIEZALEŻNY tak jak w klice tylko sprawdzenie czy się łączy

Formułowanie problemów decyzyjnych

Pierwsze słowo CZY tak ma być jak nie jest to znaczy że się coś źle myśli

NP. problem optymalnego pokolorowania grafu

CZY można pokolorować wierzchołki grafu G co najwyżej k kolorami tak by żadne dwa wierzchołki z wspólną krawędzią nie miały tego samego koloru?

RELACJA 

problem A jest w relacji a z B gdy istnieje funkcja F taka że:

1. Dziedziną F są instancje problemu A, a przeciw dziedziną (zbiorem wartości) instancje problemu B

2. wartość F(X) da się dla każdego X obliczyć w czasie wielomianowym

3. jak A(X)=1 B(F(X))=1 (nie zmienia odpowiedzi)

ważny jest kierunek np. CZY LICZBA PIERWSZA  CYKL HAMILTONA

ale w drugą stronę nie chyba że P=NP.

więc mamy :

1. NPC -NP.-zupełne takie że dla każdego A należącego do NP jest AB

2. co NP. - problemy sformułowane jako zaprzeczenia problemów NP póki co wygląda na to co-NP.!=NP. a ich częścią wspólną jest P(to wiadomo)

To tyle teorii teraz jak chcemy wykazać NPC to :

1. wykazujemy NP.

2. transformujemy ten problem do jakiegoś NPC

np. dany jest graf G i liczba l

CZY ISTNIEJE 3 KOLOROWALNY PODGRAF POSIADAJĄCY CO NAJMNIEJ l

KRAWĘDZI

(to zadanie Janczewskiego)

Udowodnij jego NP- zupełność

1. problem jest w NP. bo w czasie wielomianowym można wybrać l krawędzi i przylegające wierzchołki pokolorować losowo k kolorami a następnie sprawdzić, czy na końcach którejś z l krawędzi są dwa wierzchołki o tym samym kolorze

2. sprowadzę klasyczny problem CZY GRAF G' JEST 3 KOLOROWALNY do zadanego (nie na odwrót, łatwo się pomylić!!!) robimy G=G' l=m gdzie m to liczba krawędzi w grafie G' i koniec

3. BANAŁ JAK WIDAĆ

Zadanie pierwsze z drugiego koła

CZY PROBLEM PODZIAŁU ZBIORU POZOSTAJE NPC GDY:

ai<=3 NIE staje się wielomianowy, a algorytm jest taki :

1. sortujemy

2. wrzucamy 3 po równo do każdego z dwóch podzbiorów jak się nie da (bo liczba 3-ek nieparzysta) to dopychamy jedną 2 i jedną 1 lub trzema 1-kami jak się nie da odpowiedź NIE

3. wrzucamy 2-ki po równo (jak się nie da dopychamy dwoma 1-kami) jak się też nie da odpowiedź NIE

4. po równo 1-ki jak się nie da NIE

5. TAK

3|n NPC bo sprowadzę normalny podział zbioru, jak liczba elem jest 3n+1 to dopychamy dwie wartości równe sumie dotychczasowych elem (one razem mają więcej niż wszystkie więc trafią po jednej do każdego podzbioru a reszta będzie musiała się podzielić po równo, a liczba elam będzie 3n+3 czyli podzielna) jak liczba elem jest 3n+2 to dodajemy 4 elementy takie jak poprzednio (uzasadnienie jak wcześniej)

3|ai NPC bo sprowadzę normalny podział zbioru do tego problemu

1. Każdy element mnożę przez 3

ai=i WIELOMIANOWY (P) algorytm:

1. sprawdzam czy suma jest parzysta jak NIE to odpowiedź NIE

2. jak liczba elementów jest parzysta (n) to robimy tak elem 1 i n do zb. A elem 2 i n-1 do zb. B elem 3 i n-2 itd.

3. jak nieparzysta to tak samo tyle że element środkowy trafia do tego zbioru do którego wcześniej trafił element o połowę mniejszy a ten jest wyjmowany i trafia do przeciwnego podzbioru

ai=2i problem TRYWIALNY (tu zawsze NIE) bo

TABELKA

	STOP	COVER	MM	COLOR
STOP (nieroztrz)	T	N	N	N
COVER (NPC)	T	T	?	N
MM (P)	T	T	T	N
COLOR (T)	T	T	T	T

bo: STOP jako nieroztrzygalny nie może być sprowadzony do roztrzygalnego (bo by roztrzygnął STOP)

każdy można sprowadzić do STOP (jak TAK to zakończ jak NIE to pętla nieskończona)

każdy jest w relacji sam ze sobą (bo funkcja „identyczność” jest oczywiście P)

COLOR jest trywialny więc jest w relacji z każdym nie trywialnym (bo wystarczy znaleźć w nie trywialnym taką instancje, która odpowiada tak jak COLOR(on jako Trywialny zawsze mówi to samo) i zawsze na nią przekształcać

MM jest z COVER na pewno bo COVER jest NPC więc z def. NPC każdy Pjest w rel. Z COVER natomiast

COVER jest w relacji z MMgdy P=NP

---