Задачи динамического программирования

1. Содержание

   • Основные понятия. Справочный материал
   • Основные понятия
   • 1.2. Справочный материал. Сравнение скорости роста основных функций
   • 2 Новые быстрые версии старых алгоритмов
   • 2.1. Сортировки массивов
   • 2.1.1 Метод прямого выбора (SelectSort)
   • 2.1.2 Быстрая сортировка методом двоичных вставок (MergeSort)
   • 2.2. Преобразование Фурье (бпф)
   • 2.2.1. Дискретное преобразование Фурье
   • 2.2.2. Полубыстрое преобразование Фурье (ппф)
   • 2.2.3. Быстрое преобразование Фурье (бпф)
   • 2.3. Быстрая свертка
   • 2.3.1. Понятие свертки
   • 2.3.2. Обычный и быстрый алгоритм свертки
   • 2.4. Быстрое умножение
   • 2.4.1. Быстрое умножение чисел
   • 1 Суммирование
   • 4 Произведения чисел вдвое меньшей
   • 2.4.2. Быстрое умножение матриц
   • 2.4.3. Очень быстрое умножение числе (алгоритм Шенхаге – Штрассена)
   • 3. Задачи на графах
   • 3.1. Справочный материал
   • 3.2. Поиск минимального остова в связном неориентированном взвешенном графе
   • 3.3. Нахождение кратчайшего расстояния
   • 3.3.1. Алгоритм Форда – Беллмана
   • 3.3.2. Алгоритм Дейкстры
   • 3.4. Нахождение диаметра, радиуса и центра графа
   • 3.5. Задача об изоморфизме графов
   • 3.6. Задача коммивояжера. Её решение методом ветвей и границ.
   • Задачи динамического программирования
   • Задачи динамического программирования. Её решение методом динамического программирования.
   • 4.2. Задача об оптимальном наборе самолетом скорости и высоты
   • 4.3. Задача грабителя (задача о рюкзаке)
   • 4.4. Задача о перемножении матриц
   • 5 Классы p и np
   • 5.1 Машина Тьюринга
   • 5.2 Недетерменированные машины Тьюринга(ндмт)
   • 5.3 Сводимость. Np-полнота.
   • 5.4 Иерархия по сложности. Труднорешаемые задачи.
   • Классы сложности.
   • 6 Неразрешимые задачи
   • 6.1 Новая модель алгоритма вычислений.
   • 6.2 Нумерация программ
   • 6.3 Неразрешимые проблемы
   • 6.4 Теорема об ускорении
   • Лабораторные работы
   • Расчетно-графическое задание
   • Ответы к домашним заданиям