Дискретная математика

2019/2020

Учебный год

RUS

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

6

Кредиты

Кто читает:

Направление «Бизнес-информатика» Высшей школы бизнеса НИУ ВШЭ

Статус:

Курс обязательный

Когда читается:

1-й курс, 1 модуль

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

Аннотация

Дисциплины «Дискретная математика» является одной из базовых дисциплин для подготовки студентов по направлению Бизнес-информатика. Содержание дисциплины направлено на изучение студентами дискретной математики, как математической и логической основы разработки информационных технологий.

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

• Целями освоения дисциплины «Дискретная математика» являются: ознакомление студентов с основами современной дискретной математики; формирование навыков работы с абстрактными понятиями математики; знакомство с прикладными задачами дисциплины.

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

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

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

• Алгебра высказываний, предикаты и кванторы, логические функции
  Понятие высказывания. Логические операции на высказываниях. Предикаты и кванторы. Булевы (логические) функции и способы их задания. Эквивалентные преобразования логических формул.
• Множества и соответствия
  Множества - основные понятия. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Прямое произведение множеств. Соответствия, теоретикомножественные операции над соответствиями, полный образ и прообраз множества при данном соответствии, классификация соответствий: всюдуопределенность, функциональность, инъективность, сюръективность. Частичные функции, отображения, взаимно-однозначные соответствия. Обратимость частичной функции и отображения. Композиция соответствий и ее свойства. Матричное представление композиции соответствий. Понятие функции. Обратные функции. Суперпозиции и формулы. Способы задания функций. Обратимые отображения и их свойства. Преобразования множества, подстановки.
• Комбинаторика Предмет комбинаторики.
  Правило суммы и правило произведения. Принцип включения и исключения. Размещения, перестановки, сочетания без повторений и с повторениями. Биномиальные коэффициенты и соотношения для них. Задачи перечисления. Подсчет числа функций с конечными областями определения. Задача Муавра.
• Бинарные отношения Общее понятие отношения.
  Бинарные отношения и их свойства (рефлексивность, симметричность, транзитивность). Транзитивное замыкание отношений. Отношение эквивалентности и классы эквивалентности. Отношение толерантности, классы толерантности. Отношение порядка. Диаграммы Хассе. Линейный порядок и частичный порядок. Квазипорядок. Решетки.
• Математическая логика и логика предикатов
  Способы задания логических функций, фиктивные и существенные переменные, порядок логической функции. Формулы над системой логических функций или их суперпозиции. Теорема о разложении логических функций по переменным. Совершенные дизъюнктивные и конъюнктивные формы. Определение замкнутого класса. Полные системы функ-ций. Базис и порядок замкнутого класса. Алгебра Жегалкина. Теорема об единственности многочлена Жегалкина. Классы Поста: функции сохраняющие 0, функции сохраняющие 1, самодвойственные функции, монотонные функции, линейные функции. Теорема Поста о функциональной полноте. Логические методы анализа и синтеза переключательных схем. Логика предикатов. Предметная область и предметные переменные. Правильно по-строенные формулы. Кванторы общности и существования. Свободные и связанные пе-ременные. Общезначимые и противоречивые формулы. Запись утверждений естествен-ного языка в логике предикатов. Логический вывод в логике высказываний. Теорема де-дукции и ее следствия. Логический вывод в логике предикатов на основе правила резолюции. Извлечение ответа на вопрос из опровержения, основанного на резолюции.
• Теория графов
  Основные определения: неориентированные и ориентированные графы, мультиграфы и кратные ребра. Смежность и инцидентность. Локальные степени вершин. Способы представления графов. Матрицы смежности и инцидентности. Графы и бинарные отношения. Изоморфизм графов. Части графов, суграфы и подграфы. Пути, циклы, цепи, простые цепи в неориентированных графах. Связность и компоненты связности. Шарниры мосты и блоки графа. Расстояния. Центр, радиус, диаметр графа. Виды связности в ориентированных графах: сильная связность, односторонняя связность. Задачи о цепях: эйлеровы циклы, гамильтоновы циклы. Основные числа теории графов: цикломатическое число, хроматическое число. Бихроматические (двудольные) графы. Число внутренней устойчи-вости. Число внешней устойчивости. Метод Магу для отыскания всех максимальных внутренне устойчивых множеств, а также минимальных внешне устойчивых множеств. Метод Магу для нахождения хроматического числа графа. Деревья. Алгоритмы нахождения связных суграфов заданного графа с взвешенными ребрами с минимальной стоимостью. Плоские графы, формула Эйлера, необходимые и достаточные условия того, что граф является плоским (теорема Понтрягина-Куратовского). Транспортные сети. Потоки в транспортных сетях. Алгоритм Форда-Фалкерсона для нахождения максимального по-тока. Теорема Форда-Фалкерсона. Алгоритм Дейкстры поиска наикратчайшего пути на орграфе с взвешенными дугами.
• Теория алгоритмов
  Общее понятие алгоритма. Требования к алгоритмам. Емкостная и вычислительная сложность алгоритмов. Понятие рекурсии. Рекурсивные функции. Тезис Черча. Машины Тьюринга. Некоторые алгоритмически неразрешимые проблемы.
• Конечные автоматы
  Понятие конечного автомата Мили и автомата Мура. Примеры применения. Автоматные функции, способы их задания. Минимизация автоматов. Теорема о преобразовании периодической последовательности автоматной функцией. Теорема Мура.

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

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

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

• Промежуточная аттестация (1 модуль)
  0.6 * контрольная работа + 0.4 * самостоятельная работа

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

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

• Гашков С. Б., Фролов А. Б. - ДИСКРЕТНАЯ МАТЕМАТИКА 3-е изд., испр. и доп. Учебник и практикум для вузов - М.:Издательство Юрайт - 2019 - 483с. - ISBN: 978-5-534-11613-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-445753
• Дискретная математика для инженера : [учеб. пособие], Кузнецов О.П., 2009
• Плотникова Е. Г., Левко С. В., Логинова В. В., Хакимова Г. М. ; Под общ. ред. Плотниковой Е. Г. - МАТЕМАТИЧЕСКИЙ АНАЛИЗ И ДИСКРЕТНАЯ МАТЕМАТИКА 2-е изд., пер. и доп. Учебное пособие для вузов - М.:Издательство Юрайт - 2019 - 300с. - ISBN: 978-5-534-07545-8 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/matematicheskiy-analiz-i-diskretnaya-matematika-441347

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

• Андреев А. Е., Болотов А. А., Коляда К. В., Фролов А. Б. - ДИСКРЕТНАЯ МАТЕМАТИКА: ПРИКЛАДНЫЕ ЗАДАЧИ И СЛОЖНОСТЬ АЛГОРИТМОВ 2-е изд., испр. и доп. Учебник и практикум для академического бакалавриата - М.:Издательство Юрайт - 2019 - 317с. - ISBN: 978-5-534-04246-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-prikladnye-zadachi-i-slozhnost-algoritmov-444120
• под науч. ред. Сесекина А.Н. - ДИСКРЕТНАЯ МАТЕМАТИКА. Учебное пособие для вузов - М.:Издательство Юрайт - 2019 - 108с. - ISBN: 978-5-534-08214-2 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-438245