Н.М. Новикова - Экзаменационные вопросы
Описание файла
PDF-файл из архива "Н.М. Новикова - Экзаменационные вопросы", который расположен в категории "". Всё это находится в предмете "методы оптимизации" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Экзаменационные вопросы к курсу "Методы оптимизации",лектор: д.ф.м.н. проф. Новикова Н.М.БИЛЕТ 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.