• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
8
Кредиты

Преподаватели

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

Аннотация

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

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

  • овладение основами дискретной математики
  • приобретение навыков и их использования при дальнейшем изучении профильных дисциплин
  • приобретение навыков и их использования при проведении прикладных математических исследований
Результаты освоения дисциплины

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

  • формулировать основные понятия теории множеств
  • применять свойства множественных операций при преобразовании выражений алгебры множеств
  • доказывать тождества алгебры множеств
  • формулировать и определять основные свойства бинарных отношений
  • применять теорему о факторизации к решению задач
  • определять основные свойства упорядоченных множеств
  • определять основные свойства отображений
  • доказывать счётность множества
  • воспроизводить основные комбинаторные формулы
  • решать задачи подсчёта числа случаев, вариантов, элементов, функций и т.п.
  • решать линейные рекуррентные соотношения 1 и 2 порядка
  • формулировать основные понятия теории графов
  • проверять изоморфизм графов
  • определять метрические характеристики графов
  • описывать основные свойства деревьев
  • строить плоскую укладку планарного графа
  • применять теоремы Понтрягина-Куратовского и Вагнера для доказательства непланарности графа
  • выявлять двудольные графы
  • находить эйлеров цикл в графах или доказывать, что его не существует
  • формулировать основные понятия алгебры логики
  • решать задачи преобразования и упрощения логических формул
  • сравнивать логические функции
  • выявлять свойства логических функций
  • доказывать полноту системы логических функций
  • строить СДНФ, СКНФ, полиномы Жегалкина для логических функций
  • решать задачи минимизации логических формул
  • анализировать и строить схемы функциональных элементов.
  • формулировать основные понятия теории кодирования
  • определять однозначную декодируемость алфавитного кода
  • применять алгоритмы экономного алфавитного кодирования Хаффмана, Фано, Шеннона
  • оценивать эффективность алгоритмов экономного кодирования
  • определять расстояние Хэмминга
  • применять алгоритм кодирования Хэмминга
  • формулировать основные понятия теории формальных языков
  • строить и анализировать конечные автоматы
  • строить и анализировать регулярные выражения
  • строить и анализировать схемы функциональных элементов с задержкой
  • сравнивать конечные автоматы, регулярные выражения и схемы с задержкой
Содержание учебной дисциплины

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

  • Бинарные отношения.
    Основные понятия теории бинарных отношений, функциональные отношения.
  • Кодирование
    Основные понятия и алгоритмы экономного кодирования, кодирования с защитой от сбоев.
  • Комбинаторика
    Основные комбинаторные объекты и формулы.
  • Конечные автоматы и регулярные языки
    Основы теории конечных автоматов, регулярные выражения.
  • Множества
    Основы теории множеств
  • Теория графов
  • Алгебра логики. Схемы из функциональных элементов.
    Алгебра логики, основы теории логических схем.
Элементы контроля

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

  • неблокирующий Активность на семинарах
  • блокирует часть оценки/расчета Домашние контрольные работы
  • блокирующий Экзаменационный тест открытого типа
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.3 * Домашние контрольные работы + 0.7 * Экзаменационный тест открытого типа
  • Промежуточная аттестация (4 модуль)
    0.2 * Домашние контрольные работы + 0.3 * Промежуточная аттестация (2 модуль) + 0.5 * Экзаменационный тест открытого типа
Список литературы

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

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

  • - Верещагин Н.К., Щепин Е.В. — Информация, кодирование и предсказание - Московский центр непрерывного математического образования - 2012 - ISBN: 978-5-94057-920-5 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/71863
  • Введение в дискретную математику, [курс лекций], 264 с., Ландо, С. К., 2012
  • Хаггарти Р. - Дискретная математика для программистов - Издательство "Техносфера" - 2012 - ISBN: 978-5-94836-303-5 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/73011

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

  • - Верещагин Н.К., Шень А. — Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/9306
  • - Иорданский М.А. — Кодирование комбинаторных объектов - Издательство "Лань" - 2018 - ISBN: 978-5-8114-2787-1 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/102599
  • Лекции по дискретной математике : учеб. пособие / В.Б. Алексеев. — М. : ИНФРА-М, 2018. — 90 с. — (Высшее образование: Бакалавриат). - Режим доступа: http://znanium.com/catalog/product/952158
  • Лекции по дискретной математике: Учебное пособие / В.Б. Алексеев. - М.: НИЦ Инфра-М, 2012. - 90 с.: 60x88 1/16. - (Высшее образование: Бакалавриат). (обложка) ISBN 978-5-16-005559-6 - Режим доступа: http://znanium.com/catalog/product/278874