Бакалавриат 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).

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

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

• Vereshchagin, N., & Shen, A. (2017). Lectures on mathematical logic an algorithms theory. Part 2. Languages and calculi. ; Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. HAL CCSD.
• Задачи и упражнения по дискретной математике : учеб. пособие, Гаврилов, Г. П., 2005
• Лекции о производящих функциях, Ландо, С. К., 2007
• Основы теории чисел : учебник для вузов, Виноградов, И. М., 1972
• Сборник задач по теории вероятностей : учеб. пособие для вузов, Зубков, А. М., 1989

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

• Математическая индукция, Шень, А., 2007