87028 pto12

100

Nazwisko i imię

21.01.2006.

Grupa/rok.

sąsiad lewy

sąsiad prawy

Czas trwania testu: 100 minut Nazwiska proszę pisać CZYTELNIE literami DRUKOWANYMI_

UWAGA: Obok każdego pytania napisz końcowe rozwiązanie. Tok rozumowania prowadzącego do tego rozwiązania załącz _na oddzielnej PODPISANEJ kartce_

20

1. Dany jest zbiór n różnych liczb naturalnych A={a\,...,a„}. Wiadomo, że problem polegający na sprawdzeniu, „czy zbiór ten można rozbić na sumę dwóch rozłącznych zbiorów B i C (tj. BnC=0 i B^jC=A) o równych sumach elementów?” jest NP-zupełny. Czy pozostanie on NP-zupełny, czy też stanie się wielomianowy przy następujących modyfikacjach:

1.    wszystkie liczby a, są podzielne przez 3, (. \

2.    sumy elementów zbiorów B i C nie muszą być równe, lecz mogą się różnić o co najwyżej 3,

3.    sumy te muszą się różnić o więcej niż 3, ^

4.    a? jest podzielne przez 3. ć/ p £

5.    dwa zbiory B i C zastępujemy trzema rozłącznymi B, C i D o równych sumach elementów, w ^

Uwaga do zadań 1 i 2: Najpierw należy rozwiązać test umieszczając odpowiedzi P lub NPC przy punktach 1-5 bez ich uzasadniania. Punktacja za każde z pytań: 3 za odpowiedź poprawną, -2 za błędną, 0 za brak. W przypadku braku odpowiedzi błędnej w całym teście można uzyskać dodatkowych 5 pkt. za dowód poprawności dowolnie wybranej spośród udzielonych odpowiedzi. Uzasadnianie więcej niż jednej odpowiedzi jest niecelowe - nie będą one sprawdzane._

2. Problem plecakowy zdefiniowany jest następująco: dany jest zbiór n przedmiotów A={a_u...,a„) o znanych rozmiarach r(a,) i wartościach v(a,) będących liczbami naturalnymi. Mamy ponadto liczby naturalne R i V. Pytamy, czy w plecaku o rozmiarze R można zmieścić pewien podzbiór przedmiotów z A taki, by jego łączna wartość była nie mniejsza niż V. Wiadomo, że zagadnienie to jest NP-zupełne w przypadku ogólnym. Czy pozostanie on NP-zupełny, czy też stanie się wielomianowy po ograniczeniu się do zestawów danych o poniższych własnościach:

1.    wszystkie rozmiary przedmiotów r(a,) są jednakowe, P 5evf

2.    wszystkie wartości przedmiotów v(a,) są jednakowe, P

3.    wszystkie rozmiary r{al)<l, (U PC

4.    wszystkie wartości v(a,)>7, M p (_

5.    dla każdego przedmiotu jego rozmiar jest równy wartości r(a,)= v(a,). f-J pC_

3. Wykaż, że jeżeli P*NP, to nie może istnieć całkowicie wielomianowy' schemat aproksymacyjny dla problemu kolorowania wierzchołków' grafów przy użyciu jak najmniejszej liczby kolorów.