Różnice między wybraną wersją a wersją aktualną.
| Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:jimp2:2017:labs:algorithm [2017/05/11 04:59] mwp utworzono |
pl:dydaktyka:jimp2:2017:labs:algorithm [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| ====== Biblioteka algorithm ====== | ====== Biblioteka algorithm ====== | ||
| + | |||
| + | Zapoznać się z metodami z bilblioteki [[http://en.cppreference.com/w/cpp/algorithm]]. Dla każdej z metod jest w dokumentacji podany przykład użycia kodu. | ||
| + | |||
| + | W przypadku modyfikowania niezainicjalizowanego kontenera może się przydać [[http://en.cppreference.com/w/cpp/iterator/back_inserter]] | ||
| + | |||
| ====== Ć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): | ||
| + | <code cpp> | ||
| + | std::set<std::string> Keys(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); | ||
| + | void SortInPlace(std::vector<int> *v); | ||
| + | std::vector<int> Sort(const std::vector<int> &v); | ||
| + | void SortByFirstInPlace(std::vector<std::pair<int,int>> *v); | ||
| + | void SortBySecondInPlace(std::vector<std::pair<int,int>> *v); | ||
| + | void SortByThirdInPlace(std::vector<std::tuple<int,int,int>> *v); | ||
| + | std::vector<std::string> MapToString(const std::vector<double> &v); | ||
| + | std::string Join(const std::string &joiner, const std::vector<double> &v); | ||
| + | int Sum(const std::vector<int> &v); | ||
| + | int Product(const std::vector<int> &v); | ||
| + | bool Contains(const std::vector<int> &v, int element); | ||
| + | bool ContainsKey(const std::map<std::string, int> &v, const std::string &key); | ||
| + | bool ContainsValue(const std::map<std::string, int> &v, int value); | ||
| + | std::vector<std::string> RemoveDuplicates(const std::vector<std::string> &v); | ||
| + | void RemoveDuplicatesInPlace(std::vector<std::string> *v); | ||
| + | void InitializeWith(int initial_value, std::vector<int> *v); | ||
| + | std::vector<int> InitializedVectorOfLength(int length, int initial_value); | ||
| + | void CopyInto(const std::vector<int> &v, int n_elements, std::vector<int> *out); | ||
| + | int HowManyShortStrings(const std::vector<std::string> &v, int inclusive_short_length); | ||
| + | </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 | ||
