SylabUZ

Wygeneruj PDF dla tej strony

Metody algorytmiczne - opis przedmiotu

Informacje ogólne
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 2018/2019
Informacje o przedmiocie
Semestr 3
Liczba punktów ECTS do zdobycia 6
Typ przedmiotu obieralny
Język nauczania polski
Sylabus opracował
  • dr Florian Fabiś
Formy zajęć
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

Cel przedmiotu

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.

Wymagania wstępne

Umiejętność programowania komputerów w zakresie programowania strukturalnego. Podstawowy kurs z zakresu algorytmów i struktur danych.

Zakres tematyczny

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.)

Metody kształcenia

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

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

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.
 

 

Literatura podstawowa

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.

Literatura uzupełniająca

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.

Uwagi


Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 26-04-2018 20:29)