SylabUZ
Nazwa przedmiotu | Metody algorytmiczne |
Kod przedmiotu | 11.0-WK-IiED-MAL-L-S14_pNadGenNCWVG |
Wydział | Wydział Matematyki, Informatyki i Ekonometrii |
Kierunek | Informatyka i ekonometria |
Profil | ogólnoakademicki |
Rodzaj studiów | drugiego stopnia z tyt. magistra |
Semestr rozpoczęcia | semestr zimowy 2021/2022 |
Semestr | 3 |
Liczba punktów ECTS do zdobycia | 6 |
Występuje w specjalnościach | Systemy informacyjne |
Typ przedmiotu | obieralny |
Język nauczania | polski |
Sylabus opracował |
|
Forma zajęć | Liczba godzin w semestrze (stacjonarne) | Liczba godzin w tygodniu (stacjonarne) | Liczba godzin w semestrze (niestacjonarne) | Liczba godzin w tygodniu (niestacjonarne) | Forma zaliczenia |
Laboratorium | 30 | 2 | - | - | Zaliczenie na ocenę |
Wykład | 15 | 1 | - | - | Egzamin |
Zdobycie wiedzy i umiejętności w zakresie konstruowania, analizy i implementacji algorytmów aproksymacyjnych. Poznanie zaawansowanych metod konstruowania efektywnych algorytmów. Nabycie umiejętności implementacji algorytmów w typowych zastosowaniach, a także umiejętność ich adaptacji i modyfikacji w sytuacjach nietypowych.
Umiejętność programowania komputerów w zakresie programowania strukturalnego. Podstawowy kurs z zakresu algorytmów i struktur danych.
Wykład
1. Klasy złożoności obliczeniowej problemów decyzyjnych. (2 godz.)
2. Algorytmy aproksymacyjne. Problemy optymalizacyjne a problemy decyzyjne. Rozwiązania optymalne a rozwiązania przybliżone. Względne i bezwzględne gwarancje aproksymacji. Schematy aproksymacyjne. (3 godz.)
3. Algorytmy aproksymacyjne. Problemy: pokrycia wierzchołkowego (Vertex Cover), pokrycia zbioru (Set Cover), pakowania (Bin Packing), plecakowego (Knapsack), szeregowania (Multiprocessor Scheduling), kolorowania grafów (Graph Coloring), komiwojażera (Traveling Salesman). (4 godz.)
4. Metody algorytmiczne. Zachłanność. Algorytmy z nawrotami. Metoda podziałów i ograniczeń. Przeszukiwanie lokalne. Algorytmy probabilistyczne. (6 godz.)
Laboratorium
1. Generowanie liczb pseudolosowych. Generowanie grafów losowych. (2 godz.)
2. Wybrane algorytmy kombinatoryczne w zastosowaniach praktycznych. (4 godz.)
3. Algorytmy aproksymacyjne. (8 godz.)
4. Testowanie algorytmów wykorzystujących wybrane metody algorytmiczne. (6 godz.)
5. Algorytmy probabilistyczne. (4 godz.)
6. Wybrane algorytmy teorioliczbowe. (6 godz.)
Wykład: wykład problemowy
Laboratorium: ćwiczenia laboratoryjne w pracowni komputerowej – implementacja i testowanie wybranych algorytmów. Każdy student w trakcie semestru musi zrealizować trzy projekty. Każdy z projektów polegać będzie na zaimplementowaniu wskazanego przez prowadzącego algorytmu do rozwiązania konkretnego praktycznego zadania, napisaniu do tego programu, przetestowaniu go oraz przedstawieniu dokumentacji zgodnie z zadaną specyfikacją. Nad jednym z tych trzech projektów studenci będą pracowali w grupach 2-3 osobowych. Ponadto na zajęciach studenci będą testowali inne algorytmy
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
Wykład.
Egzamin pisemny weryfikujący efekty kształcenia w zakresie wiedzy i umiejętności.
Laboratorium.
Ocena końcowa jest wystawiana na podstawie punktów uzyskanych na zajęciach.
Punkty uzyskuje się za: napisane na zajęciach sprawdziany, zrealizowane na zajęciach projekty, aktywność na zajęciach. Na ocenę z przedmiotu składa się ocena z laboratorium (50%) oraz ocena z egzaminu (50%).
Warunkiem przystąpienia do egzaminu jest pozytywna ocena z laboratorium. Warunkiem zaliczenia przedmiotu jest pozytywna ocena z egzaminu.
1. Aho A., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa 1983.
2. Błażewicz J. : Złożoność obliczeniowa problemów kombinatorycznych, WNT, Warszawa 1988.
3. Cormen T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997
4. Vazirani V. V. : Algorytmy aproksymacyjne, WNT, 2004.
1. Dasgupta S., Papadimitriou C., Vizarni U.: Algorytmy, PWN, 2010.
2. Knuth D. : Sztuka programowania, t. 1-3, WNT, Warszawa 2001.
3. Wróblewski P.: Algorytmy, struktury danych i techniki programowania, wyd. II popr., Helion, 2001.
Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 05-05-2021 13:02)