НОУ ИНТУИТ | Повышение квалификации | Алгоритмы и модели вычислений

Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 490.00 руб. | Длительность: 14 дней

Темы: Теория вычислений, Программирование, Алгоритмы и дискретные структуры, Дискретные структуры, Алгоритмы

Рассматриваются некоторые теоретические проблемы, возникающие при разработке математического обеспечения вычислительных систем. Изучаются такие фундаментальные проблемы, как теория потоков в сетях, анализ сложности алгоритмов и сложности дискретных задач. Рассмотрены методы решения переборных задач. Даны алгоритмы решения некоторых задач на параллельной машине с произвольным доступом.

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

Вам нравится? Нравится 2 студентам

| Поделиться |

Поддержать

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

Авторизоваться

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

План занятий