Бакалавриат
2024/2025
Дискретная математика 2
Статус:
Курс по выбору (Экономика и анализ данных)
Когда читается:
1-й курс, 3 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Программа дисциплины
Аннотация
Дискретная математика 2 — курс, закрепляющий и углубляющий материал, пройденный на курсе “Дискретная математика 1”. В курсе будут изучены более сложные теоремы из теории графов и теории множеств. Также предполагается знакомство с элементарной теорией вероятностей и теорией чисел.
Цель освоения дисциплины
- Знать основы элементарной теории вероятностей: вероятностное пространство, условные вероятности, формула Байеса, математическое ожидание.
- Знать основы теории чисел: арифметика остатков, НОД и НОК, алгоритм Евклида, основная теорема арифметики.
Планируемые результаты обучения
- Уметь различать счётные множества и множества мощности континуум. Овладеть диагональным методом на примере теоремы Кантора.
- Расширить и углубить материал, пройденный на курсе “Дискретная математика 1”.
Содержание учебной дисциплины
- Теорема Дилуорса. Цепи и антицепи в бесконечных порядках. Фундированные множества, индукция по фундированному множеству.
- Сравнение бесконечных множеств. Обратная функция. Счетные множества.
- Мощность континуум. Примеры. Доказательство несчетности. Теорема Кантора--Бернштейна.
- Элементарная теория вероятностей.
- Условные вероятности. Формула полной вероятности, формула Байеса. Парадокс Симпсона.
- Случайная величина, математическое ожидание случайной величины. Лемма о среднем (математическое ожидание не больше максимума и не меньше минимума). Неравенство Маркова.
- Деление с остатком. Арифметика остатков, вычеты, свойства арифметики остатков. Признаки делимости.
- Наибольший общий делитель. Алгоритм Евклида. Линейные диофантовы уравнения. Основная теорема арифметики.
- Малая теорема Ферма. Функция Эйлера, теорема Эйлера. Китайская теорема об остатках. Оценки количества простых чисел.
- Разрешающие деревья. Основные определения и примеры. Мощностные нижние оценки.
Элементы контроля
- Домашнее задание
- КоллоквиумПроводится в конце третьего модуля в устной форме преимущественно по теоретическому материалу, изученному к моменту проведения коллоквиума. На коллоквиуме могут быть заданы вопросы по известным заранее определениям, формулировкам утверждений, доказательствам утверждений. Также на коллоквиуме могут быть заданы заранее известные задачи. Принимающий по ходу рассказа может задавать уточняющие вопросы.
- Итоговый экзамен
Промежуточная аттестация
- 2024/2025 3rd module0.299 * Домашнее задание + 0.402 * Итоговый экзамен + 0.299 * Коллоквиум
Список литературы
Рекомендуемая основная литература
- Vereshchagin, N., & Shen, A. (2017). Lectures on mathematical logic an algorithms theory. Part 2. Languages and calculi. ; Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. HAL CCSD.
- Алфутова, Н. Б. Алгебра и теория чисел. Сборник задач для математических школ : учебное пособие / Н. Б. Алфутова, А. В. Устинов. — 3-е изд. доп. и испр. — Москва : МЦНМО, 2009. — 336 с. — ISBN 978-5-94057-550-4. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9279 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Лекции по дискретной математике : учебник / М. Н. Вялый, В. В. Подольский, А. А. Рубцов [и др.]. — Москва : Высшая школа экономики, 2021. — 496 с. — ISBN 978-5-7598-2212-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/199883 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Шень, А. Вероятность: примеры и задачи : учебное пособие / А. Шень. — 2-е изд., стер. — Москва : МЦНМО, 2008. — 64 с. — ISBN 978-5-94057-284-8. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9442 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
Рекомендуемая дополнительная литература
- Зюзьков, В. М. Введение в математическую логику : учебное пособие / В. М. Зюзьков. — 2-е изд., испр. — Санкт-Петербург : Лань, 2022. — 268 с. — ISBN 978-5-8114-3053-6. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/213008 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Успенский, В. А. Простейшие примеры математических доказательств : учебное пособие / В. А. Успенский. — Москва : МЦНМО, 2009. — 56 с. — ISBN 978-5-94057-492-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9427 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Шень, А. Математическая индукция : учебное пособие / А. Шень. — 4-е изд., стер. — Москва : МЦНМО, 2011. — 32 с. — ISBN 978-5-94057-772-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9444 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.