Математическое моделирование вычислительных систем

Математическое моделирование вычислительных систем
Читается на кафедрах	Кафедра математических основ управления

Программа курса (2020)

1. Задачи дискретной оптимизации, возникающие при проектировании вычислительных систем.
2. Потоки в сетях. Задача о максимальном потоке и ее решение (алгоритмы Форда–Фалкерсона и Карзанова). Разрезы. Теорема о максимальном потоке и минимальном разрезе. Задача о потоке минимальной стоимости и ее приложения (транспортная задача, задача о назначениях, задача о максимальном потоке, задачи о кратчайшем и самом длинном путях, составление графика выполнения работ при жестких директивных интервалах, задача о паросочетаниях). Алгоритм дефекта.
3. Алгоритм В.С. Танаева нахождения допустимых многопроцессорных расписаний с прерываниями. Алгоритм Э.Г. Коффмана для случая одного процессора. Учет издержек на прерывания.
4. Задачи распознавания. Детерминированные машины Тьюринга и класс P. Рекурсивные и рекурсивно перечислимые языки.
5. Недетерминированное вычисление и класс NP.
6. Полиномиальная сводимость и NP-полные задачи. Теорема Кука. Семь основных NP-полных задач (выполнимость, 3-выполнимость, трехмерное сочетание, вершинное покрытие, клика, гамильтонов цикл, разбиение). Методы доказательства NP-полноты.
7. Задачи с числовыми параметрами. Псевдополиномиальная сводимость. Сильная NP-полнота (задачи: упорядочение работ внутри интервалов, многопроцессорное расписание без прерываний, коммивояжер, упаковка в контейнеры).
8. Псевдополиномиальные алгоритмы (задачи: разбиение, рюкзак, многопроцессорное расписание без прерываний при фиксированном числе процессоров, упаковка в контейнеры при фиксированном числе контейнеров).
9. Сводимость по Тьюрингу и NP-трудные задачи (задача K-е по порядку множество). NP-эквивалентные задачи (оптимизационные варианты семи основных NP-полных задач, оптимизационная задача коммивояжера).
10. Приближенные алгоритмы решения NP-трудных задач (упаковка в контейнеры, рюкзак, коммивояжер, многопроцессорное расписание без прерываний); оценки их погрешности. Применение теории NP-полноты к отысканию приближенных решений.
11. Класс Co-NP.
12. Метод "ветвей и границ" (задачи: коммивояжер, самый длинный путь в графе, многопроцессорное расписание без прерываний для случая различных процессоров, распределение возобновляемых ресурсов).
13. Рандомизированные алгоритмы. Лемма Шварца. (Задача проверки идентичности полиномов, задача о паросочетаниях).
14. Сети Петри. Матричная форма представления. Построение конечного дерева достижимости. Моделирование вычислительных систем. Представление конечных автоматов и графов вычислений сетями Петри.

Список литературы

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
2. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
3. Теория расписаний и вычислительные машины // Под ред. Коффмана Э.Г. М.: Наука, 1984.
4. Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы. М.: Наука, 1984.
5. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.
6. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984.
7. Л. Ловас, М. Пламмер. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.
8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 1999.
9. Lovasz L. [www.ECCC.UNI-TRIER.DE/ECCC Computational Complexity].
10. Oded Goldreich. [WWW.ECCC.UNI-TRIER.DE/ECCC Introduction to Complexity Theory].

Первые преподаватели

• к.ф.-м.н., доц., Заслуженный преподаватель МФТИ М.Г. Фуругян.
• к.ф.-м.н., доцент С.П. Тарасов

Сетевые ссылки

• Программа и задание курса ММВС // на портале МФТИ.

Комментарии:

Loading comments...