Программа курса лекций «алгоритмы дискретной оптимизации»




Скачать 24.39 Kb.
НазваниеПрограмма курса лекций «алгоритмы дискретной оптимизации»
Дата03.10.2012
Размер24.39 Kb.
ТипПрограмма курса
Программа курса лекций

«АЛГОРИТМЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ»

Лектор: ГАШКОВ С.Б.


1.Основные структуры данных

Простейшие структуры данных: массивы и односвязные списки. Двусвязные списки. Кольцевые списки. Алгоритмы вставки и удаления за константное время для списков. Стеки и их организация с помощью списков и массивов. Алгоритмы вставки и удаления за константное время. Применение стеков для вычисления последовательности операций в обратной польской записи в языке Postscript. Очереди и деки (двусторонние очереди). Их организация с помощью списков и массивов. Алгоритмы вставки и удаления за константное время.


2.Очереди с приоритетами и сортировка

Равномерные бинарные деревья. Очереди с приоритетами ("пирамиды", "кучи"). Алгоритмы изменения приоритета у элемента "кучи" ("всплытие" и "утопление"). Алгоритмы вставки произвольного и удаления максимального элементов "кучи" за логарифмическое время. Алгоритм создания "кучи" за линейное время. Сортировка массивов. Нижняя оценка времени сортировки. Пирамидальная сортировка с временем O(n\log n) в худшем случае.


3.Кратчайшие пути и стягивающие деревья

Минимальные остовные деревья. Алгоритмы Краскала и Прима. Реализация алгоритма Прима за квадратичное время. Реализация алгоритма Прима с помощью очереди с приоритетами за время O(E\log V). Равномерные m-арные деревья. Организация на их основе очередей с приоритетами. Реализация алгоритма Прима за время O(E\log_d V), где d = E/V. Кратчайшие пути. Деревья кратчайших путей. Алгоритм Дейкстры для графов с неотрицательными весами ребер. Реализация алгоритма Дейкстры за время O(E\log_d V), где E/V. Биномиальные кучи и тонкие кучи. Их применение к реализации алгоритмов Прима и Дейкстры. Алгоритм Флойда вычисления кратчайших путей между всеми парами вершин для графов с произвольными весами ребер за кубическое время. Алгоритм нахождения диаметра и радиуса графа. Алгоритм Уоршелла вычисления транзитивного замыкания графа за кубическое время. Алгоритм вычисления транзитивного замыкания графа с помощью быстрого матричного умножения и аддитивных цепочек.


4.Поиск в глубину и в ширину

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


5.Универсальные переборные задачи

Детерминированные и недетерминированные машины Тьюринга. Временная сложность вычисления на машинах Тьюринга. Языки и проблема распознавания принадлежности слова данному языку. Классы P и NP. Полиномиальная сводимость. NP – полные задачи. NP – полнота задачи выполнимости КНФ и ее интерпретация в виде "карточного пасьянса". NP –полнота задач о вершинном покрытии ребер графа, клике, независимом множестве и изоморфизме подграфу. NP  – полнота задачи о 3-выполнимости. Задача коммивояжера и метод ветвей и границ. Приближенные методы решения $NP$-полных задач. Градиентные алгоритмы.


ЛИТЕРАТУРА:

  1. Седжевик Р. Фундаментальные алгоритмы на С++, ч.1-5. ДиаСофт 2002.

  2. Кормен Т., Лейзерсон Ч., Райвест Р. Алгоритмы: построение и анализ. Любое издание.

  3. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. Любое издание.

  4. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Мир, 1985.

  5. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. Бином, 2006.

Похожие:

Программа курса лекций «алгоритмы дискретной оптимизации» iconБ. Ф. Мельников Тольяттинский государственный университет
Данные комбинации эвристик представляют собой специальный поход к построению anytime-алгоритмов для задач дискретной оптимизации
Программа курса лекций «алгоритмы дискретной оптимизации» iconПопков В. К., Токтошов Г. Ы. Методологические вопросы оптимизации инженерных сетей на неоднородной территории
Демин Н. С., Рожкова С. В., Рожкова О. В. Информационный анализ в совместной задаче непрерывно-дискретной фильтрации и обобщенной...
Программа курса лекций «алгоритмы дискретной оптимизации» iconПрограмма курса лекций (2 курс, 3 сем., 36 ч., экзамен) 4 Литература 6 ЭВМ в планировании и обработке физического эксперимента (2 курс, 3 сем., 72 ч., диф зачёт) 8 Программа курса лекций (36 часов) 8
Булева Алгебра. Основные аксиомы и теоремы. Диаграммы Вейча. Карты Карно. Применение при проектировании и анализе работы ЭВМ
Программа курса лекций «алгоритмы дискретной оптимизации» iconПрограмма курса лекций для студентов специальности «История»
Цель курса лекций – дать студентам, специализирующимся на отечественной истории, представление о процессе становления и развития...
Программа курса лекций «алгоритмы дискретной оптимизации» iconПрограмма по алгебре и дискретной математике по направлению
Магистерская программа будет реализовываться кафедрой алгебры и дискретной математики Ургу (кадм) с привлечением научных сотрудников...
Программа курса лекций «алгоритмы дискретной оптимизации» iconУчебно-методический комплекс «Биологическая химия»
«биохимия». В состав разработки включены: программа курса лекций, структура курса, приведены примеры контрольных вопросов по материалам...
Программа курса лекций «алгоритмы дискретной оптимизации» iconМетодические указания по выполнению контрольной работы №1 по дисциплине Информатика На тему: Линейные алгоритмы. Разветвляющиеся алгоритмы для студентов II курса заочного отделения специальности
Контрольная работа — это самостоятельная работа студента по дисциплине «Информатика»
Программа курса лекций «алгоритмы дискретной оптимизации» iconКонспект лекций по дисциплине «Методы и алгоритмы оценки надежности»
Рыбинская государственная авиационная технологическая академия имени П. А. Соловьева
Программа курса лекций «алгоритмы дискретной оптимизации» iconМ. Ю. Богатырев Тульский государственный университет
Благодаря им, возможности решения сложных, например, np полных задач оптимизации существенно расширились, что делает эволюционные...
Программа курса лекций «алгоритмы дискретной оптимизации» iconКурс 4 семестр Преподаватели: Соболева Марина Леонидовна, доцент кафедры теоретической информатики и дискретной математики Алфимова Анастасия Сергеевна, старший преподаватель кафедры теоретической информатики и дискретной математики
Алфимова Анастасия Сергеевна, старший преподаватель кафедры теоретической информатики и дискретной математики
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница