Introduction to Discrete Mathematics

2020/2021

Academic Year

RUS

Instruction in Russian

8

ECTS credits

Delivered at:

Department of Fundamental Mathematics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

1 year, 1-3 module

Instructors

Nozdrinova, Elena

Polotovskiy, Grigory

Samylina, Evgeniya

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

Аннотация

Настоящая дисциплина относится к профессиональному циклу дисциплин и блоку дисциплин, обеспечивающих подготовку бакалавра по направлению 01.03.01 «Математика». Настоящая дисциплина является базовой. Изучение данной дисциплины базируется на хорошем владении математическим аппаратом выпускника средней общеобразовательной школы. Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями: знать основы математического анализа, алгебры и геометрии в рамках средней общеобразовательной школы, уметь решать типовые школьные задачи по математике, помнить основные математические теоремы школьного курса математики. Курс опирается на знания студентов, приобретенные при изучении основ элементарной математики, и обеспечивает теоретическую подготовку и практические навыки в области современных методов дискретной математики.

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

• Целями освоения дисциплины «Дискретная математика» являются, с одной стороны, освоение теоретико-множественных конструкций, возникающих во многих областях высшей математики, а с другой стороны – знакомство с некоторыми темами, классическими для дискретной математики.

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

• Знает определение множества, основные операции над ними. Знает определение и свойства функции. Умеет строить биективное отображение. Знает понятие равномощных множеств.
• Знает аксиоматическую теорию натуральных чисел, аксиомы Пеано, определение и свойства сложения. Умеет оперировать дробями, рациональными числами, их свойствами. Знает вещественные числа и основные теоремы, связанные с ними. Знает обычную топологию на вещественной прямой.
• Знает некоторые комбинаторные числа и тождества, бином Ньютона для целого (в том числе отрицательного) показателя степени. Знает факториальные степени, формула включений и исключений в общем случае. Владеет понятием производящая функция последовательности. Знает линейные рекуррентные последовательности, число неприводимых многочленов над полем вычетов по простому модулю.
• Знает аксиомы Пеано натуральных чисел, знает определения сложения и умножения натуральных чисел, умеет доказывать основные свойства (дистрибутивность, коммутативность, ассоциативность)
• Знает определение дроби, знает определение рационального числа, знает определение основных операций на множестве рациональных чисел, умеет доказывать их свойства
• Знает определение действительных чисел через дедекиндовы сечения множества рациональных, знает определение действительных чисел через десятичные дроби, знает определение действительных чисел как точек прямой. Знает определение операций на множестве действительных чисел, умеет доказывать их свойства (в том числе, что множество действительных чисел с введёнными на нём сложением и умножением является полум)
• Знает формулировку теоремы Островского для простого числа р. Знает определение нормы, знает определение р-адической нормы числа, знает определение р-адического числа
• Знает определение основных комбинаторных функций (число сочетаний, число перестановок, число размещений). Умеет доказывать основные комбинаторные множества
• Знает и умеет доказывать формулу Бинома Ньютона, знает и может доказать основные свойства биноминальных коэффициентов
• Знает и умеет доказывать формулу включения-исключения
• Умеет решать задачи с помощью метода траекторий. Знает определения чисел Каталана. Знает и умеет доказывать формулу n-ого числа Каталана
• Знает определение чисел Стирлинга и Белла. Умеет выводить общую формулу для n-ого числа Стирлинга и для n-ого числа Белла
• Владеет понятием оценки комбинаторной функции. Может привести примеры оценки комбинаторных функций и доказать её корректность. Знает формулу Стирлинга.
• Умеет оценивать биноминальные коэффициенты и их суммы.
• Владеет понятием производящей функции последовательности. Умеет использовать метод производящих функций для доказательства комбинаторных тождеств.
• Владеет понятием линейной рекуррентной последовательности. Умеет находить в явном виде формулу n-ого члена последовательности, заданной линейно-рекуррентно.

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

• Множества, отношения и функции
  Множества, операции с ними: объединение, пересечение, разность, симметрическая разность, дополнение. Выражение этих операций в терминах характеристических функций. Круги Эйлера, диаграммы Венна. Множество всех подмножеств, количество элементов в нём для случая конечных множеств. Формула включений-исключений для двух, трёх и четырёх множеств. Элементарная комбинаторика. Сочетания, перестановки, размещения. Декартово произведение множеств. Бинарные отношения, их графики и простейшие типы. Обратные и противоположные отношения. Отношения эквивалентности и порождаемые ими разбиения. Функции: однозначные и многозначные, определённые всюду и частичные. Классы однозначных функций: инъективные, сюръективные, биективные. Обратная функция как обратное отношение, обратимость. Отношения порядка линейные и частичные. Монотонные функции. Направленные множества. Последовательности и направленности. Отношения предпочтения. Вполне упорядоченные множества, математическая и трансфинитная индукция. Цепи в упорядоченном множестве. Теорема Цермело, теорема Хаусдорфа, лемма Цорна, аксиома выбора, непустота декартова произведения, теорема об эквивалентности всех этих утверждений. Сумма и произведение упорядоченных множеств. Арифметика ординалов. Равномощные множества. Конечные и бесконечные множества, счётные и несчётные. Теоремы о равномощных множествах: Кантора-Шредера-Бернштейна, Кантора, другие. Иерархия мощностей. Континуум-гипотеза. Парадоксы кажущиеся и настоящие: разбиение Банаха-Тарского, парадокс Рассела. Проблема с «множеством всех множеств», классы. Мощность и порядковый тип как классы. Наивный и аксиоматический подходы к теории множеств. Аксиоматика ZFC.
• Системы чисел
  Аксиоматическая теория натуральных чисел. Аксиомы Пеано, определение и свойства сложения. Порядок. Умножение. Целые числа, их свойства. Теорема Гудстейна, её равносильность непротиворечивости аксиоматики Пеано. Дроби, рациональные числа. Их свойства. Вещественные числа как дедекиндовы сечения. Теорема Дедекинда. Вещественные числа как бесконечные вправо m-ичные дроби. Теорема о существовании супремума у ограниченного сверху множества вещественных чисел. Обычная топология на вещественной прямой. Каждое из трёх множеств: рациональных, иррациональных и вещественных чисел плотно в каждом из них как упорядоченные множества и как подмножества топологического пространства. Теорема Островского. Для простого числа р: р-адическая норма на множестве рациональных чисел, р-адические числа.
• Дополнительные главы комбинаторики
  Некоторые комбинаторные числа и тождества. Бином Ньютона для целого (в том числе отрицательного) показателя степени. Биномиальные коэффициенты, их свойства. Факториальные степени. Формула включений и исключений в общем случае. Числа Стирлинга и Белла. Метод траекторий, числа Каталана. Подсчёт сумм. Оценки комбинаторных функций. Оценки для n!, формула Стирлинга. Оценки биномиальных коэффициентов и их сумм. Производящая функция последовательности. Линейные рекуррентные последовательности.

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

• Контрольная работа
• Контрольная работа
• Контрольная работа

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

• Промежуточная аттестация (3 модуль)
  0.3 * Контрольная работа + 0.3 * Контрольная работа + 0.4 * Контрольная работа

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

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

• Комбинаторика и теория вероятностей, учебное пособие, 99 с., Райгородский, А. М., 2013
• Основы анализа. Действия над целыми, рациональными, иррациональными, комплексными числами, дополнения к учебникам по дифференциальному и интегральному исчислению, пер. с нем. Д. А. Райкова, 2-е изд., 182 с., Ландау, Э., 2010
• Теория множеств, пер. с нем. Н. Б. Веденисова ; под ред., с предисл. и доп. акад. П. С. Александрова, акад. А. Н. Колмогорова, стер., 303 с., Хаусдорф, Ф., 2017
• Элементы дискретной математики, учебник, 280 с., Судоплатов, С. В., Овчинникова, Е. В., 2002

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

• Дискретная математика : математика для менеджера в примерах и упражнениях, учебное пособие, 240 с., Москинова, Г. И., 2003
• Дискретная математика для программистов, учебное пособие, 2-е изд., 364 с., Новиков, Ф. А., 2006