1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2022/2023
4. Computer science and econometrics - drugiego stopnia z tyt. magistra
5. Algorithmical Methods

Wygeneruj PDF dla tej strony

Algorithmical Methods - opis przedmiotu

Cel przedmiotu

Acquiring knowledge and skills in the construction, analysis, and implementation of approximation algorithms. Learning advanced methods of constructing effective algorithms. Acquiring the ability to implement algorithms in typical applications, as well as the ability to adapt and modify them in unusual situations.

Wymagania wstępne

Zapisz zmiany

Computer programming skills in the field of structured programming. Basic course in algorithms and data structures.

Zakres tematyczny

Lecture
1. Classes of computational complexity of decision-making problems. (2 hours.)
2. Approximation algorithms. Optimization problems and decision problems. Optimal solutions and approximate solutions. Relative and absolute approximation guarantees. Approximation schemes. (3 hours)
3. Approximation algorithms. Problems: Vertex Cover, Set Cover, Bin Packing, Knapsack, Multiprocessor Scheduling, Graph Coloring, Traveling Salesman. (4 hours)
4. Algorithmic methods. Greedy algorithms. Backtracking. Branch-and-bound method. Local search. Probabilistic algorithms. (6 hours)

Lab
1. Generating pseudorandom numbers. Generating random graphs. (2 hours.)
2. Selected combinatorial algorithms in practical applications. (4 hours)
3. Approximation algorithms. (8 hours)
4. Testing algorithms using selected algorithmic methods. (6 hours)
5. Probabilistic algorithms. (4 hours)
6. Selected number-theoretic algorithms. (6 hours)

Metody kształcenia

Lecture: problem lecture

Laboratory: laboratory exercises in a computer lab - implementation and testing of selected algorithms. Each student must complete three projects during the semester. Each project will involve implementing an algorithm indicated by the teacher to solve a specific practical task, writing a program for it, testing it, and presenting documentation under the given specification. Students will work on one of these three projects in groups of 2-3 people. In addition, students will test other algorithms during classes.

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

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

Warunki zaliczenia

Lecture.
A written examination verifying the effects of education in terms of knowledge and skills.

Lab.
The final grade is based on the points obtained during the classes.
Points are obtained for: tests written during classes, projects completed during classes, and activities during classes. The course grade consists of the laboratory grade (50%) and the exam grade (50%).

The condition for taking the exam is a positive grade from the laboratory. The condition for passing the course is a positive grade on the exam.

Literatura podstawowa

Vijay V. Vazirani, Approximation Algorithms, Springer, 2003

Literatura uzupełniająca

David P. Williamson, David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2012

Uwagi

Zmodyfikowane przez dr Sebastian Czerwiński (ostatnia modyfikacja: 07-02-2024 19:59)