Lista 1
Zadanie 1
Inspirując się funkcją ``maksimum`` z wykładu, zaimplementuj 4 wersje funkcji do szukania minimalnego elementu na liście wykorzystując pętle.
Badamy wpływ długości listy oraz rodzaju elementów na liście na szybkość działania czterech zaimplementowanych algorytmów.
- Wylicz i narysuj jak czas działania algorytmów zależy od długości listy dla list liczb.
- Wylicz i narysuj jak czas działania algorytmów zależy od długości listy dla list napisów długości 1.
- Wylicz i narysuj jak czas działania algorytmów zależy od długości listy dla list napisów długości 32.
- Wylicz i narysuj jak czas działania algorytmów zależy od długości listy dla list napisów długości 1024.
- Wylicz i narysuj jak czas działania algorytmów zależy od długości napisu dla list długości 1000.
Czy wśród przeanalizowanych algorytmów istnieje jednoznacznie najlepszy? Jeśli tak, odpowiedź uzasadnij. Jeśli nie, spróbuj opisać w jakich sytuacjach i dlaczego niektóre algorytmy są lepsza a innym razem gorsze.
Zadanie 2
Mierzymy czas szukania miejsca zerowego dla funkcji $f(x) = \arctan(x)-1$. Stosujemy metodę bisekcji na przedziałach
$$P_n = \left(0, 10n\right),$$
dla $n$ postaci od $1$ do $100$. Możesz wykorzystać kod z wykładu jako implementację metody bisekcji lub zaimplementować ją samodzielnie.
Zmierz czas wykonania algorytmu bisekcji dla wszystkich przedziałów $P_n$ i narysuj go na wykresie. Porównaj kształt wykresu z teoretycznymi wyliczeniami z wykładu.
Zadanie 3
Załóżmy, że dysponujemy tablicą dwuwymiarową $A$ rozmiaru $n \times m$. Zdefiniujmy sąsiedztwo o promieniu $r \in \mathbb{N}$ elementu $a_{i,j}$ tej tablicy, jako zbiór wszystkich elementów tablicy $a_{x,y}$ takich, że $|x-i| \leq r$ oraz $|y-j| \leq r$.
Na przykład dla tablicy $$A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 5 & 6 \\ 2 & 2 & 3 & 4 \end{bmatrix}$$ wymiaru $3 \times 4$, określone są elementy $a_{i,j}$ dla $i \in \{0, 1, 2\}$ oraz $j \in \{0, 1, 2, 3\}$. Element $a_{1,2}=5$ jest jednocześnie swoim sąsiedztwem o promieniu $0$ $$A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & \fbox{5} & 6 \\ 2 & 2 & 3 & 4 \end{bmatrix}.$$ Sąsiedztwo o promieniu $1$ tego elementu to łącznie $9$ elementów - on sam oraz $8$ elementów wokół niego $$A = \begin{bmatrix} 1 & \fbox{2} & \fbox{3} & \fbox{4} \\ 5 & \fbox{6} & \fbox{5} & \fbox{6} \\ 2 & \fbox{2} & \fbox{3} & \fbox{4} \end{bmatrix}.$$ Sąsiedztwo o promieniu $2$ miałoby więcej elementów - o dwie kolumny lub wiersze w każdą stronę od ustalonego elementu. W przypadku elementu $a_{1,2}$, wszystkie elementy tablicy $A$ są w jego sąsiedztwie o promieniu $2$.
Element nazywamy maksimum lokalnym, jeśli jest największym w pewnym otoczeniu. Dla tablic dwuwymiarowych możemy powiedzieć, że element $a_{i,j}$ jest maksimum lokalnym, jeśli jest największy (w słabym sensie, czyli $\geq$) od wszystkich elementów ze swojego sąsiedztwa o promieniu $r=1$.
Tablicę będziemy nazywać jednomodalną, jeśli ma tylko jedno maksimum lokalne.
Napisz funkcję sąsiedztwo(A, r, i, j), która dla zadanej tablicy dwuwymiarowej NumPy `A` oraz promienia `r` będącego liczbą naturalną, zwróci elementy należące do sąsiedztwa elementu $a_{i,j}$. Wymikiem działania funkcji powinien być wycinek (widok) oryginalnej tablicy. Zwróć uwagę na to, jak sąsiedztwo zdefiniowane jest na brzegach i w rogach tablicy!
Następnie napisz funkcję maksima_lokalne(A), która dla zadanej tablicy `A` znajdzie wszystkie jej maksima lokalne. Funkcja powinna zwracać listę par współrzędnych maksimów lokalnych. Na przykład w tablicy $$A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 5 & 6 \\ 2 & 2 & 3 & 4 \end{bmatrix}$$ są dwa maksima lokalne $$A = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 5 & \fbox{6} & 5 & \fbox{6} \\ 2 & 2 & 3 & 4 \end{bmatrix},$$ co odpowiada elementom $a_{1,1}$ oraz $a_{1,3}$, zatem wynikiem działania funkcji powinna być lista
[(1, 1), (1, 3)]
Ostatecznie wykorzystaj napisane funkcje, aby stworzyć funkcję czy_jednomodalna(A), która zwraca `True` dla tablic jednomodalnych i `False` dla tablic niejednomodalnych.