ASD Ćwiczenia 1

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.