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

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

Статус: Курс обязательный (Компьютерные науки и анализ данных)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 1-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 4

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

Аннотация

Дискретная математика — курс, прививающий студентам азы математической культуры, нужные для последующего изучения как математических дисциплин, так и компьютерных наук. Курс знакомит с такими фундаментальными понятиями как множества, алгебра логики, функции и отображения, булевы функции, отношения и графы. Они являются фундаментом как для изучения математики и для структур данных в программировании. Разделы введение в теорию чисел и мощность множеств готовит студентов к изучению алгебры
Цель освоения дисциплины

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

  • Знакомство с базовыми математическими понятиями.
  • Развитие математической культуры (формулировки, изложение доказательств и т.п.).
  • Изучение фундаментальных разделов, относящихся к дискретной математике (основы алгебры логики, основы теории множеств, использование кванторов, графы, основы комбинаторики, основы теории чисел).
Планируемые результаты обучения

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

  • Владеть арифметикой остатков (вычетов). Уметь проверять элемент на обратимость, находить обратный элемент, решать линейные диофантовы уравнения от двух переменных с помощью алгоритма Евклида, знать базовые теоремы
  • Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция
  • Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями
  • Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка
  • Знать основы теории графов
  • Знать основы теории множеств, владеть формулами алгебр множеств и логики
  • Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений
  • Уметь строить разложениями в ДНФ и КНФ, проверять на полноту базис. Уметь строить булевы схемы, реализующие арифметические операции, уметь использовать их при решении задач. Уметь оценивать асимптотический размер булевых схем.
Содержание учебной дисциплины

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

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

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

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

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

  • 2024/2025 2nd module
    0.3 * Домашние задания + 0.175 * Коллоквиум 1 + 0.125 * Коллоквиум 2 + 0.125 * Контрольная работа + 0.125 * Проверочные работы на семинарах + 0.15 * Экзамен
Список литературы

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

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

  • Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
  • Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

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

  • Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., доп. — Москва : МЦНМО, [б. г.]. — Часть 2 : Языки и исчисления — 2008. — 288 с. — ISBN 978-5-94057-322-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9307 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Авторы

  • Мажуга Андрей Михайлович
  • Ахмедова Гюнай Интигам кызы
  • Соколов Евгений Андреевич