Ćwiczenia

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.

Zadanie 1

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

Zadanie 2

Udowodnij, że algorytm 2-Pakowanie jest poprawny.

Zadanie 3

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

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?