ASD Ćwiczenia 1: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu - "\ =\" na "=")
 
(Nie pokazano 13 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
==''Zadanie 1'' ==  
+
==''Zadanie 0'' ==  
 +
 
 +
Udowodnij, że algorytm 6174 ma własność stopu.
  
Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny
+
Podobnie udowodnij to dla wersji tego algorytmu z trzema cyframi z liczbą 495 zamiast 6174.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 7: Linia 9:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Dla każdego nowego niezerowego elementu, jeśli wstawiamy go na pozycję i-tą
+
Sprowadź dowód do jak najmniejszej liczby przypadków, np. możesz
to w tym momencie na pozycji (i-1)-szej jest jego poprzednik w najdłuższym ciągu malejącym
+
tylko rozważać liczby o niemalejących ciagach czterech cyfr.
kończącym się na tym elemencie
 
 
  </div>
 
  </div>
 
</div>
 
</div>
  
 +
==''Zadanie 1'' ==
  
 +
Udowodnij, że algorytm Najdłuższy-Malejący jest poprawny.
  
 
==''Zadanie 2'' ==
 
 
Udowodnij, że algorytm Permutacja-Wagowa jest poprawny
 
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
Rozwiązanie
 
Rozwiązanie
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
W każdym momencie na wadze jest w sumie pewien spójny przedział ciągu wejściowego,
+
Dla każdego nowego niezerowego elementu x, który jest aktualnie na pozycji j-tej, jeśli wstawiamy x na pozycję i-tą,
na jednej (lewej lub prawej) szalce są elementy z pozycji parzystych, na drugiej z pozycji nieparzystych.
+
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.
 
  </div>
 
  </div>
 
</div>
 
</div>
 +
  
  
 
   
 
   
  
==''Zadanie 3'' ==  
+
==''Zadanie 2'' ==  
  
Udowodnij, że algorytm Proste-Pakowanie jest poprawny
+
Udowodnij, że algorytm 2-Pakowanie jest poprawny.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 40: Linia 40:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
W każdym optymalnym pakowaniu można je tak zmienić że najmniejszy element będzie razem
+
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
+
z maksymalnym, z którym się mieści do tego samego pudełka
 
  </div>
 
  </div>
 
</div>
 
</div>
  
 +
=='''Zadanie 3''' ==
  
 +
Udowodnij poprawność algorytmu na cykliczną równoważność słów.
  
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
  
==''Zadanie 4'' ==  
+
<div class="mw-collapsible-content" style="display:none">
 +
 
 +
Relacja mniejszości dla ciągów niech będzie relacją mniejszości leksykograficznej.
 +
 
 +
Rotacją ciągu <math>u=u[1..n]</math> jest każdy ciąg postaci <math>u^{(k)}= u[k+1.. n]u[1.. k]</math>. (W szczególności
 +
<math>u^{(0)}=u^{(n)}=u)</math>.
 +
 
 +
Zdefiniujmy:
 +
<center>
 +
<math>D(u)=\{k:1\leq k\leq n</math> oraz <math>u^{(k)}>w^{(j)}</math> dla pewnego <math>j\}</math>,<br>
 +
<math>D(w)=\{k:1\leq k\leq n</math> oraz <math>w^{(k)}>u^{(j)}</math> dla pewnego <math>j\}</math>.
 +
</center>
 +
 
 +
Skorzystamy z prostego faktu:
 +
Jeśli <math>D(u)=[1.. n]</math> lub <math>D(w)=[1.. n]</math>, to <math>u,w</math> nie są równoważne.
 +
Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:
 +
<center>
 +
<math>D(w)\supseteq [1.. i]</math>\ oraz \ <math>D(u)\supseteq [1.. j]</math>.</center>
 +
 
 +
</div>
 +
</div>
  
Przypuśćmy, że mamy wage szalkową i odważniki będące potęgami trójki, dla każdej potęgi
+
=='''Zadanie 4''' ==
dokładnie jeden odważnik. Jak rozmieścić odważniki na wadze aby doładnie zważyć przedmiot o
 
zadanej wadze x.
 
  
 +
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 <math>n</math> algorytm na cykliczną równoważność wykonuje maksymalną liczbę porównan symboli?
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
Rozwiązanie
 
Rozwiązanie
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Dodajemy minimalną liczbę y>=x, której rozwinięciem w systemie trójkowym są same jedynki,
+
Dla ciągów  postaci <math> 1^*201,\ 1^*20 </math> o tej samej długości.
tworzymy liczbę z = x+y, rozwijamy z w systemie trójkowym a potem odejmujemy od każdej
 
cyfry jedynkę. Jeśli mamy -1 to odpowiedni odważnik kładziemy na szalce razem z danym przedmiotem,
 
jeśli +1 to na drugiej szalce, a jeśli zero to ignorujemy.
 
 
  </div>
 
  </div>
 
</div>
 
</div>

Aktualna wersja na dzień 12:52, 9 cze 2020

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

Zadanie 1

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

Rozwiązanie



Zadanie 2

Udowodnij, że algorytm 2-Pakowanie jest poprawny.

Rozwiązanie

Zadanie 3

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

Rozwiązanie

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 algorytm na cykliczną równoważność wykonuje maksymalną liczbę porównan symboli?

Rozwiązanie