87028 pto12
100
Nazwisko i imię
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={au...,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.
Wyszukiwarka
Podobne podstrony:
pto kolo1 1 05 tołPA- 100 Nazwisko i imię03.12.2005. Grupa/rok. sąsiad lewy sąsiad prawy Czas trwani
10099 strona1 (10) 100 Nazwisko i imię 21.01.2005. Grupa/rok. Czas trwania testu: 120 minut sąsiad l
KIFv69 Imię i nazwisko (proszę drukować): Astronomiczne Podstawy Geografii — egzamin - 28.01.2006- g
pto1 100 Nazwisko i imię 04.12.2004 Grupa/rok. sgsiad prawy sąsiad lewy Czas trwania testu: 90
3 (1035) Egzamin ISO termin zerowy dnia 27.01.2006 r.Grupa Cdr Piotr Wąsiewicz 1.
100#53 Egzamin z Mechaniki Konstrukcji sem. II sesia -1 termin Czas trwania egzaminu 120 minut 17.06
zap test 1 luty 08 imię i nazwisko nr grupy: ......... ZAP - egzamin, część testowa Czas rozwiązywan
img046 2 Egzamin z matematyki, dn.............................czas trwania egzaminu: 120 minut Imię
img047 Egzamin z matematyki, cln czas trwania egzaminu: 120 minut Imię i nazwisko ni albumu Imię i-n
A tif KOLOKWIUM Z RACHUNKU PRAWDOPODOBIEŃSTWA UW WZI ROK 19 maja 2003 roku, czas trwania 14 h IMIĘ I
BYT e) 01 2006 1 /[Amę Nazwisko Nr indeksu Grupa
Fizjologia układ nerwowy giełdy zostanie IMIĘ I NAZWISKO. WYDZIAŁ: lti^LYsit4 GRUPA: [DATA:1T.
więcej podobnych podstron