SylabUZ

Wygeneruj PDF dla tej strony

Metody algorytmiczne - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Metody algorytmiczne
Kod przedmiotu 11.0-WK-MATD-MAL-L-S14_pNadGenOQ5NR
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Matematyka
Profil ogólnoakademicki
Rodzaj studiów drugiego stopnia z tyt. magistra
Semestr rozpoczęcia semestr zimowy 2019/2020
Informacje o przedmiocie
Semestr 3
Liczba punktów ECTS do zdobycia 6
Występuje w specjalnościach Informatyka matematyczna
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 Alina Szelecka (ostatnia modyfikacja: 14-03-2020 09:13)