• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2023/2024

Дискретная математика

Статус: Курс обязательный (Экономика и анализ данных)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 1-й курс, 1-3 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 6
Контактные часы: 96

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

Аннотация

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

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

  • Знать основы теории множеств, владеть формулами алгебр множеств и логики.
  • Уметь различать счётные множества и множества мощности континуум. Овладеть диагональным методом на примере теоремы Кантора.
  • Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка.
  • Знать основы элементарной теории вероятностей: вероятностное пространство, условные вероятности, формула Байеса, математическое ожидание.
  • Знать основы теории чисел: арифметика остатков, НОД и НОК, алгоритм Евклида, основная теорема арифметики.
Планируемые результаты обучения

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

  • Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция.
  • Ознакомиться с базовыми математическими понятиями.
  • Выработать математическую культуру (культуру доказательств).
  • Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями.
  • Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений.
  • Знать основы теории графов.
Содержание учебной дисциплины

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

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

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

  • неблокирующий Домашнее задание 1
  • неблокирующий Домашнее задание 2
  • неблокирующий Коллоквиум 1
  • неблокирующий Коллоквиум 2
  • неблокирующий Промежуточный экзамен
    Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен (при условии согласования с учебным офисом) по правилам, которые дополнительно сообщаются студентам. Экзамен проводится в письменной форме после второго модуля. Письменный экзамен служит для проверки умения творчески использовать полученные знания при решении новых для студента задач. Задания в промежуточном письменном экзамене возможны по всем темам, которые изучались в первых двух модулях.
  • неблокирующий Итоговый экзамен
    Проводится после третьего модуля. Правила проведения полностью аналогичны правилам промежуточного экзамена, только задачи возможны по всем темам курса.
Промежуточная аттестация

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

  • 2023/2024 2nd module
    0.402 * Промежуточный экзамен + 0.299 * Домашнее задание 1 + 0.299 * Коллоквиум 1
  • 2023/2024 3rd module
    Оценка 3 модуля = 0.2*Оценка 2 модуля + 0.2*Домашнее задание 2 + 0.2*Коллоквиум 2 + 0.4*Итоговый экзамен
Список литературы

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

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

  • Алфутова, Н. Б. Алгебра и теория чисел. Сборник задач для математических школ : учебное пособие / Н. Б. Алфутова, А. В. Устинов. — 3-е изд. доп. и испр. — Москва : МЦНМО, 2009. — 336 с. — ISBN 978-5-94057-550-4. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9279 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
  • Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
  • Лекции по дискретной математике : учебник / М. Н. Вялый, В. В. Подольский, А. А. Рубцов [и др.]. — Москва : Высшая школа экономики, 2021. — 496 с. — ISBN 978-5-7598-2212-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/199883 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

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

  • Раскина, И. В. Логика для всех: от пиратов до мудрецов / И. В. Раскина. — Москва : МЦНМО, 2016. — 201 с. — ISBN 978-5-4439-3022-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/80155 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
  • Успенский, В. А. Простейшие примеры математических доказательств : учебное пособие / В. А. Успенский. — Москва : МЦНМО, 2009. — 56 с. — ISBN 978-5-94057-492-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9427 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.