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

{{Предмет
|Читается на кафедрах=Кафедра математических основ управления,
}}

== Программа курса (2020) ==
# Задачи дискретной оптимизации, возникающие при проектировании вычислительных систем.
# Потоки в сетях. Задача о максимальном потоке и ее решение (алгоритмы Форда–Фалкерсона и Карзанова). Разрезы. Теорема о максимальном потоке и минимальном разрезе. Задача о потоке минимальной стоимости и ее приложения (транспортная задача, задача о назначениях, задача о максимальном потоке, задачи о кратчайшем и самом длинном путях, составление графика выполнения работ при жестких директивных интервалах, задача о паросочетаниях). Алгоритм дефекта.
# Алгоритм В.С. Танаева нахождения допустимых многопроцессорных расписаний с прерываниями. Алгоритм Э.Г. Коффмана для случая одного процессора. Учет издержек на прерывания.
# Задачи распознавания. Детерминированные машины Тьюринга и класс P.  Рекурсивные и рекурсивно перечислимые языки.
# Недетерминированное вычисление и класс NP.
# Полиномиальная сводимость и NP-полные задачи. Теорема Кука. Семь основных NP-полных задач (выполнимость, 3-выполнимость, трехмерное сочетание, вершинное покрытие, клика, гамильтонов цикл, разбиение). Методы доказательства NP-полноты.
# Задачи с числовыми параметрами. Псевдополиномиальная сводимость. Сильная NP-полнота (задачи: упорядочение работ внутри интервалов, многопроцессорное расписание без прерываний, коммивояжер, упаковка в контейнеры).
# Псевдополиномиальные алгоритмы (задачи: разбиение, рюкзак, многопроцессорное расписание без прерываний   при фиксированном числе процессоров, упаковка в контейнеры при фиксированном числе контейнеров).
# Сводимость по Тьюрингу и NP-трудные задачи (задача K-е по порядку множество). NP-эквивалентные задачи (оптимизационные варианты семи основных NP-полных задач, оптимизационная задача коммивояжера).
# Приближенные алгоритмы решения NP-трудных задач (упаковка в контейнеры, рюкзак, коммивояжер, многопроцессорное расписание без прерываний); оценки их погрешности. Применение теории NP-полноты к отысканию приближенных решений.
# Класс Co-NP.
# Метод "ветвей и границ" (задачи: коммивояжер, самый длинный путь в графе,  многопроцессорное расписание без прерываний для случая различных процессоров, распределение возобновляемых ресурсов).
# Рандомизированные алгоритмы. Лемма Шварца. (Задача проверки идентичности полиномов, задача о паросочетаниях).
# Сети Петри. Матричная форма представления. Построение конечного дерева достижимости. Моделирование вычислительных систем. Представление конечных автоматов и графов вычислений сетями Петри.
 
== Список литературы ==
# ''Гэри М., Джонсон Д.'' Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
# ''Пападимитриу Х., Стайглиц К.'' Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
# Теория расписаний и вычислительные машины // Под ред. Коффмана Э.Г. М.: Наука, 1984.
# ''Танаев В.С., Гордон В.С., Шафранский Я.М.'' Теория расписаний. Одностадийные системы. М.: Наука, 1984.
# ''Питерсон Дж.'' Теория сетей Петри и моделирование систем. М.: Мир, 1984.
# ''Филлипс Д., Гарсиа-Диас А.'' Методы анализа сетей. М.: Мир, 1984.
# ''Л. Ловас, М. Пламмер''. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.
# ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы. Построение и анализ. М.: МЦНМО, 1999.
# ''Lovasz L''. [www.ECCC.UNI-TRIER.DE/ECCC Computational Complexity].
# ''Oded Goldreich''. [WWW.ECCC.UNI-TRIER.DE/ECCC Introduction to Complexity Theory].

== Первые преподаватели ==
* к.ф.-м.н., доц., Заслуженный преподаватель МФТИ [[Фуругян Меран Габибуллаевич|М.Г. Фуругян]].
* к.ф.-м.н., доцент [[Тарасов Сергей Павлович|С.П. Тарасов]]

== Сетевые ссылки ==
* [https://mipt.ru/dcam/students/curriculum/prog/discrcs/mmvs.php Программа и задание курса ММВС] // на портале МФТИ.
{{комментарии}}