--> Archiwum Forum
EartH [ Pretorianin ]
Proszę o przetłumaczenie tematu projektu na język ludzki
Zaprogramować generator podzbiorów zbioru. Użyć go do wyznaczania rozwiązania problemu szeregowania zadań ze zbioru N=‹1,2,…,n› na jednej maszynie z kryterium ważonej sumy spóźnień zadań. Wykorzystywany do tego celu jest schemat programowania dynamicznego (PD) dany w postaci wzoru rekurencyjnego
<wzór, nie udało się skopiować>
gdzie F(0)=0, zaś fk(t)=wk max‹0, t-dk), wielkość wk jest daną wagą, zaś dk danym pożądanym terminem zakończenia. Poszukiwana jest wartość F(N) . Dla tego zagadnienia zaprogramować również algorytm zachłanny szeregujący zadania według niemalejących wartości dk . Przeprowadzić eksperyment komputerowy w celu estymacji funkcji złożoności obliczeniowej dla każdego z algorytmów. Estymować odpowiednie parametry funkcji przy pomocy Excel’a metodą najmniejszych kwadratów z użyciem modułu Solver. Zestawić wykresy i porównać średni i pesymistyczny czas działania w funkcji długości danych ciągu wejściowego. Ocenić wartości błędu algorytmu zachłannego względem wartości optymalnej dostarczonej przez PD.
EartH [ Pretorianin ]
i czy można to podciągnąć pod problem komiwojażera??
Moby7777 [ Generaďż˝ ]
Po pierwsze, bez wzoru to trochę ciężko odpowiedzieć na pytanie, czy można to podciągnąć pod problem komiwojażera. Prawdopodobnie, ale nie chce mi się na siłę nad tym teraz zastanawiać.
Po drugie, z treści zadania wnioskuję, że jesteś około 2-3 roku studiów informatyki. Jeśli nie rozumiesz polecenia to jak niby chcesz je rozwiązać?
Co do treści jednak, masz do czynienia z klasycznym problemem szeregowania zadań (z tego co pamiętam to problem klasy NP), dalej: przegląd zupełny to prosta sprawa - ot brute force... Po drodze jeszcze zabawa z miarami ocen złożoności algorytmów. Od diabła algorytmiki i w sumie nie tak znowu łatwej matematyki. Jak nie rozumiesz treści to szczerze życzę Ci powodzenia w realizacji projektu w ciągu najbliższych dwóch tygodni. :)
Tak czy inaczej może przyda Ci się część materiałów z tego serwera: ftp://sith.ict.pwr.wroc.pl/ . Jest to ftp z materiałami dla studentów informatyki W-4 na PWr... konkretnie to ekipa dr Lichtensteina i okoliczne (kto ma wiedzieć ten wie, o kogo chodzi :P), która prowadzi zajęcia z tych dziedzin. Szukaj takich przedmiotów jak Teoretyczne Podstawy Informatyki czy Projektowanie Efektywnych Algorytmów... tak to się nazywało u mnie. Sam możesz szukać jakiejkolwiek teorii z zakresu informatyki.