Часы | ||
лекц. | лабор. | |
I. Модели вычислений. Понятие сложности алгоритмов.
| ||
1. Сложность. Полиномиальная и экспоненциальная сложность. Алгоритмы и структуры данных. Алгоритмы сортировки. | 6 | 8 |
Презентация: 1 Лабораторная: 1 | ||
2. Динамические структуры данных. Списки и двоичные деревья. | 6 | 8 |
Презентация: 2 Лабораторная: 2 | ||
3. Алгоритмы на графах. Способы представления графа. Алгоритм Краскала поиска минимального остовного дерева. Обход графа в глубину и в ширину. Полиномиальные алгоритмы на графах. Минимальные маршруты на графах. Алгоритмы Дейкстры и Флойда. | 6 | 8 |
Презентации: 3, 4 Программы: рекурсивный обход графа в глубину, обход графа в ширину Лабораторная: 3 | ||
4. Перебор, сокращение перебора. Динамическое программирование. | 6 | 8 |
Презентация: 5 Лабораторная: 4 | ||
5. Классы P и NP. NP-полные задачи. | 6 | 8 |
Презентации: 6, 7 | ||
Автор: В.А. Петухин