Новосибирский государственный университет
Кафедра дискретного анализа и исследования операций

Thin_Red_and_BlueA205.gif (1558 bytes)

А.Ю. Кочетов

Исследование операций
            

 

 

            

Курс лекций

                    

Устные вопросы до экзамена

4 курс, ММФ НГУ, зимняя сессия,  январь, 2016 г.

1.               Приближенные алгоритмы с гарантированной относительной точностью. Модифицированный жадный алгоритм для задачи о рюкзаке и алгоритм с точностью ¾.

2.               Аппроксимационные схемы, полиномиальные и полностью полиномиальные схемы для задачи о рюкзаке.

3.               Задача упаковки в контейнеры. Алгоритмы NF, FF, BF, FFD, отрицательный результат об аппроксимируемости.

4.               Нижние оценки Martello и Toth.

5.               Метод генерации столбцов для задачи упаковки в контейнеры.

6.               Задача календарного планирования. Критические работы, пути и критическое время проекта.

7.               Задачи календарного планирования с ограниченными ресурсами.

8.               Алгоритм Гимади для задачи со складируемыми ресурсами.

9.               Задача коммивояжера. Теорема о погрешности приближенных полиномиальных алгоритмов и алгоритмов локального спуска.

10.         Задача коммивояжера с неравенством треугольника. Алгоритм с гарантированной оценкой точности 2.

11.         Нижние оценки в задаче коммивояжера

12.         Алгоритм Лаулера для задачи  1| prec| fmax

13.         Алгоритм решения задачи  P | pmtn |Cmax

14.         Алгоритм решения задачи  P | pmtn, ri |Lmax

15.         Алгоритм решения задачи  F2 || Cmax

16.         Задача размещения в условиях конкуренциии «безнадежный» пример.

17.         Матричные игры. Определение седловой точки.

18.         Теорема Фон-Неймана.

19.         Бескоалиционные игры, равновесие по Нэшу.        

 

Список вопросов в pdf


Лектор: д.ф.-м.н. Кочетов Юрий Андреевич
e-mail: jkochet@math.nsc.ru

Редакция 12.01.2016