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


Скачать 24.39 Kb.
НазваниеПрограмма курса лекций «алгоритмы дискретной оптимизации»
Дата07.11.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.

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

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница