Алгоритмы и модели вычислений

Описание курса

Курс предлагает подборку видеоматериалов лекций, семинаров и конференций по интернет-технологиям и включает в себя следующие вопросы:

1. Основные понятия (сеть, поток и его величина, разрез и его величина, увеличивающий путь , остаточная сеть). Алгоритм Форда-Фалкерсона решения задачи о максимальном потоке. Асимптотические обозначения.
2. Теорема о максимальном потоке и минимальном разрезе. Алгоритм Карзанова решения задачи о максимальном потоке.
3. Приложение потоковых алгоритмов. Алгоритмы сортировки. Сведение задачи построения многопроцессорного расписания с прерываниями при заданных длительностях работ и директивных интервалах к задаче о максимальном потоке. Понятие кучи. Сортировка массива с помощью кучи.
4. Задачи распознавания свойств и языки. Детерминированная одноленточная машина Тьюринга. Рекурсивные и рекурсивно перечислимые языки. Полиномиально распознаваемые языки и класс P.
5. Класс NP. Соотношение между классами P и NP. Существование экспоненциального проверяющего алгоритма для языков из NP. Полиномиальная сводимость. Класс NPC. Способы доказательства NP-полноты.
6. Доказательство NP-полноты задач выполнимость и 3-выполнимость.
7. Доказательство NP-полноты задач вершинное покрытие, клика, расписание без прерываний для многопроцессорной системы. Класс co-NP. Структура классов NP и co-NP.
8. Задачи с числовыми параметрами. Псевдополиномиальные алгоритмы. Сильная NP-полнота и методы ее доказательства. Псевдополиномиальный алгоритм решения задачи о разбиении. Сильная NP-полнота задачи расписание без прерываний для многопроцессорной системы.
9. Сводимость по Тьюрингу. Доказательство NP-трудности и NP-легкости некоторых задач. Приближенные алгоритмы (решения задач упаковка в контейнеры и расписание без прерываний для многопроцессорной системы) и оценки их погрешности
10. Невозможность существования полиномиального приближенного алгоритма с фиксированной погрешностью для некоторых NP-трудных задач. Приближенный полиномиальный алгоритм решения задачи коммивояжера с неравенством треугольника.
11. Общее описание метода "ветвей и границ" и его реализация для решения задачи расписание без прерываний для многопроцессорной системы. Рандомизированный алгоритм решения задачи об идентичности полиномов и задачи о паросочетаниях.
12. EREW-алгоритмы решения задач определения номера элемента в списке, параллельная обработка префиксов, вычисление глубины вершины в двоичном дереве. CRCW-алгоритм решения задачи определения корня для вершины двоичного леса.
13. CRCW-алгоритм нахождения максимального элемента в массиве. Моделирование CRCW-машины с помощью EREW-машины. Эффективная параллельная обработка префиксов.

Что будет изучено

см. выше

Требования к обучаемому

Курс рассчитан на студентов ВУЗов, в учебном плане которых предусмотрена такая учебная дисциплина как "Менеджмент" и для пользователей широкого круга, изучающих секреты менеджмента для самообразования.