Zadania zaliczeniowe
Zadanie 1 | Zadanie 2 | Zadanie 3 | Zadanie 4 | Zadanie 5
Uwagi ogólne:
- 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 powinno być zapisane w pliku *.pdf i wysłane przez USOSMAIL w ciągu 6 dni po zaliczeniu programu (tylko za sprawozdania wysłane przed tym terminem można uzyskać maksymalną liczbę punktów).
- 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.
- 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.
Zadania zaliczeniowe:
- Zadanie 1: Algorytmy sortowania
Celem zadania jest implementacja wybranych algorytmów sortowania, przeprowadzenie systematycznych eksperymentów porównawczych oraz analiza ich złożoności obliczeniowej w praktyce (zobacz zadanie). - Zadanie 2: Złożone struktury danych
Zadanie obejmuje implementację oraz eksperymentalne porównanie wybranych dynamicznych struktur danych, a także analizę ich zachowania w zależności od sposobu budowy oraz rozmiaru danych wejściowych. Projekt ma na celu umożliwienie zrozumienia różnic między strukturami zrównoważonymi i niezrównoważonymi, wpływu danych wejściowych na degenerację drzewa, zależności między wysokością drzewa a kosztem operacji oraz znaczenia złożoności asymptotycznej w praktycznej analizie algorytmów. Dodatkowo pozwala porównać właściwości drzewa BST i kopca jako odmiennych struktur hierarchicznych (zobacz zadanie). - Zadanie 3: Algorytmy grafowe
Zadanie obejmuje implementację algorytmów sortowania topologicznego oraz ich eksperymentalne porównanie dla różnych reprezentacji grafu. Projekt ma na celu zrozumienie wpływu sposobu reprezentacji grafu na efektywność działania algorytmów, analizę zależności między gęstością grafu a kosztami obliczeń, a także rozwinięcie umiejętności interpretacji wyników eksperymentalnych w kontekście złożoności obliczeniowej (zobacz zadanie). - Zadanie 4: Algorytmy z powracaniem
Zadanie obejmuje implementację oraz eksperymentalne porównanie algorytmów przeszukiwania z wykorzystaniem techniki powracania dla wybranych problemów grafowych oraz analizę ich zachowania w zależności od rozmiaru i struktury danych wejściowych. Projekt ma na celu zrozumienie różnic między problemami o różnej złożoności obliczeniowej, wpływu przestrzeni rozwiązań na koszt przeszukiwania oraz znaczenia złożoności asymptotycznej w praktyce. Dodatkowo pozwala porównać efektywność tej samej techniki (backtracking) dla problemów łatwych i trudnych obliczeniowo (zobacz zadanie). - Zadanie 5: Algorytmy dokładne i heurystyczne dla problemu plecakowego
Zadanie obejmuje implementację oraz eksperymentalne porównanie trzech podejść algorytmicznych dla problemu plecakowego, a także analizę ich efektywności w zależności od liczby dostępnych elementów i pojemności. Projekt ma na celu zrozumienie różnic między metodami dokładnymi a heurystycznymi, zbadanie wpływu parametrów instancji na koszt obliczeń oraz ocenę jakości rozwiązań suboptymalnych względem wyznaczonego optimum, pozwala w praktyce przeanalizować kompromis pomiędzy szybkością działania algorytmu a jakością uzyskanego wyniku (zobacz zadanie).