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

2022/2023

Учебный год

RUS

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

4

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

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

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

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

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

Мажуга Андрей Михайлович

Промыслов Валентин Валерьевич

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

Аннотация

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

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

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

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

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

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

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

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

• Контрольная работа
• Коллоквиум 1
  Проводится устно
• Экзамен
• Домашние задания
  Среднее арифметическое всех оценок за ДЗ за два модуля
• Проверочные работы на семинарах
  Среднее арифметическое всех оценок за проверочные работы на семинарах за два модуля
• Коллоквиум 2
  Проводится устно

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

• 2022/2023 учебный год 2 модуль
  Итоговая Оценка за дисциплину вычисляется по следующей формуле: ИО = Округление(1/8*КЛ1+1/8*КЛ2+1/8*КР+7/40*ДЗ+3/20*СР+3/10*ЭК), где ЭК --- оценка за письменный экзамен; КР --- оценка за письменную контрольную работу; KЛ1, КЛ2 --- оценки за 1-й и 2-й коллоквиумы; СР --- среднее арифметическое всех самостоятельных работ, проведенных за семестр; ДЗ --- среднее арифметическое всех домашних заданий, сданных за семестр. Все оценки, а именно ЭК, KР, КЛ1, КЛ2, СР и ДЗ, являются вещественными числами, принадлежащими отрезку [0;10] и вычисляются без округления.

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

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

• 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). — Режим доступа: для авториз. пользователей.