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 USOSMAIL 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 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 opłacalnoś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, a dla algorytmu zachłannego dodatkowo informację czy znalezione rozwiązanie jest optymalne.
  • Dla chętnych: zakoduj algorytm programowania dynamicznego na jak najmniejszej liczbie znaków.
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/ suboptymalnego rozwiązania problemu. Porównaj efektywność tych algorytmów mierząc czas uzyskania rozwiązania 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. Podaj dla ilu procent instancji algorytm zachłanny nie znalazł rozwiązania optymalnego. Czy można ustalić w jakich przypadkach ten algorytm nie znajdzie optimum?