Algorytmy i struktury danych
Terminarz zajęć:
04.03.2016 | Algorytmy sortowania I |
11.03.2016 | Algorytmy sortowania II |
01.04.2016 | Zasady przeprowadzania eksperymentów, sprawozdania, statystyka |
08.04.2016 | Złożone struktury danych |
10.04.2016! | Algorytmy sortowania - termin wysyłania sprawozdań |
12.04.2016! | Algorytmy sortowania - zaliczenie (13:30 sala 1.6.16 i 15:10 sala 1.6.22) |
15.04.2016 | Algorytmy grafowe |
20.04.2016 | Struktury danych - termin wysyłania sprawozdań |
22.04.2016 | Struktury danych - zaliczenie |
06.05.2016 |
Kolokwium z sortowania, struktur i grafowych |
08.05.2016! | Algorytmy grafowe - termin wysyłania sprawozdań |
10.05.2016! | Algorytmy grafowe - zaliczenie (13:30 sala 1.6.16 i 15:10 sala 1.6.22) |
13.05.2016 | Algorytmy z powracaniem |
29.05.2016! | Algorytmy z powracaniem - termin wysyłania sprawozdań |
31.05.2016! | Algorytmy z powracaniem - zaliczenie |
03.06.2016 | Programowanie dynamiczne |
10.06.2016 |
Kolokwium z powracania i dynamicznego |
15.06.2016 | Programowanie dynamiczne - termin wysyłania sprawozdań |
17.06.2016 | Programowanie dynamiczne - zaliczenie |
TBA | Poprawki i powtórka przed egzaminem |
Sprawozdania:
- Zawieramy w nich tylko to co niezbędne: oszczędzamy miejsce, czas swój i czytającego. Istotne są wykresy, oraz wnioski. Nie umieszczamy w sprawozdaniach: treści zadań, kodu, tabel z liczbami, etc.
- Sprawozdania wgrywamy tutaj w zadanym terminie.
- System motywacyjny: Przekroczenie terminu (w tym sprawozdanie niekompletne, uszkodzone, etc.) oznacza przydział dodatkowego zadania. Dodatkowe zadania są określone przy każdym z projektów, opóźnione sprawozdanie powinno od razu zawirać wykonane dodatkowe zadanie.
- Sprawozdania trzeba obronić na zajęciach oraz zaprezentować własny kod na którym wykonano pomiary. To może oznaczać pytania o zawartość sprawozdań oraz kodu.
- Oceniana jest jakość sprawozdania, jakość kodu, oraz odpowiedzi na pytania.
- Każde sprawozdanie winno mieć 4 sekcje: cel badania (krótko!), metoda przeprowadzenia badania i środowisko testowe (krótko!), wyniki, dyskusja wyników i wnioski.
Wymogi statystyczne:
- Każdy pomiar należy powtórzyć minimum trzy razy.
- Dla każdego pomiaru należy obliczyć odchylenie standardowe, a z niego współczynnik zmienności. Współczynniki zmienności poddajemy analizie.
- Jeżeli współczynnik zmienności nie jest duży, uznajemy pomiary za wystarczająco dobre i przystępujemy do robienia wykresów, np. ze średnią z tych 3 pomiarów.
- Jeżeli współczynnik zmienności jest duży, należy wykonać dodatkowe pomiary, np. 8-9 pomiarów. Jeżeli mimo to zmienność jest duża (a na wykresie występują trudne do wyjaśnienia skoki) być może należy odrzucić jakąś obserwację odstającą lub zamiast średniej użyć mediany.
- Dyskusja analizy współczynnika zmienności winna znaleźć się w sprawozdaniu: w razie braku problemów wystarczy jedno zdanie. Jeżeli zastosowano jakieś czynności naprawcze będzie trzeba ze trzy zdania.
- Wykresy winny być opisane co przedstawiają: osie, jednostki, jaka miara centralna została użyta (średnia, mediana). Każdy wykres powinien mieć podpis.
- Sprawozdanie powinno zawierać informacje jak dokonano pomiarów, w tym o dokładności `aparatury pomiarowej`. Ta dokładność będzie decydować o rozmiarach badanych instancji problemów (metoda przeprowadzenia badania!).
- Wykresy winny mieć tak dobrane zakres, skalę i sposób wizualizacji danych, by były czytelne. Typ wykresu winien być dobrany odpowiednio do przedstawianego problemu.
Kolokwia:
- Kolokwia będą obejmować przerabiany materiał zgodnie z podanymi informacjami.
- Możliwe są dodatkowe niezapowiedziane kolokwia lub wejściówki.
Zaliczenie:
- Do zaliczenia przedmiotu niezbędne jest poprawne zaliczenie kompletu projektów oraz wszystkich kolokwiów.
- Ocena końcowa jest średnią ważoną z kolokwiów (waga 2) oraz projektów (waga 1).
Zadanie 1. Algorytmy sortowania
Zaimplementuj 4 sortowania (insert, merge, heap, quick).Wygeneruj tablice liczb całkowitych, gdzie ciąg danych ułożony jest w sposób losowy, rosnący, malejący, V-kształtny. Dla każdego układu dziesięć tablic o odpowiednio dobranych przyrastających rozmiarach n.
Zmierz czasy wykonania sortowań.
Wykonaj wykresy porównujące:
- Efektywność każdego algorytmu na wszystkich 4 typach danych (4 wykresy, po jednym dla algorytmu)
- Efektywność wszystkich 4 algorytmów na każdym z typów danych (4 wykresy, po jednym dla typów danych)
- złożoności obliczeniowej algorytmów
- wpływu postaci ciągów wejściowych na czas sortowania (złożoności optymistyczne i pesymistyczne)
Zadanie 2. Złożone struktury danych
Zaimplementuj struktury:- listę posortowaną (wstawiaj kolejno elementy w odpowiednie miejsce)
- drzewo BST (wstawiaj kolejno elementy do drzewa), zanotuj do sprawozdania wysokość drzew BST
- wyważone drzewo AVL (budowane metodą połowienia binarnego)
- wstawianie m elementów
- wyszukiwanie m elementów
- usuwanie m elementów
W związku z Państwa pytaniami, prawdopodobnie najsprawniejszą procedurą przeprowadzenia tego eksperymentu jest:
dla każdego n wygenerować n liczb naturalnych oraz dodatkowe m liczb naturalnych, tak by nigdzie się nie powtarzały, zadbać też o losową kolejność dla drzewa BST
zbudować z n liczb odpowiednią strukturę, zmierzyć wysokości,
wykonać wstawienie m liczb mierząc czas,
wykonać wyszukanie m liczb mierząc czas,
wykonać usunięcie m liczb mierząc czas,
powtórzyć dla wszystkich n i tyle razy ile potrzeba.
Jeżeli wykresy wychodzą, nie takie jak powinny należy skontrolować co Państwo na nich umieszczają. Mierzymy czasy dla m elementów, bo dla jednego byłby niemierzalny, ale umieszczanie na wykresie czasu dla m elementów, zresztą za każdym razem innego m nie jest najlepszym rozwiązaniem. Lepiej umieścić średni czas dla jednego elementu...
Zadanie 3. Grafy
Zaimplementuj reprezentacje grafu:- lista sąsiedztwa,
- macierz sąsiedztwa
Wygeneruj grafy nieskierowane (ale nie multigrafy!) o n wierzchołkach i współczynniku nasycenia krawędziami 50%. Dobierz 10 wartości n dobrych dla dokonania pomiarów i sporządzenia wykresów.
Wykonaj pomiary czasu i wykresy porównujące:
- reprezentacje w zależności od metody przechodzenia grafu (2 wykresy po 2 krzywe)
- metody przechodzenia grafu w zależności od reprezentacji (2 wykresy po 2 krzywe)
Zadanie dodatkowe: zaimplementuj i włącz do sprawozdania także macierz grafu.
Zadanie 4. Algorytmy z powracaniem
Zaimplementuj algorytm znajdujący pierwszy cykl Hamiltona w grafie nieskierowanym.Zaimplementuj algorytm znajdujący pierwszy cykl Eulera w grafie nieskierowanym (np. Fleurego).
Wygeneruj spójne grafy nieskierowane o n wierzchołkach i parzystym stopniu każdego z wierzchołków, o współczynnikach nasycenia krawędziami równych 30%, 50% i 70% dla 10 różnych wartości n dobranych tak, by możliwe było wykonanie pomiarów.
Zmierz czasy wykonania algorytmów i przedstaw na wykresach, osobnym dla każdego algorytmu, ale wszystkie współczynniki nasycenia razem (2 wykresy łącznie). Przedstaw i opisz zaimplementowane algorytmy, przedyskutuj ich mocne i słabe strony, szczególnie złożoność obliczeniową.
Zadanie dodatkowe: zaimplementuj i włącz do sprawozdania dodatkowo Algorytm Hierholzera.
Zadanie 5. Programowanie dynamiczne i algorytmy zachłanne.
Zaimplementuj algorytmy rozwiązujące 0-1 problem plecakowy:- algorytm pełnego przeszukania (brute force)
- algorytm programowania dynamicznego
- wybrany algorytm zachłanny
Wygeneruj n zbiór przedmiotów (waga, cena) dla 10 różnych wartości n. Rozwiąż problem plecakowy dla trzech różnych wartości W rozmiaru plecaka wszystkimi trzema algorytmami. Wartości n i W dobierz eksperymentalnie. Porównaj wyniki algorytmów (wartość plecaka) w tabelce (30 pozycji), wyznacz `stratę` algorytmu zachłannego dla poszczególnych przypadków, maksymalną, minimalną oraz średnią. Porównaj czasy wykonania algorytmów na wykresach:
- czasy wykonania dla każdego algorytmu (trzy wykresy) w zależności od n i W (trzy krzywe)
- czasy wykonania dla każdego W (trzy wykresy) w zależności od n i algorytmu (trzy krzywe)
Bibliografia:
Jako materiały rozszerzające do prowadzonych zajęć polecam "ważniaka":Złożoność obliczeniowa
Algorytmy i struktury danych