Автор: Меран Фуругян | Московский физико-технический институт
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Специалист
Длительность:
24:21:00
Студентов:
1377
Выпускников:
20
Качество курса:
5.00 | 4.80
Рассматриваются некоторые теоретические проблемы, возникающие при разработке математического обеспечения вычислительных систем. Изучаются такие фундаментальные проблемы, как теория потоков в сетях, анализ сложности алгоритмов и сложности дискретных задач. Рассмотрены методы решения переборных задач. Даны алгоритмы решения некоторых задач на параллельной машине с произвольным доступом.
Приведены и исследованы два алгоритма решения задачи о максимальном потоке (алгоритмы Форда-Фалкерсона и Карзанова). В качестве приложения потоковых алгоритмов дан алгоритм планирования вычислений в многопроцессорных вычислительных системах. Исследован алгоритм сортировки с помощью кучи. Рассматривая в качестве модели процесса вычислений детерминированную машину Тьюринга, введены и исследованы понятия рекурсивных и рекурсивно перечислимых языков, сложностных классов языков и задач (P, NP, co-NP, NPC, NPH и др.), изучена их взаимосвязь. Рассмотрены методы доказательства NP-полноты. Даны некоторые методы решения переборных задач (метод “ветвей и границ”, рандомизированные алгоритмы, приближенные алгоритмы и др.) и показана возможность применения теории NP-полноты к разработке алгоритмов решения этих задач. Приведены и исследованы параллельные алгоритмы решения некоторых задач, связанных с работой со списками и деревьями. Для каждого из приведенных алгоритмов дается обоснование и определяется вычислительная сложность.
Специальности: Программист
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 39 минут
Потоки в сетях
Основные понятия (сеть, поток и его величина, разрез и его величина, увеличивающий путь , остаточная сеть). Алгоритм Форда-Фалкерсона решения задачи о максимальном потоке. Асимптотические обозначения.
-
Лекция 3
1 час 33 минуты
Приложение потоковых алгоритмов. Алгоритмы сортировки
-
Лекция 5
1 час 39 минут
Проверяющие алгоритмы. Классы NP и NPC
Класс NP. Соотношение между классами P и NP. Существование экспоненциального проверяющего алгоритма для языков из NP. Полиномиальная сводимость. Класс NPC. Способы доказательства NP-полноты.
-
Лекция 8
1 час 31 минута
Сильная NP-полнота
Задачи с числовыми параметрами. Псевдополиномиальные алгоритмы. Сильная NP-полнота и методы ее доказательства. Псевдополиномиальный алгоритм решения задачи о разбиении. Сильная NP-полнота задачи расписание без прерываний для многопроцессорной системы.
-
Лекция 9
1 час 35 минут
NP-трудные и NP-легкие задачи. Приближенные алгоритмы
Сводимость по Тьюрингу. Доказательство NP-трудности и NP-легкости некоторых задач. Приближенные алгоритмы (решения задач упаковка в контейнеры и расписание без прерываний для многопроцессорной системы) и оценки их погрешности.
-
1 час 40 минут
-
Олег Дудник
Олег Дудник
Украина, Киев
Сергей Катревич
Сергей Катревич
Россия, Москва