Дискретная математика на ПМИ 2024/25 (пилотный поток)

2024-10-22T20:56:19Z

Avparfenov:

==ОБЪЯВЛЕНИЯ==

Канал, где дублируются важные объявления курса (рекомендуем подписаться): [https://t.me/+AtkpgnSdUtVhOGQ6 LINK]

== Контрольные мероприятия ==

'''9 ноября''', 11:00-13:00, состоится контрольная работа по материалам лекций и семинаров 1 модуля. В контрольной будет 5 задач на следующие темы:

- Индукция

- Перечислительная комбинаторика

- Множества и функции

- Булевы функции: ДНФ, многочлены Жегалкина

- Замкнутые классы булевых функций, критерий Поста

- Мощности множеств, счетные и континуальные множества, сравнение мощностей

Пользоваться материалами (ни бумажными, ни электронными) нельзя. Допускается использование лишь стандартного калькулятора (хотя едва ли он пригодится).

Длительность работы: 90 минут

Вариант контольной прошлого года [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2FZxhzEUOy5Bsy9AQQVUxapc0tLoQ7ex2%2F14V%2BwXlF3NINU%2BFVow7%2Fa%2FqPNzGnEpZ7q%2FJ6bpmRyOJonT3VoXnDag%3D%3D&name=Контрольная%20работа.pdf&nosw=1 LINK]

== Общая информация о курсе Дискретная математика, пилотный поток, 1 курс==

=== Преподаватели и ассистенты===

Лекции: [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев]

Ассистент лектора: [https://t.me/dunno_0 Артём Парфенов]

'''Распределение по группам'''

{| class="wikitable" style="text-align:center"
|-
! Группа !! Преподаватель !! Консультационные часы преподавателя !! Учебный ассистент, отвечающий за группу
|-
|| 241 || [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев] || пятница, 14:40 - 16:00 (предварительно предупредить) || [https://t.me/pururus Святослав Полонский]
|-
|| 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 Михаил Викторович Игнатьев] || вторник 18:00 - 19:20, среда 14:40 - 16:00 (предварительно предупредить) || [https://t.me/Ankh_Stas Анохин Станислав]
|-
|| 244 || [https://www.hse.ru/org/persons/314157965 Валентин Валерьевич Промыслов] || пятница, 14:40 - 16:00 (предварительно предупредить) || [https://t.me/mitseytlin Михаил Цейтлин]
|-
|| 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 Иван Сергеевич Бельдиев] || среда, 13:00 - 14:20, 16:20 - 17:40 (предварительно предупредить) || [https://t.me/i3cheese Даниил Сотников]
|}

'''Остальные ассистенты (проверяют домашние задания в разных группах):'''

[https://t.me/alfoos239 Арсений Лазо]

[https://t.me/Nikita_Solodrive Никита Солоницын]

[https://t.me/ShestakovSlava Вячеслав Шестаков]

[https://t.me/dsolunov Данила Солунов]

'''Ассистент, ответственный за лабораторные работы:'''

[https://t.me/existingone Роман Гундарин]

===Правила оценивания===

Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Трижды за весь курс (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.

== Результаты ==

{| class="wikitable" style="text-align:center"
|-
! '''[https://docs.google.com/spreadsheets/d/1ZXjCzGMFd1EyQe-C4iJVe_JmGk5TpOVP/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 241 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/12U5sr_YclnTmJ_qpfJz2A-QBNlGcH6vr/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 242 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1N0rzebvWwiOZ5i9rV8dnbZBDWRqzMxdf/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 243 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1vGlBYUQoE6QDGxN4cq0w2APermc8XHmQ/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 244 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1AfkKX5sGpi12XYMxggpZj52JfDXNM8xS/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 245 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1TYdv4R2HJ7FYDUpdeVq-5gY2seKP8l_3/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 246 группа ПМИ]'''

|}

==Программа курса==

''Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.''

'''Лекция 1'''. Метод математической индукции. Примеры задач: существование 2-раскраски областей на плоскости, неравенство Бернулли. Усиление утверждения. Ошибки в рассуждениях по индукции. Принцип полной индукции: задача о разбиении выпуклого многоугольника на треугольники непересекающимися диагоналями. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (начало).

''Литература: [1, лекция 1]''

'''Онлайн лекция 1'''. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений.

''Литература: [1, лекция 2, §5.6]''

'''Лекция 2'''. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (завершение). Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами. Доказательство теоретико-множественных тождеств: по определению и через таблицу истинности (разбор случаев). Упорядоченная пара, декартово произведение множеств. Определение функции.

''Литература: [1, §5.1-5.2, §6.3]''

'''Лекция 3.''' Определение функции, ее области определения и области значений, образа и полного прообраза множества. Композиция функций. Теорема об ассоциативности композиции всюду определенных функций. Инъекции, сюръекции, биекции. Обратная функция, критерий биективности функции. Утверждение о композиции биекций. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности, количество булевых функций от n переменных. Простейшие тождества алгебры логики.

''Литература: [1, §6.4-6.5, §5.3-5.4]''

'''Лекция 4'''. Доказательство теоретико-множественных тождеств с помощью алгебры логики. Дизъюнктивная нормальная форма, теорема о существовании ДНФ для любой булевой функции. Совершенная дизъюнктивная нормальная форма (СДНФ). Конъюнктивная нормальная форма (КНФ). Полиномы Жегалкина. Теорема о представлении булевой функции полиномом Жегалкина (существование и единственность). Суперпозиция булевых функций, замыкание класса булевых функций, свойства замыкания. Полные системы связок. Полнота системы связок «конъюнкция, дизъюнкция, отрицание» и «конъюнкция, отрицание». Полнота системы связок «XOR, конъюнкция, 1».

''Литература: [1, §6.5, §5.3-5.5]''

'''Лекция 5'''. Замкнутые классы булевых функций. Класс линейных функций, его замкнутость, лемма о нелинейной функции. Двойственная функция, принцип двойственности. Класс самодвойственных функций, его замкнутость, лемма о несамодвойственной функции. Классы функций, сохраняющих константу, их замкнутость. Класс монотонных функций, его замкнутость, лемма о немонотонной функции. Критерий Поста полноты системы булевых функций.

''Литература: [3, глава 1, §5-6]''

'''Лекция 6'''. Описание предполных классов булевых функций. Формула включений-исключений. Счетные множества, счётность целых и рациональных чисел. Подмножества счетного множества. Объединение и декартово произведение счетных множеств. Существование бесконечного подмножества у любого счетного множества. Лемма о том, что добавление счетного множества не меняет мощности. Несчетность множества бесконечных последовательностей из нулей и единиц.

''Литература: [3, глава 1, §6], [1, §5.6, §8.1-8.2], [2, §1.2-1.4]''

'''Лекция 7'''. Равномощность множеств: бесконечных последовательностей из 0 и 1; вещественных чисел; [0, 1]; [0, 1); (0, 1); множества всех подмножеств натуральных чисел. Мощность континуум. Равномощность отрезка и квадрата. Сравнение мощностей, его свойства. Утверждение о том, что счетная мощность меньше континуальной. Теорема Кантора о сравнении мощности множества и мощности множества всех его подмножеств. Теорема Кантора-Бернштейна.

''Литература: [1, §8.3-8.5], [2, §1.5-1.6]''

== Материалы курса ==

[https://disk.yandex.ru/i/qdBETGvq4dPh8A Листок 1. Математическая индукция]

[https://disk.yandex.ru/i/GWf5pGh3xvDoXA Листок 2. Перечислительная комбинаторика]

[https://disk.yandex.ru/i/2hnUJxxkWmRt1w Листок 3. Множества и функции]

[https://disk.yandex.ru/i/AWRe1MZ55QIsJA Листок 4. Булевы функции]

[https://disk.yandex.ru/i/OgWcI8AoNwAJ6Q Листок 5. Замкнутые классы булевых функций. Критерий Поста]

[https://disk.yandex.ru/i/pn8uT4aEgeiqcw Листок 6. Мощность множеств-1]

[https://disk.yandex.ru/i/KVR-kIPX-4iGfQ Листок 7. Мощность множеств-2]

== Записи лекций ==

Видеозаписи регулярных лекций появляются здесь (файлы названы датой лекции): [https://disk.yandex.ru/d/e3j_hRnQOsdtqA https://disk.yandex.ru/d/e3j_hRnQOsdtqA]

_________________________________

Две записанные онлайн-лекции расположены по ссылке: https://disk.yandex.ru/d/GqWnpqpGinYVSg

папка LEC 01 - лекция по базовой комбинаторике (прошу посмотреть до '''16.09''');

папка LEC 02 - лекция по базовым понятиям и фактам теории неориентированных графов

==Варианты зимних экзаменов прошлых лет==

[https://disk.yandex.ru/i/wHRAlvl6g9rX0g Экзамен зима 2022]

[https://disk.yandex.ru/i/E8yhFaoGLXWTiQ Экзамен зима 2021]

[https://www.dropbox.com/s/365ozmkzw46bsml/exam201221_pilot.pdf?dl=0 Экзамен зима 2020]

== Литература ==

# М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Черновик этого учебника.] В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ).
# Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 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

Дискретная математика на ПМИ 2024/25 (пилотный поток)

2024-10-02T15:24:50Z

Avparfenov:

==ОБЪЯВЛЕНИЯ==

Канал, где дублируются важные объявления курса (рекомендуем подписаться): [https://t.me/+AtkpgnSdUtVhOGQ6 LINK]

== Контрольные мероприятия ==

== Общая информация о курсе Дискретная математика, пилотный поток, 1 курс==

=== Преподаватели и ассистенты===

Лекции: [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев]

Ассистент лектора: [https://t.me/dunno_0 Артём Парфенов]

'''Распределение по группам'''

{| class="wikitable" style="text-align:center"
|-
! Группа !! Преподаватель !! Консультационные часы преподавателя !! Учебный ассистент, отвечающий за группу
|-
|| 241 || [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев] || пятница, 14:40 - 16:00 (предварительно предупредить) || [https://t.me/pururus Святослав Полонский]
|-
|| 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 Михаил Викторович Игнатьев] || вторник 18:00 - 19:20, среда 14:40 - 16:00 (предварительно предупредить) || [https://t.me/Ankh_Stas Анохин Станислав]
|-
|| 244 || [https://www.hse.ru/org/persons/314157965 Валентин Валерьевич Промыслов] || пятница, 14:40 - 16:00 (предварительно предупредить) || [https://t.me/mitseytlin Михаил Цейтлин]
|-
|| 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 Иван Сергеевич Бельдиев] || среда, 13:00 - 14:20, 16:20 - 17:40 (предварительно предупредить) || [https://t.me/i3cheese Даниил Сотников]
|}

'''Остальные ассистенты (проверяют домашние задания в разных группах):'''

[https://t.me/alfoos239 Арсений Лазо]

[https://t.me/Nikita_Solodrive Никита Солоницын]

[https://t.me/ShestakovSlava Вячеслав Шестаков]

[https://t.me/dsolunov Данила Солунов]

'''Ассистент, ответственный за лабораторные работы:'''

[https://t.me/existingone Роман Гундарин]

===Правила оценивания===

Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Трижды за весь курс (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.

== Результаты ==

{| class="wikitable" style="text-align:center"
|-
! '''[https://docs.google.com/spreadsheets/d/1ZXjCzGMFd1EyQe-C4iJVe_JmGk5TpOVP/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 241 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/12U5sr_YclnTmJ_qpfJz2A-QBNlGcH6vr/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 242 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1N0rzebvWwiOZ5i9rV8dnbZBDWRqzMxdf/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 243 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1vGlBYUQoE6QDGxN4cq0w2APermc8XHmQ/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 244 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1AfkKX5sGpi12XYMxggpZj52JfDXNM8xS/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 245 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1TYdv4R2HJ7FYDUpdeVq-5gY2seKP8l_3/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 246 группа ПМИ]'''

|}

==Программа курса==

''Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.''

'''Лекция 1'''. Метод математической индукции. Примеры задач: существование 2-раскраски областей на плоскости, неравенство Бернулли. Усиление утверждения. Ошибки в рассуждениях по индукции. Принцип полной индукции: задача о разбиении выпуклого многоугольника на треугольники непересекающимися диагоналями. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (начало).

''Литература: [1, лекция 1]''

'''Онлайн лекция 1'''. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений.

''Литература: [1, лекция 2, §5.6]''

'''Лекция 2'''. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (завершение). Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами. Доказательство теоретико-множественных тождеств: по определению и через таблицу истинности (разбор случаев). Упорядоченная пара, декартово произведение множеств. Определение функции.

''Литература: [1, §5.1-5.2, §6.3]''

'''Лекция 3.''' Определение функции, ее области определения и области значений, образа и полного прообраза множества. Композиция функций. Теорема об ассоциативности композиции всюду определенных функций. Инъекции, сюръекции, биекции. Обратная функция, критерий биективности функции. Утверждение о композиции биекций. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности, количество булевых функций от n переменных. Простейшие тождества алгебры логики.

''Литература: [1, §6.4-6.5, §5.3-5.4]''

'''Лекция 4'''. Доказательство теоретико-множественных тождеств с помощью алгебры логики. Дизъюнктивная нормальная форма, теорема о существовании ДНФ для любой булевой функции. Совершенная дизъюнктивная нормальная форма (СДНФ). Конъюнктивная нормальная форма (КНФ). Полиномы Жегалкина. Теорема о представлении булевой функции полиномом Жегалкина (существование и единственность). Суперпозиция булевых функций, замыкание класса булевых функций, свойства замыкания. Полные системы связок. Полнота системы связок «конъюнкция, дизъюнкция, отрицание» и «конъюнкция, отрицание». Полнота системы связок «XOR, конъюнкция, 1».

''Литература: [1, §6.5, §5.3-5.5]''

== Материалы курса ==

[https://disk.yandex.ru/i/qdBETGvq4dPh8A Листок 1. Математическая индукция]

[https://disk.yandex.ru/i/GWf5pGh3xvDoXA Листок 2. Перечислительная комбинаторика]

[https://disk.yandex.ru/i/2hnUJxxkWmRt1w Листок 3. Множества и функции]

[https://disk.yandex.ru/i/AWRe1MZ55QIsJA Листок 4. Булевы функции]

== Записи лекций ==

Видеозаписи регулярных лекций появляются здесь (файлы названы датой лекции): [https://disk.yandex.ru/d/e3j_hRnQOsdtqA https://disk.yandex.ru/d/e3j_hRnQOsdtqA]

_________________________________

Две записанные онлайн-лекции расположены по ссылке: https://disk.yandex.ru/d/GqWnpqpGinYVSg

папка LEC 01 - лекция по базовой комбинаторике (прошу посмотреть до '''16.09''');

папка LEC 02 - лекция по базовым понятиям и фактам теории неориентированных графов

==Варианты зимних экзаменов прошлых лет==

[https://disk.yandex.ru/i/wHRAlvl6g9rX0g Экзамен зима 2022]

[https://disk.yandex.ru/i/E8yhFaoGLXWTiQ Экзамен зима 2021]

[https://www.dropbox.com/s/365ozmkzw46bsml/exam201221_pilot.pdf?dl=0 Экзамен зима 2020]

== Литература ==

# М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Черновик этого учебника.] В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ).
# Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 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

DM1PMIbase-2024-25

2024-09-20T12:29:41Z

Avparfenov:

==ОБЪЯВЛЕНИЯ==

'''19.09.2024''' Условие задачи Д3.4 изменено! Функции f,g нужно считать всюду определенными.



== Преподаватели и ассистенты==

Лекции: Михаил Николаевич Вялый. Ассистент лектора: [https://t.me/dunno_0 Артём Вячеславович Парфенов]

Семинары:

{| class="wikitable" style="text-align:right"
|-
! Группа !! Преподаватель !! Учебный(-е) ассистент(-ы)
|-
|| 247 || Михаил Николаевич Вялый || [https://t.me/katya_klika Екатерина Михайлова]
|-
|| 248 || [https://t.me/chistopolskaia Анастасия Ильинична Чистопольская] || [https://t.me/krsv066 Кирилл Агафонов]
|-
|| 249 || [https://t.me/Ni_Mans Никита Сергеевич Майнуленко] || [https://t.me/polusladkaya_13 Екатерина Васильевна Михнёнок]
|-
|| 2410 || [https://t.me/yaognennaya Анна Тиграновна Зайцева] || [https://t.me/tioditp Андрей Новиков]
|-
|| 2411 || [https://t.me/Valinkin_M Михаил Валерьевич Валинкин] || [https://t.me/me_nella Мария Дятлова]
|-
|| 2412 || [https://t.me/theromestasenko Роман Олегович Стасенко] || [https://t.me/kunikrubika Егор Романюков]
|-
|| 2413 || [https://t.me/yaognennaya Анна Тиграновна Зайцева] || [https://t.me/hanitur Артур Бабаян]
|-
|| 2414 || Павел Павлович Соколов || [https://t.me/mariaskai13 Мария Деминова]
|-
|}

Ассистенты курса: [https://t.me/ccddtj Иван Хмура], [https://t.me/uni_vers_all Полина Микулич]

==Правила оценивания==

Элементы контроля в курсе: домашние задания (еженедельно), коллоквиумы (2), экзамены (письменные, 2).

====Домашние задания====

Домашние задания выдаются раз в неделю и должны быть выполнены в течение недели со дня выдачи. Оценка за полное решение каждой задачи из домашнего задания равна 4.
Предварительная оценка за домашнее задание выставляется в 10-балльной шкале и пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Для проверки остаточных знаний по темам домашних заданий проводится выборочная защита (устная беседа) по решенным (хотя бы частично) задачам. В случае, если студент не может ответить на ключевые вопросы по решению задачи или сформулировать используемые при решении задач теоремы и определения, преподаватель уменьшает предварительную оценку за домашнее задание на 50%. При неудаче ответа по двум задачам оценка за домашнее задание обнуляется.

Оценка за домашние задания первого семестра ДЗ1 равна среднему арифметическому оценок за домашние задания первого и второго модуля. Точный состав домашних заданий, учитываемых в этой оценке, определяется ситуативно и объявляется в конце 2 модуля.
Оценка за домашние задания третьего модуля ДЗ2 равна среднему арифметическому оценок за домашние задания третьего модуля, выставляется аналогично оценке ДЗ1.

'''Комментарий.''' Проверка домашних заданий по очевидным причинам происходит позже их сдачи. Поэтому вполне возможно, что во втором модуле будут домашние задания, которые нужно сдать во втором модуле, а проверены они будут уже в 3 модуле и войдут в оценку ДЗ2, а на ДЗ1.

====Коллоквиумы====

Проводятся для проверки теоретических знаний и умения решать стандартные задачи. Планируется два коллоквиума: один во 2 модуле, второй - в 3м. Оценки за коллоквиум Колл1, Колл2 выставляется в 10-балльной шкале. Программа коллоквиума и правила его проведения объявляются перед коллоквиумом. Основной источник информации - эта страница. Все остальные источники считаются в нашем курсе вспомогательными.

====Экзамены====

Проводятся в сессию 2 и 3 модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам.

Экзамен проводится в письменной форме. Промежуточный экзамен после второго модуля проводится по всем темам 1-2 модуля. Итоговый экзамен по курсу проводится после третьего модуля по всем темам курса (в основном задачи будут относится к темам 3 модуля). Помимо проверки усвоения материала курса, на письменном экзамене проверяется также умение творчески использовать полученные знания.

Оценки за экзамены Экз1, Экз2 выставляются в 10-балльной шкале. Критерии проверки и правила оценивания экзаменационных работ объявляются после проверки работ.

====Пересдачи====

Пересдачи домашних заданий невозможны, так как предполагается выполнение домашнего задания в определенный временной промежуток. Пересдача коллоквиума возможна до начала сессии, если коллоквиум пропущен по уважительной причине (неудовлетворительная оценка уважительной причиной не является). Пересдача экзамена проводится в письменном виде по тем же правилам, что и основной экзамен.

====Формула оценки====

Промежуточная аттестация после второго модуля.

Оценка 2 модуля = 0.25 * ДЗ1 + 0.3* Колл1 + 0.45* Экз1

'''Программой дисциплины не предусмотрено обучение в 3 модуле тех, кто получил неудовлетворительную промежуточную оценку в 1 семестре.'''

Окончательная оценка по курсу.

Оценка 3 модуля = 0.2*Оценка 2 модуля + 0.2* ДЗ2 + 0.24 * Колл2 + 0.36*Экз2

'''Правило округления.''' В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и окончательной оценок за курс. При выставлении промежуточной и окончательной оценки используется арифметическое округление.

== Результаты ==

В файлах по ссылкам содержатся

* Оценки за домашние задания, на каждое свой лист (окончательный результат - в столбце "И-оценка". Он нулевой, если в столбце "защита/с-р" стоит 0.)
По поводу защит домашних заданий обращайтесь к своим преподавателям или ассистентам.

* Оценки за теоретические контрольные и экзамены по мере их появления.

* Промежуточные и итоговые оценки за курс (имеют смысл после сдачи теоретических контрольных и экзаменов).

{| class="wikitable" style="text-align:center"
|-
! '''[https://docs.google.com/spreadsheets/d/13cmaW3lBpe_bCE6CbrHe7ePscyzYJFBJ/edit?usp=drive_link&ouid=100176966166125665216&rtpof=true&sd=true 247 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/19XfhZ7G2zb1y28ROcoHi-xik4eBrTWuQ/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 248 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1Z8npeyo9KHsmIlKpMFimcXsFG0isEgic/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 249 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1UOAduV2eX8j6aeKB7q0DUZ4mp3cstcPq/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2410 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1nmROfH9PAeWGk_4r5Hej61UJAvcD1cxS/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2411 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1neZp2IuUDD_DsxW_d_87Dstgkd-9hOYd/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2412 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1cTRcbDToBTP45qLWZ201I5tAM_-a-U4f/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2413 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1LbYZOGMqPCbX0_eOzf3Mc8kTD5C-Uf5q/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2414 группа ПМИ]'''
|}

== Материалы курса ==

 

* [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Черновик учебника.] В этой книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ, см. ниже).

* [https://drive.google.com/file/d/1Rd3PiKw7LKJMSk9XqO0Ycf7cc2sc96c0/view?usp=sharing Черновик 3 лекции]. '''Может отличаться от реальной лекции!''' Однако были просьбы выкладывать такие черновики. Если не боитесь запутаться между предварительным текстом и рассказом на лекции - пользуйтесь.

* [https://drive.google.com/file/d/1Fkc7Ie59jTruQaQDjJN16MoxXkOGfzRz/view?usp=sharing Конспекты лекций.] В этом файле будут собираться конспекты лекций. '''Обратите внимание:''' файл будет обновляться по мере чтения лекций, ссылка останется той же самой.

* Списки задачи для разбора в классе и домашние задания.
По ссылке "Занятие <номер занятия> (pdf)" содержатся и задачи для разбора в классе, и задачи домашнего задания в виде pdf файла. По ссылке "Занятие <номер занятия> (tex)" содержатся те же материалы в виде TeXовского исходника. Для компиляции нужен [https://drive.google.com/file/d/17jggxm41vxussSuRh8YqOfwmAp4NcliS/view?usp=sharing файл preamble.sty].

{| class="wikitable"
|-
|| [https://drive.google.com/file/d/1IQQp478cNZ8RgTOjap5pJBOP90IHNL6D/view?usp=sharing Занятие 1 (pdf)] || [https://drive.google.com/file/d/1hmA_LDLn9CoARI4k-8n4dSXa7mFWyxK-/view?usp=sharing Занятие 1 (tex)]
|| [https://drive.google.com/file/d/1d3aapLosnNzNHMheL2qz23HbDEC1Aacc/view?usp=sharing Занятие 2 (pdf)] || [https://drive.google.com/file/d/1XUexprnvArfpni8Nu1T9bomCOEM4m3z_/view?usp=sharing Занятие 2 (tex)]
|| [https://drive.google.com/file/d/1vSR8eQgCBY9F_r6QR-lId4wMaGjLhDt1/view?usp=sharing Занятие 3 (pdf)] || [https://drive.google.com/file/d/1wSkJuvYYw_cf2p544r985bcwcU2b7YR1/view?usp=sharing Занятие 3 (tex)]

|}

== Литература ==

# М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с.
# Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
# 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 с.: - (Бакалавриат) - Режим доступа: http://znanium.com/catalog/product/851215
# Рейнгард Дистель. Теория графов, Новосибирск: Изд-во Ин-та математики, 2002, 336 с.

DM1PMIbase-2024-25

2024-09-20T11:45:08Z

Avparfenov:

==ОБЪЯВЛЕНИЯ==

'''19.09.2024''' Условие задачи Д3.4 изменено! Функции f,g нужно считать всюду определенными.



== Преподаватели и ассистенты==

Лекции: Михаил Николаевич Вялый. Ассистент лектора: [https://t.me/dunno_0 Артём Вячеславович Парфенов]

Семинары:

{| class="wikitable" style="text-align:right"
|-
! Группа !! Преподаватель !! Учебный(-е) ассистент(-ы)
|-
|| 247 || Михаил Николаевич Вялый || [https://t.me/katya_klika Екатерина Михайлова]
|-
|| 248 || [https://t.me/chistopolskaia Анастасия Ильинична Чистопольская] || [https://t.me/krsv066 Кирилл Агафонов]
|-
|| 249 || [https://t.me/Ni_Mans Никита Сергеевич Майнуленко] || [https://t.me/polusladkaya_13 Екатерина Васильевна Михнёнок]
|-
|| 2410 || [https://t.me/yaognennaya Анна Тиграновна Зайцева] || [https://t.me/tioditp Андрей Новиков]
|-
|| 2411 || [https://t.me/Valinkin_M Михаил Валерьевич Валинкин] || [https://t.me/me_nella Мария Дятлова]
|-
|| 2412 || [https://t.me/theromestasenko Роман Олегович Стасенко] || [https://t.me/kunikrubika Егор Романюков]
|-
|| 2413 || [https://t.me/yaognennaya Анна Тиграновна Зайцева] || [https://t.me/hanitur Артур Бабаян]
|-
|| 2414 || Павел Павлович Соколов || [https://t.me/mariaskai13 Мария Деминова]
|-
|}

Ассистенты курса: [ Иван Хмура], [https://t.me/uni_vers_all Полина Микулич]

==Правила оценивания==

Элементы контроля в курсе: домашние задания (еженедельно), коллоквиумы (2), экзамены (письменные, 2).

====Домашние задания====

Домашние задания выдаются раз в неделю и должны быть выполнены в течение недели со дня выдачи. Оценка за полное решение каждой задачи из домашнего задания равна 4.
Предварительная оценка за домашнее задание выставляется в 10-балльной шкале и пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Для проверки остаточных знаний по темам домашних заданий проводится выборочная защита (устная беседа) по решенным (хотя бы частично) задачам. В случае, если студент не может ответить на ключевые вопросы по решению задачи или сформулировать используемые при решении задач теоремы и определения, преподаватель уменьшает предварительную оценку за домашнее задание на 50%. При неудаче ответа по двум задачам оценка за домашнее задание обнуляется.

Оценка за домашние задания первого семестра ДЗ1 равна среднему арифметическому оценок за домашние задания первого и второго модуля. Точный состав домашних заданий, учитываемых в этой оценке, определяется ситуативно и объявляется в конце 2 модуля.
Оценка за домашние задания третьего модуля ДЗ2 равна среднему арифметическому оценок за домашние задания третьего модуля, выставляется аналогично оценке ДЗ1.

'''Комментарий.''' Проверка домашних заданий по очевидным причинам происходит позже их сдачи. Поэтому вполне возможно, что во втором модуле будут домашние задания, которые нужно сдать во втором модуле, а проверены они будут уже в 3 модуле и войдут в оценку ДЗ2, а на ДЗ1.

====Коллоквиумы====

Проводятся для проверки теоретических знаний и умения решать стандартные задачи. Планируется два коллоквиума: один во 2 модуле, второй - в 3м. Оценки за коллоквиум Колл1, Колл2 выставляется в 10-балльной шкале. Программа коллоквиума и правила его проведения объявляются перед коллоквиумом. Основной источник информации - эта страница. Все остальные источники считаются в нашем курсе вспомогательными.

====Экзамены====

Проводятся в сессию 2 и 3 модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам.

Экзамен проводится в письменной форме. Промежуточный экзамен после второго модуля проводится по всем темам 1-2 модуля. Итоговый экзамен по курсу проводится после третьего модуля по всем темам курса (в основном задачи будут относится к темам 3 модуля). Помимо проверки усвоения материала курса, на письменном экзамене проверяется также умение творчески использовать полученные знания.

Оценки за экзамены Экз1, Экз2 выставляются в 10-балльной шкале. Критерии проверки и правила оценивания экзаменационных работ объявляются после проверки работ.

====Пересдачи====

Пересдачи домашних заданий невозможны, так как предполагается выполнение домашнего задания в определенный временной промежуток. Пересдача коллоквиума возможна до начала сессии, если коллоквиум пропущен по уважительной причине (неудовлетворительная оценка уважительной причиной не является). Пересдача экзамена проводится в письменном виде по тем же правилам, что и основной экзамен.

====Формула оценки====

Промежуточная аттестация после второго модуля.

Оценка 2 модуля = 0.25 * ДЗ1 + 0.3* Колл1 + 0.45* Экз1

'''Программой дисциплины не предусмотрено обучение в 3 модуле тех, кто получил неудовлетворительную промежуточную оценку в 1 семестре.'''

Окончательная оценка по курсу.

Оценка 3 модуля = 0.2*Оценка 2 модуля + 0.2* ДЗ2 + 0.24 * Колл2 + 0.36*Экз2

'''Правило округления.''' В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и окончательной оценок за курс. При выставлении промежуточной и окончательной оценки используется арифметическое округление.

== Результаты ==

В файлах по ссылкам содержатся

* Оценки за домашние задания, на каждое свой лист (окончательный результат - в столбце "И-оценка". Он нулевой, если в столбце "защита/с-р" стоит 0.)
По поводу защит домашних заданий обращайтесь к своим преподавателям или ассистентам.

* Оценки за теоретические контрольные и экзамены по мере их появления.

* Промежуточные и итоговые оценки за курс (имеют смысл после сдачи теоретических контрольных и экзаменов).

{| class="wikitable" style="text-align:center"
|-
! '''[https://docs.google.com/spreadsheets/d/13cmaW3lBpe_bCE6CbrHe7ePscyzYJFBJ/edit?usp=drive_link&ouid=100176966166125665216&rtpof=true&sd=true 247 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/19XfhZ7G2zb1y28ROcoHi-xik4eBrTWuQ/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 248 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1Z8npeyo9KHsmIlKpMFimcXsFG0isEgic/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 249 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1UOAduV2eX8j6aeKB7q0DUZ4mp3cstcPq/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2410 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1nmROfH9PAeWGk_4r5Hej61UJAvcD1cxS/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2411 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1neZp2IuUDD_DsxW_d_87Dstgkd-9hOYd/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2412 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1cTRcbDToBTP45qLWZ201I5tAM_-a-U4f/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2413 группа ПМИ]'''
! '''[https://docs.google.com/spreadsheets/d/1LbYZOGMqPCbX0_eOzf3Mc8kTD5C-Uf5q/edit?usp=sharing&ouid=100176966166125665216&rtpof=true&sd=true 2414 группа ПМИ]'''
|}

== Материалы курса ==

 

* [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Черновик учебника.] В этой книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ, см. ниже).

* [https://drive.google.com/file/d/1Rd3PiKw7LKJMSk9XqO0Ycf7cc2sc96c0/view?usp=sharing Черновик 3 лекции]. '''Может отличаться от реальной лекции!''' Однако были просьбы выкладывать такие черновики. Если не боитесь запутаться между предварительным текстом и рассказом на лекции - пользуйтесь.

* [https://drive.google.com/file/d/1Fkc7Ie59jTruQaQDjJN16MoxXkOGfzRz/view?usp=sharing Конспекты лекций.] В этом файле будут собираться конспекты лекций. '''Обратите внимание:''' файл будет обновляться по мере чтения лекций, ссылка останется той же самой.

* Списки задачи для разбора в классе и домашние задания.
По ссылке "Занятие <номер занятия> (pdf)" содержатся и задачи для разбора в классе, и задачи домашнего задания в виде pdf файла. По ссылке "Занятие <номер занятия> (tex)" содержатся те же материалы в виде TeXовского исходника. Для компиляции нужен [https://drive.google.com/file/d/17jggxm41vxussSuRh8YqOfwmAp4NcliS/view?usp=sharing файл preamble.sty].

{| class="wikitable"
|-
|| [https://drive.google.com/file/d/1IQQp478cNZ8RgTOjap5pJBOP90IHNL6D/view?usp=sharing Занятие 1 (pdf)] || [https://drive.google.com/file/d/1hmA_LDLn9CoARI4k-8n4dSXa7mFWyxK-/view?usp=sharing Занятие 1 (tex)]
|| [https://drive.google.com/file/d/1d3aapLosnNzNHMheL2qz23HbDEC1Aacc/view?usp=sharing Занятие 2 (pdf)] || [https://drive.google.com/file/d/1XUexprnvArfpni8Nu1T9bomCOEM4m3z_/view?usp=sharing Занятие 2 (tex)]
|| [https://drive.google.com/file/d/1vSR8eQgCBY9F_r6QR-lId4wMaGjLhDt1/view?usp=sharing Занятие 3 (pdf)] || [https://drive.google.com/file/d/1wSkJuvYYw_cf2p544r985bcwcU2b7YR1/view?usp=sharing Занятие 3 (tex)]

|}

== Литература ==

# М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с.
# Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
# 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 с.: - (Бакалавриат) - Режим доступа: http://znanium.com/catalog/product/851215
# Рейнгард Дистель. Теория графов, Новосибирск: Изд-во Ин-та математики, 2002, 336 с.

2023-09-01T13:01:09Z

Avparfenov: /* Преподаватели и ассистенты */

==ОБЪЯВЛЕНИЯ==

== Общая информация о курсе Дискретная математика, основной поток ПМИ, 1 курс==

=== Преподаватели и ассистенты===

Лекции: Михаил Николаевич Вялый. Ассистент лектора: [https://t.me/dunno_0 Артём Вячеславович Парфенов]

Семинары:

{| class="wikitable" style="text-align:right"
|-
! Группа !! Преподаватель !! Учебный(-е) ассистент(-ы)
|-
|| 236 || [https://t.me/mnvyalyi Михаил Николаевич Вялый] || [https://t.me/Gnihton Эрик Эдуардович Яппаров]
|-
|| 237 || Алина Эдуардовна Хузиева || [https://t.me/polusladkaya_13 Екатерина Васильевна Михнёнок]
|-
|| 238 || [https://t.me/Valinkin_M Михаил Валерьевич Валинкин] || [https://t.me/nizamovoff Айнур Мулланурович Низамов]
|-
|| 239 || Лиза Шатская || [https://t.me/v3ltro Иван Алексеевич Коровин]
|-
|| 2310 || [https://t.me/chistopolskaia Анастасия Ильинична Чистопольская] || [https://t.me/Sn0_w Никита Витальевич Лагода]
|-
|| 2311 || [https://t.me/Ni_Mans Никита Сергеевич Мануйленко] || [https://t.me/dac1001 Даниил Максимович Смирнов]
|-
|| 2312 || Анна Тиграновна Енгоян || [https://t.me/jtqjd0 Лейла Александровна Мурсманидзе]
|-
|| онлайн-группа || Никита Сергеевич Лукьяненко ||
|}

===Правила оценивания===

Элементы контроля в курсе: домашние задания (еженедельно), письменные контрольные работы по проверке теоретических знаний (2), экзамены (письменные, 2).

====Домашние задания====

Домашние задания выдаются раз в неделю и должны быть выполнены в течение недели со дня выдачи. Оценка за полное решение каждой задачи из домашнего задания равна 4.
Предварительная оценка за домашнее задание выставляется в 10-балльной шкале и пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Для проверки остаточных знаний по темам домашних заданий проводится выборочная защита (устная беседа) по решенным (хотя бы частично) задачам. В случае, если студент не может ответить на ключевые вопросы по решению задачи или сформулировать используемые при решении задач теоремы и определения, преподаватель уменьшает предварительную оценку за домашнее задание на 50%. При неудаче ответа по двум задачам оценка за домашнее задание обнуляется.

Оценка за домашние задания первого семестра ДЗ1 равна среднему арифметическому оценок за домашние задания первого и второго модуля. Точный состав домашних заданий, учитываемых в этой оценке определяется ситуативно и объявляется в конце 2 модуля.
Оценка за домашние задания третьего модуля ДЗ2 равна среднему арифметическому оценок за домашние задания третьего модуля, выставляется аналогично оценке ДЗ1.

'''Комментарий.''' Помимо обязательных домашних заданий будут выдаваться дополнительные домашние задания. Они не являются элементом контроля, играют чисто учебную роль и служат для тренировки в решении более трудных задач по материалам курса. Дополнительные домашние задания проверяются, но оценки за них не учитываются в оценке за курс.

====Письменные контрольные работы по проверке теоретических знаний====

Проводятся в конце второго модуля и в конце третьего модуля во время семинарских занятий по темам, изученным к моменту проведения контрольной (в третьем модуле - по всем темам, не вошедшим в первую контрольную работу). Работа письменная, проверяет знание определений и формулировок теорем курса, умение использовать их, а также понимание доказательств курса и умение использовать их. Точные правила проведения контрольных будут объявлены позднее.

Оценки за контрольные TK1 и ТК2 выставляются в 10-балльной шкале.

====Экзамены====

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

Оценки за экзамены Экз1 и Экз2 выставляются в 10-балльной шкале.

====Пересдачи====

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

====Формула оценки====

Промежуточная аттестация после второго модуля. Формула оценки зависит от результата письменного экзамена второго модуля.

Если оценка за письменный экзамен не больше 5, то '''результат экзамена в итоговой оценке не учитывается'''

оценка промежуточной аттестации = 0.25 * ДЗ1 + 0.55* ТК1

Если оценка за письменный экзамен больше 5, то

оценка промежуточной аттестации = 0.25 * ДЗ1 + 0.55* ТК1 + 0.2* Экз1

'''Программой дисциплины не предусмотрено обучение в 3 модуле тех, кто получил неудовлетворительную промежуточную оценку в 1 семестре.'''

Окончательная оценка по курсу. Формула оценки зависит от результата письменного экзамена 3 модуля.

Если оценка за письменный экзамен не больше 5, то '''результат экзамена в итоговой оценке не учитывается'''

Оценка за курс= 0.2*Оценка промежуточной аттестации 2 модуля + 0.2* ДЗ2 + 0.4 * ТК2

Если оценка за письменный экзамен больше 5, то

Оценка за курс = 0.2*Оценка промежуточной аттестации 2 модуля + 0.2* ДЗ2 + 0.4 * ТК2+ 0.2*Экз2

====Правило округления====

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и окончательной оценок за курс. При выставлении промежуточной и окончательной оценки используется арифметическое округление.



== Материалы курса ==

 

* [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Черновик учебника.] В этой книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ, см. ниже).

* Конспекты лекций 

* Списки задачи для разбора в классе и домашние задания.


* Дополнительные задачи (в одном файле, как и конспекты лекций).

== Литература ==

# М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с.
# Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
# 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 с.: - (Бакалавриат) - Режим доступа: http://znanium.com/catalog/product/851215
# Рейнгард Дистель. Теория графов, Новосибирск: Изд-во Ин-та математики, 2002, 336 с.