Zadanie z1.1 (2 punkty)
W pliku czas.py znajdują się definicje pięciu funkcji: f1, f2, ... , f5 oraz pomiar sprawdzający, czy rzeczywisty czas działania funkcji f1(n) (wyliczony w zmiennej Tn) dla różnych wartości n (równych 2000, 4000, 8000, 16000, 32000) zmienia się zgodnie z przebiegiem funkcji liniowej (Fn = n). Otrzymane wyniki interpretujemy następująco: funkcja Fn dobrze opisuje prawdziwy czas Tn funkcji f1, jeżeli ilorazy Fn/Tn są mniej więcej takie same dla wszystkich wartości n.
Wykonać podobne pomiary dla pozostałych funkcji, dobierając odpowiednie funkcje Fn. Aby dobrać odpowiednią funkcję Fn trzeba przeanalizować kod; np. jeżeli mamy 4 zagnieżdżone pętle, każda długości n, to można się spodziewać, że czas ich działania będzie się zmieniał jak funkcja n4.
Jako rozwiązanie przesłać kod programu wykonującego pomiary z dołączonymi wynikami wygenerowanymi przez ten program dla wszyskich pięciu funkcji. Wyniki te można dołączyć np. jako komentarz na końcu kodu programu.
Zadanie z1.2 (2 punkty)
Zaimplementuj dwie różne funkcje, które dla ustalonej zero-jedynkowej macierzy kwadratowej M rozmiaru n×n wyznaczają rozmiar jej największej podmacierzy zawierającej same jedynki (interpretując to graficznie – pole największego prostokątąta złożonego z samych jedynek). Oszacuj złożoność czasową zaimplementowanych funkcji, a następnie w oparciu o eksperymentalny pomiar czasu działania z zadania z1.1 przetestuj doświadczalnie zaproponowane oszacowania, np. dla n = 10, 100, 1000. Przykładowy pseudokod rozwiązujący to zadanie:
max=0 for x1=1 to n: for y1=1 to n: for x2=n downto x1 for y2=n downto y1 local_max=0 for x=x1 to x2 for y=y1 to y2 local_max+=M[x][y] if local_max==(x2-x1+1)*(y2-y1+1) and local_max>max max=local_max
Podobnie jak w poprzenim zadaniu, jako rozwiązanie należy przesłać kod programu wykonującego pomiary z dołączonymi wynikami wygenerowanymi przez ten program.
2. (28.02.2023) Heapsort Termin: 7.03.2023, godz 12.00 Zadania Sprawdzian za tydzieÅ„ (7.03) 3. (7.03.2023) Quicksort Termin: 21.03.2023, godz 12.00 Zadania Ważne: należy wybrać tylko jedno zadanie spoÅ›ród z3.2, z3.3, z3.4, z3.5. Sprawdzian za tydzieÅ„ (14.03) 3.1 (14.03.2023) Quicksort - kontynuacja 4. (21.03.2023) Listy dowiÄ…zaniowe Termin: 4.04.2023, godz 12.00 Zadania Ważne: należy wybrać tylko jedno zadanie spoÅ›ród z4.1, z4.2 4.1 (28.03.2023) Listy - kontynuacja 5. (4.04.2023) Haszowanie - metoda Å‚aÅ„cuchowa Termin: 18.04.2023, godz 12.00 Zadania 6. (18.04.2023) Haszowanie - adresowanie otwarte Termin: 9.05.2023, godz 12.00 Zadania Sprawdzian za tydzieñ (25.04)