Министерство экономического развития и торговли
Российской Федерации
Национальный исследовательский университет - Высшая школа экономики
Факультет мировой экономики и мировой политики
Программа дисциплины
ДИСКРЕТНАЯ МАТЕМАТИКА
для направления 080100.62 «Экономика. Мировая экономика» подготовки специалиста
Авторы: к. ф.-м. н., с. н.с.
Рекомендована секцией УМС Одобрена на заседании кафедры
Математические и статистические высшей математики методы в экономике на факультете экономики
Председатель Зав. кафедрой
__________________ ________________ ________________________________
«_____» __________________ 200 г. «____»___________________ 200 г
Утверждена УС факультета
философии
Ученый секретарь
_________________________________
« ____» ___________________200 г.
Москва
Тематический план учебной дисциплины
| |||||
|
|
| Аудиторные часы | Cамост. работа | |
часов | лекции | семинары | |||
1 | Дискретная математика в экономике и социологии | 1 | 1 | - | - |
Первичные понятия и их отношения | |||||
2 | Множества, бинарные отношения, графы | 11 | 3 | 4 | 4 |
IБазовый математический аппарат | |||||
3 | Элементы комбинаторики | 8 | 2 | 2 | 4 |
4 | Введение в теорию графов | 10 | 2 | 4 | 4 |
5 | Бинарные отношения и функции выбора | 10 | 2 | 4 | 4 |
6 | Паросочетания, обобщенные парсочетания, знаковые графы | 8 | 2 | 4 | 2 |
Некоторые прикладные задачи | |||||
7 | Математика выборов (обзор процедур голосования, теорема Мэя, правило Борда, критерий Кондорсе) | 2 | 2 | - | |
8. | Неполадки с демократией (теорема Эрроу, условие Парето) | 2 | 2 | - | |
9 | Вычисление коррупции (индексы Банцафа, Шепли-Шубика). Задача дележа | 2 | 2 | - | |
Итого | 54 | 18 | 18 | 18 |
Базовая литература по курсу
Дополнительная литература по курсу
Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. С английского М.: Издательский дом «Вильямс», 2001. , Адельсон-Вельский математика для инженера, М.: Энергия, 1980. Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. М.: Техносфера, 2004. , Осипова дискретной математики. М.: МАИ, 1992. А, Дискретная математика для программистов. СПб.: Питер. 2001. Яблонский в дискретную математику. М.: Наука, 1986.Формы контроля и структура итоговой оценки
Итоговый контроль: письменный зачет в конце 3-го модуля.
Содержание программы курса
«Дискретная математика»
Тема 1. Дискретная математика в экономике и социологии
Источники появления и развития дискретной математики.
Прикладные задачи социологии и экономики.
Использование методов дискретной математики для их решения.
Основная литература
, Алескеров вариантов (основы теории).- М.: Наука. 1990. – 236 с , , Шварц отношения, графы и коллективные решения. – М.: Изд. дом ГУ ВШЭ. 2006. – 298 с. Ходж Дж., Математика выборов. – М.: Изд-во МЦМНО 2007. – 224 с.Тема 2. Множества, бинарные отношения, графы
Множества и операции над множествами.
Бинарные отношения и их свойства.
Специальные классы бинарных отношений: частичные, слабые и линейные порядки.
Отношения несравнимости, толерантности и эквивалентности.
Ориентированные и неориентированные графы.
Графы и их матрицы смежности.
Двудольные графы.
Основная литература
, , Шварц отношения, графы и коллективные решения. – М.: Изд. дом ГУ ВШЭ. 2006. – 298 с. Дискретная математика для программистов. 2-е дополненное издание – М.: Техносфера. 2005. – 400с. Теория графов, издание четвертое. – М.: Книжный дом «ЛИБРОКОМ», 2009. – 296с.Тема 3. Элементы комбинаторики
Правила суммы и произведения.
Комбинаторные формулы.
Бином Ньютона.
Основная литература
Дискретная математика для программистов. 2-е дополненное издание – М.: Техносфера. 2005. – 400с.Тема 4. Введение в теорию графов
Типы графов. Маршруты и связность. Степени.
Операции над графами. Деревья.
Связность. Эйлеровы графы. Гамильтоновы графы.
Экстремальные графы.
Ориентированные графы.
Основная литература
, , Графы: теория, задачи, алгоритмы: Йошкар-Ола, МарГТУ, 2006. – 112 с. Теория графов. – М.: Книжный дом «ЛИБРОКОМ», 2009. – 352 с. Дискретная математика для программистов. 2-е дополненное издание – М.: Техносфера. 2005. – 400с. Теория графов, издание четвертое. – М.: Книжный дом «ЛИБРОКОМ», 2009. – 296с.Тема 5. Бинарные отношения и функции выбора
Бинарные отношения и их свойства.
Специальные классы бинарных отношений.
Внутреннее и внешнее описание выбора.
Механизм выбора. Функция выбора.
Классически рациональные функции выбора.
Свойства функций выбора.
Турнирный выбор.
Основная литература
, , Шварц отношения, графы и коллективные решения. – М.: Изд. дом ГУ ВШЭ. 2006. – 298 с. Андерсон Дж. Дискретная математика и комбинаторика: Пер. С английского М.: Издательский дом «Вильямс». 2003 , Алескеров вариантов (основы теории).- М.: Наука. 1990. – 236 с.Тема 6. Паросочетания, обобщенные паросочетания, знаковые графы
Паросочетания, обобщенные паросочетания.
Трансверсали семейства множеств.
Предпочтения участников и паросочетания.
Устойчивые паросочетания. Выбор по отношению предпочтения.
Знаковые графы.
Основная литература
, , Шварц отношения, графы и коллективные решения. – М.: Изд. дом ГУ ВШЭ. 2006. – 298 с.Тема 7. Математика выборов
Типы голосования: конституционное (всеобщее) голосование и голосование в малых группах.
Из истории теории голосования.
Правило простого большинства.
Правило Борда.
Парадокс Кондорсе.
Основная литература
, , Шварц отношения, графы и коллективные решения. – М.: Изд. дом ГУ ВШЭ. 2006. – 298 с. Ходж Дж., Математика выборов. – М.: Изд-во МЦМНО 2007. – 224 с. , Лезина в малых группах. Процедуры и методы сравнительного анализа. – М.: Наука. 1991. – 192 с.Тема 8. Неполадки с демократией
Парадокс Эрроу.
Парадокс Сена.
Условие Парето.
Стратегическое поведение избирателей при голосовании.
Манипулирование со стороны организатора голосования.
Процедуры, использующие в качестве вспомогательной коллективной структуры шкалу.
Процедуры, использующие в качестве вспомогательной коллективной структуры мажоритарный граф.
Процедуры, использующие турнирную матрицу.
Критерии оценки и сопоставления процедур голосования.
Основная литература
, , Шварц отношения, графы и коллективные решения. – М.: Изд. дом ГУ ВШЭ. 2006. – 298 с. Ходж Дж., Математика выборов. – М.: Изд-во МЦМНО 2007. – 224 с.Тема 9. Вычисление коррупции.
Распределение влияния групп и фракций в парламенте. Коалиции.
Голосование с квотой.
Индекс влиятельности Банцафа.
Индекс влиятельности Шепли – Шубика.
Влиятельность Банцафа в Психозии.
Влиятельность Шепли – Шубика в Психозии
Голосование в Совете Безопасности ООН.
Оценка влияния стран - участниц в Совете министров Евросоюза.
Основная литература
1. , , Шварц отношения, графы и коллективные решения. – М.: Изд. дом ГУ ВШЭ. 2006. – 298 с.
2. , , Якуба и структурная устойчивость в Российском парламенте (1905 – 1917 и 1993 – 2005 гг.). – М.: ФИЗМАТЛИТ. 2007. – 312 с.
3. Ходж Дж., Математика выборов. – М.: Изд-во МЦМНО 2007. – 224 с.
Вопросы на зачете для оценки качества освоения дисциплины *)
Тема 1.
1. Перечислить основные этапы принятия решений.
Тема 2.
1. Построить 
для графов:
2. Пусть бинарные отношения 
:
- рефлексивны,
- антирефлексивны,
- симметричны,
- асимметричны,
- транзитивны.
Будет ли их объединение обладать теми же свойствами?
3. Пусть бинарные отношения :
- рефлексивны,
- антирефлексивны,
- симметричны,
- асимметричны,
- транзитивны.
Будет ли их пересечение обладать теми же свойствами?
4. Построить транзитивное бинарное отношение на четырех альтернативах. Построить отношение несравнимости для этого бинарного отношения.
5. Бинарные отношения Р1 и Р2 заданы своими матрицами:
Какими свойствами обладают эти бинарные отношения? Построить графы, изображающие эти бинарные отношения.
6. Построить двудольный граф: Х = {2,3,5,9}, Y = {27,30,50}. Дуга между элементами х и y проводится, если х является делителем y. Подсчитать степени всех вершин этого графа.
7. 
Полным двудольным графом 
называется двудольный граф, для которого 
и любые две вершины в 
и 
соединены дугой.
а) Какова степень каждой вершины 
в 
б) Какова степень каждой вершины 
в 
в) Сколько дуг содержит граф 
г) Построить граф 
Тема 3.
1. Перечислить и охарактеризовать основные методы организации экспертиз.
2. Описать метод Делфи.
Тема 4.
1. Найти множество Парето для следующей многокритериальной ситуации:
Альтернативы | Значение критерия | |
f1 | f2 | |
x | 1 | 3 |
y | 2 | 3 |
z | 3 | 2 |
v | 3 | 1 |
w | 1 | 2 |
2. Привести критериальные оценки четырех альтернатив в трехкритериальном пространстве такие, что все три альтернативы принадлежат множеству Парето.
3. Привести критериальные оценки четырех альтернатив в трехкритериальном пространстве такие, что только одна альтернатива принадлежала множеству Парето.
4. Описать три способа выделения части множества Парето.
5. Всегда ли выбор по максимальной сумме критериальных оценок совпадает с выбором по близости к идеальной точке? Привести пример, когда это не так (для случая двух критериев).
Тема 5.
1. Построить функцию выбора по следующему бинарному отношению 
Тема 6.
1. Множество участников 
Множество кандидатов 
Предпочтения участников:
Построить мажоритарный граф. Есть ли здесь победитель Кондорсе?
2. Показать, что при нечетном числе участников граф, соответствующий мажоритарному отношению, связен. Показать, что если победитель Кондорсе существует, то он единственный.
3. Привести пример профиля предпочтений участников, когда существует два победителя Кондорсе.
4. Построить профиль избирателей, в котором правило Борда и правило «больше половины голосов» дают разный результат.
5. Удовлетворяет ли правило Борда аксиоме локальности (независимости от посторонних альтернатив)? Пояснить ответ на примере.
Тема 7
1. Четверо друзей выбирают место отдыха на лето для всей компании. Ими рассматриваются в качестве вариантов Испания (И), Греция (Г), Кипр (К) и Болгария (Б), относительно которых друзья имеют следующие предпочтения:
Р1 Р2 Р3 Р4
----
К Г Б И
И К К Г
Г Б И К
Б И Г Б
Построить коллективное решение с помощью процедуры Борда.
2. Семья из трех человек собирается покупать новый автомобиль. Выбор осуществляется среди моделей (в одной ценовой категории) следующих марок: «пежо» (Р), «рено» (R), «ситроен» (S), «опель» (О). Предпочтения членов семьи относительно этих альтернатив имеют вид:
Р1 Р2 Р3
R P C
O O R
P C O
C R P
Построить коллективное решение по правилу Фишберна.
3. Семья из четырех человек выбирает ресторан, в котором собирается отметить семейное торжество. Рассматриваются следующие варианты: итальянский (I), японский (J), мексиканский (М) и французский (F). Предпочтения членов семьи выглядят следующим образом:
Р1 Р2 Р3 Р4
----
M F J J
F J I F
I I M I
J M F M
Какой ресторан будет выбран, если коллективное решение строится по правилу
Коупленда?
4. Три друга, собираясь в путешествие в лодке по реке, решают, что им взять с собой. Варианты такие: собаку (x), ружье (y), удочку (z), бинокль (v).
Предпочтения друзей выглядят следующим образом:
P1 P2 P3
x y v
z z x
y v z
v x y
Какие предметы возьмут с собой друзья, если они воспользуются правилом Доджсона (Льюиса Кэррола)?
Тема 8.
1. Пусть в парламент прошли три партии – А, Б и В, причем партия А набрала значительно больше голосов, чем партии Б и В. Каким партиям при распределении мест в парламенте выгоднее применение квоты Хара, а каким – применение усиленной имперской квоты? Обосновать ответ.
2. Пусть в выборах участвуют 4 партии 
, число избирателей равно 100. Предпочтения избирателей приведены в таблице:
Как будет выглядеть парламент из 4 мест, если используется квота Хара?
усиленной имперской квоты? Обосновать ответ.
3. Пусть в выборах участвуют 4 партии , число избирателей равно 100. Предпочтения избирателей приведены в таблице:
Как будет выглядеть парламент из 3 мест, если используется метод наименьшего делителя?
Тема 9.
1. Найти выигрывающие коалиции в голосованиях и подсчитать для каждого участника индекс Банцафа:
- (51; 35, 35, 300
- (20; 10, 10, 1)
- (51; 49, 47, 4)
- (3; 1, 1, 1, 2)
- (20; 10, 10, 10, 1)
2. Совет директоров банка состоит из пяти человек: P, A, B, C, D. Президент банка Р имеет три голоса, остальные члены совета директоров – по одному. Решение считается принятым, если за него подано не менее четырех голосов. Известно, что Р и член совета директоров А находятся в оппозиции друг к другу и никогда не голосуют за одно решение. Найти индексы Банцафа для каждого члена совета директоров.
3. Построить характеристические функции для следующих голосований с квотой:
а) (51; 50,30,20)
б) (51;60,30,10)
в) (6;1,2,3,4)
Автор программы:
Ó , 2010
*) Данные вопросы и задания взяты из курса и «Теория принятия управленческих решений» только в качестве иллюстраций и моделей. Конкретные зачетные задания по курсу «Дискретная математика» будут опубликованы позднее
