Дискретная математика на ПМИ 2023/24 (пилотный поток) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(ссылки на тг профиль)
 
(не показано 117 промежуточных версии 4 участников)
Строка 3: Строка 3:
 
Канал, где дублируются важные объявления курса (рекомендуем подписаться): https://t.me/+PHZJZMnbCaxmMjVi
 
Канал, где дублируются важные объявления курса (рекомендуем подписаться): https://t.me/+PHZJZMnbCaxmMjVi
  
 +
___________________
 +
 +
Показ работ экзамена состоится в пятницу '''29 марта, в 14:30''', аудитория R305.
 +
 +
___________________
 +
 +
'''25 марта в 13:00''' состоится итоговый письменный экзамен по курсу. Длительность - 130 минут, на нем будет 6 задач по темам, покрывающим материал 2-3 модулей (до лекции 25 включительно). Пользоваться можно любыми бумажными материалами, и никакими электронными! Допускается использование стандартного калькулятора.
 +
 +
Распределение групп по аудиториям:
 +
 +
группы 231 и 235: аудитория R401
 +
 +
группы 233 и 234: аудитория R201
 +
 +
группа 232: аудитория R406
 +
 +
___________________
 +
 +
Лекция 19.03 отменяется.
 +
 +
___________________
 +
 +
Второй коллоквиум пройдет '''16 марта'''. Программа и правила коллоквиума приложены ниже. Расписание по группам:
 +
 +
Группа 232: 10:00, аудитория R404
 +
 +
Группа 235: 11:20, аудитория R404
 +
 +
Группа 234: 14:00, аудитория R401
 +
 +
Группа 233: 15:00, аудитория R401
 +
 +
Группа 231: 16:00, аудитория R401
 +
 +
Приходить необходимо со своей группой. Пользоваться на коллоквиуме материалами (ни бумажными, ни электронными) нельзя.
 +
 +
___________________
 +
 +
Зимний (промежуточный) экзамен состоится '''27 декабря''', начало в '''11:00'''!
 +
Длительность экзамена – 130 минут.
 +
 +
Не опаздывайте!
 +
 +
Пользоваться можно любыми бумажными материалами, и никакими электронными! Допускается использование стандартного калькулятора.
 +
 +
На экзамене будет 6 задач по темам первых 14 лекций курса и двух онлайн-лекций.
 +
 +
Распределение по аудиториям:
 +
 +
группы 231 и 234: аудитория R401
 +
 +
группы 232 и 235: аудитория R201
 +
 +
группа 233: аудитория R406
 +
 +
___________________
 +
 +
 +
Первый коллоквиум пройдет '''25 ноября'''. Программа и правила коллоквиума приложены ниже.
 +
Расписание коллоквиума по группам:
 +
 +
подгруппа 231-1: 11:10, аудитория K418
 +
 +
подгруппа 231-2: 12:40, аудитория R401
 +
 +
группа 234: 12:40, аудитория R401
 +
 +
группа 233: 15:20, аудитория R401
 +
 +
группа 235: 15:40, аудитория R401
 +
 +
группа 232: 17:30, аудитория R401
 +
 +
___________________
 +
 +
'''7 ноября, 16:20-17:40''', состоится контрольная работа по материалам лекций и семинаров 1 модуля.
 +
В контрольной будет 5 задач на следующие темы:
 +
 +
- Индукция
 +
 +
- Перечислительная комбинаторика
 +
 +
- Множества и функции
 +
 +
- Булевы функции: ДНФ, многочлены Жегалкина
 +
 +
- Замкнутые классы булевых функций, критерий Поста
 +
 +
- Мощности множеств, счетные и континуальные множества, сравнение мощностей
 +
 +
Пользоваться материалами (ни бумажными, ни электронными) нельзя. Допускается использование лишь стандартного калькулятора (хотя едва ли он пригодится).
 +
 +
Распределение групп по аудиториям:
 +
 +
R201 - группы 231, 232 и 234-1, 
 +
 +
R503 - группы 235 и 234-2, 
 +
 +
R504 - группа 233.
 +
 +
Пожалуйста, не опаздывайте: в 16:20 мы раздадим всем условия задач и начнем отсчет времени (длительность работы – 80 минут).
 +
 +
== Лабораторные работы ==
 +
 +
=== Лабораторная работа 2 (3 модуль) ===
 +
 +
Лабораторная работа состоит из двух частей: контеста и ноутбука. На выполнение работы дается чуть меньше трех недель.
 +
 +
Дедлайн и по контесту, и по ноутбуку: '''9 марта 23:59'''.
 +
 +
Контест состоит из четырех задач и сдается на платформе Codeforces. Оцениваются только задачи, которые прошли все тесты в тестирующей системе.
 +
 +
Ноутбук содержит 3 задачи, которые надо решать на языке Python. Инструкция по работе с Jupyter Notebook и сам ноутбук находятся в Google Classroom по ссылке ниже. Решения сдаются туда же.
 +
 +
Разбалловка задач указана в ноутбуке и контесте в условиях. Баллы за все задачи суммируются, сумма баллов является оценкой за ЛР-2. Максимальная возможная оценка — 12.
 +
 +
По любым вопросам по лабораторной работе стоит писать ответственному ассистенту [https://t.me/existingone Роману Гундарину].
 +
 +
[https://classroom.google.com/c/NjM4MTE5MzQzOTQz?cjc=guy75e5 Ссылка на классрум]
 +
 +
[https://codeforces.com/contests/505649 Ссылка на контест]
 +
 +
=== Лабораторная работа 1 (2 модуль) ===
 +
 +
Лабораторная работа состоит из двух частей: контеста с алгоритмическими задачами и ноутбука по библиотеке NetworkX, которые оцениваются по отдельности. На выполнение работы дается чуть меньше трех недель.
 +
 +
Дедлайн и по контесту, и по ноутбуку: '''6 декабря 23:59'''.
 +
 +
Контест состоит из пяти задач и сдается на платформе Codeforces. Оцениваются только задачи, которые прошли все тесты в тестирующей системе. Первые четыре задачи оцениваются в 2 балла. За пятую задачу можно получить от 2 до 4 баллов. Таким образом, максимальный возможный балл за контест — 12.
 +
 +
Ноутбук содержит 4 задачи, которые надо решать на языке Python, правила оценивания которых написаны в самом ноутбуке. Инструкция по работе с Jupyter Notebook и сам ноутбук находятся в  в Google Classroom по ссылке ниже. Решения сдаются туда же. За эту часть лабораторной работы можно так же получить до 12 баллов.
 +
 +
Оценка за лабораторную работу вычисляется по формуле: ''ЛАБ-1 = sqrt((НОУТБУК^0.5) * (КОНТЕСТ^1.5))''. Максимальная возможная оценка за лабораторную работу равна 12.
 +
 +
По любым вопросам по лабораторной работе стоит писать ответственному ассистенту [https://t.me/existingone Роману Гундарину]. В частности, если вы не знаете язык Python, то можно запросить консультацию.
 +
 +
[https://classroom.google.com/c/NjM4MTE5MzQzOTQz?cjc=guy75e5 Ссылка на классрум]
 +
 +
[https://codeforces.com/contestInvitation/8c9a5886f23b388d2b31be7d4e20db78105d6a69 Ссылка на контест]
 +
 +
== Контрольные мероприятия ==
 +
 +
=== Итоговый экзамен (25.03, понедельник) ===
 +
[https://disk.yandex.ru/i/x0nPB87ig-X0rQ Решения задач итогового экзамена]
 +
 +
=== Программа и правила проведения весеннего коллоквиума 2024 года (16.04, суббота) ===
 +
[https://disk.yandex.ru/i/QmOWrQuD3SoVRA Программа и правила проведения весеннего коллоквиума].
 +
 +
=== Промежуточный экзамен (27.12, среда) ===
 +
[https://disk.yandex.ru/i/BF-sRO1FSrRktw Решения задач промежуточного экзамена]
 +
 +
=== Программа и правила проведения зимнего коллоквиума 2023 года (25.11, суббота) ===
 +
[https://disk.yandex.ru/i/uvrsEG7s9xiGJQ Программа и правила проведения зимнего коллоквиума].
 +
 +
=== Контрольная работа (07.11, вторник) ===
 +
[https://disk.yandex.ru/i/igeCQ69jgkYvsg Условия задач контрольной работы].
  
 
== Общая информация о курсе Дискретная математика, пилотный поток, 1 курс==
 
== Общая информация о курсе Дискретная математика, пилотный поток, 1 курс==
Строка 20: Строка 176:
 
|| 232 || [https://www.hse.ru/org/persons/856267465 Михаил Викторович Игнатьев]  || понедельник 18:10, вторник 16:20 по нечётным неделям, четверг 19:40 по нечётным неделям, S812 || [https://t.me/khitrin Глеб Хитрин]
 
|| 232 || [https://www.hse.ru/org/persons/856267465 Михаил Викторович Игнатьев]  || понедельник 18:10, вторник 16:20 по нечётным неделям, четверг 19:40 по нечётным неделям, S812 || [https://t.me/khitrin Глеб Хитрин]
 
|-
 
|-
−
|| 233 || [Павел Павлович Соколов] || || [https://t.me/asahium Данила Биктимиров]
+
|| 233 || [https://www.hse.ru/staff/TurtlePU Павел Павлович Соколов] || вторник 11:10-12:30, пятница 11:10-12:30 и 14:40-17:40, S805 (предварительно предупредить) || [https://t.me/asahium Данила Биктимиров]
 
|-
 
|-
−
|| 234 || [https://www.hse.ru/org/persons/314157965 Валентин Валерьевич Промыслов] ||  || [https://t.me/alinash57 Алина Шипова]
+
|| 234 || [https://www.hse.ru/org/persons/314157965 Валентин Валерьевич Промыслов] || пятница 16:20-17:40, T909 (предварительно предупредить) || [https://t.me/alinash57 Алина Шипова]
 
|-
 
|-
−
|| 235 || [Роман Олегович Стасенко] || суббота 13:30-15:00 (онлайн)  || [https://t.me/dac1001 Данил Смирнов]
+
|| 235 || [https://www.hse.ru/org/persons/859152259 Роман Олегович Стасенко ] || суббота 13:30-15:00 (онлайн)  || [https://t.me/dac1001 Данил Смирнов]
 
|}
 
|}
  
Строка 34: Строка 190:
  
 
[https://t.me/Alexxxey5 Алексей Воронко]
 
[https://t.me/Alexxxey5 Алексей Воронко]
 +
 +
'''Ассистент, ответственный за лабораторные работы:'''
 +
 +
[https://t.me/existingone Роман Гундарин]
  
 
===Правила оценивания===
 
===Правила оценивания===
  
−
Домашние задания выдаются еженедельно и сдаются перед следующим семинаром (в некоторых группах - перед следующей лекцией). Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Трижды за весь курс (1-3 модули) домашнее задание разрешается сдать на неделю позже срока без потери баллов.
+
Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Трижды за весь курс (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.
 
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, между 6 и 8 округление вверх, а между 8 и 10 округление арифметическое. Т.е. 3,92 округляется до 3; 5,48 - до 5; 5,54 - до 6; 7,12 - до 8; 9,4 - до 9.
Строка 67: Строка 237:
 
''Литература: [1, §5.1-5.2, лекция 6]''
 
''Литература: [1, §5.1-5.2, лекция 6]''
  
 +
'''Онлайн лекция 1'''. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений.
 +
 +
''Литература: [1, лекция 2, §5.6]''
 +
 +
'''Лекция 3'''. Утверждение о композиции биекций. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности, количество булевых функций от n переменных. Правила алгебры логики, доказательство теоретико-множественных тождеств с помощью алгебры логики. Эквивалентность принципа математической индукции, принципа полной индукции и принципа наименьшего числа.
 +
 +
''Литература: [1, §6.5, §5.3-5.5]''
 +
 +
'''Лекция 4'''. Дизъюнктивная нормальная форма, теорема о существовании ДНФ для любой булевой функции. Совершенная дизъюнктивная нормальная форма (СДНФ). Конъюнктивная нормальная форма (КНФ). Полиномы Жегалкина. Теорема о представлении булевой функции полиномом Жегалкина (существование и единственность). Суперпозиция булевых функций, замыкание класса булевых функций, свойства замыкания. Полные системы связок. Полнота системы связок «конъюнкция, дизъюнкция, отрицание» и «конъюнкция, отрицание». Полнота системы связок «XOR, конъюнкция, 1».
 +
 +
Литература: [1, §5.5], [3, глава 1, §1-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); (0, 1); множества всех подмножеств натуральных чисел. Мощность континуум. Равномощность отрезка и квадрата. Сравнение мощностей, его свойства. Утверждение о том, что счетная мощность меньше континуальной. Теорема Кантора о сравнении мощности множества и мощности множества всех его подмножеств. Теорема Кантора-Бернштейна.
 +
 +
''Литература: [1, §8.3-8.5], [2, §1.5-1.6]''
 +
 +
'''Лекция 8'''.
 +
Бинарные отношения, теорема об ассоциативности композиции отношений. Отношение эквивалентности, теорема о разбиении множества с отношением эквивалентности на классы, состоящие из попарно эквивалентных элементов. Ориентированные графы: основные понятия. Лемма о числе ребер в ориентированном графе. Сильная связность орграфа, компоненты сильной связности. Ациклические орграфы, топологическая сортировка.
 +
 +
''Литература: [1, §3.3]''
 +
 +
'''Онлайн лекция 2'''. Графы, основные понятия (степень вершины, путь, цикл, простой путь, простой цикл). Лемма о рукопожатиях. Связность графа, компоненты связности. Неравенство, связывающее число вершин, ребер и компонент связности в графе. Деревья. Теорема об эквивалентных определениях дерева. Полное двоичное дерево. Остовное дерево в графе.
 +
 +
''Литература: [1, §3.1-3.2]''
 +
 +
'''Лекция 9'''.
 +
Эйлеровы циклы в ориентированных и неориентированных графах. Критерий существования эйлерова цикла. Двудольные графы, критерий двудольности графа. Булев куб как граф, его 2-раскрашиваемость.  Раскраски графов, хроматическое число графа. Клики и независимые множества в графе. Свойства хроматического числа. Верхняя оценка на хроматическое число через максимальную из степеней вершин графа. Теорема Брукса (без доказательства).
 +
 +
''Литература: [1, §3.4-3.5]''
 +
 +
'''Лекция 10'''.
 +
Хроматический многочлен, его вычисление для полного графа, его дополнения и дерева. Лемма о связи хроматического многочлена графа, графа с удаленным ребром и стянутым ребром. Теорема Уитни о свойствах хроматического многочлена. Паросочетание в графе. Теорема Холла. Вершинные покрытия. Утверждение о связи максимального размера паросочетания и минимального размера вершинного покрытия в произвольном графе. Теорема Кёнига (формулировка).
 +
 +
''Литература: [1, §1.11, §3.5.4]''
 +
 +
'''Лекция 11'''.
 +
Чередующийся и увеличивающий пути относительно паросочетания. Отсутствие увеличивающего пути относительно максимального паросочетания. Теорема Кёнига (доказательство). Клики и независимые множества. Теорема Рамсея. Верхняя оценка на числа Рамсея. Мыцельскиан графа.
 +
 +
''Литература: [8, теорема 2.1.1],  [1, §3.6]''
 +
 +
'''Лекция 12'''.
 +
Пример Зыкова–Мыцельского графа без треугольников со сколь угодно большим хроматическим числом. Частично упорядоченные множества: строгий и нестрогий частичные порядки, примеры, линейный порядок. Утверждение о связи строгого и нестрогого порядков. Операции с частично упорядоченными множествами: покоординатный порядок, лексикографический порядок, сумма порядков. Изоморфизм порядков, примеры.  Минимальные (максимальные) и наименьшие (наибольшие) элементы, отрезки. Замечание о единственности наименьшего элемента, пример частично упорядоченного множества с бесконечным числом минимальных элементов. Утверждение о том, что при изоморфизме порядков отрезок переходит в отрезок. Следствие о том, что натуральные, целые и рациональные числа попарно неизоморфны как линейные порядки.
 +
 +
''Литература: [1, §9.1-9.4], [2, §2.1-2.2]''
 +
 +
'''Лекция 13'''.
 +
Теорема об изоморфизме счётных плотных линейных порядков без наименьшего и наибольшего элемента.
 +
Напоминание: минимальные (максимальные) и наименьшие (наибольшие) элементы, их свойства, примеры.
 +
Принцип индукции для частично упорядоченных множеств. Фундированные множества, теорема об эквивалентности трех определений фундированного множества.
 +
Цепи и антицепи в частично упорядоченных множествах, примеры. Формулировки теорем Мирского и Дилуорса.
 +
 +
''Литература: [1, §9.5-9.6], [2, §2.2-2.3]''
 +
 +
'''Лекция 14.'''
 +
Разбиение частично упорядоченных множеств на цепи/антицепи. Теорема Мирского о том, что размер максимальной цепи в ч.у.м. равен минимальному числу антицепей, образующих разбиение этого множества. Теорема Дилуорса. Утверждение о размере максимальной цепи в булевом кубе. LYM-неравенство. Теорема Шпернера о размере максимальной антицепи в булевом кубе.
 +
 +
''Литература: [1, §9.7]''
 +
 +
'''Лекция 15.''' Вероятностное пространство, вероятностное распределение, примеры. Свойства вероятности. Пошаговое задание распределения, дерево событий. Оценка объединения. Вероятностный метод: нижняя оценка для чисел Рамсея.
 +
 +
''Литература: [1, §10.1-10.3]''
 +
 +
'''Лекция 16.''' Формула включений-исключений для вероятностей. Задача о беспорядках. Условная вероятность, примеры ее подсчета. Теорема умножения, формулы Байеса и полной вероятности. Примеры с тестом на выявление болезни. Независимые события. Независимость событий в совокупности, отличие от попарной независимости событий.
 +
 +
''Литература: [1, §10.2,10.4]''
 +
 +
'''Лекция 17.''' Случайная величина, математическое ожидание, линейность матожидания. Задача о днях рождения. Нервенство Маркова, пример применения. Дисперсия. Неравенство Чебышёва. Независимые случайные величины. Математическое ожидание и дисперсия независимых случайных величин.
 +
 +
''Литература: [1, §10.5]''
 +
 +
'''Лекция 18.''' Общая формулировка вероятностного метода, пример применения для поиска разреза в графе величины не менее половины числа ребер.  Пример применения вероятностного метода для поиска разреза величины более половины числа ребер для графа с четным числом вершин. Теорема Эрдёша о существовании графа со сколь угодно большим хроматическим числом и сколь угодно большим обхватом.
 +
 +
''Литература: [1, §10.5]''
 +
 +
'''Лекция 19.''' Вероятность выпадения ровно половины орлов при бросании честной монеты. Производящие функции, определение. Их сложение и умножение на скаляр. Произведение производящих функций, основные свойства арифметических операций. Обратимые производящие функции, примеры. Формальное дифференцирование производящих функций, свойства производной, правило Лейбница. Подстановка нуля в производящую функцию, вычисление n-го коффициента производящей функции с использованием производных. Пример применения производящих функций: вывод формулы для суммы квадратов первых n натуральных чисел.
 +
 +
''Литература: [1, §10.6], [6, глава 1]''
 +
 +
'''Лекция 20.''' Завершение вывода формулы для суммы квадратов первых n натуральных чисел. Бином Ньютона, обобщение на целые показатели. Пример получения тождества с помощью производящих функций. Связь произведения производящих функций с неупорядоченными выборками, примеры. Линейные рекуррентные соотношения с постоянными коэффициентами. Теорема о том, что производящая функция последовательности, удовлетворяющей линейному рекуррентному соотношению с постоянными коэффициентами, рациональна. Явная формула для общего члена последовательности, метод ее вывода. Числа Фибоначчи: их производящая функция и вывод явной формулы (формула Бине).
 +
 +
''Литература: [6, глава 2]''
 +
 +
'''Лекция 21.''' Правильные скобочные последовательности. Критерий того, что скобочная последовательность является правильной. Рекуррентная формула для числа правильных скобочных последовательностей. Числа Каталана, их производящая функция и ее вывод как решения квадратного уравнения.
 +
Вывод явной формулы для чисел Каталана с использованием техники производящих функций. Явная проверка того, что полученные числа удовлетворяют рекуррентному соотношению для чисел Каталана.
 +
 +
''Литература: [1, §2.10.1, §2.10.2, §2.10.4, §2.10.6], [6, §2.5]''
 +
 +
'''Лекция 22.''' Комбинаторные игры с полной информацией. Задание игры в виде ориентированного графа. Партии и стратегии. Стратегии, гарантирующие выигрыш. Цена игры. Теорема о цене игры.  Беспристрастные игры, N- и P-позиции. Анализ игры с конца, примеры. Игра ним, ее P-позиции.
 +
 +
''Литература: [1, лекция 11]''
 +
 +
'''Лекция 23.''' Задача об угадывании числа, ее сложность в адаптивном и неадаптивном случае. Модель разрешающих деревьев. Адаптивный и неадаптивный протоколы, сведение адаптивного протокола к неадаптивному. Задача о сортировке, оценки на сложность адаптивного протокола. Задача о взвешиваниях: поиск самой тяжелой монеты, сложность в адаптивном и неадаптивном случае. Метод противника. Сложность булевой функции. Сложность булевой функции CONN, определяющей связность неориентированного графа на n вершинах.
 +
 +
''Литература: [1, лекция 12]''
 +
 +
'''Лекция 24.''' Булевы схемы, определение. Задание схемы в виде ациклического ориентированного графа. Схемы-графы для функции XOR и функции голосования. Схема линейного размера для сложения двоичных чисел.  Глубина булевой схемы. Построение схемы для функции CONN, определяющей связность неориентированного графа на n вершинах (два варианта для размера и глубины). Возведение булевой матрицы в степень, связь с числом путей в графе. Вычисление произвольной булевой функции от n переменных схемой размера O(n 2^n). Существование функций с экспоненциальной схемной сложностью.
 +
 +
''Литература: [1, §13.1]''
 +
 +
'''Лекция 25.''' Существование функций с экспоненциальной схемной сложностью. Верхняя и нижняя оценки для схемной сложности функции XOR. Формулы как частный случай схем. Существование формулы, эквивалентной данной булевой схеме, той же глубины и экспоненциального размера. Теорема о балансировке булевых формул (без доказательства). Задачи выполнимости булевой схемы, КНФ и 3-КНФ. Эффективное сведение задачи выполнимости булевой схемы к задаче выполнимости 3-КНФ.
 +
 +
''Литература: [1, §13]; доказательство теоремы о балансировке булевых формул можно прочесть в §13.2''
  
 
== Материалы курса ==
 
== Материалы курса ==
Строка 73: Строка 353:
  
 
[https://disk.yandex.ru/i/EFCQBED9lzoXXQ Листок 2. Множества и функции]
 
[https://disk.yandex.ru/i/EFCQBED9lzoXXQ Листок 2. Множества и функции]
 +
 +
[https://disk.yandex.ru/i/XI-W3Ox8cPGyhg Листок 3. Перечислительная комбинаторика]
 +
 +
[https://disk.yandex.ru/i/LDFiYWIt1IyMrg Листок 4. Булевы функции]
 +
 +
[https://disk.yandex.ru/i/2ivEoGl-Bn1_Sw Листок 5. Замкнутые классы, критерий Поста]
 +
 +
[https://disk.yandex.ru/i/uTfZtyV5zVoxyw Листок 6. Мощность множеств-1]
 +
 +
[https://disk.yandex.ru/i/lq_ywReGbUEZSQ Листок 7. Мощность множеств-2]
 +
 +
[https://disk.yandex.ru/i/Sq6gdSC3oexn3Q Листок 8. Отношения и ориентированные графы]
 +
 +
[https://disk.yandex.ru/i/gVDj-J_moWmy3A Листок 9. Неориентированные графы]
 +
 +
[https://disk.yandex.ru/i/weu9RJ4fdtAUnQ Листок 10. Хроматический многочлен графа, теорема Холла]
 +
 +
[https://disk.yandex.ru/i/xWkXJ6-pj0-P_Q Листок 11. Теоремы Кёнига и Рамсея, графы с большим хроматическим числом]
 +
 +
[https://disk.yandex.ru/i/vZCf9dbEbaRBIQ Листок 12. Порядки-1]
 +
 +
[https://disk.yandex.ru/i/vgM6PxU4EBU34g Листок 13. Порядки-2]
 +
 +
[https://disk.yandex.ru/i/bsf-Xesy6LP4Vg Листок 14. Порядки-3. Теоремы Мирского, Дилуорса и Шпернера]
 +
 +
[https://disk.yandex.ru/i/G_ia7Uo8N3q4Ag Листок 15. Вероятность-1]
 +
 +
[https://disk.yandex.ru/i/lfqTlx5X_6xpdg Листок 16. Вероятность-2]
 +
 +
[https://disk.yandex.ru/i/ZZ5uvyKFduSleA Листок 17. Вероятность-3]
 +
 +
[https://disk.yandex.ru/i/6LDFA_ZwAosEyA Листок 18. Производящие функции-1]
 +
 +
[https://disk.yandex.ru/i/DhZjy2TbAFMyng Листок 19. Производящие функции-2]
 +
 +
[https://disk.yandex.ru/i/j1F9qMM801NhOQ Листок 20. Производящие функции-3]
 +
 +
[https://disk.yandex.ru/i/XTqyNIsvu1TT7Q Листок 21. Комбинаторные игры]
 +
 +
[https://disk.yandex.ru/d/7ePOYmE4TE2Xkg Листок 22. Разрешающие деревья]
 +
 +
[https://disk.yandex.ru/i/Qt05XnNuyC42PA Листок 23. Булевы схемы]
 +
 +
[https://disk.yandex.ru/i/aPxAwmTWIt3D8Q Листок 24. Булевы формулы и выполнимость]
  
 
== Записи лекций ==
 
== Записи лекций ==
Строка 78: Строка 402:
 
Видеозаписи регулярных лекций появляются здесь (файлы названы датой лекции):  https://disk.yandex.ru/d/hGokInUkIXXHsQ
 
Видеозаписи регулярных лекций появляются здесь (файлы названы датой лекции):  https://disk.yandex.ru/d/hGokInUkIXXHsQ
  
−
[https://disk.yandex.ru/d/zPdPHseA4XS68Q Лекция по базовой комбинаторике] (прошу посмотреть до '''18.09'''): 5 коротких файлов LEC 01 - PART 01, LEC 01 - PART 02, LEC 01 - PART 03, LEC 01 - PART 04, LEC 01 - PART 05.
+
Запись лекции от 6.10.23 (не попала в папку выше): https://disk.yandex.ru/i/2py47yuQfftudg
 +
 
 +
_________________________________
 +
 
 +
Две записанные онлайн-лекции расположены по ссылке: https://disk.yandex.ru/d/GqWnpqpGinYVSg
 +
 
 +
папка LEC 01 - лекция по базовой комбинаторике (прошу посмотреть до '''18.09''');
 +
 
 +
папка LEC 02 - лекция по базовым понятиям и фактам теории неориентированных графов (прошу посмотреть до '''07.11''')
 +
 
 +
==Варианты зимних экзаменов прошлых лет==
 +
 
 +
[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]
 +
 
 +
==Варианты итоговых экзаменов прошлых лет==
 +
 
 +
[https://disk.yandex.ru/i/duzjcVjaw7D8WQ Экзамен весна 2023]
 +
 
 +
[https://disk.yandex.ru/i/Y2RoEjbrOcz0mg Экзамен весна 2022]
 +
 
 +
[https://www.dropbox.com/s/zsjpn8igyadpmn2/exam210330_pilot.pdf?dl=0 Экзамен весна 2021]
  
 +
[https://www.dropbox.com/s/82vrlr9af0j3aye/exam200615_pilot.pdf?dl=0 Экзамен весна-лето 2020]
  
 
== Литература ==
 
== Литература ==
Строка 90: Строка 439:
 
# Ландо С. К. Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144 с.
 
# Ландо С. К. Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144 с.
 
# А. Ромащенко, А. Румянцев, А. Шень. Заметки по теории кодирования. — 2-е изд., испр. и доп. — М.: МЦНМО, 2017. — 88 с. URL: https://users.mccme.ru/anromash/courses/coding-theory-2017.pdf
 
# А. Ромащенко, А. Румянцев, А. Шень. Заметки по теории кодирования. — 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

Текущая версия на 11:40, 29 марта 2024

ОБЪЯВЛЕНИЯ

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

___________________

Показ работ экзамена состоится в пятницу 29 марта, в 14:30, аудитория R305.

___________________

25 марта в 13:00 состоится итоговый письменный экзамен по курсу. Длительность - 130 минут, на нем будет 6 задач по темам, покрывающим материал 2-3 модулей (до лекции 25 включительно). Пользоваться можно любыми бумажными материалами, и никакими электронными! Допускается использование стандартного калькулятора.

Распределение групп по аудиториям:

группы 231 и 235: аудитория R401

группы 233 и 234: аудитория R201

группа 232: аудитория R406

___________________

Лекция 19.03 отменяется.

___________________

Второй коллоквиум пройдет 16 марта. Программа и правила коллоквиума приложены ниже. Расписание по группам:

Группа 232: 10:00, аудитория R404

Группа 235: 11:20, аудитория R404

Группа 234: 14:00, аудитория R401

Группа 233: 15:00, аудитория R401

Группа 231: 16:00, аудитория R401

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

___________________

Зимний (промежуточный) экзамен состоится 27 декабря, начало в 11:00! Длительность экзамена – 130 минут.

Не опаздывайте!

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

На экзамене будет 6 задач по темам первых 14 лекций курса и двух онлайн-лекций.

Распределение по аудиториям:

группы 231 и 234: аудитория R401

группы 232 и 235: аудитория R201

группа 233: аудитория R406

___________________


Первый коллоквиум пройдет 25 ноября. Программа и правила коллоквиума приложены ниже. Расписание коллоквиума по группам:

подгруппа 231-1: 11:10, аудитория K418

подгруппа 231-2: 12:40, аудитория R401

группа 234: 12:40, аудитория R401

группа 233: 15:20, аудитория R401

группа 235: 15:40, аудитория R401

группа 232: 17:30, аудитория R401

___________________

7 ноября, 16:20-17:40, состоится контрольная работа по материалам лекций и семинаров 1 модуля. В контрольной будет 5 задач на следующие темы:

- Индукция

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

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

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

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

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

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

Распределение групп по аудиториям:

R201 - группы 231, 232 и 234-1, 

R503 - группы 235 и 234-2, 

R504 - группа 233.

Пожалуйста, не опаздывайте: в 16:20 мы раздадим всем условия задач и начнем отсчет времени (длительность работы – 80 минут).

Лабораторные работы

Лабораторная работа 2 (3 модуль)

Лабораторная работа состоит из двух частей: контеста и ноутбука. На выполнение работы дается чуть меньше трех недель. 

Дедлайн и по контесту, и по ноутбуку: 9 марта 23:59.

Контест состоит из четырех задач и сдается на платформе Codeforces. Оцениваются только задачи, которые прошли все тесты в тестирующей системе.

Ноутбук содержит 3 задачи, которые надо решать на языке Python. Инструкция по работе с Jupyter Notebook и сам ноутбук находятся в Google Classroom по ссылке ниже. Решения сдаются туда же.

Разбалловка задач указана в ноутбуке и контесте в условиях. Баллы за все задачи суммируются, сумма баллов является оценкой за ЛР-2. Максимальная возможная оценка — 12.

По любым вопросам по лабораторной работе стоит писать ответственному ассистенту Роману Гундарину.

Ссылка на классрум

Ссылка на контест

Лабораторная работа 1 (2 модуль)

Лабораторная работа состоит из двух частей: контеста с алгоритмическими задачами и ноутбука по библиотеке NetworkX, которые оцениваются по отдельности. На выполнение работы дается чуть меньше трех недель. 

Дедлайн и по контесту, и по ноутбуку: 6 декабря 23:59.

Контест состоит из пяти задач и сдается на платформе Codeforces. Оцениваются только задачи, которые прошли все тесты в тестирующей системе. Первые четыре задачи оцениваются в 2 балла. За пятую задачу можно получить от 2 до 4 баллов. Таким образом, максимальный возможный балл за контест — 12.

Ноутбук содержит 4 задачи, которые надо решать на языке Python, правила оценивания которых написаны в самом ноутбуке. Инструкция по работе с Jupyter Notebook и сам ноутбук находятся в в Google Classroom по ссылке ниже. Решения сдаются туда же. За эту часть лабораторной работы можно так же получить до 12 баллов.

Оценка за лабораторную работу вычисляется по формуле: ЛАБ-1 = sqrt((НОУТБУК^0.5) * (КОНТЕСТ^1.5)). Максимальная возможная оценка за лабораторную работу равна 12.

По любым вопросам по лабораторной работе стоит писать ответственному ассистенту Роману Гундарину. В частности, если вы не знаете язык Python, то можно запросить консультацию.

Ссылка на классрум

Ссылка на контест

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

Итоговый экзамен (25.03, понедельник)

Решения задач итогового экзамена

Программа и правила проведения весеннего коллоквиума 2024 года (16.04, суббота)

Программа и правила проведения весеннего коллоквиума.

Промежуточный экзамен (27.12, среда)

Решения задач промежуточного экзамена

Программа и правила проведения зимнего коллоквиума 2023 года (25.11, суббота)

Программа и правила проведения зимнего коллоквиума.

Контрольная работа (07.11, вторник)

Условия задач контрольной работы.

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

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

Лекции: Артём Максимович Максаев

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

Группа Преподаватель Консультационные часы преподавателя Учебный ассистент, отвечающий за группу
231 Артём Максимович Максаев пятница 14:40-16:00, T909 (предварительно предупредить) Максим Калинку
232 Михаил Викторович Игнатьев понедельник 18:10, вторник 16:20 по нечётным неделям, четверг 19:40 по нечётным неделям, S812 Глеб Хитрин
233 Павел Павлович Соколов вторник 11:10-12:30, пятница 11:10-12:30 и 14:40-17:40, S805 (предварительно предупредить) Данила Биктимиров
234 Валентин Валерьевич Промыслов пятница 16:20-17:40, T909 (предварительно предупредить) Алина Шипова
235 Роман Олегович Стасенко суббота 13:30-15:00 (онлайн) Данил Смирнов

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

Артём Парфёнов

Артём Потарусов

Алексей Воронко

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

Роман Гундарин

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

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

Результаты

231 группа ПМИ 232 группа ПМИ 233 группа ПМИ 234 группа ПМИ 235 группа ПМИ

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

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

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

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

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

Литература: [1, §5.1-5.2, лекция 6]

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

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

Лекция 3. Утверждение о композиции биекций. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности, количество булевых функций от n переменных. Правила алгебры логики, доказательство теоретико-множественных тождеств с помощью алгебры логики. Эквивалентность принципа математической индукции, принципа полной индукции и принципа наименьшего числа.

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

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

Литература: [1, §5.5], [3, глава 1, §1-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); (0, 1); множества всех подмножеств натуральных чисел. Мощность континуум. Равномощность отрезка и квадрата. Сравнение мощностей, его свойства. Утверждение о том, что счетная мощность меньше континуальной. Теорема Кантора о сравнении мощности множества и мощности множества всех его подмножеств. Теорема Кантора-Бернштейна.

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

Лекция 8. Бинарные отношения, теорема об ассоциативности композиции отношений. Отношение эквивалентности, теорема о разбиении множества с отношением эквивалентности на классы, состоящие из попарно эквивалентных элементов. Ориентированные графы: основные понятия. Лемма о числе ребер в ориентированном графе. Сильная связность орграфа, компоненты сильной связности. Ациклические орграфы, топологическая сортировка.

Литература: [1, §3.3]

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

Литература: [1, §3.1-3.2]

Лекция 9. Эйлеровы циклы в ориентированных и неориентированных графах. Критерий существования эйлерова цикла. Двудольные графы, критерий двудольности графа. Булев куб как граф, его 2-раскрашиваемость. Раскраски графов, хроматическое число графа. Клики и независимые множества в графе. Свойства хроматического числа. Верхняя оценка на хроматическое число через максимальную из степеней вершин графа. Теорема Брукса (без доказательства).

Литература: [1, §3.4-3.5]

Лекция 10. Хроматический многочлен, его вычисление для полного графа, его дополнения и дерева. Лемма о связи хроматического многочлена графа, графа с удаленным ребром и стянутым ребром. Теорема Уитни о свойствах хроматического многочлена. Паросочетание в графе. Теорема Холла. Вершинные покрытия. Утверждение о связи максимального размера паросочетания и минимального размера вершинного покрытия в произвольном графе. Теорема Кёнига (формулировка).

Литература: [1, §1.11, §3.5.4]

Лекция 11. Чередующийся и увеличивающий пути относительно паросочетания. Отсутствие увеличивающего пути относительно максимального паросочетания. Теорема Кёнига (доказательство). Клики и независимые множества. Теорема Рамсея. Верхняя оценка на числа Рамсея. Мыцельскиан графа.

Литература: [8, теорема 2.1.1], [1, §3.6]

Лекция 12. Пример Зыкова–Мыцельского графа без треугольников со сколь угодно большим хроматическим числом. Частично упорядоченные множества: строгий и нестрогий частичные порядки, примеры, линейный порядок. Утверждение о связи строгого и нестрогого порядков. Операции с частично упорядоченными множествами: покоординатный порядок, лексикографический порядок, сумма порядков. Изоморфизм порядков, примеры. Минимальные (максимальные) и наименьшие (наибольшие) элементы, отрезки. Замечание о единственности наименьшего элемента, пример частично упорядоченного множества с бесконечным числом минимальных элементов. Утверждение о том, что при изоморфизме порядков отрезок переходит в отрезок. Следствие о том, что натуральные, целые и рациональные числа попарно неизоморфны как линейные порядки.

Литература: [1, §9.1-9.4], [2, §2.1-2.2]

Лекция 13. Теорема об изоморфизме счётных плотных линейных порядков без наименьшего и наибольшего элемента. Напоминание: минимальные (максимальные) и наименьшие (наибольшие) элементы, их свойства, примеры. Принцип индукции для частично упорядоченных множеств. Фундированные множества, теорема об эквивалентности трех определений фундированного множества. Цепи и антицепи в частично упорядоченных множествах, примеры. Формулировки теорем Мирского и Дилуорса.

Литература: [1, §9.5-9.6], [2, §2.2-2.3]

Лекция 14. Разбиение частично упорядоченных множеств на цепи/антицепи. Теорема Мирского о том, что размер максимальной цепи в ч.у.м. равен минимальному числу антицепей, образующих разбиение этого множества. Теорема Дилуорса. Утверждение о размере максимальной цепи в булевом кубе. LYM-неравенство. Теорема Шпернера о размере максимальной антицепи в булевом кубе.

Литература: [1, §9.7]

Лекция 15. Вероятностное пространство, вероятностное распределение, примеры. Свойства вероятности. Пошаговое задание распределения, дерево событий. Оценка объединения. Вероятностный метод: нижняя оценка для чисел Рамсея.

Литература: [1, §10.1-10.3]

Лекция 16. Формула включений-исключений для вероятностей. Задача о беспорядках. Условная вероятность, примеры ее подсчета. Теорема умножения, формулы Байеса и полной вероятности. Примеры с тестом на выявление болезни. Независимые события. Независимость событий в совокупности, отличие от попарной независимости событий.

Литература: [1, §10.2,10.4]

Лекция 17. Случайная величина, математическое ожидание, линейность матожидания. Задача о днях рождения. Нервенство Маркова, пример применения. Дисперсия. Неравенство Чебышёва. Независимые случайные величины. Математическое ожидание и дисперсия независимых случайных величин.

Литература: [1, §10.5]

Лекция 18. Общая формулировка вероятностного метода, пример применения для поиска разреза в графе величины не менее половины числа ребер. Пример применения вероятностного метода для поиска разреза величины более половины числа ребер для графа с четным числом вершин. Теорема Эрдёша о существовании графа со сколь угодно большим хроматическим числом и сколь угодно большим обхватом.

Литература: [1, §10.5]

Лекция 19. Вероятность выпадения ровно половины орлов при бросании честной монеты. Производящие функции, определение. Их сложение и умножение на скаляр. Произведение производящих функций, основные свойства арифметических операций. Обратимые производящие функции, примеры. Формальное дифференцирование производящих функций, свойства производной, правило Лейбница. Подстановка нуля в производящую функцию, вычисление n-го коффициента производящей функции с использованием производных. Пример применения производящих функций: вывод формулы для суммы квадратов первых n натуральных чисел.

Литература: [1, §10.6], [6, глава 1]

Лекция 20. Завершение вывода формулы для суммы квадратов первых n натуральных чисел. Бином Ньютона, обобщение на целые показатели. Пример получения тождества с помощью производящих функций. Связь произведения производящих функций с неупорядоченными выборками, примеры. Линейные рекуррентные соотношения с постоянными коэффициентами. Теорема о том, что производящая функция последовательности, удовлетворяющей линейному рекуррентному соотношению с постоянными коэффициентами, рациональна. Явная формула для общего члена последовательности, метод ее вывода. Числа Фибоначчи: их производящая функция и вывод явной формулы (формула Бине).

Литература: [6, глава 2]

Лекция 21. Правильные скобочные последовательности. Критерий того, что скобочная последовательность является правильной. Рекуррентная формула для числа правильных скобочных последовательностей. Числа Каталана, их производящая функция и ее вывод как решения квадратного уравнения. Вывод явной формулы для чисел Каталана с использованием техники производящих функций. Явная проверка того, что полученные числа удовлетворяют рекуррентному соотношению для чисел Каталана.

Литература: [1, §2.10.1, §2.10.2, §2.10.4, §2.10.6], [6, §2.5]

Лекция 22. Комбинаторные игры с полной информацией. Задание игры в виде ориентированного графа. Партии и стратегии. Стратегии, гарантирующие выигрыш. Цена игры. Теорема о цене игры. Беспристрастные игры, N- и P-позиции. Анализ игры с конца, примеры. Игра ним, ее P-позиции.

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

Лекция 23. Задача об угадывании числа, ее сложность в адаптивном и неадаптивном случае. Модель разрешающих деревьев. Адаптивный и неадаптивный протоколы, сведение адаптивного протокола к неадаптивному. Задача о сортировке, оценки на сложность адаптивного протокола. Задача о взвешиваниях: поиск самой тяжелой монеты, сложность в адаптивном и неадаптивном случае. Метод противника. Сложность булевой функции. Сложность булевой функции CONN, определяющей связность неориентированного графа на n вершинах.

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

Лекция 24. Булевы схемы, определение. Задание схемы в виде ациклического ориентированного графа. Схемы-графы для функции XOR и функции голосования. Схема линейного размера для сложения двоичных чисел. Глубина булевой схемы. Построение схемы для функции CONN, определяющей связность неориентированного графа на n вершинах (два варианта для размера и глубины). Возведение булевой матрицы в степень, связь с числом путей в графе. Вычисление произвольной булевой функции от n переменных схемой размера O(n 2^n). Существование функций с экспоненциальной схемной сложностью.

Литература: [1, §13.1]

Лекция 25. Существование функций с экспоненциальной схемной сложностью. Верхняя и нижняя оценки для схемной сложности функции XOR. Формулы как частный случай схем. Существование формулы, эквивалентной данной булевой схеме, той же глубины и экспоненциального размера. Теорема о балансировке булевых формул (без доказательства). Задачи выполнимости булевой схемы, КНФ и 3-КНФ. Эффективное сведение задачи выполнимости булевой схемы к задаче выполнимости 3-КНФ.

Литература: [1, §13]; доказательство теоремы о балансировке булевых формул можно прочесть в §13.2

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

Листок 1. Математическая индукция

Листок 2. Множества и функции

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

Листок 4. Булевы функции

Листок 5. Замкнутые классы, критерий Поста

Листок 6. Мощность множеств-1

Листок 7. Мощность множеств-2

Листок 8. Отношения и ориентированные графы

Листок 9. Неориентированные графы

Листок 10. Хроматический многочлен графа, теорема Холла

Листок 11. Теоремы Кёнига и Рамсея, графы с большим хроматическим числом

Листок 12. Порядки-1

Листок 13. Порядки-2

Листок 14. Порядки-3. Теоремы Мирского, Дилуорса и Шпернера

Листок 15. Вероятность-1

Листок 16. Вероятность-2

Листок 17. Вероятность-3

Листок 18. Производящие функции-1

Листок 19. Производящие функции-2

Листок 20. Производящие функции-3

Листок 21. Комбинаторные игры

Листок 22. Разрешающие деревья

Листок 23. Булевы схемы

Листок 24. Булевы формулы и выполнимость

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

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

Запись лекции от 6.10.23 (не попала в папку выше): https://disk.yandex.ru/i/2py47yuQfftudg

_________________________________

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

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

папка LEC 02 - лекция по базовым понятиям и фактам теории неориентированных графов (прошу посмотреть до 07.11)

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

Экзамен зима 2022

Экзамен зима 2021

Экзамен зима 2020

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

Экзамен весна 2023

Экзамен весна 2022

Экзамен весна 2021

Экзамен весна-лето 2020

Литература

  1. М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. Черновик этого учебника. В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ).
  2. Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
  3. Яблонский С. В. Введение в дискретную математику. 4-е издание, стереотипное - М.: Высшая школа, 2003. - 484 с.
  4. 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
  5. Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: https://znanium.com/catalog/document?id=343807
  6. Ландо С. К. Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144 с.
  7. А. Ромащенко, А. Румянцев, А. Шень. Заметки по теории кодирования. — 2-е изд., испр. и доп. — М.: МЦНМО, 2017. — 88 с. URL: https://users.mccme.ru/anromash/courses/coding-theory-2017.pdf
  8. Р. Дистель, "Теория графов", второе издание, 2002, Springer, Graduate Texts in Mathematics, 173 https://books.google.ru/books?id=pZm8AAAAQBAJ&hl=ru&source=gbs_navlinks_s
Источник — «http://wiki.cs.hse.ru/index.php?title=Дискретная_математика_на_ПМИ_2023/24_(пилотный_поток)&oldid=84393»