Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

Московский физико-технический институт

(государственный университет)

 

 

УТВЕРЖДАЮ

    Проректор по учебной работе

                         Ю.А. Самарский

      «____»_____________2003 г.

 

 

П Р О Г Р А М М А

по курсу: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ   ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

по направлению            511600

факультет                   ФУПМ

кафедра математических основ управления

курс III

семестр 6

лекции 32 часа             Экзамен – нет

семинары 32 часа     Зачет с оценкой – 6 семестр

лабораторные занятия – нет.

самостоятельная работа – 2 часа в неделю

ВСЕГО ЧАСОВ  64

 

Программу и задание составили:  доц.  С.П. Тарасов,

                                                      доц.  М.Г. Фуругян

 

Программа утверждена на заседании кафедры математических основ управления 17 сентября 2003 г.

 

Заведующий кафедрой _____________С.А. Гуз

 

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. Computational Complexity.

WW.ECCC.UNI-TRIER.DE/ECCC.

10. Oded Goldreich. Introduction to Complexity Theory. WWW.ECCC.UNI-TRIER.DE/ECCC.

З А Д А Н И Е 

1. С помощью алгоритма Форда-Фалкерсона найти максимальный поток из  s в t в сети с дугами     (s, 1),  (s, 2), (s, 3), (1,2), (1, t), (2, 3), (2, t), (3, t),  пропускные способности которых равны 2, 3, 1, 4, 3, 1, 2, 2  соответственно.

2. Рассмотрим сеть с несколькими источниками и несколькими стоками, в которой каждый источник si производит ровно pi единиц потока, а каждый сток tj потребляет ровно qj единиц, при этом  \sum{p_{i}}= \sum{q_{j}} . Описать алгоритм, проверяющий, возможен ли поток с такими ограничениями?

3. С помощью алгоритма Карзанова найти максимальный поток из s в t в сети из задачи 1.

4. Определить вычислительную сложность алгоритма Карзанова. Является ли этот алгоритм полиномиальным?

5. С помощью алгоритма дефекта найти поток минимальной стоимости в сети G=(V, A), V = {1, 2, 3, 4}, A   =   {(1,2), (1,3), (2,3), (2,4), (3,2), (3,4), (4,1)}. Параметры дуг (Lij, Uij, cij) следующие: (0,2,2), (0,4,5), (0,1,1), (0,4,3), 0,1,1), (1,2,6), (3,3,0).

6. Построить допустимое расписание (с прерываниями) выполнения трех заданий на двух одинаковых процессорах. Директивные интервалы и длительности заданий следующие: [b1, f1] = [0, 6], [b2,f2] = [0, 3], [b3, f3] = [1, 6], t1   =   5, t2 = 3, t3 = 4. (Решить данную задачу путем сведения ее к задаче о максимальном потоке.)

7. Является ли язык L = {< M > | M - такая машина Тьюринга, что если она останавливается, то использует при этом не более 50 первых ячеек ленты} рекурсивным? Здесь < M > - описание машины Тьюринга  M.

8. Верно ли, что всякий язык L принадлежащий   NP   является рекурсивно перечислимым? Будет ли он рекурсивным?  

9. Верно ли, что задача проверки непланарности графа лежит в NP? (Граф называется непланарным, если он не может  быть изображен на плоскости так, что никакие две его дуги не пересекаются.)

10. Верно ли, что в co - NP есть полные языки?

     В задачах 11 -  29  все числовые параметры  предполагаются натуральными. В задачах  11 - 17   определить, принадлежат ли соответствующие языки классам NP или co - NP . Если  язык принадлежит NP , определить, является ли он NP -полным.

11.  Упаковка множеств. Заданы семейство C конечных множеств и число K, K<= | C|. Верно ли, что в C имеется K непересекающихся множеств?

12.  Наибольший общий подграф. Заданы два графа G1  = (V1, E1),   G= (V2, E2 и    число  K.  Существуют  ли   

такие   подмножества E' принадлежащее E1 и E'2 принадлежащее E2 , что / E'1 / = / E'2 / >= K, а подграфы  G'1 = (V'1, E'1) и G'= (V'2, E'2)  изоморфны?

13.  Доминирующее    множество.    Заданы    граф      G = (V, E) и число K <=| V|. Существует ли такое подмножество V'  принадлежащее   V, что |V'|  <= K и каждая вершина v принадлежащая V\V' соединена ребром по крайней мере с одной вершиной из V' ?

14.  Минимум суммы квадратов. Заданы конечное множество N, размер si для каждого i принадлежащего N и число K. Верно ли, что заданное разбиение множества N   на K  непересекающихся подмножеств N1, ..., NK имеет минимальный вес  \sum\limits_{j=1}^{K}(\sum\limits_{i\in N_j}s_i)^2 среди разбиений N на K непересекающихся подмножеств?

15. Паросочетание. Задан двудольный граф G и число K . Верно ли, что в G существует K  непересекающихся по вершинам ребер (паросочетание мощности K)?

16.  Упаковка в контейнеры. Заданы конечное множество N  предметов, размер v i каждого предмета i \in N, вместимость V контейнера и число K. Существует ли такое разбиение множества N на непересекающиеся подмножества N1, ..., NK , что

\sum\limits_{i\in N_j}v_i  <= V    для всех j=1....K?

17. Интеграл от произведения косинусов. Задана последовательность  чисел a1, a2, ..., an . Верно ли, что 

\int\limits_0^{2\pi}(\sum\limits_{i=1}^{k}cos(a_ix))dx=0 ?

Для задач 18, 19 описать

псевдополиномиальные алгоритмы.

18.  Рюкзак.   Заданы конечное множество предметов N, стоимости si , размеры vi для всех i \inN, числа V и S. Существует ли подмножество M принадлежащее N, такое, что  \sum\limits_{i\in N} v_i <= V , \sum\limits_{i\in N} s_i <= S ?  Найти это подмножество M (если оно существует). Вычислительная сложность алгоритма O(/N/×min{V,S}), требуемая память O(/N/× min{V,S}) .

19. Упаковка в контейнеры    (задача 16)   в  предположении, что число контейнеров K - фиксировано. Найти требуемое разбиение (если оно существует). Вычислительная сложность алгоритма O(VK ).

20. Доказать сильную NP-полноту задачи многопроцессорное расписание без прерываний . (Заданы конечное множество заданий  N, число одинаковых процессоров  m, длительность  ti  для каждого i \in N и общий директивный срок  D. Существует ли  m-процессорное расписание без прерываний для заданий из  N, которое удовлетворяет общему директивному сроку  D?)

Описать алгоритмы решения задач 21 - 22,

основанные на  методе " ветвей и границ " .

21.  Минимаксная задача теории расписаний. Заданы конечное множество заданий N, m процессоров различной производительности, длительность tij выполнения задания     i   \in   N на процессоре j. Построить оптимальное по быстродействию расписание (без прерываний) выполнения заданий N.

22.  Самый длинный путь. Заданы ориентированный граф G=(V,E),   длины его дуг dij >= 0(i,j) \in E, и вершины s \in V , t \in V.  Найти простой путь из  s  в  t, сумма длин дуг которого максимальная.

23. Доказать, что "жадный" алгоритм построения максимального остовного дерева в графе даёт оптимальное решение.

Для задач 24, 25 описать полиномиальные

 приближенные алгоритмы с оценкой r <= 2.

(Алгоритм имеет оценку r <= K  (r2 <=K ), если стоимости находимых им решений не более чем в K раз (не более чем на K ) отличаются от стоимостей оптимальных решений.)

24.  Минимаксная задача теории расписаний , в которой длительность выполнения задания i \in N на каждом процессоре равна ti .

25. Оптимизационный вариант задачи вершинное покрытие (найти вершинное покрытие в графе, содержащее наименьшее число вершин).

26. Доказать, что если P <> NP, то не существует полиномиальных приближенных алгоритмов решения оптимизационной задачи коммивояжера с оценками r <= K, r <= K, где  K - константа.

27. Доказать, что задача нахождения 3-мерного сочетания является NP-трудной и NP-лёгкой.

28. Доказать, что если Р = NP, то для оптимизационной задачи коммивояжёра существует полиномиальный алгоритм.

29. С помощью сети Петри разработать алгоритм генерации допустимых расписаний в задаче   оптимального распределения возобновляемых ресурсов (Заданы конечное множество заданий N, частичный порядок их выполнения в виде графа G=(N,A) (если (i,j) \in A, то задание j может быть начато только после окончания выполнения задания i), длительность ti для каждого задания i \in N, число видов возобновляемых ресурсов K, запасы ресурсов Rj (j=1, ..., K) и потребности rij задания i \in N в ресурсах j-го типа. Построить оптимальное по быстродействию расписание выполнения заданий N без прерываний, при котором не нарушаются отношения предшествования (граф G) и ограничения на ресурсы (в каждый момент времени t   \sum r_{ij} <=Rj  (j=1, ..., K), где сумма берется по всем заданиям i   \in   N, которые выполняются в момент времени t.)

 

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика