SylabUZ
Nazwa przedmiotu | Algorithmical Methods |
Kod przedmiotu | 11.0-WK-CSEED-AM-S22 |
Wydział | Wydział Matematyki, Informatyki i Ekonometrii |
Kierunek | Computer science and econometrics |
Profil | ogólnoakademicki |
Rodzaj studiów | drugiego stopnia z tyt. magistra |
Semestr rozpoczęcia | semestr zimowy 2023/2024 |
Semestr | 3 |
Liczba punktów ECTS do zdobycia | 6 |
Występuje w specjalnościach | Information systems |
Typ przedmiotu | obieralny |
Język nauczania | angielski |
Sylabus opracował |
|
Forma zajęć | Liczba godzin w semestrze (stacjonarne) | Liczba godzin w tygodniu (stacjonarne) | Liczba godzin w semestrze (niestacjonarne) | Liczba godzin w tygodniu (niestacjonarne) | Forma zaliczenia |
Wykład | 15 | 1 | - | - | Egzamin |
Laboratorium | 30 | 2 | - | - | Zaliczenie na ocenę |
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.
Computer programming skills in the field of structured programming. Basic course in algorithms and data structures.
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)
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.
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
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.
Vijay V. Vazirani, Approximation Algorithms, Springer, 2003
David P. Williamson, David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2012
Zmodyfikowane przez dr Ewa Synówka (ostatnia modyfikacja: 10-04-2024 21:17)