Теория сложностей вычислительных процессов и структур
Программа курса назад  

Программа курса “Теория сложностей вычислительных процессов и структур”

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

назад