Algorytmy i struktury danych · Laboratorium 1

Projektowanie poprawnych algorytmów

Celem jest przejście od nieformalnego pomysłu do algorytmu, którego wynik i zakończenie potrafisz uzasadnić. Kod jest ostatnim etapem tego procesu.

1. Specyfikacja

Wybierz problem wyszukiwania najmniejszego elementu niepustej tablicy. Zapisz:

wejście: tablica porównywalnych wartości,
warunek wstępny: tablica zawiera co najmniej jeden element,
wyjście: najmniejsza wartość z tablicy,
warunek końcowy: wynik nie jest większy od żadnego elementu wejścia.

Zadanie 1. Wyjaśnij, dlaczego brak warunku niepustości uniemożliwia poprawne zainicjalizowanie kandydata na minimum.

2. Pseudokod i niezmiennik

minimum(A):
  wynik ← A[0]
  dla i od 1 do długość(A) - 1:
    jeżeli A[i] < wynik:
      wynik ← A[i]
  zwróć wynik

Niezmiennik pętli: przed iteracją o indeksie i zmienna wynik przechowuje minimum fragmentu A[0..i-1].

Zadanie 2. Uzasadnij kolejno inicjalizację, zachowanie niezmiennika i wniosek po zakończeniu pętli. Oddziel argument poprawności wyniku od argumentu zakończenia.

3. Implementacja i testy

Zaimplementuj algorytm w wybranym języku bez używania gotowej funkcji minimum. Przygotuj testy dla tablicy jednoelementowej, wartości powtarzających się, liczb ujemnych oraz minimum na początku i na końcu.

Zadanie 3. Dla każdej klasy testu zapisz oczekiwany wynik przed uruchomieniem programu. Test może wykazać błąd, lecz skończona liczba testów nie dowodzi poprawności dla wszystkich danych.

4. Pomiar

Zmierz czas dla rosnących rozmiarów wejścia, zachowując tę samą metodę generowania danych. W Pythonie użyj modułu timeit, który ogranicza wpływ przypadkowych różnic pojedynczego pomiaru.

python -m timeit -s "from solution import minimum; a=list(range(10000,0,-1))" "minimum(a)"

Zadanie 4. Zestaw co najmniej pięć rozmiarów wejścia. Wyjaśnij, dlaczego wykres czasu wspiera ocenę wydajności, ale sam nie stanowi dowodu złożoności asymptotycznej.

5. Sprawozdanie

Specyfikacja z warunkiem wstępnym i końcowym.
Pseudokod oraz dowód z użyciem niezmiennika.
Implementacja i tabela przypadków testowych.
Tabela pomiarów, wykres i krótka interpretacja.
Opis użycia AI albo informacja, że AI nie użyto.

Przykład opisu AI: „Użyłam modelu GPT-5 do sprawdzenia kompletności argumentu po promptcie: «Wskaż brakujący krok w poniższym dowodzie niezmiennika pętli, bez przepisywania rozwiązania». Sugestię o osobnym uzasadnieniu zakończenia zweryfikowałam względem definicji niezmiennika i samodzielnie poprawiłam dowód.”

Źródła

Anany Levitin, Introduction to the Design and Analysis of Algorithms, Pearson, wyd. 3.
Python: dokumentacja modułu timeit.