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

Материал из викиФизтех

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Математическое моделирование вычислительных систем
Читается на кафедрах Кафедра математических основ управления


Программа курса (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].

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

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

Комментарии

Перейти к форме добавления комментария


Добавить комментарий
На сайте {{SITENAME}} комментарии можно оставлять всем. Если Вы не хотите оставаться анонимным, зарегистрируйтесь или представьтесь. Это бесплатно.