1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2022/2023
4. Informatics and Econometrics - Second-cycle studies leading to MS degree
5. Algorithmical Methods

Generate PDF for this page

Algorithmical Methods - course description

Aim of the course

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.

Prerequisites

Save changes

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

Scope

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

Teaching methods

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

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

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.
 

 

Recommended reading

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.

Further reading

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.

Notes

Modified by dr Alina Szelecka (last modification: 19-05-2022 21:47)