Комбинаторика и теория графов 2026/2027: различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Строка 38: Строка 38:




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


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

Версия от 13:38, 6 сентября 2026

ОБЪЯВЛЕНИЯ

Группа курса


Общая информация о курсе Комбинаторика и теория графов, М++, 1 курс

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

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

Семинарист: Иван Сергеевич Бельдиев

Ассистенты: Пётр Крамарский, Михаил Далингер, Андрей Кандрашкин

Таблица оценок

Ведомость

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

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

Экзамен — это письменная работа. Пересдача проводится по правилам экзамена. Комиссия проводится по тем же правилам в письменном формате (передаётся только экзамен, формула учитывает накопленную за курс оценку по остальным элементам контроля).

Оценка за курс

Итоговая оценка = Округление(0.25 * ДЗ + 0.35 * КОЛЛ + 0.4 * ЭКЗ)

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

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

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

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


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

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

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

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

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

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

На курсе есть две предзаписанные онлайн-лекции:

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

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

Литература

  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 https://archive.org/details/discretemathemat0000lova/page/n9/mode/2up
  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
Источник — https://wiki.cs.hse.ru/index.php?title=Комбинаторика_и_теория_графов_2026/2027&oldid=97227