CZĘŚĆ 1 - Złożoność

1. Co robi i ile zużywa czasu następująca procedura „zagadka”.

Wskazówka: rozwiąż odpowiednie równanie rekurencyjne.

procedure zagadka(tab: array [1..n] of integer, n: integer);

begin

x:= -∞; {*co najmniej liczba typu integer*}

for i:= 1 to n do

for j:= i to n do

for k:= i to j do x:= max (x, tab [k]);

pos:= pozycja_elementu_w_tab;

tab [pas] :=: tab [n] {*zamiana miejscami*}

zagadka (tab, n-1)

end;

Odp.: Procedura sortuje rosnąco.
Liczba kroków:
3*pętla for ------------ n³
pos:=pozycja x ------- O(n)
zagadka(tab, n-1) --- 1 krok w tył
T(n) = 1, dla n=1;
T(n) = T(n-1) +n³+ n + c, dla n>1 //n rośnie wolniej od n³, c to jakaś drobna wartość, obie można zignorować
Otrzymujemy T(n) = T(n-1) +n³, podstawiamy do wzoru T = aT(n-1) + d(n)
Nasze wartości: a=1,
=1, d(n)=n³, d(n)=ω(aⁿ)
T(n) = O(n*d(n)) = O(n*n³) = O(n⁴)

2. Spójny graf planarny G zapisano w postaci macierzy sąsiedztwa wierzchołków. Naszkicuj algorytm
1-absolutnie aproksymacyjny dla znajdowania rozmiaru maksymalnej kliki w G i oszacuj jego złożoność obliczeniową.

Odp.: Maksymalna klika w grafie planarnym może mieć najwyżej 4 wierzchołki (innymi słowy nie da się narysować planarnej kliki, która miałaby 5 lub więcej wierzchołków).
Algorytm:

Kod:

begin
    if n=1 then return 1
    else return 3 //pozostałe możliwości to 2 lub 4, więc algorytm pomyli się najwyżej o 1
end

3. Dla małych rozmiarów danych algorytmy o dużej złożoności asymptotycznej są zwykle szybsze od algorytmów o mniejszej złożoności. Biorąc to pod uwagę programista napisał następujący algorytm hybrydowy do obliczania wartości n-tej liczby Fibonacciego.

procedure hybryda (n: integer) : integer;

begin

if n < 10 then

begin

if n ≤ 2 then return 1

else return (hybryda (n-1) + hybryda (n-2))

end;

A[1]:=A[2]:=1;

for i:=3 to n do A[i]:=A[i-1] + A[i-2];

return A[n]

end.

Oszacuj asymptotycznie liczbę kroków wykonywanych przez ten algorytm jako funkcję wartości n. Czy jest ona tożsama z funkcją złożoności obliczeniowej? Jeśli nie, to podaj, czy złożoność obliczeniowa hybrydy jest: wielomianowa, super wielomianowa, wykładnicza, super wykładnicza.

Odp.: T(n) = 1, dla n=1,2;
T(n) = T(n-1)+T(n-2), dla n
{3,...,9};
T(n) = n, dla n>9 (tylko ten przypadek jest istotny)
Liczba kroków T(n) = O(n)
Złożoność Obliczeniowa = O(2^s, gdzie s - rozmiar problemu
Złożoność Obliczeniowa jest wykładnicza.

4. Ułóż odpowiednie równanie rekurencyjne, a następnie za pomocą symbolu θ(∙) oszacuj asymptotyczną liczbę kroków wykonywaną przez poniższą funkcję F(n). Podkreśl słowo, które najlepiej charakteryzuje jej klasę złożoności obliczeniowej; subliniowa, liniowa, wielomianowa, superwielomianowa, wykładnicza, superwykladnicza.

function f(n:integer):real;

begin

x:=1;

if n > 1 then

for i:= 1 to 2 do

k:=1;

while n > 0 do

begin

n:= n-2*k-1;

k:=k+1;

end;

return x;

end.

Odp.: T(n) = aT(n/b) + d(n)
a - ilość wykonań pętli for, a=2
b = 4
d(n) - ilość wykonań pętli while,
przykład dla n=16:
n=16, n=13, n=8, n=1
d(n) =

a = d(b)
T(n) = 2T(n/4) +

T(n) =

T(n) =
=

CZĘŚĆ 2 - Redukcje

1. Problem MEC(G,k) (Maximum Edge Coloring) zdefiniowany jest następująco. Dane są:

graf G i liczba naturalna k; znajdź podgraf G'
G zawierający największą możliwą liczbę krawędzi, który jest k- barwny krawędziowo. Podaj rozwiązanie problemu MEC(C7,2).

Pokaż, że MEC(G,k) jest NP.-trudny.

Wskazówka: Zacznij od zdefiniowania wersji decyzyjnej MEC(G,k,p).

Odp.: Ciekawostka: profesor przekreślił wszelkie wskazówki, stwierdzając, że one tylko utrudniają znalezienie rozwiązania.

1. Istnieje rozwiązanie dla MEC(C7, 2). Przykład:

_

/ \

| |

\

Algorytm jest NP-trudny, ponieważ można go zredukować do problemu ścieżki Hamiltona, który jest NP-trudny.

2. Problem maxTSP zdefiniowany jest następująco: Dana jest macierz nieujemnych odległości M i próg p; czy istnieje cykl Hamiltona o długości ≥ p? Udowodnij, że problem maxTSP również pozostanie NP.-zupelny.

Wskazówka: Zacznij od pomnożenia wszystkich liczb przez -1.

Odp.: Maksymalny próg = ilość wierzchołków.

Zdaniem profesora ustalenie tego progu jest jednoznaczne udzieleniu dowodu. Nie mam pojęcia dlaczego, ktoś to rozumie?

3. Udowodnij, że problem KLIKI jest NP-zupełny nawet wówczas, gdy graf G jest spójny i niehamiltonowski.

Odp.: Aby z grafu hamiltonowskiego uzyskać graf niehamiltonowski , wystarczy dodać do niego nowy wierzchołek i połączyć krawędzią z dowolnym innym wierzchołkiem w tym grafie. To podobno też jest samo w sobie dowodem. Ponownie nie wiem, dlaczego.

4. Mamy 5 problemów z klasy NP, miedzy którymi istnieje relacja α jak na rysunku. Przyjmując, że P≠NP do każdego z nich przypisz dowolny, ale konkretny problem decyzyjny, zapisując go w postaci:

1. Name………………………...Name In Outsz dowolny, ale konkretny problem decyzyjny, zapisujac uper wykładnicza.. Czy jest ona tożsama z funkcją złoIn……………………………..Out……………………………..

2. Name………………………In……………………………..Out……………………………..

3. Name………………………In……………………………..Out……………………………..

4. Name………………………In……………………………..Out……………………………..

5. Name………………………In……………………………..Out……………………………..

Odp.: W punkcie 1 i 2 umieszczamy dowolne problemy NPC, w 3-im problem NPI, w 4-tym P, a w 5-tym problem jest trywialny. Przykład dla

3. NAME: Izomorfizm grafów, IN: grafy G1 i G2 OUT: Czy G1 jest izomorficzny z G2?

5

4

3

2

1

---