Cz1

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

2. Dany jest graf G. Naszkicuj program lgs(G), który zwraca liczbę gwiazd spinających zawartych w G. Oszacuj precyzyjnie jego złożoność, w przypadku gdy G zapisany jest w postaci:
   a) macierzy sąsiedztwa wierzchołków
   b) listy sąsiadów
   c) pęków wyjściowych

3. Podaj za pomocą wzoru liczbę kroków i za pomocą ϴ(*) złożoność obliczeniową następującego funkcji określonej dla liczb naturalnych n:

4. Na płaszczyznę rzucono n prostych. Niech R9n) oznacza największą możliwą liczbę regionów (ograniczonych lub nie) powstałych w ten sposób, np. R(0) = 1, R(1) = 2. Wiadomo, że R(n) = xR(n-1)+yn. Ustal wartość x i y. Oszacuj tempo wzrostu R(n). Podaj wartość R(4).

Cz2

1. Ty masz 100-wierzchołkowy graf hamiltonowski G zapisany w postaci macierzy sąsiedztwa wierzchołków A(G) i bardzo Ci zależy na tym, aby stwierdzić, czy graf zawiera klikę K₁₀ lub większą, gdyż możesz za to uzyskać 25 punktów. Ja mam program, który rozwiązuje problem jak na wejściu poda się macierz sąsiedztwa wierzchołków grafu niehamiltonowskiego. Jak przerobisz macierz A(G), byś mógł skorzystać z mojego programu? Napisz algorytm i oszacuj jego złożoność obliczeniową.

2. Następujący algorytm rozwiązuje optymalizacyjną wersję problemu suma podzbioru w sposób 2-aproksymacyjny, tzn. znajduje podzbiór A’A takie, że k/2 ≤ a_i przy ograniczeniu a_i ≤ k
   (* do sumy -> i:a_i є A’)

a) oszacuj złożoność
b) podaj przykład danych I(tu jest i), dla których F₀(I) ~= 2F_ss*(I)
c) niech SS będzie algorytmem SS*, z którego usunięto instrukcję (*). Pokaż, że nie istnieje stała Ɛ<∞ taka, że SS jest algorytmem Ɛ-aproksymacyjnym

1. Zaprojektuj algorytm wielomianowy dla wyznaczania indeksy chromatycznego danego grafy G, zapisanego w postaci macierzy sąsiedztwa wierzchołków, który jest 4/3-aproksymacyjny. Udowodnij, że dla tego problemu nie istnieje schemat FPTAS, chyba, że P=NP.

2. Udowodnij, że problem pakowania pudełek (dany jest zbiór przedmiotów o znanych wielkościach
   a₁ … a_n oraz rozmiar pudełek l(tu jest el); należy zminimalizować liczbę pudełek koniecznych do zapakowania wszystkich przedmiotów) jest NP-trudny.