Вопросы к экзамену (1162396)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Экзаменационные вопросы к курсу "Методы оптимизации”, лектор: д.ф.-м.н. проф. Новикова Н.М.

БИЛЕТ 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. Kлacc co-NP. Примep задачи, допускающей хорошую характеризацию. Доказательство утверждения о взаимоотношении классов NPC и co-NP.

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

БИЛЕТ 8.

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

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

БИЛЕТ 9.

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

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

БИЛЕТ 10.

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

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

БИЛЕТ 11.

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

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

БИЛЕТ 12.

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

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

БИЛЕТ 13.

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

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

БИЛЕТ 14.

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

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

БИЛЕТ 15.

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

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

БИЛЕТ 16.

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

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

БИЛЕТ 17.

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

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

БИЛЕТ 18.

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

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

БИЛЕТ 19.

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

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

БИЛЕТ 20.

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

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

БИЛЕТ 21.

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

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

БИЛЕТ 22.

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

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

БИЛЕТ 23.

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

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

БИЛЕТ 24.

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

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

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов вопросов/заданий