Методы оптимизации 1. Введение в теорию сложности. Понятие о сложности решения задач.
Основные определения: индивидуальная и массовая задачи, кодировка, алгоритм решения массовой задачи, временная сложность алгоритма. Классы Р и NР (формальные определения, примеры).
NР-полные (универсальные) задачи.
Теорема об экспоненциальной временной оценке для задач из класса NP. Класс со-NP. Задачи, допускающие хорошую характеризацию. Определение полиномиальной сводимости. Класс NPC. Теорема Кука /без док-ва/. Критерий NР-полноты. Док-во NP-полноты задачи ЦЛН.
Сильная NP-полнота и псевдополиномиальность.
Доказательство NP-подноты задачи 3-выполнимость. HP-трудные задачи. Взаимоотношение классов Р, NP и NPC, NP и co-NP. Класс PSPACE. Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке. Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения.
Приближенное решение задач комбинаторной оптимизации.
Определение комбинаторной задачи оптимизации и приближенного алгоритма ее решения. Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке. Определение е-приближенного алгоритма и полностью полиномиальной приближенной схемы /ПППС/. Связь между существованием ПППС и псевдополиномиальностью. Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания. Пример задачи о коммивояжере. 2. Методы линейного программирования (ЛП).
Понятие о сложности задач ЛП.
Определение основной задачи ДП (озЛП). Принцип граничных решений и геометрическое описание симплекс-метода. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП.
Метод эллипсоидов.
Теорема о границах решений задач ЛП с целыми коэффициентами. Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами. Полиномиальный алгоритм округления e1-приближенного решения системы линейных неравенств. Метод эллипсоидов е-приближенного решения озЛП. Оценка сложности метода эллипсоидов. Полиномиальность ЛП.
Теория двойственности ЛП.
Следствия систем линейных неравенств. Афинная лемма Фаркаша /без док-ва/. Лемма Фаркаша о неразрешимости. Теорема двойственности ЛП. Сведение озЛП к однородной системе уравнений с ограничением положительности. 3. Элементы математического программирования (МП).
Метод Кармаркара решения задач ЛП и обзор идей МП.
Метод Кармаркара - метод внутренней точки (в отличие от симплекс-метода). Понятие о градиентных и Ньютоновских методах минимизации. Условная оптимизация, способы освобождение от ограничений (методы барьеров и штрафов). Классификация задач МП. Преимущества выпуклого случая.
Двойственность в МП.
Необходимые условия локального минимума при ограничениях-неравенствах для дифференцируемых функций. Теорема Куна-Таккера. Понятие о регулярности ограничений-неравенств в задаче МП. Метод множителей Лагранжа.
4. Основные способы решения переборных задач.
Метод ветвей и границ (МВГ).
МВГ в глобальной оптимизации. Общее описание метода. Стратегии МВГ. МВГ для булева программирования (БД).
Целочисленное линейное программирование (ЦЛП).
Отличие задач ЦЛП и ЛП: существенная нелинейность ограничений типа целочисленности. Неэффективность округления решения ЛП до ближайшего целого. Случай вполне унимодулярной матрицы ограничений. МВГ в ЦЛП.
Метод динамического программирования (ДП).
Общая схема метода. Пример для задачи о рюкзаке. Теоретические основы ДП. Метод ДП для БП с неотрицательными коэффициентами. Связь с МВГ. Литература:
М. Гэри, Д. Джонсон "Вычислительные машины и труднорешаемые задачи", М.: МИР, 1902.
Х-Пападимитриу, К-Стайглиц "Комбинаторная оптимизация", М.: Мир, 1985.
Л.Г.Хачиян "Сложность задач ЛП", Знание, 1987, No .10.
А.Г. Сухарев, А.В. Тимохов, В.В. Федоров "Курс методов оптимизации", М.: Наука, 1985.
В.Г. Карманов "Математическое программирование". М.: Наука, 1986.
А.Г. Сухарев, А.В. Тимохов, В.В. Федоров "Курс методов оптимизации", М.: Наука, 1985.
М. Мину "Математическое программирование", М.: Наука, 1990.
Х. Пападимитриу, К. Стайглиц "Комбинаторная оптимизация", М.: Мир, 1985.
2 Понятие сложности задачи Известно, что интуитивное представление о сложности задачи не всегда адекватно, а если поставлена существенно незнакомая проблема,...
Метрики сложности программ При оценке сложности программ, как правило, выделяют три основные группы метрик: метрики размера программ, метрики сложности потока...
Д. Черных Общая постановка задачи оптимизации Общая постановка задачи оптимизации. Общие методы решения задач оптимизации, метод исключения, метод неопределенных множителей Лагранжа....
Билет 10. Теория сложности вычислений Теория сложности вычислений является разделом теории вычислений, изучающим стоимость работы, требуемой для решения вычислительной...
