Discrete Mathematics

2024/2025

Academic Year

RUS

Instruction in Russian

10

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-4 module

Instructor

Nozdrinova, Elena

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

Аннотация

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

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

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

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

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

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

• Множества, отношения и функции
• Системы чисел
• Дополнительные главы комбинаторики

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

• Контрольная работа
• Контрольная работа
• Экзамен
• Экзамен

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

• 2024/2025 2nd module
  0.4 * Контрольная работа + 0.6 * Экзамен
• 2024/2025 4th module
  0.4 * Контрольная работа + 0.6 * Экзамен

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

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

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

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

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

Авторы

• Ноздринова Елена Вячеславовна