Соответствие билетов и страниц в книге

1. 1. Определения: индивидуальной и массовой задачи (4,5), кодировки задачи(7), алгоритма решения иассовой задачи(6), временной сложности алгоритма(8)

2. Формула градиентного метода в задаче безусловной минимизации (41,42)

2. 1. Задачи распознавания свойств (6). Классы P и NP (8,10)

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

3.1. Теорема об экспоненциальной временной оценке для задач из класса NP (11)

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

4. 1. Определение полиомиальной сводимости (13). Класс NPC (14). Теорема Кука (без доказательства) (14)

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

5. 1. Критерий NP-полноты (15). Д-во NP-полноты задачи ЦЛН (15)

2. Методы глобальной минимизации (52, обзорно 52-55)

6. 1. Д-во NP-полноты задачи 3-выполнимость (17 упр4). NP-трудные задачи (18)

2. Формула градиентного метода в задаче безусловной минимизации (42)

7. 1. Класс co-NP. Пример задачи, допускающей хорошую характеризацию (5). Д-во утверждения о взаимоотношении классов NPC и co-NP (???)

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

8. 1. Взаимоотношение классов P, NP и NPC, NP и co-NP (???). Класс PSPACE (19)

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

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

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

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

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

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

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

12. 1. Определение ?-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС) (23,24). Связь между существованием ПППС и псевдополиномиальностью (???)

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

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

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

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

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

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

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

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

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

17. 1. Следствия систем линейных неравенств (34). Афинная лемма Фаркаша (без доказательства)(35)

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

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

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

19. 1. Теорема двойственности ЛП (35,36)

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

20. 1. Сведение озЛП к однородной системе уравнений с огрничением x>0 (37)

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

21.1. Классификация задач математического программирования (39). Преимущества выпуклого случая (40,41)

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

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

2 Идея метода Кармаркара (37)

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

2. Описание метода эллипсоидов (32)

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

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