Тигры

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

(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (09:49, 12 декабря 2013) (править) (отменить)
(Автомат)
 
(8 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
= Теория игры и исследования операций =
+
= Теория игр и исследования операций =
-
[[Изображение:Furugyan.jpg|thumb|240px|Фуругян Меран Габибулаевич]]
+
[[Изображение:Furugyan.jpg|thumb|240px|Фуругян Меран Габибуллаевич]]
== Информация о курсе ==
== Информация о курсе ==
-
* Лектор — Фуругян Меран Габибулаевич
+
* Лектор — [http://io.cs.msu.su/preps/furugyan.htm Фуругян Меран Габибуллаевич];
-
* Отчётность — экзамен
+
* Отчётность — экзамен;
-
* Контрольные работы. 3—4 на раздел, оценки от 2 до 5, отсутствие 0. Контрольные проводятся без предварительного оповещения, те, кто опоздал, ждут следующей пары. На контрольных будет только то, что будет на лекциях. Иногда лектор просит некоторые вещи докзать студентам самостоятельно.
+
* В течение курса проводятся контрольные работы, в количестве примерно от 3 до 6 штук, оценки от 2 до 5, за отсутствие выставляется оценка 0. Контрольные проводятся без предварительного оповещения; те, кто опоздал, ждут следующей пары. На контрольных проверяется только тот материал, что дан на лекциях. Иногда лектор просит студентов некоторые вещи доказать самостоятельно (на лекции — качестве домашнего задания; потом может быть использовано в качестве одного из вопросов контрольной работы). Средний балл за контрольные работы учитывается при выставлении оценки за экзамен.
== Литература ==
== Литература ==
-
* Гермейер Ю. Б., «Введение в теорию исследования операций», наука, 1971 год
+
* Гермейер Ю. Б., «Введение в теорию исследования операций», Наука, 1971 год;
-
* Давыдов Э. Г., «Исследование операций», Высшая школа, 1990 год
+
* Давыдов Э. Г., «Исследование операций», Высшая школа, 1990 год;
-
* Морозов Вл. В., «Основы теории игр», МВ, 2002 год
+
* Морозов Вл. В., «Основы теории игр», МВ, 2002 год;
-
* Васин А. А., Морозов Вл. В. «Теория игр и модели мат. экономики», МВО, 2005 год
+
* Васин А. А., Морозов Вл. В. «Теория игр и модели мат. экономики», МВО, 2005 год.
 +
 
 +
== Источники информации ==
 +
* [http://www.intuit.ru/department/algorithms/algomodex/ Похожий курс «Алгоритмы и модели вычислений»] — этот курс читается лектором в МФТИ, он совпадает с третьей частью данного курса и со второй (кроме алгоритма дефекта). На сайте можно посмотреть видео онлайн.
 +
** [http://sirian.su/vmk/9/tiio/ Скачать все видео (зеркало 1)]
 +
** [http://foo.ru/files/cmc/tigr/ Скачать все видео (зеркало 2)]
== Экзамен ==
== Экзамен ==
-
'''ВАЖНО! Если вы не хотите жуткого геморроя и ненужного напряжения мозга - ходите на контрольные, чего бы вам это не стоило. Окупится сторицей. Правда, высока вероятность, что и о предмете после этого в голове ничего не останется :)'''
+
 
-
===Автомат===
+
''Настоятельно рекомендуется посещение контрольных в виду возможного возникновения больших проблем с сдачей экзамена в дальнейшем в противном случае.''
 +
 
 +
=== Автомат ===
 +
 
По результатам контрольных будут составлены списки. Вероятнее всего, по этим спискам, студентам будут предложены оценки автоматом за экзамен, как среднеарифметическое по всем трем контрольным.
По результатам контрольных будут составлены списки. Вероятнее всего, по этим спискам, студентам будут предложены оценки автоматом за экзамен, как среднеарифметическое по всем трем контрольным.
Строка 23: Строка 31:
Наиболее важный момент: если хотя бы за одну контрольную стоит неявка или два балла, то засчитать среднее арифметическое нельзя (даже если там все остальные пятерки), и нужно будет сдавать экзамен. На экзамене наибольший упор будет сделан на темы, которые вошли в контрольные, которые были не сданы или сданы на двойку. С теми людьми, были застуканы на лекции за разговорами (таких около 4х человек) или получили все три двойки (или неявки) за контрольные, на экзамене ждет отдельный разговор с лектором.
Наиболее важный момент: если хотя бы за одну контрольную стоит неявка или два балла, то засчитать среднее арифметическое нельзя (даже если там все остальные пятерки), и нужно будет сдавать экзамен. На экзамене наибольший упор будет сделан на темы, которые вошли в контрольные, которые были не сданы или сданы на двойку. С теми людьми, были застуканы на лекции за разговорами (таких около 4х человек) или получили все три двойки (или неявки) за контрольные, на экзамене ждет отдельный разговор с лектором.
-
===Сам экзамен===
+
В 2013 году автоматы ставились так: считалось среднее арифметическое за контрольные (нули и двойки тоже учитывались), далее предлагалась оценка по следующей схеме: если среднее арифметическое больше n, то предлагалась оценка n+1. То есть за 544 ставилась 5, за 5 3 2 ставилась 4.
 +
 
 +
=== Основной экзамен ===
Идите на основной экзамен '''в любом случае''', даже если ваши знания еле дотягивают до 3ки. Я побоялся идти из-за диплома, в результате - 3 на пересдаче, и потом две попытки пересдачи тройки. Отказываться от оценки нельзя, но при некоторых условиях учебная часть может разрешить ее пересдать. На основном экзамене есть хоть какой-то шанс попасть не к лектору.
Идите на основной экзамен '''в любом случае''', даже если ваши знания еле дотягивают до 3ки. Я побоялся идти из-за диплома, в результате - 3 на пересдаче, и потом две попытки пересдачи тройки. Отказываться от оценки нельзя, но при некоторых условиях учебная часть может разрешить ее пересдать. На основном экзамене есть хоть какой-то шанс попасть не к лектору.
Строка 42: Строка 52:
* Программа курса и билеты можно взять [http://www.cmc-msu.ru/files09.html отсюда] либо с форума [http://www.cmcspec.ru/ipb/index.php?showtopic=653 cmcspec]
* Программа курса и билеты можно взять [http://www.cmc-msu.ru/files09.html отсюда] либо с форума [http://www.cmcspec.ru/ipb/index.php?showtopic=653 cmcspec]
* В качестве '''лекций''' нужно ботать лекции Глазковой (плюс еще есть [http://www.intuit.ru/department/algorithms/algomodex/ какие-то видеолекции по третьей части])
* В качестве '''лекций''' нужно ботать лекции Глазковой (плюс еще есть [http://www.intuit.ru/department/algorithms/algomodex/ какие-то видеолекции по третьей части])
-
* Всего есть 3 темы: 1я (про ант.игры) - полный пиздец, 2я (про потоки) - приятная, но с говнецом, 3я (про классы задач) - самая адекватная. Для собственной самооценки советую ботать сначала именно 3ю. :)
+
* Всего есть 3 темы: 1я (про антагонистические игры) — полный пиздец, 2я (про потоки) — приятная, но с говнецом, 3я (про классы задач) — самая адекватная. Для собственной самооценки советую ботать сначала именно 3ю. :)
* По всем трем необходимо знать основные определения и алгоритмы (опр. седловой точки, теорему фон-Неймана, стратегии, смешанные стратегии, алгоритм Форда, Карзанова, 7 NP-полных задач, определение NP, NPC, NP-полноты, NP-трудной задачи, NP-легкой задачи + каким образом различные задачи сводятся к основным семи)
* По всем трем необходимо знать основные определения и алгоритмы (опр. седловой точки, теорему фон-Неймана, стратегии, смешанные стратегии, алгоритм Форда, Карзанова, 7 NP-полных задач, определение NP, NPC, NP-полноты, NP-трудной задачи, NP-легкой задачи + каким образом различные задачи сводятся к основным семи)
* В качестве бомб и '''ответов на вопросы''' можно использовать материалы [http://www.cmc-msu.ru/files09.html отсюда]
* В качестве бомб и '''ответов на вопросы''' можно использовать материалы [http://www.cmc-msu.ru/files09.html отсюда]
Строка 54: Строка 64:
*сведение решения матричной игры к ЛП с доказательством
*сведение решения матричной игры к ЛП с доказательством
*доказать, что К-е по порядку множество - NP-трудная задача
*доказать, что К-е по порядку множество - NP-трудная задача
-
*приближенный алгоритм решения задачи о рюкзаке с сложностью O(n^3/eps)
+
*приближенный алгоритм решения задачи о рюкзаке со сложностью O(n^3/eps)
Вопросы бывают из всех тем, например:
Вопросы бывают из всех тем, например:
*Сильная NP полнота
*Сильная NP полнота
-
*Задачи о парасочетаниях
+
*Задачи о паросочетаниях
*Алгоритмы решения задачи о рюкзаке
*Алгоритмы решения задачи о рюкзаке
*Алгоритм Брауна
*Алгоритм Брауна
-
*7 основных зада
+
*7 основных задач
*лемма Шварца
*лемма Шварца
*алгоритм дефекта
*алгоритм дефекта
*алгоритм Форда Фалкерсона
*алгоритм Форда Фалкерсона
-
*теорема Фоннеймана
+
*теорема фон Неймана
-
Это, конечно не полный список вопросов :)
+
Это, конечно, неполный список вопросов :)
{{Курс Тигры}}
{{Курс Тигры}}
{{Лекции}}
{{Лекции}}

Текущая версия

Содержание

[править] Теория игр и исследования операций

Фуругян Меран Габибуллаевич
Фуругян Меран Габибуллаевич

[править] Информация о курсе

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

[править] Литература

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

[править] Источники информации

[править] Экзамен

Настоятельно рекомендуется посещение контрольных в виду возможного возникновения больших проблем с сдачей экзамена в дальнейшем в противном случае.

[править] Автомат

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

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

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

В 2013 году автоматы ставились так: считалось среднее арифметическое за контрольные (нули и двойки тоже учитывались), далее предлагалась оценка по следующей схеме: если среднее арифметическое больше n, то предлагалась оценка n+1. То есть за 544 ставилась 5, за 5 3 2 ставилась 4.

[править] Основной экзамен

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

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

Дополнительные задачки – не сложные, но не совпадают с теми, которые представлены в билетах.

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

Можно приносить с собой рукописные материалы. Ахтунг, лектор может захотеть проверить, ваш ли это почерк.

[править] Пересдача

Итак, пересдача. Все пересдачи в начале 2000-х году Фуругян принимал единолично, чем огорчил очень многих ;) Спрашивает строго, но справедливо. Однако в 2010 году, и на первой и на второй пересдачах были аспиранты, что не может не радовать. :)

На пересдачах пользоваться материалов категорически запрещено. Замеченных в списывании ждёт "нехилая анальная дранка". (с) Если есть возможность воздержаться - воздержитесь: сдать экзамен на 3, не написал обе части билета, прилично зная термин, возможно!

[править] По чему и как ботать?

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

[править] Что спрашивают? Примеры

Лектор спрашивает из всех разделов, уделяя особое внимание вопросам из третьей части (NP и т.п.), алгоритму дефекта и САМЫМ последним лекциям. Фуругян спрашивает вполне адекватно, ставит оценки от двух до пяти даже тому народу, у которых не было контрольных. Спрашивает всех подряд. Как полагает анонимус, Фуругян спрашивает ОЧЕНЬ ЧАСТО из последних лекций, так как у многих студентов есть привычка немного не дочитывать до конца (обычно пару самых последних вопросов не спрашивают), что ему не нравится.

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

Пример вопросов на 3й пересдаче:

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

Вопросы бывают из всех тем, например:

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

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

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


01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16


Календарь

Сентябрь
04 11 18 25
Октябрь
02 09 16 23 30
Ноябрь
06 13 20 27
Декабрь
04 11 18



Материалы по курсу
Контрольная 1 | Контрольная 2 | Контрольная 3


Лекции

10 семестр История развития вычислительных технологий в СССР, России | Современные проблемы прикладной математики
9 семестр Формальная спецификация и верификация программ | Теория игры и исследования операций | История и методология прикладной математики | Основы российского права | История религии | Параллельная обработка данных
8 семестр Верификация программ на моделях | Математические основы теории прогнозирования | Основы квантовой физики и квантовых вычислений | Методы оптимизации | Распределённые операционные системы
7 семестр Вычислительные Системы | Объектно-ориентированные Анализ и Проектирование | Искусственный Интеллект | Математическая Логика | Функциональный Анализ | Социология | Параллельная Обработка Данных
6 семестр Основы Кибернетики | Численные Методы | Конструирование Компиляторов | Компьютерные Сети
5 семестр Базы Данных | Языки Программирования | Экономические Науки
3 семестр Операционные системы

Спецкурсы
Осень 2013 Современная криптография | Дизайн и реализация ОС FreeBSD
Весна 2011 Практические аспекты сетевой безопасности | Сетевое администрирование в UNIX
Осень 2010 UNИX | Теория функционального программирования. Язык Haskell | Введение в информационную безопасность | Информационный поиск
Весна 2010 UNИX | Архитектура и программирование массивно-параллельных вычислительных систем | Язык Ада
Осень 2009 UNИX | Введение в парадигмы программирования
Весна 2009 UNИX | Архитектура и программирование массивно-параллельных вычислительных систем
Осень 2008 UNИX | Структурные методы обработки изображений и сигналов
Весна 2008 UNИX | Вопросы организации вычислительных кластеров на основе UNIX-серверов | Философия математики
Осень 2007 UNИX
Весна 2007 UNИX | Практика мультипарадигмального программирования
Осень 2006 Введение в теорию построения оптимизирующих компиляторов

Отдельные лекции Bruce Eckel, The State of The Java Union | Richard Stallman: Free software: ethics and practice, Copyright vs Community in the Age of Computer Networks | Наану Александр, Vim | Erinn Clark, The Tor Project: Anonymity Online
Личные инструменты
Разделы