Экзаменационные вопросы (1162395)

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

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

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

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

БИЛЕТ 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-приближенного решения озЛП.

Кроме этого предполагаются дополнительные вопросы на двойственность в ЛП (найти двойственную) и на классы сложности (привести пример).

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

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

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

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

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

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