Просмотр исходного текста страницы Дискретная математика на ПМИ 2022/23 (пилотный поток)

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

Первый коллоквиум пройдет '''10 декабря''', 9:00-18:00! Программа и регламент коллоквиума выложены ниже.

Зимний (промежуточный) экзамен состоится '''23 декабря''', 9:00-11:00!

== Контрольные мероприятия ==
=== Программа и правила проведения зимнего коллоквиума 2022 года (10.12, суббота) ===
[https://drive.google.com/file/d/1L8T8YjAk1ath-bAOckv4fLSrsU7NiDRS/view?usp=share_link Программа и правила проведения зимнего коллоквиума].

По умолчанию предполагается, что коллоквиум для всех студентов пилотного потока будет проводиться в аудитории 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 курс==

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

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

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

{| class="wikitable" style="text-align:center"
|-
! Группа !!  Преподаватель !! Учебный ассистент, отвечающий за группу
|-
|| 221 || [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев] ||   Артём Мацкевич 
|-
|| 222 || [https://www.hse.ru/staff/lsysoeva Любовь Николаевна Сысоева]  ||  Игорь Паншин 
|-
|| 223 || [https://www.hse.ru/staff/lsysoeva Любовь Николаевна Сысоева] ||  Марина Романова 
|-
|| 224 || Валентин Валерьевич Промыслов ||  Анна Оверчук
|-
|| 225 || [https://www.hse.ru/org/persons/225553845 Никита Сергеевич Лукьяненко] ||   Леонид Черепанов
|}

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

Дарья Чубарова

Иван Скворцов

Диана Казбекова

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

Вес коллоквиумов в итоговой оценке 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.

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

{| class="wikitable" style="text-align:center"
|-
! '''[https://docs.google.com/spreadsheets/d/1Yp4s81Sbp9mWjCaZSM8pN-H7_MoXN50E209RyszARfQ/edit#gid=0 221 группа]''' 
! '''[https://docs.google.com/spreadsheets/d/1Yp4s81Sbp9mWjCaZSM8pN-H7_MoXN50E209RyszARfQ/edit#gid=225218895 222 группа]''' 
! '''[https://docs.google.com/spreadsheets/d/1Yp4s81Sbp9mWjCaZSM8pN-H7_MoXN50E209RyszARfQ/edit#gid=163786512 223 группа]''' 
! '''[https://docs.google.com/spreadsheets/d/1Yp4s81Sbp9mWjCaZSM8pN-H7_MoXN50E209RyszARfQ/edit#gid=1117335713 224 группа]''' 
! '''[https://docs.google.com/spreadsheets/d/1Yp4s81Sbp9mWjCaZSM8pN-H7_MoXN50E209RyszARfQ/edit#gid=1267756270 225 группа]''' 
|}

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

'''Лекция 1'''. Метод математической индукции. Примеры задач. Усиление утверждения. Принцип полной индукции. Эквивалентность принципа математической индукции, принципа полной индукции и принципа наименьшего числа.

'''Лекция 2'''. Операции со множествами. Парадокс Рассела. Доказательство теоретико-множественных тождеств. Декартово произведение множеств. Бинарные отношения, теорема об ассоциативности композиции отношений. Функции. Инъекции, сюръекции, биекции. Обратная функция, критерий обратимости функции. Утверждение о композиции биекций.

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

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

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

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

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

'''Лекция 8'''. Равномощность отрезка и квадрата. Частично упорядоченные множества: строгий и нестрогий частичные порядки, их связь, линейный порядок. Операции с частично упорядоченными множествами: сумма порядков, покоординатный порядок, лексикографический порядок. Изоморфизм порядков, примеры. Минимальные (максимальные) и наименьшие (наибольшие) элементы, отрезки. Фундированные множества, принцип индукции.

'''Лекция 9'''. Изоморфизм конечных линейных порядков одинаковой мощности. Теорема о том, что счетный линейный порядок изоморфен подмножеству рациональных чисел. Цепи и антицепи в частично упорядоченных множествах. Теорема о том, что размер максимальной цепи равен минимальному числу антицепей, образующих разбиение множества. Теорема Дилуорса.

'''Лекция 10'''. LYM-лемма, теорема Шпернера о размере максимальной антицепи в булевом кубе. Графы, основные понятия (степень вершины, путь, цикл, простой путь, простой цикл). Лемма о рукопожатиях. Связность графа, компоненты связности. Неравенство, связывающее число вершин, ребер и компонент связности в графе. Деревья.

'''Лекция 11'''. Теорема об эквивалентных определениях дерева. Полное двоичное дерево. Остовное дерево в графе. Ориентированные графы: основные понятия. Лемма о числе ребер в ориентированном графе. Сильная связность орграфа, компоненты сильной связности. Ациклические орграфы, топологическая сортировка. Эйлеровы циклы в ориентированных и неориентированных графах. Критерий существования эйлерова цикла. Двудольные графы, критерий двудольности графа.


== Материалы курса ==
[https://disk.yandex.ru/i/z5rw0zQEZCsPbw Листок 1]

[https://disk.yandex.ru/i/9h76SMlpNg90HQ Листок 2]

[https://disk.yandex.ru/i/QA91CthMNoF4wQ Листок 3]

[https://disk.yandex.ru/i/6dDtSMfPZ_uauQ Листок 4]

[https://disk.yandex.ru/d/uNPvwk8VwKB16Q Листок 5]

[https://disk.yandex.ru/d/iTgIVJCGOc3UgQ Листок 6]

[https://disk.yandex.ru/i/eM177-okiP4CKQ Листок 7]

[https://disk.yandex.ru/d/JTs994uvwbI6CQ Листок 8]

[https://disk.yandex.ru/d/DD5YNpTAn-e1qw Листок 9]

[https://disk.yandex.ru/i/9d333AQWf-8Pug Листок 10]

[https://disk.yandex.ru/i/yBG4fI5zolaJHA Листок 11]


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

#  М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 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 
# 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