Informacje dla studentów << Algorytmy i struktury danych <<

Zadania zaliczeniowe

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

Uwagi ogólne:

  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. W niektórych zadaniach należy dodatkowo umożliwić wczytywanie danych wejściowych z pliku tekstowego (jeśli ta opcja jest konieczna zaznaczono to w treści zadania).
  3. Do każdego programu należy stworzyć automatyczny generator danych wejściowych, który zostanie wykorzystany do generowania danych na potrzeby testów obliczeniowych.
  4. Sprawozdanie z danego tematu powinno być zapisane w pliku *.pdf i wysłane przez platformę eKursy najpóźniej 3 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 powinien być obliczony jako średnia z 10 pomiarów. Na wykresie należy przedstawić błąd pomiaru (odchylenie standardowe) dla każdego punktu, a jeśli błędy są nieznaczne podać te dane w postaci tabelarycznej.
  6. Każde sprawozdanie powinno zawierać informację o tym, w jakim języku programowania zakodowano poszczególne algorytmy, na jakiej platformie wykonano testy (sprzęt i system operacyjny) oraz kto jest autorem sprawozdania.

Zadanie 1: Algorytmy sortowania

Program
  • Zaimplementuj następujące algorytmy sortowania ciągu liczb naturalnych w porządku malejącym:
    • Shell Sort z algorytmem bazowym Insertion Sort oraz przyrostami Hibbarda,
    • Merge Sort,
    • Heap Sort,
    • Quick Sort rekurencyjny z pivotem, którym jest skrajnie prawy element ciągu,
    • Quick Sort iteracyjny z pivotem, którym jest skrajnie prawy element ciągu.
  • Program powinien obsługiwać następujące dane wejściowe: n-elementowy ciąg liczb naturalnych wczytywany z klawiatury (n<=10), ciąg liczb naturalnych generowany przez generator danych będący częścią programu.
  • Dane wyjściowe:
    • czas sortowania,
    • dodatkowo dla celów prezentacji programu na zajęciach:
      1. ciąg wejściowy i wyjściowy,
      2. liczba scaleń podzbiorów (dla algorytmu Merge sort),
      3. wartość przyrostu w każdej iteracji (dla algorytmu Shell sort).
Testy
  • Wygeneruj po 10 n-elementowych ciągów zawierających liczby naturalne losowe, rosnące, malejące, A-kształtne i V-kształtne, dla 10-15 różnych wartości n. 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.
    Liczby w każdym ciągu należą do przedziału <1,10×n>. Przedział dla n należy dobrać eksperymentalnie – ciągi powinny być wystarczająco długie, aby można było zaobserwować jak rośnie czas obliczeń w zależności od n, a jednocześnie by możliwe było wykonanie pomiarów.
    Przykładowo: generujemy 10 losowych ciągów po 1000 elementów z przedziału <1,10000>, sortujemy je algorytmem A i wyznaczamy średni czas jaki algorytm ten potrzebuje aby posortować losowy ciąg 1000-elementowy – to będzie jeden punkt na wykresie; następnie generujemy 10 losowych ciągów po 5000 elementów z przedziału <1,50000> i sortujemy je algorytmem A, liczymy średni czas – to będzie drugi punkt na wykresie; tę procedurę wykonujemy dla 10 różnych n.
  • Zastosuj zaimplementowane algorytmy do posortowania każdego ciągu liczbowego. Zapisz czasy działania algorytmów.
Sprawozdanie
  • Stwórz N wykresów (N = liczba algorytmów sortowania, czyli robimy 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.
  • Stwórz 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 N krzywych – po jednej krzywej dla każdego algorytmu sortującego – pokazując w ten sposób efektywność zaimplementowanych metod sortowania dla wybranej postaci danych.
  • 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

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, element szukany również wypisujemy),
    • podanie na którym poziomie drzewa znajduje się węzeł o kluczu wskazanym przez użytkownika, wypisanie wszystkich elementów znajdujących się na tym samym poziomie a następnie usunięcie tego węzła,
    • wypisanie wszystkich elementów drzewa w porządku malejącym (wykorzystać do tego jedną z metod trawersowania drzewa binarnego),
    • wypisanie w porządku pre-order podrzewa, ktorego korzeń (klucz) podaje użytkownik, podanie wysokości tego poddrzewa, a następnie usunięcie tego poddrzewa metodą post-order,
    • równoważenie drzewa przez rotacje (algorytm DSW) lub przez usuwanie korzenia (należy wybrać jedną metodę); elementy drzewa należy wypisać w porządku pre-oder przed i po zrównoważeniu drzewa.
  • Program powinien obsługiwać następujące dane wejściowe: n-elementowy różnowartościowy ciąg liczb naturalnych wczytywany z klawiatury (n<=15) oraz generowany przez generator danych będący częścią programu.
  • Dane wyjściowe: czas działania procedury (wyszukiwania min/max, wypisania elementów, równoważenia drzewa) oraz informacje podane w poszczególnych podpunktach.
  • 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).
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 (przy AVL nie wliczaj czasu sortowania), wyszukiwanie elementu o minimalnej wartości, równoważenia drzewa BST.
    • Sprawozdanie
    • Wykonaj 2 wykresy (jeden wykres dla każdej z operacji: tworzenie struktury, wyszukanie minimum) 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

    Program
    • Zaimplementuj 2 algorytmy sortowania topologicznego wierzchołków grafu: (i) z wykorzystaniem procedury przechodzenia w głąb (algorytm Tarjana) i (ii) z usuwaniem wierzchołków o zerowym stopniu wejściowym (algorytm Kahna). Każdy z algorytmów należy zaimplementować na dwóch reprezentacjach maszynowych grafu: (a) macierz sąsiedztwa, (b) lista następników. Razem należy zaimplementować algorytmy: Tarjan_ms, Tarjan_ln, Kahn_ms, Kahn_ln.
    • Algorytmy powinny wykrywać cykle w grafie wejściowym. W wersji przedstawianej na zaliczenie w przypadku znalezienia cyklu, należy przerwać sortowanie i wyświetlić komunikat: „Graf zawiera cykl. Sortowanie niemożliwe.”
    • Program powinien umożliwiać wystartowanie algorytmu Tarjana z wierzchołka podanego przez użytkownika (ta wersja będzie wykorzystywana tylko podczas zaliczania programu na zajęciach) lub z wierzchołka domyślnego – o zerowym stopniu wejściowym (ta wersja będzie wykorzystywana do testów).
    • 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.
    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.
    Sprawozdanie
    • Wykonaj wykresy t=f(n) zależności czasu obliczeń t od liczby n wierzchołków w grafie (jeden wykres dla każdej reprezentacji maszynowej grafu). 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

    Program
    • Zaimplementuj algorytm z powracaniem (Robertsa-Floresa) znajdujący cykl Hamiltona w grafie nieskierowanym (na macierzy sąsiedztwa) i w grafie skierowanym (na macierzy grafu).
    • Zaimplementuj algorytm z powracaniem (Fleury’ego) znajdujący cykl Eulera w grafie nieskierowanym (na macierzy sąsiedztwa) i w grafie skierowanym (na macierzy grafu).
    • 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.
    Testy
    • Wygeneruj proste cykliczne i acykliczne 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.
      Na potrzeby testowania algorytmu Robertsa-Floresa generowane grafy cykliczne powinny być hamiltonowskie, a na potrzeby testowania algorytmu Fleury’ego – eulerowskie.
    • Zastosuj algorytmy do znalezienia cykli Hamiltona i Eulera w wygenerowanych grafach. Zapisz czasy działania algorytmów (oddzielnie dla grafów cyklicznych i acyklicznych).
    Sprawozdanie
    • Wykonaj 2 wykresy powierzchniowe 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 cyklicznym grafie skierowanym.
    • Wykonaj 2 wykresy powierzchniowe 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 acyklicznym grafie skierowanym.
    • Wykonaj 2 wykresy powierzchniowe 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 cyklicznym grafie nieskierowanym.
    • Wykonaj 2 wykresy powierzchniowe 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 acyklicznym 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 cyklicznych i acyklicznych o różnym nasyceniu.
    • Odpowiedz jaką reprezentację maszynową grafu Twoim zdaniem najlepiej zastosować w przypadku każdego algorytmu i dlaczego.

      • Jeśli nie masz możliwości wykonania wykresów 3D, to zamiast nich:
      • Wykonaj 4 wykresy (2 wykresy dla grafu nieskierowanego: cyklicznego i acyklicznego, 2 wykresy dla grafu skierowanego: cyklicznego i acyklicznego) 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 4 krzywe – jedna krzywa dla grafu nieskierowanego cyklicznego, druga dla grafu nieskierowanego acyklicznego, trzecia dla grafu skierowanego cyklicznego, czwarta dla grafu skierowanego acyklicznego.
      • Wykonaj 4 wykresy (2 wykresy dla grafu nieskierowanego: cyklicznego i acyklicznego, 2 wykresy dla grafu skierowanego: cyklicznego i acyklicznego) 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 4 krzywe – jedna krzywa dla grafu nieskierowanego cyklicznego, druga dla grafu nieskierowanego acyklicznego, trzecia dla grafu skierowanego cyklicznego, czwarta dla grafu skierowanego acyklicznego.

      w górę

      Zadanie 5: Programowanie dynamiczne

      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.
      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.
      Sprawozdanie
      • 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ę