1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2018/2019
4. Mathematics - drugiego stopnia z tyt. magistra
5. Metody algorytmiczne

Wygeneruj PDF dla tej strony

Metody algorytmiczne - opis przedmiotu

Cel przedmiotu

Extensive knowledge of algorithms’ constructing and analysis. The ability to implement typical algorithms in practice and also the skills in adapting and modifying of those in extraordinary situations.

Wymagania wstępne

Zapisz zmiany

Gaining of competences in computer structured programming. Basic course in algorithms and data structured.

Zakres tematyczny

Lecture
1. NP – complete problems. (2 h)
2. Approximation algorithms. Optimization and decision problems. Optimum and approximate solutions. Absolute performance guarantee and relative performance guarantee of approximation algorithm. Approximation schemes: PTAS, FPTAS. (3 h)
3. Some approximation algorithms. Vertex Cover, Set Cover, Bin Packing, Knapsack, Multiprocessor Scheduling, Graph Coloring, Traveling Salesman. (4 h)
4. Algorithmic methods. Greedy algorithms. Backtracking algorithms. Branch-and-Bound (BB) method. Dynamic programming. Genetic algorithms. Probabilistic algorithms. (6 h)
 

Laboratory
1. Generating random number. Generating random graphs. (2 h)
2. Selected combinatorial algorithms for practical applications (4 h)
3. Approximation algorithms. (8 h)
4. Testing of algorithms that use selected algorithmic methods. (6 h)
5. Probabilistic algorithms. (4 h)
6. Selected algorithms with numbers. (6 h)

Metody kształcenia

Lecture: problem lecture.
Laboratory: laboratory exercises in computer lab – implementation and testing of selected algorithms.
Each student is supposed to realize three projects during the semester. Each project will consist in implementation of the selected algorithm to solve a concrete practical task, writing a program for it, testing it and presenting a documentation in accordance with the assigned specification. On one out of the three projects the students will work in 2-3 person groups. Furthermore the students will test other algorithms.

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

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

Warunki zaliczenia

Lecture. Written examination verifying the education outcome in area of knowledge and skills.
Laboratory. Final grade is granted based on number of points received during studies. Points are received for written tests, active participation in classes and completed project.
Final course grade consists of laboratory classes’ grade (50%) and examination grade (50%). Positive grade from laboratory classes is the necessary condition for participation in examination. The positive grade from examination is the necessary condition for course completion.

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. Aho A., Hopcroft J.E., Ullman J.D., : The Design and Analysis of Computer Algorithms.
2. T.H. Cormen, Ch.E. Leiserson, R.L. Rivest: Introduction to Algorithms, MIT Press, 2001.
3. Knuth D.E.: The Art of Computer Programming.
4. Vazarni V. V. : Approximation Algorithms, Springer, 2003.

Uwagi

Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 30-06-2018 09:24)