Приведены и исследованы два алгоритма решения задачи о максимальном потоке (алгоритмы Форда-Фалкерсона и Карзанова). В качестве приложения потоковых алгоритмов дан алгоритм планирования вычислений в многопроцессорных вычислительных системах. Исследован алгоритм сортировки с помощью кучи. Рассматривая в качестве модели процесса вычислений детерминированную машину Тьюринга, введены и исследованы понятия рекурсивных и рекурсивно перечислимых языков, сложностных классов языков и задач (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-машины. Эффективная параллельная обработка префиксов.

Скачать Видеоурок Алгоритмы и модели вычислений - Intuit.ru (2009) WEBRIP + UA-IX

Letitbit.net Часть 1
Letitbit.net Часть 2
Letitbit.net Часть 3

Turbobit.net Часть 1
Turbobit.net Часть 2
Turbobit.net Часть 3