Экзаменационные билеты по курсу. Методы оптимизации

Экзаменационные вопросы к курсу "Методы оптимизации",

лектор: д.ф.-м.н. проф. Новикова Н.М.

БИЛЕТ 1.

1. Определения: индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.

2. Формула градиентного метода в задаче безусловной минимизации.

БИЛЕТ 2.

1. Задачи распознавания свойств. Классы P и NP.

2. Формула метода Ньютона в задаче безусловной минимизации.

БИЛЕТ 3.

1. Теорема об экспоненциальной временной оценке для задач из класса NP.

2. Идея метода штрафов.

БИЛЕТ 4.

1. Определение полиномиальной сводимости. Класс NPC. Теорема Кука (без доказательства).

2. Геометрическое описание симплекс-метода.

БИЛЕТ 5.

1. Критерий NP-полноты. Доказательство NP-полноты задачи ЦЛН.

2. Методы глобальной минимизации.

БИЛЕТ б.

1. Доказательство NP-полноты задачи 3-выполнимости. NP-трудные задачи.

2. Формула градиентного метода в задаче безусловной минимизации.

БИЛЕТ 7.

1. Класс со-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и со-NP.

2. Формула метода Ньютона в задаче безусловной минимизации.

БИЛЕТ 8.

1. Взаимоотношение классов P, NP и NPC, NP и со-NP. Класс PSPACE.

2. Полиномиальный алгоритм округления e1-приближенного решения системы линейных неравенств.

БИЛЕТ 9.

1. Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке.

2. Идея метода эллипсоидов.

БИЛЕТ 10.

1. Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения.

2. Идея метода штрафов.

БИЛЕТ 11.

1. Определение комбинаторной задачи оптимизации и приближенного алгоритма ее решения. Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке.

2. Идея метода Ньютона.

БИЛЕТ 12.

1. Определение е-приближенного алгоритма и полностью полиномиальной приближенной схемы /ПППС/. Связь между существованием ПППС и псевдополиномиальностью.

2. Теорема оптимальности для разложимых функций.

БИЛЕТ 13.

1. Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания.

2. Геометрическая идея симплекс-метода.

БИЛЕТ 14.

1. Определение озЛП. Принцип граничных решений. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП.

2. Идея метода ветвей и границ. Пример для задачи БЛП.

БИЛЕТ 15.

1. Теорема о границах решений задач ЛП с целыми коэффициентами.

2. Метод ветвей и границ для ЦЛП. Различные стратегии метода.

БИЛЕТ 16.

1. Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами.

2. Метод ветвей и границ для глобальной минимизации липшицевых функций.

БИЛЕТ 17.

1.Следствия систем линейных неравенств. Афинная лемма Фаркаша (без док-ва)

2.Понятие о временной сложности алгоритмов.

БИЛЕТ 18.

1. Лемма Фаркаша о неразрешимости.

2. Понятие о недетерминировано - полиномиальных задачах.

БИЛЕТ 19.

1. Теорема двойственности ЛП.

2. Метод динамического программирования для БЛП с неотрицательными коэффициентами.

БИЛЕТ 20.

1. Сведение озЛП к однородной системе уравнений с ограничением х>=0, х не 0.

2. Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи.

БИЛЕТ 21.

1. Классификация задач математического программирования. Преимущества выпуклого случая.

2. Полиномиальный алгоритм округления е1-приближенного решения системы линейных неравенств.

БИЛЕТ 22.

1. Необходимые условия локального минимума при ограничениях - неравенствах для дифференцируемых функций.

2. Идея метода Кармаркара.

БИЛЕТ 23.

1.Понятие о регулярности ограничений - неравенств в задаче математического программирования.

2.Описание метода эллипсоидов.

БИЛЕТ 24.

1.Теорема о малочисленности решения задачи ЛП с целыми коэффициентами для вполне унимодулярных матриц ограничений.

2.Оценка сложности метода эллипсоидов поиска е2-приближенного решения озЛП.

Те, кому не были зачтены задачи, получат еще и задачи вместе с билетами

Кроме того: обязательно надо уметь привести примеры на принадлежность задачи конкретному классу сложности и построить двойственную задачу к конкретной задаче ЛП, заданной в произвольной форме.

Лекции можно взять по адресу: http://www.ccas.ru/depart/malashen/53kmsu.htm