Экзаменационные вопросы
Описание файла
Документ из архива "Экзаменационные вопросы", который расположен в категории "". Всё это находится в предмете "методы оптимизации" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Экзаменационные вопросы"
Текст из документа "Экзаменационные вопросы"
Экзаменационные вопросы к курсу "Методы оптимизации"
лектор: д.ф.-м.н. Новикова Н.М.
БИЛЕТ 1.
1. Определения: индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.
2.Формула градиентного метода в задаче безусловной минимизации.
БИЛЕТ 2.
1.Задачи распознавания свойств. Классы Р и NP.
2.Формула метода Ньютона в задаче безусловной минимизации.
БИЛЕТ 3.
1.Теорема об экспоненциальной временной оценке для задач из класса NP.
2.Идея, метода штрафов.
БИЛЕТ 4.
1.Определение полиномиальной сводимости. Класс NPC. Теорема Кука /без док-ва/.
2.Геометрическое описание симплекс-метода.
БИЛЕТ 5.
1.Критерий NP-полноты. Док-во NP-полноты задачи ЦЛН.
2.Методы глобальной минимизации.
БИЛЕТ 6.
1.Док-во NP-полноты задачи 3 -выполнимость. NP-трудные задачи.
2.Формула градиентного метода в задаче безусловной минимизации. —
БИЛЕТ 7.
1.Класс co-NP. Пример задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и сo-NР.
2.Формула метода, Ньютона в задаче безусловной минимизации.
БИЛЕТ 8.
1.Взаимоотношение классов Р, NP и NPC, NP и co-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.
2.Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи.
БИЛЕТ 21.
1 .Классификация задач мат. программирования. Преимущества выпуклого случая.
2.Полиномиальный алгоритм округления e1-приближенного ' решения системы линейных неравенств.
БИЛЕТ 22.
1 .Необходимые условия локального минимума при ограничениях-неравенствах для дифференцируемых функций.
2.Идея метода Кармаркара.
БИЛЕТ 23.
1.Понятие о регулярности ограничений-неравенств в задаче
математического программирования.
2.Описание метода эллипсоидов.
БИЛЕТ 24.
1.Теорема о целочисленности решения задачи ЛП с целыми
коэффициентами для вполне унимодулярных матриц ограничений,
2.Оценка сложности метода эллипсоидов е2-приближенного решения озЛП.
Кроме этого предполагаются дополнительные вопросы на двойственность в ЛП (найти двойственную) и на классы сложности (привести пример).