Программа курса «Построение и анализ алгоритмов»

Скачать 16.61 Kb.

Название	Программа курса «Построение и анализ алгоритмов»
Дата публикации	14.03.2015
Размер	16.61 Kb.
Тип	Программа курса

100-bal.ru > Информатика > Программа курса

Программа курса

«Построение и анализ алгоритмов»

(МГ-1 МОКН+ФИИТ)

Элементы теории сложности. Основные классы временнóй сложности алгоритмов, решающих полиномиальные задачи. Сертификаты и определение класса NP. Полиномиальная сводимость и NP-полные задачи. Примеры NP-полных задач для графов, множеств, чисел. Класс Co-NP и его пересечение с NP. Полиномиальная иерархия и класс PSPACE. QSAT, задача планирования и война провайдеров.
Базовые алгоритмы на графах. Сравнение видов представления графов. Сравнение стратегий поиска. Алгоритм Тарьяна разбиения орграфа на компоненты сильной связности.
Жадные алгоритмы. Основной принцип и выбор параметра. Методы доказательства корректности. Интервальные расписания. Оптимальное кеширование. Алгоритмы Дейкстры, Краскла и Хаффмана как примеры жадных алгоритмов.
Алгоритмы Разделяй-и-властвуй. Основные виды возникающих рекуррентных соотношений и соответствующие оценки сложности алгоритма. Сортировка слиянием и подсчет числа инверсий в перестановке. Ближайшая пара точек на плоскости. Умножение целых чисел. Вычисление конволюций и быстрое преобразование Фурье.
Динамическое программирование. Основные принципы и рекуррентные соотношения. Взвешенное интервальное расписание. Приближение множества точек ломаной по МНК. Сумма подмножеств и задача о рюкзаке. Выравнивание строк (включая алгоритм, работающий в линейном пространстве). Алгоритм Форда-Беллмана как пример динамического программирования.
Потоки и их применение. Сведение задач к задаче о максимальном потоке / минимальном разрезе: непересекающиеся пути в графах, циркуляции, составление опросников, расписание авиалиний, разделение изображения и фона.
Полиномиально разрешимые случаи NP-трудных задач. Маленькие вершинные покрытия. Независимые множества на деревьях. Интервальная раскраска на окружности.
Приближенные алгоритмы. Использование жадных эвристик: задача о выравнивании нагрузки и выбор центров. Метод оценивания: задачи о покрытии множествами и вершинном покрытии. Линейное программирование в задачах о вершинном покрытии и о выравнивании нагрузки. Классы трудных задач по приближаемости: APX, PTAS, FPTAS. FPTAS для задачи о рюкзаке.
Вероятностные алгоритмы. Задачи о конфликтном доступе (агенты и центр). Реберная связность. MAX-3-SAT. Выбор k-го сверху значения в несортированном массиве. Рандомизированное хэширование. Граница Чернова и максимальное число элементов в ячейке хэш-таблицы.

Добавить документ в свой блог или на сайт

Похожие:

	Программа дисциплины «Построение и анализ алгоритмов» Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений подготовки 231000....		Программа по формированию навыков безопасного поведения на дорогах... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 231000....
	Программа по формированию навыков безопасного поведения на дорогах... Тема: Понятие алгоритмов, свойства алгоритма. Исполнители алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...		План-конспект урока алгоритм. Свойства алгоритмов. Виды алгоритмов. Формы записи алгоритмов Преподавание алгебры в 7 классе ведётся по умк «Алгебра 7 класс» под редакцией А. Г. Мордковича. Учебное пособие для изучения курса...
	Конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов... ...		Программа по формированию навыков безопасного поведения на дорогах... Такое построение курса позволяет в полной мере использовать в обучении операции мышления: анализ и синтез, сравнение и аналогию,...
	Программа по формированию навыков безопасного поведения на дорогах... Иметь представление об алгоритмах, свойствах алгоритмов и записи алгоритмов. Приводить примеры алгоритмов из жизни. Применять готовые...		Урок по информатике по теме «Методика обучения сортировке одномерного массива» Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом прямого выбора и методом пузырька;...
	Название курса Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики...		Конспект по теме «Алгоритмы» Цель урока: дать учащимся понятие алгоритма, изучить свойства алгоритмов, применение алгоритмов в жизнедеятельности человека
	Урок 18 построение циркулем и линейкой. Примеры задач на построение цели Цели: дать представление о новом классе задач – построение геометрических фигур с помощью циркуля и линейки без масштабных делений...		Программа по формированию навыков безопасного поведения на дорогах... Урок 50. Анализ контрольной работы. Алгоритм — модель деятельности исполнителя алгоритмов
	Типы алгоритмов. Алгоритмы с повторениями ...		Вопросы к экзамену по дисциплине «Основы конструирования и моделирования костюма» Расчет и построение базовой конструкции плечевой одежды (спинка, перед). Построение базисной сетки
	Конспект урока литературы по теме Построение парами. Переход на площадку. Построение в шеренгу. В центре площадки ребята образуют круг и делятся на две команды		Конспект урока математики в 3 классе Построение парами. Переход на площадку. Построение в шеренгу. В центре площадки ребята образуют круг и делятся на две команды

Школьные материалы