SylabUZ
Nazwa przedmiotu | Algorithmical Methods |
Kod przedmiotu | 11.0-WK-MATED-AM-S22 |
Wydział | Wydział Matematyki, Informatyki i Ekonometrii |
Kierunek | Mathematics |
Profil | ogólnoakademicki |
Rodzaj studiów | drugiego stopnia z tyt. magistra |
Semestr rozpoczęcia | semestr zimowy 2022/2023 |
Semestr | 3 |
Liczba punktów ECTS do zdobycia | 6 |
Występuje w specjalnościach | Mathematical computer science |
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ę |
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.
Gaining of competences in computer structured programming. Basic course in algorithms and data structured.
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)
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.
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
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.
A. Aho, J. Hopcroft, J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
T.H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th Edition, MIT Press, Cambridge, Massachusetts, 2022.
V. V. Vazirani, Approximation Algorithms, Springer Berlin, Heidelberg, 2003.
R. Sedgewick, K. Wayne, Algorithms, 4th Edition, Addison-Wesley Professional, 2011.
D. Jungnickel, Graphs, Networks and Algorithms, Springer-Verlag, Berlin Heidelberg, 2008.
The descripion has been prepared by dr Florina Fabiś.
Zmodyfikowane przez dr Ewa Sylwestrzak-Maślanka (ostatnia modyfikacja: 21-02-2024 13:20)