• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2018/2019

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

Статус: Курс обязательный (Бизнес-информатика)
Направление: 38.03.05. Бизнес-информатика
Когда читается: 1-й курс, 2-4 модуль
Формат изучения: Full time
Язык: русский
Кредиты: 8

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

Аннотация

Дискретная математика – базовая дисциплина, входящая в цикл ОПД.00 «Общие профессиональные дисциплины направления» и блок СД.00 «Специальные дисциплины». Дискретная математика – наука, лежащая в основе современной прикладной математике, результаты и методы которой (наряду с математическим анализом и линейной алгеброй) используются практически в любой дисциплине, включающей в себя математические модели. В то же время дискретная математика – наука более молодая и, соответственно, менее глубокая и более доступная для изучения «без купюр». Освоение курса не требует знаний, выходящих за рамки школьной программы, но при обучении используются понятия, параллельно возникающие в курсах математического анализа, геометрии и алгебры, теоретических основ информатики.
Цель освоения дисциплины

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

  • Познакомить студентов с основами современной дискретной математики;
  • Показать, как дискретная математика используется в экономических и «программистских» дисциплинах
  • Научить студентов работать с формальными математическими понятиями, в том числе строго доказывать простые утверждения
Результаты освоения дисциплины

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

  • Умение записывать словесные рассуждения в логической форме.
  • Понимание разницы между счетными и континуальными множествами.
  • Знание определений теории множеств и их связи с математической логикой.
  • Освоение начальных комбинаторных навыков
  • Умение применять бинарные отношения к прикладным моделям.
  • Освоение теории графов и их приложений.
  • Понимание основных алгоритмически неразрешимых проблем.
  • Понимание работы системы RSA
Содержание учебной дисциплины

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

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

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

  • неблокирующий Контрольная работа (4 шт)
  • неблокирующий Домашнее задание
  • неблокирующий Экзаменационная контрольная.
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.15 * Домашнее задание + 0.4 * Контрольная работа (4 шт) + 0.45 * Экзаменационная контрольная.
Список литературы

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

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

  • - Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. — Бинарные отношения, графы и коллективные решения - Издательство "Физматлит" - 2012 - ISBN: 978-5-9221-1363-2 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/59762
  • - Микони С. В. — Дискретная математика для бакалавра: множества, отношения, функции, графы - Издательство "Лань" - 2012 - ISBN: 978-5-8114-1386-7 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/4316

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

  • - Виленкин Н.Я. — Рассказы о множествах - Московский центр непрерывного математического образования - 2007 - ISBN: 978-5-94057-036-3 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/9309