Дискретная математика на ПМИ 2022/23 (пилотный поток) — различия между версиями
Amaksaev (обсуждение | вклад) |
Amaksaev (обсуждение | вклад) |
||
| Строка 97: | Строка 97: | ||
'''Лекция 4'''. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности. Правила алгебры логики, доказательство теоретико-множественных тождеств с помощью алгебры логики. Формулы, полные системы связок. Полнота системы связок «конъюнкция, дизъюнкция, отрицание». Дизъюнктивная нормальная форма, СДНФ. Полнота системы связок «XOR, конъюнкция, 1». | '''Лекция 4'''. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности. Правила алгебры логики, доказательство теоретико-множественных тождеств с помощью алгебры логики. Формулы, полные системы связок. Полнота системы связок «конъюнкция, дизъюнкция, отрицание». Дизъюнктивная нормальная форма, СДНФ. Полнота системы связок «XOR, конъюнкция, 1». | ||
| − | ''Литература: [1, §2.9, §5.3-5.5]'' | + | ''Литература: [1, §2.9, §5.3-5.5], [3, глава 1, §1-4]'' |
'''Лекция 5'''. Теорема о представлении булевой функции полиномом Жегалкина (существование и единственность). Класс линейных функций, лемма о нелинейной функции. Принцип двойственности, класс самодвойственных функций, лемма о несамодвойственной функции. Классы функций, сохраняющих константу. Класс монотонных функций, лемма о немонотонной функции. Критерий Поста полноты системы булевых функций. | '''Лекция 5'''. Теорема о представлении булевой функции полиномом Жегалкина (существование и единственность). Класс линейных функций, лемма о нелинейной функции. Принцип двойственности, класс самодвойственных функций, лемма о несамодвойственной функции. Классы функций, сохраняющих константу. Класс монотонных функций, лемма о немонотонной функции. Критерий Поста полноты системы булевых функций. | ||
| + | |||
| + | ''Литература: [3, глава 1, §5-6]'' | ||
'''Лекция 6'''. Описание предполных классов булевых функций. Формула включений-исключений. Счетные множества, счётность целых и рациональных чисел. Объединение и декартово произведение счетных множеств. Лемма о том, что добавление счетного множества не меняет мощности. | '''Лекция 6'''. Описание предполных классов булевых функций. Формула включений-исключений. Счетные множества, счётность целых и рациональных чисел. Объединение и декартово произведение счетных множеств. Лемма о том, что добавление счетного множества не меняет мощности. | ||
| − | ''Литература: [1, §5.6, §8.1-8.2], [2, §1.2-1.4]'' | + | ''Литература: [3, глава 1, §6], [1, §5.6, §8.1-8.2], [2, §1.2-1.4]'' |
'''Лекция 7'''. Равномощность множеств: бесконечных последовательностей из 0 и 1; вещественных чисел; [0, 1]; [0, 1); множества всех подмножеств натуральных чисел. Мощность континуум. Несчетность множества бесконечных последовательностей из 0 и 1. Сравнение мощностей, теорема Кантора. Теорема Кантора-Бернштейна. | '''Лекция 7'''. Равномощность множеств: бесконечных последовательностей из 0 и 1; вещественных чисел; [0, 1]; [0, 1); множества всех подмножеств натуральных чисел. Мощность континуум. Несчетность множества бесконечных последовательностей из 0 и 1. Сравнение мощностей, теорема Кантора. Теорема Кантора-Бернштейна. | ||
Версия 20:06, 27 ноября 2022
Содержание
ОБЪЯВЛЕНИЯ
Первый коллоквиум пройдет 10 декабря, 9:00-18:00! Программа и регламент коллоквиума выложены ниже.
Зимний (промежуточный) экзамен состоится 23 декабря, 9:00-11:00!
Контрольные мероприятия
Программа и правила проведения зимнего коллоквиума 2022 года (10.12, суббота)
Программа и правила проведения зимнего коллоквиума.
По умолчанию предполагается, что коллоквиум для всех студентов пилотного потока будет проводиться в аудитории R401. Для групп, начинающих сдачу коллоквиума в 14:40 и позднее, возможен перенос в другую аудиторию.
Коллоквиум состоится 10 декабря с 9:00 до 18:00. Студенты из разных групп (и подгрупп) приглашаются на разное время согласно расписанию. Приходите вовремя: сдавать с другой (под)группой не разрешается!
Группы 221ПМИ, 225ПМИ: в 9:00.
Подгруппа 224-1ПМИ: в 11:15.
Подгруппа 224-2ПМИ: в 12:00.
Группа 223ПМИ: в 14:40.
Подгруппа 222-1ПМИ в 15:40.
Подгруппа 222-2ПМИ: в 16:20.
Общая информация о курсе Дискретная математика, пилотный поток, 1 курс
Преподаватели и ассистенты
Лекции: Артём Максимович Максаев
Распределение по группам
| Группа | Преподаватель | Консультационные часы преподавателя | Учебный ассистент, отвечающий за группу |
|---|---|---|---|
| 221 | Артём Максимович Максаев | пн 13:00-18:00 (по предварительной договоренности), S909 | Артём Мацкевич |
| 222 | Любовь Николаевна Сысоева | пн 13:30-14:30, вт 17:40-18:40 (по предварительной договоренности) | Игорь Паншин |
| 223 | Любовь Николаевна Сысоева | пн 13:30-14:30, вт 17:40-18:40 (по предварительной договоренности) | Марина Романова |
| 224 | Валентин Валерьевич Промыслов | вт 14:30-18:00, пт 9:00-14:00 (по предварительной договоренности), S909 | Анна Оверчук |
| 225 | Никита Сергеевич Лукьяненко | вт 19:50-21:10 (по предварительной договоренности) | Леонид Черепанов |
Остальные ассистенты (проверяют домашние задания в разных группах):
Дарья Чубарова
Иван Скворцов
Диана Казбекова
Правила оценивания
Вес коллоквиумов в итоговой оценке 30%, промежуточного экзамена 15%, итогового 30%, домашних заданий 25%.
Промежуточная оценка выставляется по фактически проведенным в 1-2 модулях контрольным мероприятиям с весами: коллоквиум 30%, промежуточный экзамен 40%, домашние задания 30%. В промежуточной оценке учитываются те домашние задания, которые будут проверены в первом семестре.
Домашние задания выдаются еженедельно и сдаются перед следующим семинаром (в некоторых группах - перед следующей лекцией). Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания.
Экзамен — это письменная работа. Пересдача проводится по правилам экзамена. Комиссия проводится в устном формате без учета накопленной оценки.
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, между 6 и 8 округление вверх, а между 8 и 10 округление арифметическое. Т.е. 3,92 округляется до 3; 5,48 - до 5; 5,54 - до 6; 7,12 - до 8; 9,4 - до 9.
Результаты
| 221 группа | 222 группа | 223 группа | 224 группа | 225 группа |
|---|
Программа курса
Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.
Лекция 1. Метод математической индукции. Примеры задач. Усиление утверждения. Принцип полной индукции. Эквивалентность принципа математической индукции, принципа полной индукции и принципа наименьшего числа.
Литература: [1, лекция 1]
Лекция 2. Операции со множествами. Парадокс Рассела. Доказательство теоретико-множественных тождеств. Декартово произведение множеств. Бинарные отношения, теорема об ассоциативности композиции отношений. Функции. Инъекции, сюръекции, биекции. Обратная функция, критерий обратимости функции. Утверждение о композиции биекций.
Литература: [1, §5.1-5.2, лекция 6, лекция 7]
Лекция 3. Отношение эквивалентности, теорема о разбиении множества с отношением эквивалентности на классы, состоящие из попарно эквивалентных элементов. Правило суммы, задача о числе путей. Число элементов в объединении двух множеств. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Сочетания с повторениями.
Литература: [1, §7.5, лекция 2]
Лекция 4. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности. Правила алгебры логики, доказательство теоретико-множественных тождеств с помощью алгебры логики. Формулы, полные системы связок. Полнота системы связок «конъюнкция, дизъюнкция, отрицание». Дизъюнктивная нормальная форма, СДНФ. Полнота системы связок «XOR, конъюнкция, 1».
Литература: [1, §2.9, §5.3-5.5], [3, глава 1, §1-4]
Лекция 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]
Лекция 8. Равномощность отрезка и квадрата. Частично упорядоченные множества: строгий и нестрогий частичные порядки, их связь, линейный порядок. Операции с частично упорядоченными множествами: сумма порядков, покоординатный порядок, лексикографический порядок. Изоморфизм порядков, примеры. Минимальные (максимальные) и наименьшие (наибольшие) элементы, отрезки. Фундированные множества, принцип индукции.
Литература: [1, лекция 9], [2, §2.1-2.4]
Лекция 9. Изоморфизм конечных линейных порядков одинаковой мощности. Теорема о том, что счетный линейный порядок изоморфен подмножеству рациональных чисел. Цепи и антицепи в частично упорядоченных множествах. Теорема о том, что размер максимальной цепи равен минимальному числу антицепей, образующих разбиение множества. Теорема Дилуорса.
Литература: [1, §9.5, §9.7], [2, §2.2]
Лекция 10. LYM-лемма, теорема Шпернера о размере максимальной антицепи в булевом кубе. Графы, основные понятия (степень вершины, путь, цикл, простой путь, простой цикл). Лемма о рукопожатиях. Связность графа, компоненты связности. Неравенство, связывающее число вершин, ребер и компонент связности в графе. Деревья.
Литература: [1, §3.1-3.2]
Лекция 11. Теорема об эквивалентных определениях дерева. Полное двоичное дерево. Остовное дерево в графе. Ориентированные графы: основные понятия. Лемма о числе ребер в ориентированном графе. Сильная связность орграфа, компоненты сильной связности. Ациклические орграфы, топологическая сортировка. Эйлеровы циклы в ориентированных и неориентированных графах. Критерий существования эйлерова цикла. Двудольные графы, критерий двудольности графа.
Литература: [1, §3.3-3.5]
Материалы курса
Литература
- М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. Черновик этого учебника. В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ).
- Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
- Яблонский С. В. Введение в дискретную математику. 4-е издание, стереотипное - М.: Высшая школа, 2003. - 484 с.
- Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
- Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: https://znanium.com/catalog/document?id=343807
