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

Бакалавриат 2020/2021

Статус: Курс обязательный (Программная инженерия)

Направление: 09.03.04. Программная инженерия

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

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 1-4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Гнатенко Антон Романович, Дашков Евгений Владимирович, Лукьяненко Никита Сергеевич, Максаев Артем Максимович, Трофимова Анастасия Алексеевна, Хрыстик Михаил Андреевич, Шварц Дмитрий Александрович

Язык: русский

Кредиты: 10

Контактные часы: 140

Полная версия программы учебной дисциплины

Аннотация

Курс знакомит слушателя с основами разделов математики, необходимых для разработки и анализа алгоритмов, но остающихся за рамками традиционных вводных математических курсов. Среди рассматриваемых тем: арифметика остатков, формализм множеств и отношений, частичные порядки, графы, булевы функции и схемы, элементы комбинаторики, формальной логики, теории алгоритмов, функционального программирования. Поскольку курс адресован вчерашним школьникам, особое внимание уделяется знакомству с логико-математическим языком, простейшими приемами доказательств, понятиями индукции и рекурсии.

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

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

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

Понятия индукции и рекурсии (неформальное рассмотрение). Алфавиты и строки. Индуктивное определение строки. Принцип индукции. Рекурсивное определение строковых функций. Примеры доказательств.
Логика (неформальное рассмотрение). Высказывания, логические связки, предикаты и кванторы. Таблицы истинности, тавтологии. Корректные рассуждения. Выражение понятий на формально-логическом языке.
Индукция по \N: различные формы. Делимость. Деление с остатком. Арифметика по модулю. Фундаментальная теорема арифметики. Теорема Эйлера и малая теорема Ферма. (Расширенный) алгоритм Евклида. Цепные дроби. Линейные сравнения и уравнения в целых числах. Китайская теорема об остатках. Криптосистема RSA.
Основные теоретико-множественные конструкции и аксиомы. Алгебра множеств. Алгебра бинарных отношений.
(Частичные) функции, инъекции, биекции. Равномощность и вложимость. Характеристические функции. Наборы и функции с конечной областью определения. Теоремы Кантора и Кантора-Шрёдера-Бернштейна. Мощность множеств \N^2, \Z, \Q, \R^2, \N^\ N, \R^\N.
Принцип Дирихле и его следствия. Конечные и счетные множества. Правила суммы и произведения. Число функций, подмножеств, инъекций, биекций. Число подмножеств фиксированной мощности. Биномиальные коэффициенты и их свойства; биномиальная теорема. Задача Муавра. Принцип включений--исключений и его приложения.
Специальные бинарные отношения. Порядки; особые элементы в порядках. Изоморфизм порядков. Линейные порядки; цепи и антицепи. Отношения эквивалентности; фактормножества и разбиения. Число разбиений конечного множества. Теорема Дилуорса.
Графы. Степени вершин. Подграфы, дополнения. Изоморфизм графов. Пути и циклы. Связность. Дервья. Остовное дерево. Двудольные и k-дольные графы. Эйлеров и гамильтонов пути. Орграфы. Графы де Брёйна.
Классическая вероятностная модель. Условная вероятность, теорема Байеса. Формула полной вероятности. Случайные величины; функция распределения. Математическое ожидание и его свойства.
Булевы функции. Замкнутые классы. Полнота. Критерий Поста. Схемы функциональных элементов.
Формальные степенные ряды. Производящие функции. Комбинаторные приложения.
Линейные рекуррентные соотношения. Характеристические многочлены.
Логика первого порядка. Синтаксис и семантика. Эквивалентность и общезначимость. Система натурального вывода. Корректность и полнота. Теорема о компактности.
Машины Тьюринга. Вычислимость, разрешимость и перечислимость. Проблема остановки.
Бестиповое \lambda-исчисление. Основы функционального программирования.

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

Контрольные работы (КР)
Домашние задания (ДЗ)
Экзамен

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

Промежуточная аттестация (2 модуль)
Во 2-ом модуле производится промежуточная аттестация за осенний семестр. В осеннем семестре проводятся две контрольные работы (КР1 и КР2); выдается и проверяется домашнее задание (ДЗ2). Оценка за контрольную работу выставляется в долях единицы без округления (т.е. с максимальной доступной используемым вычислительным средствам точностью). Оценка ДЗ2 также выставляется в долях единицы без округления. Оценка ДЗ2 может быть больше единицы за счет "бонусных баллов". Накопленная оценка НК2 за осенний семестр вычисляется по формулам: НК2' = 10 * min (1, 0.35 * КР1 + 0.35 * КР2 + 0.3 * ДЗ2) НК2 = ОКРУГЛ (НК2'). Здесь и далее ОКРУГЛение производится к ближайшему целому числу, причем полуцелые числа округляются вверх. Если НК2 >= 4, то промежуточная оценка за осенний семестр Э2 = НК2. Если НК2 < 4, студенту предлагается выполнить итоговое контрольное задание ИК2, оцениваемое по десятибалльной системе. В этом случае промежуточная оценка за осенний семестр Э2 = ОКРУГЛ (0.7 * ИК2 + 0.3 * НК2').
Промежуточная аттестация (4 модуль)
В весеннем семестре проводятся две контрольные работы (КР3 и КР4); выдается и проверяется домашнее задание (ДЗ4). Оценки выставляются так же, как и в осеннем семестре. Накопленная оценка НК4 за весенний семестр вычисляется по формулам: НК4' = 10 * min (1, 0.35 * КР3 + 0.35 * КР4 + 0.3 * ДЗ4) НК4 = ОКРУГЛ (НК4'). Если НК4 >= 4, то итоговая оценка за весенний семестр Э4 = НК4. Если НК4 < 4, студенту предлагается выполнить итоговое контрольное задание ИК4, оцениваемое по десятибалльной системе. В этом случае итоговая оценка за весенний семестр Э4 = ОКРУГЛ (0.7 * ИК4 + 0.3 * НК4'). Результирующая оценка Р по дисциплине выставляется по десятибалльной шкале согласно формуле Р = ОКРУГЛ (0.5 * Э2 + 0.5 * Э4).

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

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

Аннотация

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

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

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

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

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

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

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