Дискретная математика на ПМИ 2024/25 (пилотный поток) — различия между версиями
Amaksaev (обсуждение | вклад) |
|||
| (не показано 10 промежуточных версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
==ОБЪЯВЛЕНИЯ== | ==ОБЪЯВЛЕНИЯ== | ||
| − | Канал, где дублируются важные объявления курса (рекомендуем подписаться): | + | Канал, где дублируются важные объявления курса (рекомендуем подписаться): [https://t.me/+AtkpgnSdUtVhOGQ6 LINK] |
== Контрольные мероприятия == | == Контрольные мероприятия == | ||
| Строка 10: | Строка 10: | ||
Лекции: [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев] | Лекции: [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев] | ||
| + | |||
| + | Ассистент лектора: [https://t.me/dunno_0 Артём Парфенов] | ||
'''Распределение по группам''' | '''Распределение по группам''' | ||
| Строка 17: | Строка 19: | ||
! Группа !! Преподаватель !! Консультационные часы преподавателя !! Учебный ассистент, отвечающий за группу | ! Группа !! Преподаватель !! Консультационные часы преподавателя !! Учебный ассистент, отвечающий за группу | ||
|- | |- | ||
| − | || 241 || [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев] || | + | || 241 || [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев] || пятница, 14:40 - 16:00 (предварительно предупредить) || [https://t.me/pururus Святослав Полонский] |
|- | |- | ||
| − | || 242 || [https://www.hse.ru/org/persons/225516943 Иван Сергеевич Бельдиев] || | + | || 242 || [https://www.hse.ru/org/persons/225516943 Иван Сергеевич Бельдиев] || среда, 13:00 - 14:20, 16:20 - 17:40 (предварительно предупредить) || [https://t.me/Serious_Meow Максим Малков] |
|- | |- | ||
| − | || 243 || [https://www.hse.ru/org/persons/856267465 Михаил Викторович Игнатьев] || | + | || 243 || [https://www.hse.ru/org/persons/856267465 Михаил Викторович Игнатьев] || вторник 18:00 - 19:20, среда 14:40 - 16:00 (предварительно предупредить) || [https://t.me/Ankh_Stas Анохин Станислав] |
|- | |- | ||
| − | || 244 || [https://www.hse.ru/org/persons/314157965 Валентин Валерьевич Промыслов] || | + | || 244 || [https://www.hse.ru/org/persons/314157965 Валентин Валерьевич Промыслов] || пятница, 14:40 - 16:00 (предварительно предупредить) || [https://t.me/mitseytlin Михаил Цейтлин] |
|- | |- | ||
| − | || 245 || [https://www.hse.ru/org/persons/859152259 Роман Олегович Стасенко ] || | + | || 245 || [https://www.hse.ru/org/persons/859152259 Роман Олегович Стасенко ] || вторник 15:00 - 16:20, четверг: 11:00 - 12:30 (предварительно предупредить) || [https://t.me/starRlCK Михаил Разуваев] |
|- | |- | ||
| − | || 246 || [https://www.hse.ru/org/persons/225516943 Иван Сергеевич Бельдиев] || | + | || 246 || [https://www.hse.ru/org/persons/225516943 Иван Сергеевич Бельдиев] || среда, 13:00 - 14:20, 16:20 - 17:40 (предварительно предупредить) || [https://t.me/i3cheese Даниил Сотников] |
|} | |} | ||
| Строка 77: | Строка 79: | ||
==Программа курса== | ==Программа курса== | ||
| − | ''Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.'' | + | ''Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.'' |
| + | '''Лекция 1'''. Метод математической индукции. Примеры задач: существование 2-раскраски областей на плоскости, неравенство Бернулли. Усиление утверждения. Ошибки в рассуждениях по индукции. Принцип полной индукции: задача о разбиении выпуклого многоугольника на треугольники непересекающимися диагоналями. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (начало). | ||
| + | |||
| + | ''Литература: [1, лекция 1]'' | ||
| + | |||
| + | '''Онлайн лекция 1'''. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений. | ||
| + | |||
| + | ''Литература: [1, лекция 2, §5.6]'' | ||
| + | |||
| + | '''Лекция 2'''. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (завершение). Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами. Доказательство теоретико-множественных тождеств: по определению и через таблицу истинности (разбор случаев). Упорядоченная пара, декартово произведение множеств. Определение функции. | ||
| + | |||
| + | ''Литература: [1, §5.1-5.2, §6.3]'' | ||
== Материалы курса == | == Материалы курса == | ||
| + | |||
| + | [https://disk.yandex.ru/i/qdBETGvq4dPh8A Листок 1. Математическая индукция] | ||
| + | |||
| + | [https://disk.yandex.ru/i/GWf5pGh3xvDoXA Листок 2. Перечислительная комбинаторика] | ||
== Записи лекций == | == Записи лекций == | ||
| Строка 90: | Строка 107: | ||
Две записанные онлайн-лекции расположены по ссылке: https://disk.yandex.ru/d/GqWnpqpGinYVSg | Две записанные онлайн-лекции расположены по ссылке: https://disk.yandex.ru/d/GqWnpqpGinYVSg | ||
| − | папка LEC 01 - лекция по базовой комбинаторике (прошу посмотреть до ''' | + | папка LEC 01 - лекция по базовой комбинаторике (прошу посмотреть до '''16.09'''); |
| − | папка LEC 02 - лекция по базовым понятиям и фактам теории неориентированных графов | + | папка LEC 02 - лекция по базовым понятиям и фактам теории неориентированных графов |
==Варианты зимних экзаменов прошлых лет== | ==Варианты зимних экзаменов прошлых лет== | ||
Текущая версия на 19:39, 18 сентября 2024
Содержание
ОБЪЯВЛЕНИЯ
Канал, где дублируются важные объявления курса (рекомендуем подписаться): LINK
Контрольные мероприятия
Общая информация о курсе Дискретная математика, пилотный поток, 1 курс
Преподаватели и ассистенты
Лекции: Артём Максимович Максаев
Ассистент лектора: Артём Парфенов
Распределение по группам
| Группа | Преподаватель | Консультационные часы преподавателя | Учебный ассистент, отвечающий за группу |
|---|---|---|---|
| 241 | Артём Максимович Максаев | пятница, 14:40 - 16:00 (предварительно предупредить) | Святослав Полонский |
| 242 | Иван Сергеевич Бельдиев | среда, 13:00 - 14:20, 16:20 - 17:40 (предварительно предупредить) | Максим Малков |
| 243 | Михаил Викторович Игнатьев | вторник 18:00 - 19:20, среда 14:40 - 16:00 (предварительно предупредить) | Анохин Станислав |
| 244 | Валентин Валерьевич Промыслов | пятница, 14:40 - 16:00 (предварительно предупредить) | Михаил Цейтлин |
| 245 | Роман Олегович Стасенко | вторник 15:00 - 16:20, четверг: 11:00 - 12:30 (предварительно предупредить) | Михаил Разуваев |
| 246 | Иван Сергеевич Бельдиев | среда, 13:00 - 14:20, 16:20 - 17:40 (предварительно предупредить) | Даниил Сотников |
Остальные ассистенты (проверяют домашние задания в разных группах):
Ассистент, ответственный за лабораторные работы:
Правила оценивания
Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Трижды за весь курс (1-3 модули) домашнее задание разрешается сдать на неделю позже срока без потери баллов.
Экзамен — это письменная работа. Пересдача проводится по правилам экзамена. Комиссия проводится в устном формате без учета накопленной оценки.
Оценка за курс в сессию после 2 модуля считается по формуле:
Промежуточная оценка = Округление(0.25 * ДЗ + 0.15 * КР + 0.25 * КОЛЛ-1 + 0.05 * ЛАБ-1 + 0.3 * ЭКЗ-1), где ДЗ – оценка за первые 12 домашних заданий, КР — оценка за контрольную работу, КОЛЛ-1 – оценка за коллоквиум-1, ЛАБ-1 – оценка за лабораторную работу-1, ЭКЗ-1 – оценка за экзамен-1.
Итоговая оценка за курс в сессию после 3 модуля считается по формуле:
Итоговая оценка = Округление(0.25 * ДЗ + 0.1 * КОЛЛ-1 + 0.2 * КОЛЛ-2 + 0.05 * ЛАБ-2 + 0.15 * ЭКЗ-1 + 0.25 * ЭКЗ-2), где ДЗ – оценка за все домашние задания за 1-3 модули, КОЛЛ-1 – оценка за коллоквиум-1, КОЛЛ-2 – оценка за коллоквиум-2, ЛАБ-2 – оценка за лабораторную работу-2, ЭКЗ-1 – оценка за экзамен-1, ЭКЗ-2 – оценка за экзамен-2.
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, между 6 и 8 округление вверх, а между 8 и 10 округление арифметическое. Т.е. 3,92 округляется до 3; 5,48 - до 5; 5,54 - до 6; 7,12 - до 8; 9,4 - до 9.
Результаты
| 241 группа ПМИ | 242 группа ПМИ | 243 группа ПМИ | 244 группа ПМИ | 245 группа ПМИ | 246 группа ПМИ |
|---|
Программа курса
Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.
Лекция 1. Метод математической индукции. Примеры задач: существование 2-раскраски областей на плоскости, неравенство Бернулли. Усиление утверждения. Ошибки в рассуждениях по индукции. Принцип полной индукции: задача о разбиении выпуклого многоугольника на треугольники непересекающимися диагоналями. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (начало).
Литература: [1, лекция 1]
Онлайн лекция 1. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений.
Литература: [1, лекция 2, §5.6]
Лекция 2. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (завершение). Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами. Доказательство теоретико-множественных тождеств: по определению и через таблицу истинности (разбор случаев). Упорядоченная пара, декартово произведение множеств. Определение функции.
Литература: [1, §5.1-5.2, §6.3]
Материалы курса
Листок 1. Математическая индукция
Листок 2. Перечислительная комбинаторика
Записи лекций
Видеозаписи регулярных лекций появляются здесь (файлы названы датой лекции): TBA
_________________________________
Две записанные онлайн-лекции расположены по ссылке: https://disk.yandex.ru/d/GqWnpqpGinYVSg
папка LEC 01 - лекция по базовой комбинаторике (прошу посмотреть до 16.09);
папка LEC 02 - лекция по базовым понятиям и фактам теории неориентированных графов
Варианты зимних экзаменов прошлых лет
Литература
- М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. Черновик этого учебника. В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ).
- Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
- Яблонский С. В. Введение в дискретную математику. 4-е издание, стереотипное - М.: Высшая школа, 2003. - 484 с.
- Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
- Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: https://znanium.com/catalog/document?id=343807
- Ландо С. К. Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144 с.
- А. Ромащенко, А. Румянцев, А. Шень. Заметки по теории кодирования. — 2-е изд., испр. и доп. — М.: МЦНМО, 2017. — 88 с. URL: https://users.mccme.ru/anromash/courses/coding-theory-2017.pdf
- Р. Дистель, "Теория графов", второе издание, 2002, Springer, Graduate Texts in Mathematics, 173 https://books.google.ru/books?id=pZm8AAAAQBAJ&hl=ru&source=gbs_navlinks_s
