Кроме вопросов, представленных ниже, Новикова рекомендовала проработать двойственность (поиск двойственной) и классы сложности (примеры).

1. 1. Определения: индивидуальной и массовой задачи, кодировки задачи, алгоритма решения иассовой задачи, временной сложности алгоритма
   2. Формула градиентного метода в задаче безусловной минимизации

2. ---

   1. Задачи распознавания свойств. Классы P и 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 и co-NP
   2. Формула метода Ньютона в задаче безусловной минимизации

8. ---

   1. Взаимоотношение классов P, NP и NPC, NP и co-NP. Класс PSPACE
   2. Полиномиальный алгоритм округления e1-приближенного решения системы линейных неравенств

9. ---

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

10. ---

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

11. ---

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

12. ---

    1. Определение e-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью
    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. Сведение озЛП к однородной системе уравнений с огрничением x>0
    2. Применение метода динамического программирования для понижения размерности разложимой оптимизационной задачи

21. ---

    1. Классификация задач математического программирования. Преимущества выпуклого случая
    2. Полиномиальный алгоритм округления e1-приближенного решения систкмы линейных неравенств

22. ---

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

23. ---

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

24. ---

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