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

Zadania zaliczeniowe

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

 

Uwagi ogolne:

  1. 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).
  2. W każdym programie należy zapewnić możliwość wprowadzania danych z klawiatury i wczytywania z pliku tekstowego.
  3. Każdy program powinien być odporny na błędy wejściowe, ktore może wprowadzić użytkownik.
  4. Sprawozdanie z danego tematu powinno być zapisane w pliku *.pdf i wysłane emailem najpóźniej 4 dni po zaliczeniu programu.
  5. 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 przedstaw błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podaj te dane w postaci tabelarycznej.


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,
    - Shell Sort z przyrostami Shella,
    - Shell Sort z przyrostami Knutha,
    - Quick Sort w wersji rekurencyjnej (pivot = pierwszy 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,
    - 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).
  • 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 i napisz jaki jest jej zwiazek z liczbą operacji wykonanych przez algorytm. Czy testy potwierdzają tę zależność?
  • Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania.

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 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 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. Proszę zapewnić odporność na błędy.
    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 drzewie.
  • Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania.

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:
    • macierz sąsiedztwa,
    • lista następnikow,
    • lista krawędzi.
    Razem należy zaimplementować następujące algorytmy: DFS_msasiedztwa, DFS_lnastepnikow, DFS_lkrawedzi, DEL_msasiedztwa, DEL_lnastepnikow, DEL_lkrawedzi.
  • 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 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 (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.

w górę

Zadanie 4: Algorytmy z powracaniem

I
program
  • Zaimplementuj algorytm Robersta-Floresa znajdujący cykl Hamiltona w grafie nieskierowanym (na macierzy sąsiedztwa) i w grafie skierowanym (na liscie nastepnikow).
  • Zaimplementuj algorytm Fleury'ego znajdujący cykl Eulera w grafie nieskierowanym (na macierzy sąsiedztwa) i w grafie skierowanym (na liscie nastepnikow).
II
testy
  • Wygeneruj 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).
  • 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 (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 (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.
  • Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania.

w górę

Zadanie 5: Programowanie dynamiczne

I
program
  • Zaimplementuj algorytm programowania dynamicznego APD rozwiązujący 0-1 problem plecakowy.
  • Zaimplementuj algorytm zachłanny AZ rozwiązujący 0-1 problem plecakowy.
  • Zaimplementuj algorytm wyczerpujący AW rozwiązujący 0-1 problem plecakowy.

  • Wszystkie 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 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 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 obu algorytmów.
  • Ponadto sprawozdanie powinno zawierać informację na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania.

w górę