Algorytmy i Struktury Danych

6. Algorytmy zachłanne

1. (1p.) Podaj algorytm optymalnego wyboru zajęć oparty na programowa-

niu dynamicznym, obliczający iteracyjnie wartość m

i

dla i = 1, 2, . . . , n,

gdzie m

i

jest rozmiarem największego podzbioru

{1, . . . , i} nie kolidują-

cych zajęć. Przyjmij, że zajęcia są posortowane niemalejąco ze względu na
czas zakończenia. Porównaj czas swego algorytmu z czasem Greedy-Activity-Selector.

2. (1p.) Pokaż, że następujące strategie zachłanne nie są poprawne dla pro-

blemu wyboru zajęć:

(a) wybieranie zadania o najmniejszym czasie trwania spośród zajęć zgod-

nych z dotychczas wybranymi

(b) wybieranie zadania, które koliduje z najmniejszą liczbą innych zadań

pozostałych jeszcze do wybrania

3. (2p.) Mamy dany zbiór zajęć, które mają się odbywać w jak najmniej-

szej liczbie sal. Podaj efektywny algorytm zachłanny wyznaczający przy-
dział zajęć do sal. (Problem równoważny – kolorowanie grafu przedziałów:
wierzchołki – zajęcia, krawędzie – pary kolidujących zajęć; chcemy poko-
lorować wierzchołki tak, aby żadna krawędź nie miała dwóch końców tego
samego koloru.)

4. (1p.) Wykaż, że ciągły problem plecakowy ma własność wyboru zachłan-

nego.

5. (2p.) Podaj rozwiązanie dyskretnego problemu plecakowego, oparte na

programowaniu dynamicznym, działające w czasie O(nW ), gdzie n jest
liczbą przedmiotów, a W maksymalnym dopuszczalnym obciążeniem ple-
caka.

6. (1p.)

Przypuśćmy, że w dyskretnym problemie plecakowym kolejność

przedmiotów posortowanych rosnąco według ciężaru jest taka sama jak
przy uporządkowaniu malejącym według wartości. Podaj efektywny algo-
rytm znadjdujący optymalne rozwiązanie dla tej wersji problemu.

7. (2p.) Dane są odległości między kolejnymi stacjami benzynowymi na pew-

nej trasie. (Można przyjąć, że pierwsza stacja jest na początku trasy a
ostatnia na końcu.) Pełen bak pozwala na przejechanie n km. Podaj
algorytm wyznaczający najmniej liczny zbiór stacji, na których musimy
tankować, aby przejechać całą trasę. Udowodnij poprawność rozwiązania.

8. (1p.) Zaprojektuj algorytm, który dla danego zbioru punktów na prostej

{x

1

, . . . , x

n

} wyznacza najmniej liczny zbiór przedziałow domkniętych o

długości jednostkowej, przykrywających wszystkie dane punkty. Uzasad-
nij poprawność swego algorytmu.

1

9. (1p.) Jaki jest optymalny kod Huffmana dla następującego zbioru częstości

wystąpień liter?

a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21

Uogólnij swoją odpowiedź na przypadek, gdy częstości stanowią n począt-
kowych liczb Fibonacciego.

10. (2p.) Udowodnij, że koszt drzewa kodu prefiksowego można obliczyć jako

sumę po wszystkich węzłach wewnętrznych (nie liściach), sum częstości
wystąpień ich potomków.

11. (2p.) Niech C = {0, . . . , n − 1} będzie zbiorem znaków. Udowodnij, że

każdy optymalny kod prefiksowy dla C można przedstawić przy pomocy
ciągu 2n − 1 + n⌈lg n⌉ bitów. (Wskazówka: Użyj 2n − 1 bitów do repre-
zentacji drzewa.)

12. (1p.) Uogólnij algorytm Huffmana do kodów trójkowych (tzn. kodów

używających symboli 0, 1, i 2) i udowodnij, że generuje on optymalne
kody trójkowe.

13. (2p.) Wykaż, że (S, N

k

) jest matroidem, gdzie S jest skończonym zbiorem,

a

N

k

jest podzbiorem wszystkich podzbiorów S o rozmiarze nie większym

niż k.

14. (2p.) Dla danej macierzy T o wartościach rzeczywistych i wymiarze n

× n

wykaż, że (S, N ) jest matroidem, gdzie S jest zbiorem kolumn macierzy
T

, i A

∈ N wtedy i tylko wtedy, gdy kolumny A są liniowo niezależne.

15. (2p.) Wykaż, że jeśli (S, N ) jest matroidem, to matroidem jest także

(S, N

′

), gdzie N

′

= {A

′

: S − A

′

zawiera pewien maksymalny A

∈ N }. Z

definicji tej wynika, że maksymalne niezależne podzbiory matroidu (S, N

′

)

są dopełnieniami maksymalnych niezależnych podzbiorów matroidu (S, N ).

16. (2p.) Niech S będzie skończonym zbiorem, a S

1

, . . . , S

k

– podziałem S na

rozłączne podzbiory. Niech

N = {A : |A∩S

i

| ≤ 1 dla każdego i = 1, . . . , k}.

Wykaż, że (S, N ) jest matroidem.

17. (2p.) Jak w algorytmie szeregowania zadań stwierdzić w czasie O(|A|) czy

zbiór zadań A jest niezależny? (Skorzystaj z własności: A jest niezależny
wtedy i tylko wtedy gdy dla t = 1, . . . , n, N

t

(A) ≤ t.)

2