Discrete Mathematics

2019/2020

Academic Year

RUS

Instruction in Russian

8

ECTS credits

Delivered by:

Department of Mathematics

Type:

Compulsory course

When:

1 year, 2-4 module

Instructor Instructors

Bronevich, Andrey

Veselova, Yuliya A.

Гладышев Андрей Владимирович

Goryainov, Victor

Kodaneva, Nadezhda

Levin, Ilya

Mikhaylets, Ekaterina

Петрова Вера Тимофеевна

Правдивец Николай Александрович

Sokolova, Ekaterina

Shvarts, Dmitry

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

Аннотация

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

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

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

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

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

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

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

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

• Контрольная работа (4 шт)
• Домашнее задание
• Экзаменационная контрольная.
  Форма экзамена: Экзамен проводится в письменной форме с использованием асинхронного прокторинга. Асинхронный прокторинг означает, что за всеми действиями студента во время проведения экзамена будет “наблюдать” компьютер. Процесс проведения экзамена записывается, анализируется искусственным интеллектом и человеком (проктором). Пожалуйста, будьте внимательны и чётко следуйте инструкциям! Платформа проведения: Экзамен проводится на платформе Moodle, онлайн платформе для проведения тестовых заданий различного уровня сложности. Прокторинг осуществляется с помощью системы Экзамус. Ссылка на прохождение экзаменационного задания будет размещена в ЛМС. К экзамену необходимо подключиться за 15 минут до начала. Технические требования и правила проведения экзамена: https://elearning.hse.ru/student_steps Для участия в экзамене студент обязан: Подготовить документ, удостоверяющий личность (паспорт, разворот с именем и фотографией) для идентификации перед началом выполнения экзаменационного задания; Проверить работу видеокамеры и микрофона, скорость работы сети Интернет (для наилучшего результата рекомендуется подключение компьютера к сети через кабель); Подготовить необходимые для выполнения экзаменационных заданий инструментов. Отключить в диспетчере задач компьютера иные приложения, кроме браузера, в котором будет выполняться вход на платформу StartExam. В случае, если одно из необходимых условий участия в экзамене невозможно выполнить, необходимо за 7 дней до даты проведения экзамена проинформировать об этом преподавателя или сотрудника учебного офиса для принятия решения об участии студента в экзаменах. Во время экзамена студентам запрещено: Выключать видеокамеру, микрофон; Покидать место выполнения экзаменационного задания (выходить за угол обзора камеры); Отводить взгляд от экрана компьютера, рабочего стола; Пользоваться умными гаджетами (смартфон, планшет и др.); Привлекать посторонних лиц для помощи в проведении экзамена, разговаривать с посторонними во время выполнения заданий; Вслух громко зачитывать задания. Нарушения связи: Кратковременным нарушением связи во время экзамена считается потеря сетевой связи студента с платформой Экзамус не более 1 минуты. Долговременным нарушением связи во время экзамена считается потеря сетевой связи студента с платформой Экзамус более 1 минуты. Долговременное нарушение связи во время экзамена является основанием для принятия решения о прекращении экзамена и выставление оценки “неудовлетворительно” (0 по десятибалльной шкале. В случае долговременного нарушения связи с платформой Экзамус во время выполнения экзаменационного задания, студент должен уведомить об этом преподавателя, зафиксировать факт потери связи с платформой (скриншот, ответ от провайдера сети Интернет) и обратиться в учебный офис с объяснительной запиской о случившемся для принятия решения о пересдаче экзамена.

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

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

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

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

• Дискретная математика для инженера, Кузнецов, О. П., 2004
• Микони С. В. - Дискретная математика для бакалавра: множества, отношения, функции, графы - Издательство "Лань" - 2012 - 192с. - ISBN: 978-5-8114-1386-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/4316

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

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