Циљ предмета: Упознавање студената са основним елементима теорије нумеричке сложености и анализе алгоритама, као и принципима формирања алгоритама за решавање проблема у различитим областима (теорији графова, алгебри, геометрији, области низова и скупова).
- Временска и просторна сложеност алгоритма и проблема. Полиномијални алгоритми.
- Детерминистичка и недетерминистичка Тјурингова машина.
- NP класа проблема. NP комплетност и NP тешки проблеми.
- Конструкција алгоритама индукцијом; примери.
- Појачавање индуктивне хипотезе; доказивање исправности алгоритма.
- Алгоритми на графовима: обиласци графова; најкраћи путеви;
- Проблеми упаривања у графу; транспортне мреже; Хамилтонове контуре.
- Геометријски алгоритми: проблеми са многоуглом; конвексни омотач.
- Алгебарски алгоритми: проблеми са полиномима.
- Проблеми са матрицама.
- Алгоритми над низовима и скуповима.
- Неки алгоритми криптографије.
- Паралелни алгоритми; алгоритми за мреже рачунара.
- Израда семинарског рада
Литература
- М. Живковић, Алгоритми, Математички факултет, Београд 2000.
- З. Огњановић, Н. Крџавац, Увод у теоријско рачунарство, ФОН, Београд 2004.
- Leung Joseph, ed., Handbook of Scheduling : Algorithms, Models, Performance Analysis, Boca Raton [etc.] : Chapman and Hall/CRC, 2004.
Материјали
