ASD Ćwiczenia 1

From Studia Informatyczne

Spis treści

Zadanie 0

Udowodnij, że algorytm 6174 ma własność stopu.

Podobnie udowodnij to dla wersji tego algorytmu z trzema cyframi z liczbą 495 zamiast 6174.

Rozwiązanie

Sprowadź dowód do jak najmniejszej liczby przypadków, np. możesz tylko rozważać liczby o niemalejących ciagach czterech cyfr.

Zadanie 1

Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny.

Rozwiązanie

Dla każdego nowego niezerowego elementu x, który jest aktualnie na pozycji j-tej, jeśli wstawiamy x na pozycję i-tą, to w tym momencie na pozycji (i-1)-szej jest pewien jego poprzednik y w najdłuższym ciągu malejącym kończącym się na pozycji j-tej. To znaczy w szczególności, że y>x, oraz że y jest na pewnej pozycji mniejszej od j.



Zadanie 2

Udowodnij, że algorytm 2-Pakowanie jest poprawny.

Rozwiązanie

W każdym optymalnym pakowaniu można je tak zmienić, że najmniejszy element będzie razem z maksymalnym, z którym się mieści do tego samego pudełka

Zadanie 3

Udowodnij poprawność algorytmu na cykliczną równoważność słów.

Rozwiązanie

Relacja mniejszości dla ciągów niech będzie relacją mniejszości leksykograficznej.

Rotacją ciągu u=u[1..n] jest każdy ciąg postaci u^{(k)}\ =\ u[k+1.. n]u[1.. k]. (W szczególności

u^{(0)}=u^{(n)}=u).

Zdefiniujmy:

D(u)=\{k:1\leq k\leq n oraz u^{(k)}>w^{(j)} dla pewnego j\},
D(w)=\{k:1\leq k\leq n oraz w^{(k)}>u^{(j)} dla pewnego j\}.

Skorzystamy z prostego faktu:

Jeśli D(u)=[1.. n] lub D(w)=[1.. n], to u,w nie są równoważne. Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:

D(w)\supseteq [1.. i]\ oraz \ D(u)\supseteq [1.. j].

Zadanie 4

Operacja dominującą w algorytmie na cykliczną równoważność jest porównanie dwóch elementów tablic u,v (czy są równe, jeśli nie to który jest mniejszy). Liczba porównań jest liniowa. Dla jakich ciągów zadanej dlugości długości n algorytm na cykliczną równoważność wykonuje maksymalną liczbę porównan symboli?

Rozwiązanie

Dla ciągów postaci 1^*201,\ 1^*20 o tej samej długości.