AiSD zadania

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

Zadania zaliczeniowe

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

Uwagi ogolne:

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).
W każdym programie należy zapewnić możliwość wprowadzania danych z klawiatury i wczytywania z pliku tekstowego.
Każdy program powinien być odporny na błędy wejściowe, ktore może wprowadzić użytkownik.
Sprawozdanie z danego tematu powinno być zapisane w pliku *.pdf i wysłane emailem najpóźniej 3 dni po zaliczeniu programu.
W sprawozdaniu osie wykresów powinny być opisane (jakie dane na której osi, jednostki pomiaru). Każdy punkt na wykresie funkcji t=f(n) powinien być obliczony jako średnia z 5-10 pomiarów. Na wykresie należy przedstawić błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podaj te dane w postaci tabelarycznej.
Każde sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania.

Zadanie 1: Algorytmy sortowania

I	program Zaimplementuj następujące algorytmy sortowania ciągu liczb naturalnych w porządku malejącym: - Merge Sort, - Heap Sort, - Insertion Sort, - Shell Sort z przyrostami Knutha, - Quick Sort w wersji rekurencyjnej (pivot = ostatni element ciągu). Dane wejściowe: n-elementowy ciąg liczb naturalnych wczytywany z klawiatury (n<=10) oraz generowany przez generator danych będący częścią programu. Dane wyjściowe: - czas sortowania, - liczba operacji porównania i liczba operacji zamiany elementów podczas sortowania (nie dotyczy algorytmu Merge Sort), - w przypadku liczb wczytywanych z klawiatury dodatkowo: (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). Przykład ciągu A-kształtnego: 1,3,5,7,8,6,4,2. Przykład ciągu V-kształtnego: 8,6,4,2,1,3,5,7,9. Zastosuj zaimplementowane algorytmy do posortowania każdego ciągu liczbowego. Zapisz czasy działania algorytmów oraz liczbę operacji (porównanie i zamiana).
III	sprawozdanie Wykonaj 5 wykresów (jeden wykres dla każdej metody sortowania) 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. Wykonaj 5 wykresów (jeden wykres dla każdej metody sortowania) k=f(n) zależności liczby operacji k 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. Podaj złożoność obliczeniową każdego algorytmu (w przypadku średnim, pesymstycznym i optymistycznym) i napisz jaki jest jej zwiazek z liczbą operacji wykonanych przez algorytm. Czy testy potwierdzają tę zależność?

w górę

Zadanie 2: Złożone struktury danych

I	program Zaimplementuj algorytm konstruowania drzewa AVL metodą przeszukiwania 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 i największej wartości i wypisanie ścieżki poszukiwania (od korzenia do elementu szukanego), 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 (in-order), wypisanie wszystkich elementów drzewa w porządku pre-order, usunięcie całego drzewa element po elemencie metodą post-order, wypisanie w porządku pre-order podrzewa, ktorego korzeń (klucz) podaje użytkownik, równoważenie drzewa przez rotacje (algorytm DSW) lub przez usuwanie korzenia (należy wybrać jedną metodę). Dane wejściowe: n-elementowy ciąg liczb naturalnych wczytywany z klawiatury (n<=10) oraz generowany przez generator danych będący częścią programu. Po wykonaniu procedury wybranej przez użytkownika program wraca do menu (w pętli, dopóki użytkownik nie wybierze opcji wyjścia z programu). Program powinien wyświetlać informacje o wyniku zakończonej procedury.
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 (bez czasu sortowania), wyszukiwanie elementu o minimalnej wartości, wypisywanie wszystkich elementów drzewa (in-order), 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 losowym drzewie BST.

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 (algorytm Kahna) dla następujących reprezentacji maszynowych grafu skierowanego: macierz sąsiedztwa, macierz grafu. Razem należy zaimplementować następujące algorytmy: DFS_msasiedztwa, DFS_mgrafu, DEL_msasiedztwa, DEL_mgrafu. Wszystkie algorytmy powinny wykrywać cykle w grafie wejściowym. W przypadku znalezienia cyklu, należy przerwać sortowanie i wyświetlić komunikat: Graf zawiera cykl. Sortowanie niemożliwe. Program powinien mieć możliwość wczytywania danych z klawiatury oraz 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 proste 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) dla 10-15 różnych wartości n z przedziału <100,k> (k należy je dobrać eksperymentalnie tak, aby możliwe było wykonanie pomiarów i aby jego wartość była możliwie duża; proponowane k=1500). Zastosuj wszystkie algorytmy 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 w skali logarytmicznej (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 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.

w górę

Zadanie 4: Algorytmy z powracaniem

I	program Zaimplementuj algorytm z powracaniem znajdujący cykl Hamiltona w grafie nieskierowanym (na macierzy sąsiedztwa) i w grafie skierowanym (na liście następników). Zaimplementuj algorytm z powracaniem znajdujący cykl Eulera w grafie nieskierowanym (na macierzy sąsiedztwa) i w grafie skierowanym (na liście następników). W przypadku braku poszukiwanego cyklu w grafie należy wyświetlić komunikat: Graf wejściowy nie zawiera cyklu. Jeśli poszukiwany cykl istnieje program wypisuje go w postaci listy wierzchołków, przez które przechodzi cykl. Program powinien mieć możliwość wczytywania danych z klawiatury oraz 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/łuków, a pary w kolejnych liniach to pary wierzchołków połączonych krawędzią/łukiem. Spacja jest separatorem liczb w pojedynczej linii.
II	testy Wygeneruj proste grafy nieskierowane i skierowane o n wierzchołkach i współczynniku nasycenia krawędziami równym s={10,20,30,40,50,60,70,80,90} (dla wszystkich 9-ciu wartości) 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). Jeśli współczynnik nasycenia jest równy X to oznacza, że graf zawiera X% możliwych krawędzi: graf nieskierowany o nasyceniu X ma X% z (n(n-1))/2 krawędzi graf skierowany o nasyceniu X ma X% z (n(n-1)) łuków. Zastosuj algorytmy do znalezienia cykli w wygenerowanych grafach. Zapisz czasy działania algorytmów.
III	sprawozdanie Wykonaj 2 wykresy (jeden wykres dla grafu nieskierowanego, drugi wykres dla grafu skierowanego) 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 grafu nieskierowanego, druga dla grafu skierowanego. Wykonaj 2 wykresy (jeden wykres dla grafu nieskierowanego, drugi wykres dla grafu skierowanego) 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 grafu nieskierowanego, druga dla grafu skierowanego. Wykonaj 2 wykresy 3D (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 cyklu w grafie skierowanym. Wykonaj 2 wykresy 3D (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 cyklu w grafie nieskierowanym. 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 zaimplementowanych 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.

w górę

Zadanie 5: Programowanie dynamiczne

I	program Zaimplementuj algorytmy rozwiązujące 0-1 problem plecakowy: algorytm programowania dynamicznego AD algorytm zachłanny AZ (sortowanie po współczynniku oplacalności: wartość na jednostkę masy) algorytm siłowy AB. Wszystkie implementacje powinny spełniać następujące wymagania: należy umożliwić wczytywanie danych (zbiór przedmiotów z parametrami i pojemność plecaka) z klawiatury oraz z pliku tekstowego; format danych w pliku: pierwszy wiersz to para liczb n b (liczba przedmiotów, pojemność plecaka), kolejne wiersze to pary liczb r w (rozmiar przedmiotu, wartość przedmiotu). Spacja jest separatorem liczb w pojedynczej linii. program winien być odporny na wszelkie błędy wprowadzane przez użytkownika przy podawaniu danych wejściowych; na potrzeby prezentacji algorytmów program powinien wyświetlać: elementy wybrane do plecaka, ich sumaryczny rozmiar oraz wartość funkcji celu.
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 zaimplementowane 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 każdego algorytmu wykres t=f(n) zależności czasu obliczeń t od liczby n przedmiotów, przy stałej pojemności plecaka b. Wykonaj w skali logarytmicznej wykres t=f(n) zależności czasu obliczeń t od liczby n przedmiotów, przy stałej pojemności plecaka b. Na wykresie przedstaw 3 krzywe (jedna krzywa dla każdego algorytmu). Wykonaj dla każdego algorytmu wykres t=f(b) zależności czasu obliczeń t od pojemności plecaka b, przy stałej liczbie przedmiotów n. Wykonaj dla każdego algorytmu 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 wszystkich algorytmów. Czy można ustalić w jakich przypadkach algorytm zachłanny nie daje rozwiązania optymalnego?

w górę