pto11

4. Problem maksymalizacji liczby zapamiętanych programów (MLZP) zdefiniowany jest następująco: Dany jest zbiór programów o długościach l_ul₂,...J_neN i 2 dyskietki o pojemności LeN każda. Znaleźć upakowanie jak największej liczby tych programów na dyskietkach. Algorytm Smallest-First (SF), zapisujący te programy od najkrótszego do najdłuższego, najpierw na jednej a potem na drugiej dyskietce, jest 1-absolutnie przybliżony oraz ^-względnie przybliżony. Oszacuj precyzyjnie wartość k.

5. Czy poniższy algorytm może być uznany za dowód, że problem testowania czy liczba A7 jest pierwsza należy do klasy P?

algorytm LiczbaZłożona (n); begin

for /:=2 to [n!2 ! do if n modz-0 then return true return false end;

6. Problem zdefiniowany jest następująco: Dana jest macierz A o rozmiarze 3xn wypełniona liczbami całkowitymi. Pytamy, czy istnieje wektor kolumnowy ^-elementowy X, którego wszystkie wyrazy są

0'

równe ±1, dla którego zachodzi AX=

. Wykaż, że jest to problem NP-zupełny.