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

Course type:: Compulsory course

When:: 1 year, 1-4 module

Instructors

Nozdrinova, Elena

Tsaplina, Ekaterina

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

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

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

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

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

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

Системы чисел
Теория множеств
Отношения и функции
Дополнительные главы комбинаторики
Графы
Булевы функции
Конечные автоматы

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

Самостоятельная работа
Самостоятельная работа
Экзамен
Самостоятельная работа
Самостоятельная работа
Экзамен

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

2025/2026 2nd module
0.2 * Самостоятельная работа + 0.2 * Самостоятельная работа + 0.6 * Экзамен
2025/2026 4th module
0.2 * Самостоятельная работа + 0.2 * Самостоятельная работа + 0.6 * Экзамен

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

Авторы

Цаплина Екатерина Вадимовна
Ноздринова Елена Вячеславовна

Bachelor’s Programme 'Pure and Applied Mathematics'

Discrete Mathematics

Instructors

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