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




Скачать 16,51 Kb.
НазваниеПрограмма дисциплины Дискретная математика для социологов
Дата03.02.2016
Размер16,51 Kb.
ТипПрограмма дисциплины
Правительство Российской Федерации


Государственное образовательное бюджетное учреждение

высшего профессионального образования


«Государственный университет –

Высшая школа экономики»


Общеуниверситетская кафедра высшей математики


Программа дисциплины


Дискретная математика для социологов


для направления 040200.62

«Социология»

подготовки бакалавра


Автор: Дагаев Д.А.


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


______________________________ Высшей математики ГУ ВШЭ

______________________________

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

______________________________ Зав. кафедрой проф. Макаров А.А.

___________________________

«_____» __________________ 2011 г. «____»__________________ 2011 г.


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

Социологии

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

________________________________

« ____» ___________________2011 г.


Москва, 2011


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


Требования к студентам:

Курс «Дискретная математика для социологов» предназначен для студентов 1-го курса бакалавриата факультета социологии. Он является курсом по выбору и читается во втором семестре.

Для успешного освоения материала курса студенты должны владеть курсом математики в объёме школьной программы.


Цель курса:

Социолог-исследователь в своей научной и практической деятельности нередко сталкивается с математическими объектами, имеющими дискретную структуру. Многие задачи, которые приходится в связи с этим решать, носят комбинаторный характер (например, к таким задачам можно отнести задачу составления репрезентативной выборки из группы людей, поделенной по некоторому признаку на несколько подгрупп). Ряд других социологических задач может быть сформулирован на языке теории графов (например, к таким задачам относится сетевой анализ). Целью курса «Дискретная математика для социологов» является знакомство студентов с основными понятиями и методами двух разделов дискретной математики – комбинаторики и теории графов.


Задача курса:

В результате прослушивания курса студент должен:

  • освоить основные понятия и методы комбинаторики и теории графов;

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

  • научиться решать комбинаторные задачи и задачи теории графов, а также анализировать полученные решения;

  • приобрести необходимые знания и навыки для прослушивания последующих курсов, имеющих как прикладную, так и теоретическую математическую направленность.



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




Тема

Аудиторные часы

Самостоятельная работа

Всего







Лекции

Семинары








1

Множества и операции с ними

2

1

5

7

2

Комбинаторика. Основные задачи комбинаторики.

2

2

7

11

3

Бином Ньютона. Свойства биномиальных коэффициентов

2

2

7

11

4

Принцип включений и исключений. Диаграммы Эйлера-Венна

2

2

7

11

5

Разбиения натурального числа

2

1

6

9

6


Рекуррентные соотношения. Последовательность Фибоначчи

2

1

6

10

7

Контрольная работа


2










8

Основные понятия теории графов

2

4

7

11

9

Изоморфизм графов

2

2

5

9

10

Эйлеровы пути и циклы

2

2

5

9

11

Гамильтоновы пути и циклы

2

2

5

9

12

Задача коммивояжера

2

2

8

11




ИТОГО

24

21

63

108



Формы контроля

  • Текущий контроль осуществляется на семинарах в форме обсуждения прочитанной литературы, проверки и обсуждения семинарских домашних заданий и решения семинарских задач. Оценка за семинары выставляется с учетом активности студента на занятиях, выполнения им семинарских домашних и аудиторных работ.

Текущий контроль также включает в себя контрольную работу и отдельное домашнее задание, тематика которого оговаривается со студентами в индивидуальном порядке.

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


  • Итоговый контроль: зачет.


Результирующая оценка вычисляется по формуле


Результирующая оценка = 0,4×Оценка за зачет + 0,6×Накопленная оценка

Указанная схема формирования результирующей оценки применяется только при наличии положительного результата выполнения зачетной работы (т.е. при получении студентами за зачет не менее 4 баллов). В противном случае независимо от итоговой суммы баллов работа студента оценивается «незачет».


В случае пересдачи или комиссии пересдается лишь зачетная работа, а накопленная оценка остается неизменной.


Литература

Базовые учебники


1. Андреева Т.В. Методические указания по курсу «Дискретная математика для социологов». М.: ГУ ВШЭ, 2007.

2. Оре О. Графы и их применение. М.: Мир, 1965.

3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005.


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


1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2008.

2. Верещагин Н.К., Шень А. Начала теории множеств. М.: МЦНМО, 2002.

3. Воробьев Н.Н. Числа Фибоначчи. М.: Наука, 1984.

4. Мудров В.И. Задача о коммивояжере. М.: Знание, 1969.


Содержание программы


Тема 1. Множества и операции с ними.

Множество, элементы множества, подмножества. Равенство множеств. Мощность множества. Пустое множество. Основные операции с множествами: объединение, пересечение, разность, дополнение, симметрическая разность. Простейшие свойства операций с множествами.


Литература:

1. Верещагин Н.К., Шень А. Начала теории множеств. М.: МЦНМО, 2002. Разделы 1.1 и 1.2.

2. Андреева Т.В. Методические указания по курсу «Дискретная математика для социологов». М.: ГУ ВШЭ, 2007. Часть I. §1.


Тема 2. Комбинаторика. Основные задачи комбинаторики.

Правило суммы и правило произведения. Размещения без повторений и размещения с повторениями. Перестановки. Сочетания. Число сочетаний.


Литература:

1. Андреева Т.В. Методические указания по курсу «Дискретная математика для социологов». М.: ГУ ВШЭ, 2007. Часть I. §§1-4.

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. Глава VIII, §1.


Тема 3. Бином Ньютона. Свойства биномиальных коэффициентов

Бином Ньютона и биномиальные коэффициенты. Связь биномиальных коэффициентов с числом сочетаний. Свойства биномиальных коэффициентов.


Литература:

1. Андреева Т.В. Методические указания по курсу «Дискретная математика для социологов». М.: ГУ ВШЭ, 2007. Часть I. §5.

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. Глава VIII, §1.


Тема 4. Принцип включений и исключений. Диаграммы Эйлера-Венна

Принцип включений – исключений. Формула включений – исключений. Графическое представление пересекающихся множеств с помощью диаграмм Эйлера-Венна.


Литература:

1. Андреева Т.В. Методические указания по курсу «Дискретная математика для социологов». М.: ГУ ВШЭ, 2007. Часть I. §7.

2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. Глава VIII, §2.


Тема 5. Разбиения натурального числа.

Представление натурального числа в виде суммы натуральных чисел. Количество целочисленных решений уравнения x1+...+xk = n.


Литература:

1. Андреева Т.В. Методические указания по курсу «Дискретная математика для социологов». М.: ГУ ВШЭ, 2007. Часть I. §6.


Тема 6. Рекуррентные соотношения. Последовательность Фибоначчи.

Задание последовательности чисел с помощью рекуррентных соотношений. Задача о кроликах. Последовательность Фибоначчи. Свойства чисел Фибоначчи.


Литература:

1. Воробьев Н.Н. Числа Фибоначчи. М.: Наука, 1984. Введение, §1.


Тема 8. Основные понятия теории графов.

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


Литература:

1. Андреева Т.В. Методические указания по курсу «Дискретная математика для социологов». М.: ГУ ВШЭ, 2007. Часть II. §9.

2. Оре О. Графы и их применение. М.: Мир, 1965. Глава I.

3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. Глава VI, §1.


Тема 9. Изоморфизм графов.

Понятие о взаимно-однозначном соответствии и изоморфизме. Изоморфные графы. Необходимые условия изоморфности неориентированных графов.


Литература:

1. Андреева Т.В. Методические указания по курсу «Дискретная математика для социологов». М.: ГУ ВШЭ, 2007. Часть II. §11.

2. Оре О. Графы и их применение. М.: Мир, 1965. Глава I, §3.

3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2005. Глава VI, §1.


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

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

Литература:

1. Оре О. Графы и их применение. М.: Мир, 1965. Глава II, §§1-4.


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

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


Литература:

1. Оре О. Графы и их применение. М.: Мир, 1965. Глава II, §§5,6.


Тема 12. Задача коммивояжера.

Задача коммивояжера. Точные методы решения задачи и «быстрые», но неточные алгоритмы.


Литература:

1. Мудров В.И. Задача о коммивояжере. М.: Знание, 1969.


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


1. Докажите, что для любых конечных множеств A, B, C выполняется соотношение (A∩B)∩C=A∩(B∩C).

2. Сколькими способами в високосном году могут распределиться дни рождения студентов группы, состоящей из 25 человек?

3. Сколько различных 10-буквенных слов (возможно, бессмысленных) можно составить из букв слова СОЦИОЛОГИЯ, если каждую букву разрешается использовать ровно по одному разу?

4. В выражении (2+x)100 раскрыли скобки и привели подобные слагаемые. Чему равен коэффициент при x95?

5. В ходе социологического исследования выяснилось, что 70% респондентов читают газету А, 60% - газету B, 50% - газету С, 30% - газеты А и В, 30% - газеты В и С, 20% - газеты А и С, 10% - газеты А, В и С. Постройте диаграмму Эйлера-Венна. Сколько респондентов читают хотя бы две газеты? Сколько респондентов читают ровно две газеты?

6. Пусть un – n-ое число последовательности Фибоначчи. Что больше: 2u14 или u16?

7. Построить все попарно неизоморфные графы, содержащие 4 вершины и не имеющие петель и кратных ребер.

8. Сколько ребер в полном графе, содержащем n вершин?

9. По заданному графу определить, существует ли в нем эйлеров цикл.

10. Привести пример графа, для которого «жадный» алгоритм решения задачи коммивояжера приводит к неоптимальному решению.


Автор программы _________________________________ / Д.А. Дагаев /

Похожие:

Программа дисциплины Дискретная математика для социологов iconПрограмма наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках
Наименование дисциплины: Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках
Программа дисциплины Дискретная математика для социологов iconРабочая программа учебной дисциплины опд. Ф «Дискретная математика»
Соответствие гос (для федеральных дисциплин) или соответствия требованиям ооп (для региональных и вузовских) указание на недостаточно...
Программа дисциплины Дискретная математика для социологов iconРабочая программа по дисциплине «дискретная математика» для специальности 010200 Прикладная математика и информатика Форма обучения: очная
Рабочая программа составлена на основании гос впо 010200 – Прикладная математика и информатика, утвержденного в 2000 г
Программа дисциплины Дискретная математика для социологов iconРабочая программа учебной дисциплины ен. Ф «Дискретная математика»
Рабочая программа учебной дисциплины обсуждена на заседании кафедры математики и математического моделирования факультета информационных...
Программа дисциплины Дискретная математика для социологов iconДискретная математика
Общая трудоемкость дисциплины составляет 4 зачетных единицы, 144 часа, в том числе 72 часа аудиторных занятий
Программа дисциплины Дискретная математика для социологов iconРабочая программа дисциплины «Математика» для специальности
Рабочая программа учебной дисциплины «Математика» предназначена для реализации государственных требований к минимуму содержания и...
Программа дисциплины Дискретная математика для социологов iconРабочая программа дисциплины «Математика» для специальности
Рабочая программа учебной дисциплины «Математика» предназначена для реализации государственных требований к минимуму содержания и...
Программа дисциплины Дискретная математика для социологов iconРабочая программа дисциплины «математика»
Рабочая программа дисциплины «математика» для студентов, обучающихся по направлению 080200 «Менеджмент»
Программа дисциплины Дискретная математика для социологов iconРабочая программа дисциплины «математика»
Рабочая программа дисциплины «математика» для студентов, обучающихся по направлению 100400 «Туризм»
Программа дисциплины Дискретная математика для социологов iconРабочая программа дисциплины «математика»
Рабочая программа дисциплины «математика» для студентов, обучающихся по направлению 080200 «Менеджмент»
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib2.znate.ru 2012
обратиться к администрации
Библиотека
Главная страница