Приведены и исследованы два
алгоритма решения задачи о максимальном потоке (алгоритмы
Форда-Фалкерсона и Карзанова). В качестве приложения потоковых
алгоритмов дан алгоритм планирования вычислений в многопроцессорных
вычислительных системах. Исследован алгоритм сортировки с помощью кучи.
Рассматривая в качестве модели процесса вычислений детерминированную
машину Тьюринга, введены и исследованы понятия рекурсивных и рекурсивно
перечислимых языков, сложностных классов языков и задач (P, NP, co-NP,
NPC, NPH и др.), изучена их взаимосвязь. Рассмотрены методы
доказательства NP-полноты. Даны некоторые методы решения переборных
задач (метод "ветвей и границ”, рандомизированные алгоритмы,
приближенные алгоритмы и др.) и показана возможность применения теории
NP-полноты к разработке алгоритмов решения этих задач. Приведены и
исследованы параллельные алгоритмы решения некоторых задач, связанных с
работой со списками и деревьями. Для каждого из приведенных алгоритмов
дается обоснование и определяется вычислительная сложность.

Название:
Алгоритмы и модели вычислений
Производитель: intuit.ru
Автор:
М.Г. Фуругян
Год выпуска: 2009
Язык: русский
Продолжительность:
~17 часов (13 лекций)
Уровень: для специалистов

Файл:
Качество:
WEBRIP
Видео: VP6, 480x360 (4:3), 25 fps, 400 kbps
Аудио:
MP3, 44.1 kHz, 96 kbps, stereo
Размер: 4 Gb

Список
лекций
1. Потоки в сетях
Основные понятия (сеть, поток и его
величина, разрез и его величина, увеличивающий путь , остаточная сеть).
Алгоритм Форда-Фалкерсона решения задачи о максимальном потоке.
Асимптотические обозначения.

2. Потоки в сетях (продолжение)
Теорема
о максимальном потоке и минимальном разрезе. Алгоритм Карзанова решения
задачи о максимальном потоке.

3. Приложение потоковых
алгоритмов. Алгоритмы сортировки
Сведение задачи построения
многопроцессорного расписания с прерываниями при заданных длительностях
работ и директивных интервалах к задаче о максимальном потоке. Понятие
кучи. Сортировка массива с помощью кучи.

4. Распознающие
алгоритмы. Класс P
Задачи распознавания свойств и языки.
Детерминированная одноленточная машина Тьюринга. Рекурсивные и
рекурсивно перечислимые языки. Полиномиально распознаваемые языки и
класс P.

5. Проверяющие алгоритмы. Классы NP и NPC
Класс NP.
Соотношение между классами P и NP. Существование экспоненциального
проверяющего алгоритма для языков из NP. Полиномиальная сводимость.
Класс NPC. Способы доказательства NP-полноты.

6. Семь основных
NP-полных задач
Доказательство NP-полноты задач выполнимость и
3-выполнимость.

7. NP-полнота некоторых задач. Класс co-NP
Доказательство
NP-полноты задач вершинное покрытие, клика, расписание без прерываний
для многопроцессорной системы. Класс co-NP. Структура классов NP и
co-NP.

8. Сильная NP-полнота
Задачи с числовыми параметрами.
Псевдополиномиальные алгоритмы. Сильная NP-полнота и методы ее
доказательства. Псевдополиномиальный алгоритм решения задачи о
разбиении. Сильная NP-полнота задачи расписание без прерываний для
многопроцессорной системы.

9. NP-трудные и NP-легкие задачи.
Приближенные алгоритмы
Сводимость по Тьюрингу. Доказательство
NP-трудности и NP-легкости некоторых задач. Приближенные алгоритмы
(решения задач упаковка в контейнеры и расписание без прерываний для
многопроцессорной системы) и оценки их погрешности.

10.
Применение теории NP-полноты к разработке приближенных алгоритмов
Невозможность
существования полиномиального приближенного алгоритма с фиксированной
погрешностью для некоторых NP-трудных задач. Приближенный полиномиальный
алгоритм решения задачи коммивояжера с неравенством треугольника.

11.
Метод "ветвей и границ". Рандомизированные алгоритмы
Общее описание
метода "ветвей и границ" и его реализация для решения задачи расписание
без прерываний для многопроцессорной системы. Рандомизированный алгоритм
решения задачи об идентичности полиномов и задачи о паросочетаниях.

12.
Алгоритмы параллельных вычислений
EREW-алгоритмы решения задач
определения номера элемента в списке, параллельная обработка префиксов,
вычисление глубины вершины в двоичном дереве. CRCW-алгоритм решения
задачи определения корня для вершины двоичного леса.

13.
Алгоритмы параллельных вычислений (продолжение)
CRCW-алгоритм
нахождения максимального элемента в массиве. Моделирование CRCW-машины с
помощью EREW-машины. Эффективная параллельная обработка префиксов.