Вопросы отсортированные по страницам
Описание файла
PDF-файл из архива "Вопросы отсортированные по страницам", который расположен в категории "". Всё это находится в предмете "методы оптимизации" из 8 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Вопросы, отсортированные по страницам 1. 1.1. Определения: индивидуальной и массовой задачи (4,5), кодировки задачи(7), алгоритма решения иассовойзадачи(6), временной сложности алгоритма(8)2. 17.2. Понятие о временной сложности алгоритмов (8)3. 18.2. Понятие о недетерминированно-полиномиальных задачах (8-10)4. 2.1. Задачи распознавания свойств (6). Классы P и NP (8,10)5. 3.1. Теорема об экспоненциальной временной оценке для задач из класса NP (11)6. 4.1. Определение полиомиальной сводимости (13). Класс NPC (14). Теорема Кука (без доказательства) (14)7.
5.1. Критерий NP-полноты (15). Д-во NP-полноты задачи ЦЛН (15)8. 6.1. Д-во NP-полноты задачи 3-выполнимость (17 упр4). NP-трудные задачи (18)9. 7.1. Класс co-NP. Пример задачи, допускающей хорошую характеризацию (5). Д-во утверждения овзаимоотношении классов NPC и co-NP (???)10. 8.1. Взаимоотношение классов P, NP и NPC, NP и co-NP (???). Класс PSPACE (19)11. 9.1. Псевдополиномиальные алгоритмы (21). Пример для задачи о рюкзаке (19)12. 10.1. Сильная NP-полнота (21). Теорема о связи сильной NP-полноты задачи с существованиемпсевдополиномиального алгоритма ее решения (21)13. 11.1. Определение комбинаторной задачи оптимизации и приближенного алгоритма ее решения (22,23).Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке (23)14.
12.1. Определение ?-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС)(23,24). Связь между существованием ПППС и псевдополиномиальностью (???)15. 13.1. Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачамраспознавания (24)16. 14.1. Определение озЛП (25). Принцип граничных решений(26). Алгебраическая и битовая сложность ЛП (27).Результаты о сложности для задач, близких к ЛП (28)17. 15.1. Теорема о границах решений задач ЛП с целыми коэффициентами (28)18. 16.1. Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами (29)19.
8.2. Полиномиальный алгоритм округления ?1-приближенного решения системы линейных неравенств (30)20. 21.2. Полиномиальный алгоритм округления ?1-приближенного решения систкмы линейных неравенств (30)21. 9.2. Идея метода эллипсоидов (31)22. 23.2. Описание метода эллипсоидов (32)23. 24.2. Оценка сложности метода эллипсоидов ?2-приближенного решения озЛП (32)24. 17.1. Следствия систем линейных неравенств (34). Афинная лемма Фаркаша (без доказательства)(35)25. 18.1. Лемма Фаркаша о неразрешимости (35)26.
19.1. Теорема двойственности ЛП (35,36)27. 20.1. Сведение озЛП к однородной системе уравнений с огрничением x>0 (37)28. 22.2 Идея метода Кармаркара (37)29. 21.1. Классификация задач математического программирования (39). Преимущества выпуклого случая (40,41)30. 1.2. Формула градиентного метода в задаче безусловной минимизации (41,42)31. 6.2. Формула градиентного метода в задаче безусловной минимизации (42)32. 11.2. Идея метода Ньютона (43)33. 2.2. Формула метода Ньютона в задаче безусловной минимизации (43)34.
7.2. Формула метода Ньютона в задаче безусловной минимизации (43)35. 3.2.Идея метода штрафов (44)36. 10.2. Идея метода штрафов (44)37. 4.2. Геометрическое описание симплекс-метода38. 13.2. Геометрическая идея симплекс-метода39. 22.1. Необходимые условия локального минимума при ограничениях-неравенствах для дифференцируемыхфункций (47,48)40. 23.1.
Понятие о регулярности ограничений-неравенств в задаче математичиского программирования (47,48)41. 5.2. Методы глобальной минимизации (52, обзорно 52-55)42. 14.2. Идея метода ветвей и границ(54). Пример для задачи БЛП (56)43. 16.2. Метод ветвей и границ для глобальной минимизации Липшицевых функций (54)44. 24.1. Теорема о целочисленности решения задачи ЛП с целыми коэффициентами для вполне унимодулярныхматриц ограничений (56)45.
15.2. Метод ветвей и границ для ЦЛП(57). Различные стратегии метода (58)46. 12.2. Теорема оптимальности для разложимых функций (60)47. 20.2. Применение метода динамического программирования для понижения размерности разложимойоптимизационной задачи (62)48. 19.2. Метод динамического программирования для БЛП с неотрицательными коэффициентами (63,64).
