AiSD zadania

Informacje dla studentów >> Algorytmy i struktury danych (Informatyka) >>

Zadania zaliczeniowe

Zadanie 1 | Zadanie 2 | Zadanie 3 | Zadanie 4 | Zadanie 5

Terminem zaliczenia programu jest dzień wyszczególniony w terminarzu zajęć. Tylko w tym dniu można uzyskać maksymalną punktację za program (w przypadku niemożności zaliczenia programu na wyznaczonych zajęciach należy umowić się na zaliczenie indywidualne). Sprawozdanie z danego tematu (pojedynczy plik pdf) powinno być wysłane emailem najpóźniej 4 dni po zaliczeniu programu.

Zadanie 1: Algorytmy sortowania

I	program Zaimplementuj następujące algorytmy sortowania ciągu liczb naturalnych w porządku malejącym: - Selection Sort, - Heap Sort, - Shell Sort (z przyrostami liczonymi metodą ustaloną przez grupę), - Quick Sort w wersji rekurencyjnej oraz iteracyjnej (pivot zgodnie z ustaleniami grupy). Dane wejściowe: n-elementowy ciąg liczb naturalnych wczytywany z klawiatury (n<=10) lub generowany przez generator danych będący częścią programu. Proszę zapewnić odporność na błędy. Dane wyjściowe: czas sortowania, oraz w przypadku liczb wczytywanych z klawiatury: (i) ciąg wejściowy i wyjściowy, (ii) wartość pivota w każdej iteracji (Quick sort), (iii) wartość przyrostu w każdej iteracji (Shell sort).
II	testy Wygeneruj n-elementowe ciągi liczb naturalnych podanych w postaci losowej, rosnącej, malejącej, A-kształtnej i V-kształtnej (dla 10-15 różnych wartości n z przedziału <10,k>, przy czym k należy dobrać eksperymentalnie: możliwie duże ale takie, aby możliwe było wykonanie pomiarów). Zastosuj algorytmy SS, HS, ShS, QSr, QSi do posortowania każdego ciągu liczbowego. Zapisz czasy działania algorytmów.
III	sprawozdanie Wykonaj 5 wykresów (jeden wykres dla każdej metody sortowania: SS, HS, ShS, QSi, QSr) t=f(n) zależności czasu obliczeń t od liczby n elementów tablicy. Na każdym wykresie przedstaw 5 krzywych - po jednej krzywej dla każdej postaci danych wejściowych - pokazując w ten sposób zależność wybranego algorytmu od danych wejściowych. Wykonaj 5 wykresów (jeden wykres dla każdej postaci danych wejściowych) t=f(n) zależności czasu obliczeń t od liczby n elementów tablicy. Na każdym wykresie przedstaw 5 krzywych - po jednej krzywej dla każdego algorytmu sortującego - pokazując w ten sposób efektywność zaimplementowanych metod sortowania dla wybranej postaci danych. Wypisz zalety i wady algorytmu Quick sort w wersji rekurencyjnej oraz iteracyjnej. Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania. Uwagi dotyczące wykresów: Osie wykresów powinny być opisane (jakie dane na której osi). Każdy punkt na wykresie powinien być obliczony jako średnia z 5-10 pomiarów. Na wykresie przedstaw błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podaj te dane w postaci tabelarycznej.

w górę

Zadanie 2: Złożone struktury danych

I	program Zaimplementuj algorytm konstruowania drzewa AVL metodą połowienia binarnego oraz algorytm konstruowania 'losowego' drzewa BST (bierzemy kolejne elementy ciągu liczbowego i wstawiamy je do drzewa). Zaimplementuj procedury obsługujące następujące operacje na obu drzewach: wyszukanie w drzewie elementu o najmniejszej wartości i wypisanie jej (wyszukiwanie zaczynamy od korzenia), usunięcie elementu drzewa o wartości klucza podanej przez użytkownika (użytkownik wpisuje ile węzłów chce usunąć i podaje wartości kluczy), wypisanie wszystkich elementów drzewa w porządku rosnącym, usunięcie całego drzewa element po elemencie metodą post-order. wypisanie wartości korzenia. Procedury mają być wywoływane automatycznie jedna po drugiej, w kolejności podanej powyżej. Program powinien wyświetlać informacje o wyniku zakończonej procedury. Program winien być odporny na błędy wprowadzane przez użytkownika. Zaimplementuj wybraną procedurę równoważenia drzewa BST: równoważenie przez rotacje (algorytm DSW), równoważenie przez usuwanie korzenia.
II	testy Wygeneruj n-elementowe posortowane malejąco ciągi liczb naturalnych (dla 10-15 różnych wartości n z przedziału <10,k>, przy czym k należy dobrać eksperymentalnie tak, aby możliwe było wykonanie pomiarów i aby jego wartość była możliwie duża). Zmierz czasy wykonywania następujących operacji na obu drzewach: tworzenie drzewa, wyszukiwanie elementu o minimalnej wartości, wypisywanie wszystkich elementów drzewa, równoważenia drzewa BST.
III	sprawozdanie Wykonaj 3 wykresy (jeden wykres dla każdej z operacji: tworzenie struktury, wyszukanie minimum, wypisanie in-order) t=f(n) zależności czasu obliczeń t od liczby n elementów w drzewie. Na każdym wykresie przedstaw 2 krzywe - po jednej krzywej dla każdej struktury. Wykonaj wykres t=f(n) zależności czasu równoważenia t od liczby n elementów w drzewie. Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania. Uwagi dotyczące wykresów: Osie wykresów powinny być opisane (jakie dane na której osi). Każdy punkt na wykresie powinien być obliczony jako średnia z 5-10 pomiarów. Na wykresie przedstaw błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podaj te dane w postaci tabelarycznej.

w górę

Zadanie 3: Algorytmy grafowe

I	program Zaimplementuj algorytmy sortowania topologicznego wierzchołków grafu (a) z wykorzystaniem procedury przechodzenia w głąb (DFS) i (b) z usuwaniem wierzchołków o zerowym stopniu wejściowym dla następujących reprezentacji maszynowych grafu skierowanego: lista następników, macierz sąsiedztwa, macierz grafu. Razem należy zaimplementować 6 algorytmów: DFS_lista, DFS_msasiedztwa, DFS_mgrafu, DEL_lista, DEL_msasiedztwa, DEL_mgrafu. Program powinien mieć możliwość wczytywania danych z pliku tekstowego zawierającego graf zapisany w postaci listy krawędzi, gdzie para liczb w pierwszej linii to informacja o liczbie wieczchołków i liczbie krawędzi, a pary w kolejnych liniach to pary wierzchołków połączonych łukiem. Spacja jest separatorem liczb w pojedynczej linii.
II	testy Wygeneruj grafy skierowane acykliczne o n wierzchołkach i współczynniku nasycenia krawędziami równym 50% (oznacza to, że liczba krawędzi grafu wynosi 50% z n(n-1)/2), nie będące multigrafami, dla 10-15 różnych wartości n z przedziału <10,k> (k należy dobrać eksperymentalnie tak, aby możliwe było wykonanie pomiarów i aby jego wartość była możliwie duża). Zastosuj wszystkie 6 algorytmów do posortowania wygenerowanych grafów. Zapisz czasy działania algorytmów.
III	sprawozdanie Wykonaj 3 wykresy (jeden wykres dla każdej reprezentacji maszynowej grafu) t=f(n) zależności czasu obliczeń t od liczby n wierzchołków w grafie. Na każdym wykresie przedstaw 2 krzywe - po jednej krzywej dla każdej metody sortowania topologicznego. Wykonaj 2 wykresy (jeden wykres dla każdej metody sortowania topologicznego) t=f(n) zależności czasu obliczeń t od liczby n wierzchołków w grafie. Na każdym wykresie przedstaw 3 krzywe - po jednej krzywej dla każdej reprezentacji maszynowej grafu. Opisz zalety i wady każdej reprezentacji grafu z punktu widzenia ich zastosowania w zaimplementowanych algorytmach. Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania. Uwagi dotyczące wykresów: Osie wykresów powinny być opisane (jakie dane na której osi). Każdy punkt na wykresie powinien być obliczony jako średnia z 5-10 pomiarów. Na wykresie przedstaw błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podaj te dane w postaci tabelarycznej.

w górę

Zadanie 4: Algorytmy z powracaniem

I	program Zaimplementuj algorytm Robersta-Floresa AH znajdujący (a) jeden (pierwszy znaleziony) cykl Hamiltona, (b) wszystkie cykle Hamiltona w grafie nieskierowanym (zbiór cykli ma być różnowartościowy). Zaimplementuj algorytm Fleury'ego AE znajdujący (a) jeden (pierwszy znaleziony) cykl Eulera, (b) wszystkie cykle Eulera w grafie nieskierowanym (zbiór cykli ma być różnowartościowy). Uwaga: jeśli mamy cykle A i B, takie że cykl A jest odbiciem lustrzanym cyklu B, to tylko jeden z nich ma być wypisany na wyjściu. Razem należy zaimplementować 2 algorytmy, każdy z dwoma warunkami stopu przekazywanymi jako parametr wejściowy (stop po znalezieniu pierwszego cyklu / stop po znalezieniu wszystkich cykli). Można wybrać dowolną reprezentację maszynową grafu (taką samą dla obu algorytmów). Milej widziane są implementacje algorytmów, w których nie zastosowano instrukcji break.
II	testy Wygeneruj grafy nieskierowane o n wierzchołkach i współczynniku nasycenia krawędziami równym s: dla 9-ciu wartości s z przedziału <10,90> oraz dla 10-15 różnych wartości n z przedziału <10,k> (k należy dobrać eksperymentalnie tak, aby możliwe było wykonanie pomiarów i aby jego wartość była możliwie duża). Zastosuj oba algorytmy do znalezienia jednego i wszystkich cykli w wygenerowanych grafach. Zapisz czasy działania algorytmów.
III	sprawozdanie Wykonaj 2 wykresy (jeden wykres dla poszukiwania jednego cyklu, drugi wykres dla poszukiwania wszystkich cykli) t=f(n) zależności czasu obliczeń t od liczby n wierzchołków w grafie przy stałej wartości nasycenia s=50%. Na każdym wykresie przedstaw 2 krzywe - po jednej krzywej dla każdego algorytmu. Wykonaj 2 wykresy (jeden wykres dla każdego algorytmu) t=f(n) zależności czasu obliczeń t od liczby n wierzchołków w grafie przy stałej wartości nasycenia s=50%. Na każdym wykresie przedstaw 2 krzywe - jedna krzywa dla poszukiwania jednego cyklu, drugi - dla poszukiwania wszystkich cykli. Wykonaj 2 wykresy (jeden wykres dla poszukiwania jednego cyklu, drugi wykres dla poszukiwania wszystkich cykli) t=f(s) zależności czasu obliczeń t od nasycenia s przy stałej liczbie wierzchołków n. Na każdym wykresie przedstaw 2 krzywe - po jednej krzywej dla każdego algorytmu. Wykonaj 2 wykresy (jeden wykres dla każdego algorytmu) t=f(s) zależności czasu obliczeń t od nasycenia s przy stałej liczbie wierzchołków n. Na każdym wykresie przedstaw 2 krzywe - jedna krzywa dla poszukiwania jednego cyklu, drugi - dla poszukiwania wszystkich cykli. Wykonaj 2 wykresy (jeden wykres dla każdego algorytmu) t=f(n,s) zależności czasu obliczeń t od liczby n wierzchołków w grafie i nasycenia s, dla poszukiwania wszystkich cykli. Podaj jaka jest złożoność obliczeniowa zaproponowanych algorytmów oraz do jakich klas złożoności obliczeniowej należą badane problemy poszukiwania cyklu Hamiltona i cyklu Eulera w grafie (wersja przeszukiwania i wersja decyzyjna). Przedstaw obserwacje związane z działaniem obu algorytmów dla grafów o różnym nasyceniu. Odpowiedz jaką reprezentację maszynową grafu Twoim zdaniem najlepiej zastosować w przypadku każdego algorytmu i dlaczego. Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania. Uwagi dotyczące wykresów: Osie wykresów powinny być opisane (jakie dane na której osi). Każdy punkt na wykresie powinien być obliczony jako średnia z 5-10 pomiarów. Na wykresie przedstaw błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podaj te dane w postaci tabelarycznej.

w górę

Zadanie 5: Programowanie dynamiczne

I	program Zaimplementuj algorytm programowania dynamicznego APD rozwiązujący 0-1 problem plecakowy. Zaimplementuj algorytm wyczerpujący AW rozwiązujący 0-1 problem plecakowy. Obie implementacje powinny spełniać następujące wymagania: (i) należy umożliwić wczytywanie danych (zbiór przedmiotów z parametrami i pojemność plecaka) z klawiatury oraz z pliku ASCII; (ii) format danych w pliku powinien być zdefiniowany przez twórców programu i objaśniony na wstępie; (iii) program winien być odporny na wszelkie błędy wprowadzane przez użytkownika przy podawaniu danych wejściowych.
II	testy Wygeneruj dane wejściowe dla problemu plecakowego: n-elementowy zbiór przedmiotów, każdemu z nich przyporządkuj rozmiar r(i) oraz wartość w(i). Parametry rozmiar i wartość przyjmują wartości ze zbioru liczb naturalnych. Każdy przedmiot jest unikatowy (ma inny identyfikator), ale w zbiorze może istnieć wiele przedmiotów o takim samym rozmiarze / wartości. Ustal pojemność plecaka b, do którego zapakujesz przedmioty ze zbioru. Zastosuj oba algorytmy do znalezienia optymalnego rozwiązania problemu. Porównaj efektywność tych algorytmów mierząc czas uzyskania rozwiązania optymalnego przez każdą metodę dla tych samych instancji problemu.
III	sprawozdanie Wykonaj dla algorytmu APD wykres t=f(n) zależności czasu obliczeń t od liczby n przedmiotów, przy stałej pojemności plecaka b. Wykonaj dla algorytmu AW wykres t=f(n) zależności czasu obliczeń t od liczby n przedmiotów, przy stałej pojemności plecaka b. Wykonaj dla algorytmu APD wykres t=f(b) zależności czasu obliczeń t od pojemności plecaka b, przy stałej liczbie przedmiotów n. Wykonaj dla algorytmu AW wykres t=f(b) zależności czasu obliczeń t od pojemności plecaka b, przy stałej liczbie przedmiotów n. Wykonaj dla algorytmu APD wykres t=f(n,b) zależności czasu obliczeń t od liczby n przedmiotów i pojemności plecaka b. Wykonaj dla algorytmu AW wykres t=f(n,b) zależności czasu obliczeń t od liczby n przedmiotów i pojemności plecaka b. Podaj jaka jest złożoność obliczeniowa zaproponowanych algorytmów oraz do jakich klas złożoności obliczeniowej należy 0-1 problem plecakowy (wersja optymalizacyjna i decyzyjna). Przedstaw obserwacje związane z działaniem obu algorytmów. Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania. Uwagi dotyczące wykresów: Osie wykresów powinny być opisane (jakie dane na której osi). Każdy punkt na wykresie powinien być obliczony jako średnia z 5-10 pomiarów. Na wykresie przedstaw błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podaj te dane w postaci tabelarycznej.

w górę