• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 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