• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Discrete Mathematics

2020/2021
Academic Year
RUS
Instruction in Russian
10
ECTS credits
Course type:
Compulsory course
When:
1 year, 1-4 module

Instructors

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

Аннотация

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

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

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

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

  • Понятия индукции и рекурсии (неформальное рассмотрение). Алфавиты и строки. Индуктивное определение строки. Принцип индукции. Рекурсивное определение строковых функций. Примеры доказательств.
  • Логика (неформальное рассмотрение). Высказывания, логические связки, предикаты и кванторы. Таблицы истинности, тавтологии. Корректные рассуждения. Выражение понятий на формально-логическом языке.
  • Индукция по \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