• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
14
Март

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

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
3
Кредиты
Статус:
Курс по выбору
Когда читается:
1-й курс, 4 модуль

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

Аннотация

Настоящая программа учебной дисциплины устанавливает требования к образовательным результатам и результатам обучения студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих дисциплину «Дискретная математика для социологов», учебных ассистентов и студентов направления подготовки 39.03.01 «Социология», обучающихся по образовательной программе «Социология». Программа учебной дисциплины разработана в соответствии с: • Образовательным стандартом НИУ ВШЭ; • Образовательной программой 39.03.01 «Социология». • Объединенным учебным планом университета по образовательной программе «Социология», утвержденным в 2018г.
Цель освоения дисциплины

Цель освоения дисциплины

  • Целями освоения дисциплины «Дискретная математика для социологов» являются знакомство студентов с основными понятиями и методами двух разделов дискретной математики – комбинаторики и теории графов.
Результаты освоения дисциплины

Результаты освоения дисциплины

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

Содержание учебной дисциплины

  • Множества и операции с ними.
    Множество, элементы множества, подмножества. Равенство множеств. Мощность множества. Пустое множество. Основные операции с множествами: объединение, пересечение, разность, дополнение, симметрическая разность. Простейшие свойства операций с множествами.
  • Комбинаторика. Основные задачи комбинаторики
    Правило суммы и правило произведения. Размещения без повторений и размещения с повторениями. Перестановки. Сочетания. Число сочетаний
  • Бином Ньютона. Свойства биномиальных коэффициентов.
    Бином Ньютона и биномиальные коэффициенты. Связь биномиальных коэффициентов с числом сочетаний. Свойства биномиальных коэффициентов.
  • Разбиения натурального числа.
    Представление натурального числа в виде суммы натуральных чисел. Количество целочисленных решений уравнения x1+...+xk = n.
  • Основные понятия теории графов.
    Граф, ребра графа, вершины графа. Графы неориентированные и ориентированные. Отношения смежности и инцидентности. Неориентированный полный граф. Ориентированный полный граф. Полный граф. Расширения понятия графа (петли, несколько ребер). Простой граф. Конечный граф. Изоморфные графы. Степени вершин. Пути и циклы. Связность. Подграфы. Связные компоненты (или компоненты связности). Деревья. Остовное дерево (каркас).
  • Изоморфизм графов.
    Понятие о взаимно-однозначном соответствии и изоморфизме. Изоморфные графы. Необходимые условия изоморфности неориентированных графов.
  • Эйлеровы пути и циклы
    Задача о кенигсбергских мостах. Эйлеровы пути и циклы. Теорема о существовании эйлеровых путей и циклов в графе. Алгоритм построения эйлеровых циклов.
  • Гамильтоновы пути и циклы.
    Сложность задачи проверки существования гамильтонова цикла. Задача обхода шахматной доски конем.
  • Задача коммивояжера и другие задачи на графах.
    Задача коммивояжера. Точные методы решения задачи и «быстрые», но неточные алгоритмы.
Элементы контроля

Элементы контроля

  • неблокирующий Аудиторная работа
  • неблокирующий Домашние задания
  • неблокирующий Зачет
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (4 модуль)
    0.36 * Аудиторная работа + 0.24 * Домашние задания + 0.4 * Зачет
Список литературы

Список литературы

Рекомендуемая основная литература

  • - Гаврилов Г.П., Сапоженко А.А. — Задачи и упражнения по дискретной математике - Издательство "Физматлит" - 2009 - ISBN: 978-5-9221-0477-7 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/2157
  • Задачи и упражнения по дискретной математике : учеб. пособие, Гаврилов Г. П., Сапоженко А. А., 2005

Рекомендуемая дополнительная литература

  • Дискретная математика : курс лекций для студентов-механиков, Редькин Н. П., 2006
  • Лекции по математической логике и теории алгоритмов. Ч.1: Начала теории множеств, Верещагин Н. К., Шень А., 2012
  • Теория графов, Оре О., Врублевской И. Н., 1968