Математическое моделирование вычислительных систем
Материал из ВикиФизтех
Версия от 15:55, 31 марта 2020; imported>Дмитрий Русланович Гончар
Математическое моделирование вычислительных систем | |
---|---|
Читается на кафедрах | Кафедра математических основ управления |
Программа курса (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].
Первые преподаватели[править | править код]
- к.ф.-м.н., доц., Заслуженный преподаватель МФТИ М.Г. Фуругян.
- к.ф.-м.н., доцент С.П. Тарасов
Сетевые ссылки[править | править код]
- Программа и задание курса ММВС // на портале МФТИ.
Комментарии:
Loading comments...