Вопросы к экзамену
Описание файла
Документ из архива "Вопросы к экзамену", который расположен в категории "". Всё это находится в предмете "методы оптимизации" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Вопросы к экзамену"
Текст из документа "Вопросы к экзамену"
Экзаменационные вопросы к курсу "Методы оптимизации”, лектор: д.ф.-м.н. проф. Новикова Н.М.
БИЛЕТ 1.
-
Определения: индивидуальной и массовой задачи, кодировки задачи, алгоритма решения массовой задачи, временной сложности алгоритма.
-
Формула градиентного метода в задаче безусловной минимизации.
БИЛЕТ 2.
-
Задачи распознавания свойств. Классы Р и NP.
-
Формула метода Ньютона в задаче безусловной минимизации.
БИЛЕТ 3.
-
Теорема об экспоненциальной временной оценке для задач из класса NP.
-
Идея метода штрафов.
БИЛЕТ 4.
-
Определение полиномиальной сводимости. Класс NPC. Теорема Кука /без док-ва/.
-
Геометрическое описание симплекс-метода.
БИЛЕТ 5.
-
Критерий NP-полноты. Док-во NP-полноты задачи ЦЛН.
-
Методы глобальной минимизации.
БИЛЕТ 6.
-
Док-во NP-полноты задачи 3-выполнимость. NP-трудные задачи.
-
Формула градиентного метода в задаче безусловной минимизации.
БИЛЕТ 7.
-
Kлacc co-NP. Примep задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.
-
Формула метода Ньютона в задаче безусловной минимизации.
БИЛЕТ 8.
-
Взаимоотношение классов Р, NP и NPC, NP и co-NP. Класс PSPACE.
-
Полиномиальный алгоритм округления e1-приближенного решения системы линейных неравенств.
БИЛЕТ 9.
-
Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке.
-
Идея метода эллипсоидов.
БИЛЕТ 10.
-
Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения. I
-
Идея метода штрафов.
БИЛЕТ 11.
-
Определение комбинаторной задачи оптимизации и приближенного алгоритма ее решения. Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке.
-
Идея метода Ньютона.
БИЛЕТ 12.
-
Определение e-приближенного алгоритма и полностью полиномиальной приближенной схемы /ПППС/. Связь между существованием ПППС и псевдополиномиальностью.
-
Теорема оптимальности для разложимых функций.
БИЛЕТ 13.
-
Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания.
-
Геометрическая идея симплекс-метода.
БИЛЕТ 14.
-
Определение озЛП. Принцип граничных решений. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП.
-
Идея метода ветвей и границ. Пример для задачи БЛП.
БИЛЕТ 15.
-
Теорема о границах решений задач ЛП с целыми коэффициентами.
-
Метод ветвей и границ для ЦЛП. Различные стратегии метода.
БИЛЕТ 16.
-
Теорема о мере несовместности систем линейных неравенств с целыми I коэффициентами.
-
Метод ветвей и границ для глобальной минимизации липшицевых функций.
БИЛЕТ 17.
-
Следствия систем линейных неравенств. Афинная лемма Фаркаша /без док-ва/.
-
Понятие о временной сложности алгоритмов.
БИЛЕТ 18.
-
Лемма Фаркаша о неразрешимости.
-
Понятие о недетерминированно полиномиальных задачах.
БИЛЕТ 19.
-
Теорема двойственности ЛП.
-
Метод динамического программирования для БЛП с неотрицательными коэффициентами.
БИЛЕТ 20.
-
Сведение озЛП к однородной системе уравнений с ограничением х >= 0, х не 0.
-
Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи.
БИЛЕТ 21.
-
Классификация задач матем.программирования. Преимущества выпуклого случая.
-
Полиномиальный алгоритм округления e1-приближенного решения системы линейных неравенств.
БИЛЕТ 22.
-
Необходимые условия локального минимума при ограничениях-неравенствах для дифференцируемых функций.
-
Идея метода Кармаркара.
БИЛЕТ 23.
-
Понятие о регулярности ограничений-неравенств в задаче математического программирования.
-
0писание метода эллипсоидов.
БИЛЕТ 24.
-
Теорема о целочисленности решения задачи ЛП с целыми коэффициентами для вполне унимодулярных матриц ограничений.
-
0ценка сложности метода эллипсоидов поиска е2-приближенного решения озЛП.
Те, кому не были зачтены задачи, получат еще и задачи вместе с билетами
Кроме того: обязательно надо уметь привести примеры на принадлежность
задачи конкретному классу сложности и построить двойственную задачу к
конкретной задаче ЛП, заданной в произвольной форме.