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

2023/2024

Учебный год

RUS

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

4

Кредиты

Кто читает:

Кафедра компьютерной безопасности

Статус:

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

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

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

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

Герасимов Евгений Геннадьевич

Шейкин Всеволод Владимирович

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

Аннотация

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

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

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

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

• Знание основных понятий и методов комбинаторики, теории автоматов
• Умение исследовать комбинаторные свойства дискретных моделей
• Умение применять методы дискретной математики в различных приложениях математики и компьютерных наук

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

• Элементарные комбинаторные подсчеты
• Метод производящих функций в комбинаторике
• Графы
• Конечные автоматы
• Эффективная вычислимость, сложность, классы P и NP

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

• Контрольная работа №1
• Контрольная работа №2
• Экзамен
• Индивидуальная активность

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

• 2023/2024 учебный год 4 модуль
  0.2 * Индивидуальная активность + 0.15 * Контрольная работа №1 + 0.15 * Контрольная работа №2 + 0.5 * Экзамен

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

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

• 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
• Дискретная математика и комбинаторика, Андерсон, Дж. А., 2003
• Комбинаторика, Виленкин, Н. Я., 2006

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

• Лекции о производящих функциях, Ландо, С. К., 2007