Бакалавриат
2019/2020
Дискретная математика для социологов
Статус:
Курс по выбору (Социология)
Направление:
39.03.01. Социология
Кто читает:
Кафедра высшей математики
Где читается:
Факультет социальных наук
Когда читается:
1-й курс, 4 модуль
Формат изучения:
без онлайн-курса
Язык:
русский
Кредиты:
3
Контактные часы:
40
Программа дисциплины
Аннотация
Настоящая программа учебной дисциплины устанавливает требования к образовательным результатам и результатам обучения студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих дисциплину «Дискретная математика для социологов», учебных ассистентов и студентов направления подготовки 39.03.01 «Социология», обучающихся по образовательной программе «Социология». Программа учебной дисциплины разработана в соответствии с: • Образовательным стандартом НИУ ВШЭ; • Образовательной программой 39.03.01 «Социология». • Объединенным учебным планом университета по образовательной программе «Социология», утвержденным в 2018г.
Цель освоения дисциплины
- Целями освоения дисциплины «Дискретная математика для социологов» являются знакомство студентов с основными понятиями и методами двух разделов дискретной математики – комбинаторики и теории графов.
Планируемые результаты обучения
- Способен учиться, приобретать новые знания, умения, в том числе в области, отличной от профессиональной
- Способен работать в команде
- Способен использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования при решении профессиональных задач
- Способен критически воспринимать, обобщать, анализировать профессиональную информацию
Содержание учебной дисциплины
- Множества и операции с ними.Множество, элементы множества, подмножества. Равенство множеств. Мощность множества. Пустое множество. Основные операции с множествами: объединение, пересечение, разность, дополнение, симметрическая разность. Простейшие свойства операций с множествами.
- Комбинаторика. Основные задачи комбинаторикиПравило суммы и правило произведения. Размещения без повторений и размещения с повторениями. Перестановки. Сочетания. Число сочетаний
- Бином Ньютона. Свойства биномиальных коэффициентов.Бином Ньютона и биномиальные коэффициенты. Связь биномиальных коэффициентов с числом сочетаний. Свойства биномиальных коэффициентов.
- Разбиения натурального числа.Представление натурального числа в виде суммы натуральных чисел. Количество целочисленных решений уравнения x1+...+xk = n.
- Основные понятия теории графов.Граф, ребра графа, вершины графа. Графы неориентированные и ориентированные. Отношения смежности и инцидентности. Неориентированный полный граф. Ориентированный полный граф. Полный граф. Расширения понятия графа (петли, несколько ребер). Простой граф. Конечный граф. Изоморфные графы. Степени вершин. Пути и циклы. Связность. Подграфы. Связные компоненты (или компоненты связности). Деревья. Остовное дерево (каркас).
- Изоморфизм графов.Понятие о взаимно-однозначном соответствии и изоморфизме. Изоморфные графы. Необходимые условия изоморфности неориентированных графов.
- Эйлеровы пути и циклыЗадача о кенигсбергских мостах. Эйлеровы пути и циклы. Теорема о существовании эйлеровых путей и циклов в графе. Алгоритм построения эйлеровых циклов.
- Гамильтоновы пути и циклы.Сложность задачи проверки существования гамильтонова цикла. Задача обхода шахматной доски конем.
- Задача коммивояжера и другие задачи на графах.Задача коммивояжера. Точные методы решения задачи и «быстрые», но неточные алгоритмы.
Промежуточная аттестация
- Промежуточная аттестация (4 модуль)0.36 * Аудиторная работа + 0.24 * Домашние задания + 0.4 * Зачет
Список литературы
Рекомендуемая основная литература
- Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике - Издательство "Физматлит" - 2009 - 416с. - ISBN: 978-5-9221-0477-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2157
- Задачи и упражнения по дискретной математике : учеб. пособие, Гаврилов, Г. П., 2005
Рекомендуемая дополнительная литература
- Дискретная математика : курс лекций для студентов-механиков, Редькин, Н. П., 2006
- Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин, Н. К., 2012
- Теория графов, Оре, О., 1968