Algorytmy i struktury danych - Bioinformatyka
Zajęcia laboratoryjne kończą się zaliczeniem, na którego ocenę składają się oceny z 5 zadań
(programy i sprawozdania) oraz 2 kolokwiów (waga 2x większa niż dla zadań). Zadania studenci wykonują w grupach 2-osobowych.
Za każdy program mozna uzyskać max. 3 punkty, za sprawozdanie max. 2 punkty. Spónienie z oddaniem programu
karane jest -0.5 punkta za każdy tydzień, a z oddaniem sprawozdanie -0.1 za każdy dzień spóznienia.
Obie osoby z grupy muszą być obecne przy oddawaniu każdego zadania (wyjątek - usprawiedliwienie lekarskie). Prowadzący wybiera, która osoba będzie odpowiadała
na pytania związane z programem lub/i sprawozdaniem.
Plan zajęć
Wymagania do sprawozdań
Zadania zaliczeniowe
Zadanie pierwsze (Algorytmy sortowania)
Termin zaliczenia programu (+ wykresy):19.03.2018; sprawozdanie dostarczone mailem (pdf): 26.03.2018
- zaimplementuj następujące algorytmy: insertion sort, shell sort, selection sort, heap sort oraz quick sort
- wygeneruj n-elementowe zbiory wejściowe; ciąg danych jest ułożony w sposób losowy, rosnący, malejący, stały, A-kształtny (rosnąco-malejący, np. 1,3,5,7,9,8,6,4,2)
Dla 10 różnych wartości n (dobrane wartości tak, żeby można było dokonać pomiaru czasu) utwórz następujące wykresy t=f(n)
- porównaj dla każdego algorytmu efektywność jego działania w zależności od danych wejściowych (5 wykresów - dla każdego algorytmu)
- porównaj dla każdego rodzaju danych wejściowych efektywność działania różnych algorytmów (5 wykresów - dla każdego rodzaju danych wejściowych)
Zaimplementuj algorytm quicksort rekurencyjnie. Porównaj różne sposoby wyboru klucza do porównania: skrajnie prawego lub losowo wybranego elementu ciągu. Utwórz 2 wykresy porównujące efektywność działania algorytmów w zależności od wyboru różnego klucza.
Do sprawozdania: Jaka jest złożoność badanych algortymów? Czy rozkład danych wejściowych wpływa na działanie algorytmu (najgorsze, najlepsze przypadki)?
Zadanie drugie (Złożone struktury danych)
Termin zaliczenia zadania + wykresy - 16.04.2018; sprawozdanie dostarczone mailem (pdf) -23.04.2018
Wygeneruj n-elementowe ciągi liczb naturalnych (10 różnych wartości n, które mają być tak dobrane, żeby można było dokonać pomiaru czasu). Liczby mają być losowo ułożone i nie mogą się powtarzać.
Zaimplementuj poszczególne funkcje operujące na listach:
- Dodanie elementu we własciwe miejsce (z sortowaniem)
- Wyszukanie elementu
- Usuwanie elementu
- Usuwanie całej listy
- Tworzenie listy z losowej tablicy elementów - wykorzystanie funkcji dodawania
Zaimplementuj poszczególne funkcje operujące na drzewach AVL:
- Dodanie elementu
- Usuwanie elementu
- Wyszukiwanie elementu z wywietlaniem ścieżki
- Przeglądanie drzewa inorder oraz preorder
- Tworzenie drzewa z posortowanej tablicy elementów metodš połowienia binarnego (wykorzystanie funkcji dodawania)
- Usuwanie drzewa postorder
Dokonaj pomiaru czasu następujacych operacji
- Tworzenie struktury
- Wyszukiwanie n/10 elementów (mierzymy czas całoci, a nie dla pojedynczego elementu)
- Usuwanie całej struktury
Utwórz 3 wykresy t=f(n) (dla każdej operacji osobny) porównując czas działania poszczególnych operacji na różnych strukturach dynamicznych: w licie oraz w wyważonym drzewie poszukiwań binarnych (AVL).
DO SPRAWOZDANIA: Sformuuj wnioski dotyczące operacji wykonywanych na różnych strukturach.
Oszacuj złożoność obliczeniową poszczególnych operacji dla wszystkich struktur.
Jakie zastosowanie mogą znaleźć drzewa BST i AVL?
W jakim celu wyważa się drzewa?
Zadanie trzecie (Algorytmy grafowe)
Termin zaliczenia zadania + wykres - 07.05.2018; sprawozdanie mailem z wykresami (pdf)- 14.05.2018
- Wygeneruj spójny skierowany graf acykliczny o n wierzchołkach
- współczynnik nasycenia łukami w grafie powinien być równy 50% (czyli 50% z n(n-1)/2)
- najłatwiej jest utworzyć graf acykliczny skierowany poprzez wypełnienie odpowiednią liczbą jedynek górnego trójkąta macierzy sąsiedztwa
- Graf jest reprezentowany poprzez macierz sąsiedztwa, listę następników oraz tabelę krawędzi.
- Zaimplementuj algorytm sortowania topologicznego dla każdej z reprezentacji zgodnie z algorytmem przeszukiwania:
* w głąb - etykietowanie wierzchołków pre- i postorder. Kolejnosc wierzchołków postorder (ułożonych malejaco) to kolejnoć wierzchołków w uszeregowaniu topologicznym.
- dokonaj pomiaru czasu działania algorytmów dla każdej reprezentacji grafu
- ogólne idee algorytmów, mają być takie same dla różnych reprezentacji grafu, różnice wynikają z innej złożoności wyszukiwania następników w grafie
- nie należy przekształcać każdej reprezentacji np. w liste następników, a nastepnie sortować
- nie należy upraszczać algorytmów ze względu na przygotowanie danych wejściowych (np. macierz sąsiedztwa jest górnotrójkątna i tylko tam sprawdzamy czy są łuki)
- Pomiary czasu przedstaw na wykresie t=f(n), dla 10 różnych wartości n
- W sprawozdaniu, oprócz wykresów:
- dla każdej z badanych reprezentacji grafu podaj złożoność: pamięciową, znalezienia pojedynczej krawędzi oraz znalezienia wszystkich następników wierzchołka
- oszacuj złożoność obliczeniową algorytmów sortowania topologicznego (jak się zmienia w zależności od reprezentacji grafu i z czego to wynika)
- które grafy można sortować topologiczne?
Zadanie czwarte (Algorytmy z powracaniem)
Termin zaliczenia zadania + wykresy; sprawozdanie mailem (pdf)-
Należy wykonać obie części zadania: A oraz B
Część A Szukanie cyklu Hamiltona i Eulera w grafie hamiltonowskim (i eulerowskim)
- Utwórz 2 typy grafów spójnych nieskierowanych o n wierzchołkach (wybierz dowolną reprezentację grafu; swój wybór krótko uzasadnij)
- Współczynnik nasycenia krawędziami w grafach powinien być równy odpowiednio 30% i 70%. Utwórz najpierw cykl Hamiltona w grafie (losując kolejne wierzchołki), a nastepnie dopełnij graf krawędziami wg. współczynnika nasycenia w taki sposób, aby stopień każdego wierzchołka był parzysty.
- Zaimplementuj algorytm znajdowania cyklu Eulera w grafie (opisz go w kilku zdaniach w sprawozdaniu, oszacuj złożoność obliczeniową algorytmu)
- Zaimplementuj algorytm z powracaniem znajdowania cyklu Hamiltona w grafie (opisz go w kilku zdaniach, oszacuj złożoność obliczeniową algorytmu)
- Dokonaj pomiaru czasu działania algorytmów dla 10 różnych wartości n, wyniki przedstaw na dwóch wykresach t=f(n) (oddzielnie dla cyklu Eulera i Hamiltona)
- Przedstaw obserwacje związane z działaniem obu algorytmów w zależności od nasycenia grafu
Część B - należy wykonać jeden z dwóch wariantów
- Utwórz graf nieskierowany z nasyceniem krawędziami równym 50%
Wariant I - w grafie nie ma cyklu Hamiltona (np. jeden losowo wybrany wierzcholek moze byc izolowany) - w takim grafie szukamy cyklu H., co sprowadza się do przeszukania wszystkich możliwych ścieżek
Wariant II - w grafie utworzonym tak jak w poprzednim zadaniu (ale o nasyceniu 50%) szukamy wszystkich możliwych cykli Hamiltona w grafie (czyli po znalezieniu pierwszego cyklu nie przerywamy obliczeń, tylko kontynuujemy przeszukiwanie wszystkich możliwych ścieżek)
Oba warianty mają taką samą złożoność obliczeniową
- Dokonujemy pomiaru czasu dla różnych wartości n, ale uwaga - tutaj n musi być znacznie mniejsze!
Cykl Eulera jest to cykl przechodzący przez wszystkie krawędzie grafu dokładnie jeden raz, natomiast cykl Hamiltona jest to cykl przechodzący przez wszystkie wierzchołki grafu dokładnie jeden raz.
Zadanie piąte (Problem plecakowy)
Termin zaliczenia zadania (program + wykresy)
Wyjeżdżając na wycieczkę musisz spakować plecak o maksymalnej pojemności C. Do plecaka spakuj takie przedmioty, aby ich wartość była jak największa, a jednocześnie ich objętość nie przekroczyła pojemności plecaka. Wyznacz te elementy za pomocą algorytmu programowania dynamicznego oraz algorytmu brute force.
- Wygeneruj zbiór n przedmiotów, dla każdego podając jego objętość (wi) i wartość (pi).
Wartości n oraz C dobierz eksperymentalnie. Dane te umieść w pliku, w następujący sposób:
C
n
p1 w1
p2 w2
...
pn wn
- Zaimplementuj algorytm programowania dynamicznego (PD) oraz algorytm brute force, które rozwiążą
problem poszukiwania najbardziej wartościowego zbioru przedmiotów. Dane do obliczeń mają być wczytywane z plików (przynajmniej na potrzeby zajęć - turniej zaliczeniowy).
- Porównaj efektywność działania algorytmów dla tych samych instancji testowych poprzez pomiar czasu obliczeń (dla 10-15 różnych punktów pomiarowych).
- Przedstaw wyniki na wykresach (lub w formie tabelki) t=f(n) (dla stałej pojemnośći plecaka c) oraz t=f(c) (dla stałej liczby przedmiotów n)
- Zastanów się nad wnioskami dotyczącymi zastosowanych metod oraz ich złożoności obliczeniowej. Do jakiej klasy problemów należy rozważany problem?