Бакалавриат
2024/2025
Дискретная математика (углубленный курс)
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1-3 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
6
Программа дисциплины
Аннотация
Дискретная математика-1 — базовый вводный курс, прививающий студентам азы математической культуры, нужные для последующего изучения как математических дисциплин, так и компьютерных наук. Курс знакомит с такими фудндаментальными понятиями как множества, алгебра логики, функции и отображения, булевы функции, отношения и графы. Они являются фундаментом как для изучения математики и для структур данных в программировании. Разделы введение в теорию чисел и мощность множеств готовит студентов к изучению алгебры и последующему изучению вычислимых функций в рамках курса дискретная математика-2.
Цель освоения дисциплины
- Развитие математической культуры (культуры доказательств).
- Изучение фундаментальных разделов, относящихся к дискретной математике, необходимых для успешного прохождения последующих курсов.
Содержание учебной дисциплины
- Математическая индукция
- Множества и функции
- Комбинаторика
- Булевы функции и логика
- Полные системы связок, отношения
- Критерий Поста
- Счетные множества
- Мощности множеств, континуальные множества
- Частично упорядоченные множества
- Цепи и антицепи: теоремы Дилуорса и Шпернера
- Графы: основные понятия
- Ориентированные графы. Сильная связность, эйлеровы пути и циклы, топологическая сортировка
- Двудольные графы, паросочетания и вершинные покрытия, теорема Кёнига
- Теорема Холла, теорема Рамсея
- Раскраски графов, хроматическое число графа
- Вероятностное пространство, свойства вероятности
- Условная вероятность
- Математическое ожидание, вероятностный метод
- Оценки для биномиальных коэффициентов. Неравенство Чернова
- Производящие функции
- Линейные рекурентные соотношения с постоянными коэффициентами. Числа Каталана
- Комбинаторные игры с полной информацией. Теорема о цене игры
- Разрешающие деревья
- Булевы схемы
- Задачи выполнимости булевой схемы, КНФ и 3-КНФ
- Коды с исправлением ошибок
Элементы контроля
- Домашние заданияВыдается после каждого семинара (кроме двух-трех последних семинаров курса) и содержит 5-9 задач по теме семинара.
- Контрольная работаПроводится в начале 2-го модуля и содержит 5-6 задач по темам лекций и семинаров 1-го модуля. Пользоваться можно лишь ручкой и стандартным калькулятором
- Коллоквиум-1Проводится в конце 2-го модуля. Студент получает билет с теоретическими вопросами и задачами по всем темам 1-2 модулей и отвечает его устно. Пользоваться можно лишь ручкой и стандартным калькулятором.
- Лабораторная работа-1Проводится во 2-м модуле. Состоит из нескольких практических задач по темам курса, в которых нужно написать код. На выполнение задач дается около двух недель.
- Экзамен-1Экзамен проводится в сессию после 2 модуля письменной форме в аудитории. Во время подготовки можно использовать любые печатные материалы, но запрещается использовать электронные средства коммуникации.
- Коллоквиум-2Проводится в конце 3-го модуля. Студент получает билет с теоретическими вопросами и задачами по всем темам 1-3 модулей и отвечает его устно. Пользоваться можно лишь ручкой и стандартным калькулятором
- Лабораторная работа-2Проводится в 3-м модуле. Состоит из нескольких практических задач по темам курса, в которых нужно написать код. На выполнение задач дается около двух недель
- Экзамен-2
Промежуточная аттестация
- 2024/2025 2nd module0.25 * Домашние задания + 0.25 * Коллоквиум-1 + 0.15 * Контрольная работа + 0.05 * Лабораторная работа-1 + 0.3 * Экзамен-1
- 2024/2025 3rd module0.25*ДЗ+0.1*Колл1+0.15*Экз1+0.2*Колл2+0.05*Лр2+0.25*Э2, где ДЗ -Домашние задания, Колл1 - Коллоквиум-1, Экз1 - Экзамен-1, Колл2 - Коллоквиум-2, Лр2 - Лабораторная работа-2, Э2 - Экзамен-2
