Материал из eSyr's wiki.

Содержание 1 Теория игры и исследования операций 1.1 Информация о курсе 1.2 Литература 1.3 Экзамен 1.3.1 Билеты 1.3.2 Автомат 1.3.3 Сам экзамен 1.3.4 Пересдача 1.3.5 По чему и как ботать? 1.3.6 Что спрашивают?

Теория игры и исследования операций

Информация о курсе

• Лектор — Фуругян Меран Габибулаевич
• Отчётность — экзамен
• Контрольные работы. 3—4 на раздел, оценки от 2 до 5, отсутствие — 0. Контрольные проводятся без предварительного оповещения, те, кто опоздал, ждут следующей пары. На контрольных будет только то, что будет на лекциях. Иногда лектор просит некоторые вещи докзать студентам самостоятельно.

Литература

• Гермейер Ю. Б., «Введение в теорию исследования операций», наука, 1971 год
• Давыдов Э. Г., «Исследование операций», Высшая школа, 1990 год
• Морозов Вл. В., «Основы теории игр», МВ, 2002 год
• Васин А. А., Морозов Вл. В. «Теория игр и модели мат. экономики», МВО, 2005 год

Экзамен

Билеты

Тигры (билеты)

Автомат

ВАЖНО! Если вы не хотите жуткого геморроя и ненужного напряжения мозга - ходите на контрольные, чего бы вам это не стоило. Окупится сторицей. Правда, высока вероятность, что и о предмете после этого в голове ничего не останется :)

По результатам контрольных будут составлены списки. Вероятнее всего, по этим спискам, студентам будут предложены оценки автоматом за экзамен, как среднеарифметическое по всем трем контрольным.

То есть, те, кто имеет за все контрольные 5,5,5, получат пять автоматом. Аналогичную оценку получат и те, кто получил две пятерки и одну четверку. В некоторых случаях, возможно будут выставлена итоговая пять, если всего одна работа написана на пять, а две другие на четыре (эти случаи будут рассматривать отдельно). Про оценки 3 и 4 ничего конкретного не говорилось, но, по всей видимости, ситуация выставления оценок аналогичная.

Наиболее важный момент: если хотя бы за одну контрольную стоит неявка или два балла, то засчитать среднее арифметическое нельзя (даже если там все остальные пятерки), и нужно будет сдавать экзамен. На экзамене наибольший упор будет сделан на темы, которые вошли в контрольные, которые были не сданы или сданы на двойку. С теми людьми, были застуканы на лекции за разговорами (таких около 4х человек) или получили все три двойки (или неявки) за контрольные, на экзамене ждет отдельный разговор с лектором.

Сам экзамен

Идите на основной экзамен в любом случае, даже если ваши знания еле дотягивают до 3ки. Я побоялся идти из-за диплома, в результате - 3 на пересдаче, и потом две попытки пересдачи тройки. Отказываться от оценки нельзя, но при некоторых условиях учебная часть может разрешить ее пересдать. На основном экзамене есть хоть какой-то шанс попасть не к лектору.

Теоретически, на подготовку должно хватить пяти дней спокойно. Практически, пять дней готовиться к экзамену на 5м курсе в стиле "дым-из-ушей" не хотелось совершенно, поэтому мне их и не хватило.

Дополнительные задачки – не сложные, но не совпадают с теми, которые представлены в билетах. Андрей Адинец отвечал какой-то девушке в течении часа. Фуругян спрашивает вполне адекватно, ставит оценки от двух до пяти даже тому народу, у которых не было контрольных. Спрашивает всех подряд.

Все экзаменаторы спрашивают, ориентируясь на результаты контрольных.

Отказаться от тройки практически невозможно, тем кто не хочет три – совет: если чувствуете что четверка уже обламывается, то сами предложите прийти на пересдачу, т.к. когда объявят оценку отмазаться от нее почти не возможно.

Пересдача

Итак, пересдача. Все пересдачи в этом году Фуругян принимал единолично, чем огорчил очень многих ;) Спрашивает строго, но справедливо. Оба раза тройку я получил, из-за незнания довольно простых алгоритмов из последней лекции (которую я осилил только к третьему разу). Первый раз - построение Эйлерова графа, второй раз - рандомизированный алгоритм решения задачи о паросочетаниях. Как я понимаю, он последнюю лекцию спрашивает ВСЕГДА, так как у многих студентов есть привычка немного не дочитывать до конца (обычно пару самых последних вопросов не спрашивают), что ему не нравится.

На последней пересдаче я уже знал все на зубок, вопросы были такие:

• сведение решения матричной игры к ЛП с доказательством
• доказать, что К-е по порядку множество - NP-трудная задача
• приближенный алгоритм решения задачи о рюкзаке с сложностью O(n^3/eps)

По чему и как ботать?

• Программа курса и билеты можно взять отсюда либо с форума cmcspec
• В качестве лекций нужно ботать лекции Глазковой (плюс еще есть какие-то видеолекции по третьей части)
• Всего есть 3 темы, нужно по всем трем знать основные определения и алгоритмы (опр. седловой точки, теорему фон-Неймана, стратегии, смешанные стратегии, алгоритм Форда, Карзанова, 7 NP-полных задач, определение NP, NPC, NP-полноты, NP-трудной задачи, NP-легкой задачи + каким образом различные задачи сводятся к основным семи)
• В качестве бомб и ответов на вопросы можно использовать материалы отсюда

Что спрашивают?

Лектор спрашивает из всех разделов, уделяя особое внимание вопросам из третьей части (NP и т.п.), алгоритму дефекта и САМЫМ последним лекциям. Потом еще пришло несколько аспирантов, среди которых высокого отмечали как наиболее лояльного. Вопросы были из всех тем, например:

• Сильная NP полнота
• Задачи о парасочетаниях
• Алгоритмы решения задачи о рюкзаке
• Алгоритм Брауна
• 7 основных зада
• лемма Шварца
• алгоритм дефекта
• алгоритм Форда Фалкерсона
• теорема Фоннеймана

Это, конечно не полный список вопросов:)