Программа курса лекций «алгоритмы дискретной оптимизации»
Скачать 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), где d = E/V. Биномиальные кучи и тонкие кучи. Их применение к реализации алгоритмов Прима и Дейкстры. Алгоритм Флойда вычисления кратчайших путей между всеми парами вершин для графов с произвольными весами ребер за кубическое время. Алгоритм нахождения диаметра и радиуса графа. Алгоритм Уоршелла вычисления транзитивного замыкания графа за кубическое время. Алгоритм вычисления транзитивного замыкания графа с помощью быстрого матричного умножения и аддитивных цепочек. 4.Поиск в глубину и в ширину Поиск в глубину и его дерево. Использование стека при организации поиска в глубину за линейное время. Вычисление связных компонент, нахождение цикла, распознавание двудольности, топологическая сортировка за линейное время. Поиск в ширину и использование очереди при его организации за линейное время. Дерево поиска в ширину как дерево кратчайших путей в графе с единичными весами ребер. 5.Универсальные переборные задачи Детерминированные и недетерминированные машины Тьюринга. Временная сложность вычисления на машинах Тьюринга. Языки и проблема распознавания принадлежности слова данному языку. Классы P и NP. Полиномиальная сводимость. NP – полные задачи. NP – полнота задачи выполнимости КНФ и ее интерпретация в виде "карточного пасьянса". NP –полнота задач о вершинном покрытии ребер графа, клике, независимом множестве и изоморфизме подграфу. NP – полнота задачи о 3-выполнимости. Задача коммивояжера и метод ветвей и границ. Приближенные методы решения $NP$-полных задач. Градиентные алгоритмы. ЛИТЕРАТУРА:
|
Похожие:
 | Б. Ф. Мельников Тольяттинский государственный университет Данные комбинации эвристик представляют собой специальный поход к построению anytime-алгоритмов для задач дискретной оптимизации | | Попков В. К., Токтошов Г. Ы. Методологические вопросы оптимизации инженерных сетей на неоднородной территории Демин Н. С., Рожкова С. В., Рожкова О. В. Информационный анализ в совместной задаче непрерывно-дискретной фильтрации и обобщенной... |
| Программа курса лекций (2 курс, 3 сем., 36 ч., экзамен) 4 Литература 6 ЭВМ в планировании и обработке физического эксперимента (2 курс, 3 сем., 72 ч., диф зачёт) 8 Программа курса лекций (36 часов) 8 Булева Алгебра. Основные аксиомы и теоремы. Диаграммы Вейча. Карты Карно. Применение при проектировании и анализе работы ЭВМ | | Программа курса лекций для студентов специальности «История» Цель курса лекций – дать студентам, специализирующимся на отечественной истории, представление о процессе становления и развития... |
| Программа по алгебре и дискретной математике по направлению Магистерская программа будет реализовываться кафедрой алгебры и дискретной математики Ургу (кадм) с привлечением научных сотрудников... | | Учебно-методический комплекс «Биологическая химия» «биохимия». В состав разработки включены: программа курса лекций, структура курса, приведены примеры контрольных вопросов по материалам... |
| Методические указания по выполнению контрольной работы №1 по дисциплине Информатика На тему: Линейные алгоритмы. Разветвляющиеся алгоритмы для студентов II курса заочного отделения специальности Контрольная работа — это самостоятельная работа студента по дисциплине «Информатика» | | Конспект лекций по дисциплине «Методы и алгоритмы оценки надежности» Рыбинская государственная авиационная технологическая академия имени П. А. Соловьева |
| М. Ю. Богатырев Тульский государственный университет Благодаря им, возможности решения сложных, например, np полных задач оптимизации существенно расширились, что делает эволюционные... | | Курс 4 семестр Преподаватели: Соболева Марина Леонидовна, доцент кафедры теоретической информатики и дискретной математики Алфимова Анастасия Сергеевна, старший преподаватель кафедры теоретической информатики и дискретной математики Алфимова Анастасия Сергеевна, старший преподаватель кафедры теоретической информатики и дискретной математики |