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)
Na bazie wyników przeprowadź dyskusję dotyczącą:
  • 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 dodatkowe: zaimplementuj i włącz do sprawozdania także sortowanie Shella.


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)
Wygeneruj ciągi liczb naturalnych losowo ułożonych i nie powtarzających się. Dziesięć ciągów o odpowiednio dobranych przyrastających rozmiarach n. Wykonaj pomiary czasów wykonania i wykonaj wykresy porównujące:
  • wstawianie m elementów
  • wyszukiwanie m elementów
  • usuwanie m elementów
Przeprowadź dyskusję dotyczącą operacji wykonywanych na różnych strukturach, w tym oszacuj złożoność obliczeniową. Opisz zalety i wady struktur.

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
Zaimplementuj algorytmy przechodzenia grafu wszerz (BFS) oraz w głąb (DFS).
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)
Przedyskutuj wady i zalety metod reprezentacji grafu oraz algorytmów przechodzenia grafu.

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