Программа
курса “Теория сложностей
вычислительных процессов и структур”
- Сортировка массивов. Пузырьковая
сортировка (BubbleSort). Метод прямого выбора (SelectSort). Быстрая сортировка
методом двоичных вставок (MergeSort).
- Быстрое умножение чисел.
- Задачи на графах. Поиск минимального
остова в связном неориентированном взвешенном графе по алгоритму Краскала.
Нахождение кратчайшего расстояния между парой вершин по алгоритмам Форда –
Беллмана и Дейкстры. Нахождение диаметра, радиуса и центра графа. Задача об
изоморфизме графов. Задача коммивояжера, ее решение методом ветвей и границ.
- Задачи динамического программирования.
Метод динамического программирования. Задача об оптимальном наборе самолетом
скорости и высоты. Задача грабителя (задача о рюкзаке). Задача о перемножении
матриц.