- Алгоритм Форда-Фалкерсона решения задачи о максимальном потоке. Теорема о максимальном потоке и минимальном разрезе.
- Алгоритм Карзанова решения задачи о максимальном потоке.
- Сведение задачи построения многопроцессорного расписания с прерываниями при заданных длительностях работ и директивных интервалах к задаче о максимальном потоке.
- Распознающие алгоритмы. Класс P. Задачи распознавания свойств и языки. Детерминированная одноленточная машина Тьюринга. Рекурсивные и рекурсивно перечислимые языки. Полиномиально распознаваемые языки и класс P.
- Проверяемые алгоритмы. Классы
и 
- Класс NP. Соотношение между классами P и NP. Существование экспоненциального проверяющего алгоритма для языков из NP. Полиномиальная сводимость. Класс NPC. Способы доказательства NP-полноты.
- Семь основных
полных задач. - Доказательство NP-полноты задач выполнимость и 3-выполнимость.
- полнота некоторых задач. Класс
- Доказательство NP-полноты задач вершинное покрытие, клика, расписание без прерываний для многопроцессорной системы. Класс co-NP. Структура классов NP и co-NP.
- Сильная полнота.
- Задачи с числовыми параметрами. Псевдополиномиальные алгоритмы. Сильная NP-полнота и методы ее доказательства. Псевдополиномиальный алгоритм решения задачи о разбиении. Сильная полнота задачи расписание без прерываний для многопроцессорной системы.
- трудные и легкие задачи. Приближенные алгоритмы.
- Сводимость по Тьюрингу. Доказательство NP-трудности и NP-легкости некоторых задач. Приближенные алгоритмы (решения задач упаковка в контейнеры и расписание без прерываний для многопроцессорной системы) и оценки их погрешности.
- Применение теории полноты к разработке приближенных алгоритмов.
- Невозможность существования полиномиального приближенного алгоритма с фиксированной погрешностью для некоторых NP-трудных задач. Приближенный полиномиальный алгоритм решения задачи коммивояжера с неравенством треугольника.
- Метод ветвей и границ. Общее описание метода «ветвей и границ» и его реализация для решения задачи расписание без прерываний для многопроцессорной системы. Рандомизированный алгоритм решения задачи об идентичности полиномов и задачи о паросочетаниях.
- Алгоритмы параллельных вычислений.EREW-алгоритмы решения задач определения номера элемента в списке, параллельная обработка префиксов, вычисление глубины вершины в двоичном дереве. CRCW-алгоритм решения задачи определения корня для вершины двоичного леса. Алгоритм нахождения максимального элемента в массиве. Моделирование CRCW-машины с помощью EREW-машины. Эффективная параллельная обработка префиксов.
- Решение задачи линейного программирования различными методами.
- Решение транспортной задачи.
- Целочисленное программирование.
- Задача водопроводчика. Целочисленное линейное программирование с булевыми переменными.
- Задача загрузки преподавательского состава и обеспечение студентов аудиториями.
- Задача назначения экипажей транспортных самолетов.
- Задача размещения промышленных предприятий.
- Паросочетания и задача о назначениях.
- Задача о назначениях. Венгерский алгоритм.
- Задача о размещении производства.
- Повреждение узлов и дуг в сетях.
- Задача о перевозках.
- Нахождение критического пути и критических работ в сети.
- Задача о распределении ресурсов.
- Составление графика выполнения заданий с известными временными характеристиками.
- Задача о хранении и сбыте товара.
- Методы управления проектами.
- Распределение ресурсов в сетевых графиках проектов.
- Способы задания графов. Фундаментальные циклы и разрезы.
- Сильно связные графы. Проблемы введения на дорогах одностороннего движения. Выбор критериев оптимальности.
- Задача китайского почтальона.
- Задача коммивояжера.
- Нахождение в сетях центров и медиан.
- Оптимальный выбор места для складского помещения.
- Календарное сетевое планирование. Разложение графа без циклов на слои.
- Планирование транспортных потоков.
- Правильная раскраска графов и задача об уборке мусора.
- Правильная раскраска графов и оптимальное расписание.
- Составление оптимального расписания.
48. Нахождение остова кратчайших путей в заданной сети.
49. Поиск в глубину.
50. Поиск в ширину.
- Потоки в сетях. Простые варианты задачи о максимальном потоке. Различные обобщения (несколько источников, несколько стоков).
- Потоки в сетях. Простые варианты задачи о максимальном потоке. Различные обобщения (пропускные способности на вершинах).
- Максимальный поток между каждой парой парой вершин.
- Потоки минимальной стоимости.
- Подходы к решению о максимальных потоках в многопродуктовых сетях.
Загрузка...
