• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Discrete Mathematics

2020/2021
Academic Year
RUS
Instruction in Russian
4
ECTS credits
Course type:
Compulsory course
When:
2 year, 1, 2 module

Instructors


Guskova, Mariia

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

Аннотация

Настоящая дисциплина относится к базовой части математического и естественнонаучного цикла дисциплин образовательной программы "Информатика и вычислительная техника". Цели изучения дисциплины: знакомство с понятиями дискретной математики и теории графов; освоение основных приемов решения практических задач по темам дисциплины; развитие способности интерпретации формальных алгебраических структур, развитие четкого логического мышления. В результате освоения дисциплины студент должен: • Знать базовые понятия дисциплины • Понимать доказательства ключевых теорем курса • Иметь навыки использования математического аппарата дисциплины в дальнейшей учебной и профессиональной деятельности
Цель освоения дисциплины

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

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

Планируемые результаты обучения

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

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

  • Элементы теории множеств
    Типы множеств, основные операции над множествами, законы и, способы доказательств в теории множеств, формула включений и исключений и ее применения.
  • Элементы математической логики
    Основные понятия и способы доказательств в булевской логике, логические функции и их представления, основные понятия логики высказываний, методы доказательства в логике высказываний
  • Методы подсчета и оценивания
    Производящие функции для последовательностей чисел, основные свойства производящих функций, применение производящих функций для решения рекуррентных уравнений и нахождения конечных сумм
  • Комбинаторные схемы
    Определение чисел размещений, перестановок и сочетаний предметов без повторений и с повторениями, определение чисел упорядоченных и неупорядоченных разбиений конечных множеств, бином Ньютона и полиноминальная формула
  • Транспортные сети
    Транспортные сети и их свойства, арифметические и алгебраические потоки, соотношения на транспортной сети, разрезы в транспортной сети, задача о максимальной величине потока в транспортной сети и алгоритм Форда-Фалкерсона, теорема Форда-Фалкерсона
  • Основы теории графов
    Виды графов, связные графы и деревья, матрицы инцидентности, смежноси и весовые матрицы, построение остовных деревьев в связных графах, минимальное остовное дерево, определение остовных деревьев по матрице инцидентности, нахождение минимальных путей на ориентированных графах, мультиграфы и эйлеровы циклы
Элементы контроля

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

  • неблокирующий Активность на семинарских занятиях 1
  • неблокирующий Домашние задания 1
  • неблокирующий Контрольная работа 1
  • неблокирующий Контрольная работа 2
  • неблокирующий Самостоятельная работа 1
  • неблокирующий Экзамен 1
  • неблокирующий контрольно-измерительные материалы
    контрольно-измерительные материалы
  • неблокирующий Активность на семинарских занятиях 2
  • неблокирующий Домашние задания 2
  • неблокирующий Контрольная работа 3
  • неблокирующий Контрольная работа 4
  • неблокирующий Самостоятельная работа 2
  • неблокирующий Экзамен 2
  • неблокирующий контрольно-измерительные материалы
    контрольно-измерительные материалы
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.1 * Активность на семинарских занятиях 1 + 0.1 * Активность на семинарских занятиях 2 + 0.075 * Контрольная работа 1 + 0.075 * Контрольная работа 2 + 0.075 * Контрольная работа 3 + 0.075 * Контрольная работа 4 + 0.25 * Экзамен 1 + 0.25 * Экзамен 2
Список литературы

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

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

  • Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике - Издательство "Физматлит" - 2009 - 416с. - ISBN: 978-5-9221-0477-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2157
  • Гладков Л.А., Курейчик В.В., Курейчик В.М. - Дискретная математика - Издательство "Физматлит" - 2014 - 496с. - ISBN: 978-5-9221-1575-9 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/71976

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

  • Дискретная математика : Алгоритмы и программы: Учеб. пособие, Иванов, Б. Н., 2002
  • Дискретная математика : Логика, группы, графы, Акимов, О. Е., 2001