Правительство Российской Федерации
Государственное образовательное бюджетное учреждение

высшего профессионального образования
«Государственный университет - Высшая школа экономики»

Факультет Менеджмента

Программа дисциплины
Дискретная математика для социологов
для направления 040200.62 Социология подготовки бакалавра

Автор: к.ф.-м.н, преподаватель Андреева Т.В.

Рекомендована секцией УМС Одобрена на заседании кафедры

Математические и статистические Высшей математики

методы в экономике

Председатель

_________________ А.С. Шведов Зав. кафедрой С.А. Логвенков

___________________________

«_____» __________________ 200 г. «____»__________________ 200 г

Утверждена УС факультета

Психологии

Ученый секретарь

________________________________

« ____» ___________________200 г.
Москва

1. 
   Пояснительная записка.
   

Требования к студентам: Учебная дисциплина “Дискретная математика для социологов” (4-й и 5-й модули учебного плана 1-го курса факультета Социологии) не требует предварительных знаний, выходящих за рамки программы общеобразовательной полной средней школы.
Аннотация: В настоящее время умение описывать дискретные математические объекты, строить прикладные дискретные математические модели и работать с ними составляет необходимую часть ремесла грамотного исследователя, аналитика, практика. Учебная дисциплина направлена на изучение основных понятий, методов и результатов комбинаторики, теории графов, дискретной вероятности, которые с середины XX века играют совершенно особую, всё возрастающую роль в естественно–научных и гуманитарных исследованиях. Дисциплина является необходимым языковым и методологическим основанием для формирования знаний и навыков работы с дискретными объектами, особенно актуальными в практике современного социолога-аналитика. Методы комбинаторного анализа и теории графов позволяют строить и исследовать математико-социологические модели, решать конкретные реальные социологические задачи, являются средством четкой формулировки понятий и проблем во многих социологических исследованиях. “Дискретную математику для социологов” следует рассматривать как важную часть системы фундаментальной подготовки современного социолога. Предпочтение в курсе отдается конструктивным комбинаторным рассуждениям и конструктивной операционной стороне комбинаторного анализа, теории графов, теории выбора и бинарных отношений. Основной акцент делается на методы, составляющие математическую основу – ядро информационных технологий социологических исследований, которые реально используются современным мировым профессиональным научно-деловым сообществом в аналитических разработках и в практической деятельности.
Целью курса является:

- овладение базовыми понятиями, основными определениями и элементарными результатами дискретной математики (комбинаторного анализа и теории графов), необходимыми в практической социологической деятельности;

- развитие логического мышления и умения оперировать дискретными объектами, развитие навыков вычисления конечных сумм, перечисления комбинаторных объектов и графов.

Дискретной математике вообще, а комбинаторике и теории – в особенности, присущи внутренняя математическая целостность, конкретность и внешняя элегантность.

Программа курса предусматривает лекции (56 часов), семинарские занятия (28 часов). Курсовых работ нет. В самостоятельную работу студентов входит освоение теоретического материала, изучение базового учебника и основной литературы, знакомство с дополнительной литературой, начальное ознакомление с профессиональной литературой (предназначенной для углубленного изучения научной области), подготовка к семинарским занятиям, подготовка к выполнению промежуточных контрольных работ, выполнение домашних заданий, подготовка к итоговой контрольной работе.
Учебная задача дисциплины: В результате изучения курса “Дискретная математика для социологов” студент должен:

• 
  знать и уметь использовать элементарные математические методы и результаты комбинаторики и теории графов для постановки и решения теоретических и прикладных задач социологии;
  
• 
  овладеть навыками самостоятельной аналитической работы и умением постоянно пополнять свой профессиональный математический инструментарий, следя за развитием математических и информационных технологий социологических и социально-экономических исследований.
  

Материал курса предназначен для дальнейшего использования, прежде всего, в “Теоретико-вероятностных моделях в социологии” (1-й – 2-й модули 2-го курса), в “Математико-статистических моделях в социологии” (3-й – 4-й модули 2-го курса), в “Анализе социологических данных – 1” (4-й – 5-й модули 2-го курса), в социологическом и политологическом моделировании, в дисциплинах, посвященных построению и оцениванию современных социальных, политических, экономических, управленческих, правовых моделей, методик, технологий. Учебная дисциплина нацелена на развитие у студентов начальных навыков системной аналитики.

2. 
   Тематический план учебной дисциплины
   

№	Название темы	Всего часов	Аудиторные часы		Самостоятельная работа
			лекции	Семинары и практические занятия
Четвертый модуль
1.	Комбинаторные методы дискретной математики	98	26	14	58
1.1	История развития, классические задачи	10	4	2	4
1.2	Размещения и производящие функции	32	8	6	18
1.3	Рекуррентные соотношения. Разбиения.	17	4	3	10
1.4	Логические методы комбинаторного анализа	17	4	3	10
1.5	Двенадцатеричный путь.	8	2	0	6
1.6	Модели и задачи комбинаторного анализа в социологии.	14	4	0	10
2.	Отношения и функции	26	8	2	16
2.1	Определения и основные понятия.	12	4	0	8
2.2	Частично упорядоченные множества. Функции Выбора	12	4	0	8
2.3	Контрольная работа	2		2
Пятый модуль
3.	Элементы теории графов (модуль 5)	92	22	12	58
3.1	История развития, классические задачи	14	4	2	8
3.2	Ориентированные и неориентированные графы	34	8	6	20
3.3	Эйлеровы пути и циклы	14	3	1	10
3.4	Гамильтоновы пути и циклы	14	3	1	10
3.5	Паросочетания в графах	16	4	2	10

Итого часов: 216 56 28 132

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

В конце пятого модуля проводится письменный экзамен продолжительностью 80 минут.

Каждая форма контроля оценивается в 10-балльной шкале. Итоговая оценка складывается из оценки за промежуточную контрольную работу (с весом 0.2), из оценок за два домашних задания (с равными весами по 0.2), из оценки текущего контроля (с весом 0.1), из оценки за итоговую контрольную работу (с весом 0.3) и округляется до целых единиц. Итоговая оценка (результат округления) выставляется в пятибалльной и в 10-балльной системах в ведомость и в зачетную книжку студента (оценкам 1, 2, 3 в 10-балльной системе соответствует оценка “неудовлетворительно” в пятибалльной системе, оценкам 4, 5 – “удовлетворительно”, оценкам 6, 7 – “хорошо”, оценкам 8, 9, 10 – “отлично”).

IV. Учебно-методическое обеспечение дисциплины:

1. 
   Литература
   

Базовый учебник
Журавлёв Ю.И., Флёров Ю.А. Дискретный анализ. Ч.I: Учебное пособие. – М.: Изд-во МФТИ, 1999.

Основная литература
1. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992, 2004.

2. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. – М.: Вузовская книга, 1999, 2001.

3. Москинова Г.И. Дискретная математика. Учебное пособие для ВУЗов. – М.: Логос, 2000.

4. Ниворожкина Л.И. и др. Основы статистики с элементами теории вероятностей для экономистов: Руководство для решения задач. – Ростов-на-Дону: Феникс, 1999.

5. Оре Ойстин. Графы и их применение. – М.: Эдиториал УРСС, 2002.

6. Политическое моделирование. Хрестоматия к курсу, ч.2 / Составитель Д.С.Шмерлинг. – М.: Изд-во ГУ-ВШЭ, 2001.

7. Стенли Р. Перечислительная комбинаторика. – М.: Мир, 1990

8. Томас Ричард. Количественные методы анализа хозяйственной деятельности. – М.: Дело и Сервис, 1999, 2003.

9. Эддоус М., Стэнсфилд Р. Методы принятия решений. – М.: Аудит, ЮНИТИ, 1997.
Дополнительная литература
1. Акимов О.Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001.

2. Алексаченко В.А. Логика. Множества. Вероятность. – М.: Вузовская книга, 2001.

3. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

4. Виленкин Н.Я. Популярная комбинаторика. – М.: Наука, 1975.

5. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. – М.: Наука, 1977.

6. Емеличев В.А. Лекции по теории графов. – М.: Наука, 1990

7. Кемени Джон Дж., Снелл Дж.Л., Томпсон Дж.Л. Введение в конечную математику. – М.: Мир, 1965.

8. Колмогоров А.Н., Журбенко И.Г., Прохоров А.В. Введение в теорию вероятностей. – М.: Наука, 1982.

9. Кормен Томас, Лейзерсон Чарльз, Ривест Рональд. Алгоритмы: построение и анализ. – М.: МЦНМО, 2001.

10. Курбатов В.И., Угольницкий Г.А. Математические методы социальных технологий: Учебное пособие. – М.: Вузовская книга, 1998.

11. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.

12. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.

13. Оре Ойстин. Теория графов. – М.: Наука, 1968.

14. Плаус Скотт. Психология оценки и принятия решений. – М.: ИИД “Филинъ”, 1998.

15. Романовский И.В. Дискретный анализ. Учебное пособие. – СПб.-М.: Невский диалект – Физматлит, 2000, 2001, 2003.

16. Рыбников К.А. Введение в комбинаторный анализ. – М.: Изд-во МГУ, 1972.

17. Рыбников К.А. Комбинаторный анализ. Задачи и упражнения. – М.: Наука,1982.

18. Судоплатов С.В., Овчинников Е.В. Элементы дискретной математики. Учебник. – М.: ИНФРА-М, 2002.

19. Толстова Ю.Н. Анализ социологических данных. Методология, дескриптивная статистика, изучение связей между номинальными признаками. – М.: Научный мир, 2000.

20. Уилсон Р.Дж. Введение в теорию графов. - М.: Мир, 1977

21. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. – М.: Мир, 1966.

22. Харари Фрэнк. Теория графов. – М.: Едиториал УРСС, 2003

Литература для углубленного изучения научной области
1. Анастази Анна, Урбина Сьюзан. Психологическое тестирование. 7-е международное издание. – СПб.: Питер, 2001.

2. Андерсон Джеймс. Дискретная математика и комбинаторика. – М.: ИД “Вильямс”, 2003.

3. Басакер Роберт Дж., Саати Томас Л. Конечные графы и сети. – М.: Наука, 1974.

4. Бурков В.Н. и др. Теория графов в управлении организационными системами. – М.: СИНТЕГ, 2001.

5. Грэхем Рональд Л., Кнут Дональд Е., Паташник Орен. Конкретная математика. Основание информатики. – М.: Мир, 1998.

6. Кемени Джон Дж., Снелл Дж.Л. Кибернетическое моделирование. Некоторые приложения. – М.: Советское радио, 1972.

7. Кофман Арнольд. Введение в прикладную комбинаторику. – М.: Наука, 1975.

8. Кристофидес Никос. Теория графов. Алгоритмический подход. – М.: Мир, 1978.

9. Кузютин Д.В. Математические методы стратегического анализа многосторонних отношений: Голосование. Многосторонние соглашения: Учебное пособие. – СПб.: Изд-во Санкт-Петербургского университета, 2000.

10. Математические методы в социальных науках / Сб. статей под ред. Пауля Ф. Лазарсфельда и Нейла У. Генри. – М.: Прогресс, 1973.

11. Миркин Б.Г. Проблема группового выбора. – М.: Наука, 1974.

12. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 1992.

13. Риордан Дж. Введение в комбинаторный анализ. – М.: ИЛ, 1963.

14. Сачков В.Н. Вероятностные методы в комбинаторном анализе. – М.: Наука, 1978.

15. Сачков Ю.В. Вероятностная революция в науке (Вероятность, случайность, независимость, иерархия). – М.: Научный мир, 1999.

16. Светлов В.А. Аналитика конфликта. – СПб.: ООО “Росток”, 2001.

17. Сидоренко Е.В. Методы математической обработки в психологии. – СПб.: Речь, 2000.

18. Тараканов В.Е. Комбинаторные задачи и (0,1)-матрицы. – М.: Наука, 1985.

19. Угольницкий Г.А. Модели социальной иерархии. – М.: Вузовская книга, 2000.

20. Хеллевик Оттар. Социологический метод. – М.: Весь Мир, 2002.

21. Холл Маршалл. Комбинаторика. – М.: Мир, 1970.

22. Эрдёш Пауль, Спенсер Джоэл. Вероятностные методы в комбинаторике. – М.: Мир, 1976.

23. Яблонский С.В. Введение в дискретную математику: Учебное пособие для ВУЗов. – М.: Высшая школа, 2001.
V. Содержание программы.
Раздел 1. Комбинаторные методы дискретной математики.
Тема 1.1. История развития, классические задачи.

Структура курса дискретной математики. Два направления математического образования (дискретность и непрерывность, конечность и актуальная бесконечность). Предмет комбинаторики, история развития, генезис современного состояния. Конструирование и анализ комбинаторных алгоритмов. Два правила комбинаторики (правило суммы, правило произведения). Классические задачи комбинаторного анализа. Задача размещения объектов по ячейкам при различных ограничениях. Количество слов в алфавите при различных ограничениях.

Основная литература

[2], С. 73 - 77

Дополнительная литература

[18], С. 159 – 161.

Тема 1.2. Размещения и производящие функции.

Количество всевозможных размещений различных объектов по различным ячейкам. Количество различных слов заданной длины в заданном алфавите. Количество размещений различных объектов по различным ячейкам при условии, что каждая ячейка содержит не более одного элемента. Количество слов заданной длины без повторений символов в заданном алфавите. Перестановки элементов. Упорядоченные размещения различных объектов по различным ячейкам.

Число монотонных слов заданной длины в заданном алфавите. Задача Муавра о числе способов представления натурального числа как упорядоченной суммы неотрицательных целых чисел. Сочетания и биномиальные коэффициенты. Производящие функции. Бином Ньютона. Основные комбинаторные тождества для чисел сочетаний. Полиномиальные коэффициенты. Задача о числе размещений различных объектов по различным ячейкам при заданном количестве объектов в каждой ячейке. Производящая функция для полиномиальных коэффициентов, основные комбинаторные тождества для них.
Основная литература

[2], С. 86 – 92

Дополнительная литература

[18], С. 162, 167 – 169.

Тема 1.3. Рекуррентные соотношения. Разбиения.

Рекуррентные соотношения, задача о Ханойских башнях. Рекуррентные соотношения для биномиальных коэффициентов. Разбиения объектов на классы (числа Стирлинга второго рода), связь разбиений с размещениями.

Основная литература

[2], С. 103 - 106

Дополнительная литература

[18], С. 163.

Тема 1.4. Логические методы комбинаторного анализа.

Принцип включений – исключений. Формула включений – исключений. Задача о числе беспорядков.

Основная литература

[2], С. 77 – 79.

Дополнительная литература

[18], С. 166.

Тема 1.5 Двенадцатеричный путь.

Двенадцатеричный путь: количество размещений объектов по ячейкам (объекты различные или одинаковые; ячейки различные или одинаковые; размещения произвольные, либо каждая ячейка не пуста, либо в каждой ячейке не более одного элемента).

Основная литература

[2], С. 77 – 79.

Дополнительная литература

[18], С. 166.

Тема 1.6. Модели и задачи комбинаторного анализа в социологии.

Комбинаторные задачи планирования выборочных обследований. Экстремальные комбинаторные задачи о выборе информативных признаков, “о покрытиях”. Модели парных взаимодействий.

Основная литература

[4].

Дополнительная литература

[2], [10], [14], [19].

Раздел 2. Отношения и функции.
Тема 2.1 Определения и основные понятия.

Понятие декартова произведения множеств. Отношения, матричное и графическое представление отношений. Бинарные отношения и их свойства.

Основная литература

[2].

Дополнительная литература

[17], С. 166.

Тема 2.2 Частично упорядоченные множества. Функции выбора

Специальные классы бинарных отношений: частичные порядки, слабые порядки, линейные порядки, отношения эквивалентности. Внутренняя и внешняя устойчивость. Ядро. Выбор по отношениям предпочтения. Свойства функций выбора.

Основная литература

[2].

Дополнительная литература

[17].
Раздел 3. Элементы теории графов.

Тема 3.1. История развития, генезис понятий, классические задачи.

Становление и развитие теории графов. Задача Эйлера о кенигсбергских мостах. Проблема четырех красок. Генезис современного состояния предмета.

Основная литература

[2], С. 173 – 174.

[3], С. 192 – 200.

[5], С. 11 – 29.

Дополнительная литература

[15], С. 127 – 130.

[18], С. 108 – 113.
Тема 3.2. Ориентированные и неориентированные графы.

Определение графа. Графы неориентированные и ориентированные. Отношения смежности и инцидентности. Неориентированный полный граф. Ориентированный полный граф. Расширения понятия графа (петли, несколько ребер). Простой граф. Конечный граф. Изоморфные графы. Степени вершин. О представлении графов (матрица инциденций, матрица смежности вершин). Пути и циклы. Связность. Подграфы. Связные компоненты (или компоненты связности). Поиск в графе. Примеры задач поиска в графе (базы данных, задача о взаимозачетах). Поиск в глубину. Поиск в ширину. Деревья. Остовное дерево (каркас). Алгоритм построения остовного дерева методом поиска в глубину. Кратчайшие пути в связном неориентированном графе из заданной вершины до всех остальных вершин.

Основная литература

[2], С. 174 – 175, 183 - 192.

[3], С. 215 – 222.

[5], С. 47 – 90.

Дополнительная литература

[3], С. 238 – 273.

[15], С. 133 – 144.

[18], С. 119 – 125.

Тема 3.3. Эйлеровы пути и циклы.

Эйлеровы пути и циклы. Теорема о существовании эйлеровых путей и циклов в графе. Алгоритм построения эйлеровых циклов. Оценка сложности алгоритма.

Основная литература

[2], С. 194 – 199.

[5], С. 34 – 37.

Дополнительная литература

[1], C. 270 – 277.

Тема 3.4. Гамильтоновы пути и циклы.

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

Основная литература

[2], С. 73 – 77.

[5], С. 40 – 42.

Дополнительная литература

[22], С. 85 – 87.

Тема 3.5. Паросочетания в графах.

Двудольные графы. Паросочетания в графах. Нахождение максимального паросочетания в графе (задача о назначениях). Системы представителей множеств. Системы различных представителей, необходимое и достаточное условие их существования.

Основная литература

[5].

Дополнительная литература

[3].

VI. Вопросы для оценки качества освоения программы,

тематика заданий по различным формам текущего контроля
Домашнее задание 1.

Размещения, перестановки, сочетания. Биномиальные коэффициенты. Рекуррентные соотношения. Числа Фибоначчи. Разбиения. Основные комбинаторные тождества и соотношения. Метод включений - исключений.

Домашнее задание 2.

Изоморфизм графов. Степени вершин и количество ребер в графе. Пути и циклы. Пути максимальной длины. Компоненты связности. Эйлеровы и гамильтоновы циклы.

Контрольная работа 1. Элементы комбинаторики.

Размещения, перестановки, сочетания.

Биномиальные коэффициенты.

Разбиения.

Основные комбинаторные тождества и соотношения.

Метод включений – исключений.

Методические указания студентам.
Для закрепления материала каждой лекции рекомендуется активная работа на семинарах, регулярное выполнение домашних заданий и решение дополнительных задач на текущую тему, даваемых на семинарах, имеющихся в задачниках [2, 6] (Основная литература), а также в основной литературе [1, 4, 9, 11].
Автор программы: Т.В.Андреева