Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:jimp2:2017:labs:algorithm [2017/05/11 06:08] mwp [Biblioteka algorithm] |
pl:dydaktyka:jimp2:2017:labs:algorithm [2019/06/27 15:50] (aktualna) |
====== Ćwiczenia do wykonania ====== | ====== Ćwiczenia do wykonania ====== |
| |
[7 plusów] Przy pomocy algorytmów znajdujących się w bibliotece algorithm należy zaimplementować następujące metody (kolejność przypadkowa): | - [7 plusów] Przy pomocy algorytmów znajdujących się w bibliotece algorithm należy zaimplementować następujące metody (kolejność przypadkowa): |
<code cpp> | <code cpp> |
std::set<std::string> Keys(const std::map<std::string, int> &m); | std::set<std::string> Keys(const std::map<std::string, int> &m); |
std::set<std::string> Values(const std::map<std::string, int> &m); | std::vector<int> Values(const std::map<std::string, int> &m); |
std::map<std::string, int> DivisableBy(const std::map<std::string, int> &m,int divisor); | std::map<std::string, int> DivisableBy(const std::map<std::string, int> &m,int divisor); |
void SortInPlace(std::vector<int> *v); | void SortInPlace(std::vector<int> *v); |
int HowManyShortStrings(const std::vector<std::string> &v, int inclusive_short_length); | int HowManyShortStrings(const std::vector<std::string> &v, int inclusive_short_length); |
</code> | </code> |
| - **[5 punktów]** Zadanie polega na dodaniu do aplikacji Academia możliwości układania harmonogramu zajęć uwzględniającego różne ograniczenia. W podstawowej wersji należy jedynie uwzględnić brak bilokacji (i multilokacji) studentów z danego roku i nauczycieli akademickich. Zajęcia również w danym oknie czasowym i w danej sali mogą się odbywać tylko jedne zajęcia. Każdy nauczyciel musi poprowadzić określoną listę przedmiotów. Ogólnie ułożenie optymalnego planu zadań jest zadaniem [[https://en.wikipedia.org/wiki/List_of_NP-complete_problems|bardzo trudnym]], dlatego prawdopodobnie algorytm będzie rozwijany miesiącami. Jednak zanim specjalny zespół od problemów optymalizacyjnych dostarczy wreszcie gotowe rozwiązanie chcielibyśmy mieć namiastkę działającego oprogramowania! Na szczęście jest to możliwe należy zdefiniować kontrakt w postaci interfejsu **Scheduler** specjalny zespół dostarczy nam za kilka miesięcy algorytm **SophisticatedHighlyOptimizedScheduler**, a my możemy już napisać bardzo uproszczony algorytm zachłanny, który będzie dostarczał często nieoptymalne wyniki, ale na razie wystarczy. Należy więc przygotować klasy: |
| - **SchedulingItem** pojedynczy element harmonogramu, obiekt wartości, zawiera pola: |
| - course_id - identyfikator kursu |
| - teacher_id - identyfikator nauczyciela akademickiego prowadzącego te zajęcia o tej godzinie |
| - room_id - identyfikator pomieszczenia w którym odbywają się zajęcia |
| - time_slot - okno czasowe, w którym odbywają się zajęcia, dla uproszczenia cały tydzień jest podzielony na N okien czasowych nie zachodzących na siebie (np. dla 20: 1 => pon 8:00-10:00, 2 => pon 10:00-12:00, ... 20 => pią 14:00-16:00). Zajęcia wymagają zawsze pojedynczego okna czasowego i zawsze są z nim wyrównane tzn. nie mogą zajmować połowę 12ego i połowę 13ego |
| - year - rok studiów na którym obowiązuje przedmiot |
| - **Schedule** cały harmonogram, udostępnia następujące metody: |
| - Schedule OfTeacher(int teacher_id) const - wylicza fragment harmonogramu związany z danym nauczycielem akademickim (może się przydać copy_if...) |
| - Schedule OfRoom(int room_id) const - j.w. tylko związany z danym pomieszczeniem |
| - Schedule OfYear(int year) const - j.w. dla danego roku studiów |
| - std::vector<int> AvailableTimeSlots(int n_time_slots) const - wylicza wektor jeszcze nie zajętych okien czasowych, gdzie n_time_slots jest maksymalną wartością okna czasowego |
| - void InsertScheduleItem(const SchedulingItem &item) - wstawia nowy element planu |
| - size_t Size() const - zwaraca rozmiar planu |
| - **Scheduler** najważniejszy element układacz planu, interfejs czysto abstrakcyjny stanowiący kontrakt między nami a zespołem pracującym nad zoptymalizowaną wersją algorytmu. |
| - Schedule PrepareNewSchedule(const std::vector<int> &rooms, const std::map<int, std::vector<int>> &teacher_courses_assignment, const std::map<int, std::set<int>> &courses_of_year, int n_time_slots) |
| - rooms - dostępne pomieszczenia |
| - teacher_courses_assignment - rozpiska nauczycieli (klucz w mapie) i prowadząnych przez nich przedmiotów (wartosć w mapie) |
| - courses_of_year - kursy (wartość w mapie) wymagane dla danego rocznika (klucz w mapie) |
| - n_time_slots - ilość slotów czasowych |
| - **NoViableSolutionFound** wyjątek wyrzucany, gdy nie udaje się stworzyć planu |
| - **GreedyScheduler** wersja [[https://pl.wikipedia.org/wiki/Algorytm_zach%C5%82anny|zachłanna]] implentacji algorytmu układacza planu zwykła pętla która próbuje przypisywać po kolei przedmioty do sal i nauczycieli |
| |
| |
| |
| |