• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
2019/2020

Дискретная математика (адаптационный курс)

Статус: Дисциплина общефакультетского пула
Когда читается: 1, 2 модуль
Преподаватели: Сысоева Любовь Николаевна
Язык: русский
Кредиты: 2
Контактные часы: 28

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

Аннотация

Формально курс дискретной математики не требует "не школьных" знаний. Но нужно очень хорошее знание школьной программы. Также очень полезна (по крайней мере, на первых порах) олимпиадная подготовка. Для многих студентов изучать дискретную математику в предложенном темпе тяжело. Задача курса - пройти начало этого пути медленнее, попутно закрывая (или по крайней мере обозначая) пробелы школьного образования студентов. Побочная (но не менее важная) цель курса - создание у студентов привычки аккуратно и формально работать с определениями и доказательствами (в частности, отличать "доказательство" от "правдоподобного рассуждения"). Темы курса согласованы с "базовым" курсом ПМИ ФКН, но его изучение будет полезно и для направлений ПИ и ПАД. Примерный порядок тем - множества и логика, комбинаторика, функции и отношения, графы, начала теории чисел.
Цель освоения дисциплины

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

  • Дать возможность изучать дискретную математику студентам в комфортном для них темпе
  • Создание у студентов привычки аккуратно и формально работать с определениями и доказательствами
Планируемые результаты обучения

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

  • Освоение студентами основ дискретной математики
  • Создание у студентов привычки аккуратно и формально работать с определениями и доказательствами
Содержание учебной дисциплины

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

  • Множества и логика
    Множества и операции над ними. Связь алгебры логики и алгебры множеств: предикаты, юнивёрсум и дополнение, законы де Моргана, кванторы, эквивалентность тождеств алгебры множеств и алгебры логики, импликация и включение множеств. Алгоритм построения ДНФ (и КНФ) по таблице истинности Определение булевых схем, реализующих булевы функции, через последовательности присваиваний и графов (стандартный базис). Задание функции булевой схемой (последовательностью присваиваний) Формулы — схемы специального вида Общее определение схем (для произвольного базиса) Базис — полный базис.
  • Комбинаторика
    Правила суммы и произведения. Отображения и подсчёты. Правило суммы. Правило произведения — биекция с декартовым произведением множеств. Число двоичных слов длины n. Число подмножеств n-элементного множества. Размещения. Перестановки. Подсчёт количества слов длины k с разными буквами. Подсчёты с кратностью: сколько различных слов можно составить из слова «Математика»? Число сочетаний. Количество k-элементных подмножеств n-элементного множества. Дискретная вероятность. Биномиальные коэффициенты. Количество путей по узлам клеток (вправо и вверх) из (0,0) в (i,j). Треугольник Паскаля и его свойства: симметрия, возрастание биномиальных коэффициентов к середине. Бином Ньютона и биномиальные коэффициенты. Рекуррентное соотношение. Сумма биномиальных коэффициентов и её комбинаторный смысл. Знакопеременная сумма биномиальных коэффициентов. Комбинаторные доказательства. Рекуррентное соотношение на биномиальные коэффициенты в треугольнике Паскаля. Метод точек и перегородок. Формула Муавра. Число сочетаний с повторениями. Числа Фибоначчи. Числа Каталана (доказательство явной формулы). Характеристические функции. Доказательство формула включений-исключений. Подсчёт сюръекций. Подсчёт числа отображений (всюду определённых функций), функций, инъекций, биекций из n-элементного множества в m-элементное множество. Принцип Дирихле.
  • Функции и отношения
    Формальное определение отношений и их свойств: рефлексивность, транзитивность, симметричность, антисимметричность. Задание бинарного отношения таблицей, двудольным графом, перечислением пар. Примеры отношений эквивалентности: рациональные числа, равные и подобные треугольники, неопределённые интегралы. Формальное определение. Т.: Классы эквивалентности не пересекаются или совпадают. Теоретико-множественные операции с отношениями. Операция обращения. Описание с помощью булевых матриц. Композиция отношений (связь с базами данных).
  • Графы
    Неориентированные графы. Определение неориентированных графов Степень вершины. Сумма степеней вершин~"--- удвоенное количество рёбер. Число людей, сделавших нечётное число рукопожатий, чётно. Теоретико множественные операции с графами. Определение подграфа Определение путей и циклов (через подграфы). Связные графы и компоненты связности (через подграфы). Деревья. Связность. Двураскрашиваемый граф. Граф двураскрашиваемый тогда и только тогда, когда нет циклов нечётной длины. Эйлеровы маршруты.
  • Начала теории чисел
    Арифметика остатков, вычеты, обратимые элементы. Основная теорема арифметики. Алгоритм Евклида для решения линейных диофантовых уравнений с двумя неизвестными, поиск обратных элементов. Малая теорема Ферма. Китайская теорема об остатках. Функция Эйлера, теорема Эйлера.
Элементы контроля

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

  • неблокирующий Домашние задания
  • неблокирующий Экзамен (устный)
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.3 * Домашние задания + 0.7 * Экзамен (устный)
Список литературы

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

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

  • 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

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

  • Discrete mathematics, Biggs, N. L., 2004