Дискретный анализ — 2

Дата публикации

14 сентября 2026

Паспорт

  • Где и когда. IV семестр программы 01.03.02 «Прикладная математика и информатика», профиль «Математика», набор 2025. Это второй семестр единого годового курса «Дискретный анализ».
  • Объём. 135 часов, 3 з.е.: 60 аудиторных часов (30 лекций и 30 семинаров), 45 часов самостоятельной работы и 30 часов на подготовку и сдачу экзамена.
  • Кафедра. Кафедра дискретной математики.
  • Преподаватель. В доступной программе 2022/23 указаны д. ф.-м. н. А. М. Райгородский и к. э. н. Д. Г. Ильинский. Это данные исторической программы, не подтверждение текущего распределения групп.
  • Итоговый контроль. Экзамен в IV семестре по учебному плану набора 2025.

Содержание опубликованной программы

Кафедра публикует весеннюю программу «Дискретный анализ» 2022/23, но не называет её «— 2». Ниже дан полный тематический список этого документа; он относится к историческому варианту курса и не выдается за программу 2025.

  1. Оценки факториалов и биномиальных коэффициентов.
  2. Графы, орграфы, мультиграфы и псевдографы; деревья, формула Кэли и унициклические графы.
  3. Маршруты, цепи и циклы; эйлеровы графы и орграфы.
  4. Гамильтоновы пути и циклы, условие Дирака, связность и число независимости.
  5. Последовательности и графы де Брёйна.
  6. Плоские и планарные графы, формула Эйлера.
  7. Случайные графы и их связность.
  8. Хроматическое, кликовое числа и число независимости; теоремы Боллобаша.
  9. Жадное построение независимого множества и теорема Эрдёша о большом обхвате и хроматическом числе.
  10. Гиперграфы, теорема Эрдёша—Ко—Радо и граф пересечений.
  11. Величина \(m(n,k,t)\) и теорема Франкла—Уилсона.
  12. Хроматическое число пространства и его нижняя оценка.
  13. Независимые множества, клики и теорема Турана.
  14. Граф Кнезера и теорема Ловаса.
  15. Теория Рамсея, вероятностный метод, локальная лемма Ловаса и оценка Франкла—Уилсона.
  16. Многоцветные и двудольные числа Рамсея.
  17. Системы общих представителей и жадная верхняя оценка.
  18. Системы общих представителей в геометрии, размерность Вапника—Червоненкиса, \(\varepsilon\)-сети и приложения в статистике.
  19. Хроматическое число гиперграфа и задача о минимальном числе рёбер.
  20. Проблема Борсука.

Литература в программе 2022/23

Н. Алон и Дж. Спенсер, Вероятностный метод; Р. Грэхэм, Начала теории Рамсея; А. М. Райгородский, Линейно-алгебраический метод в комбинаторике и Модели случайных графов и их применения; А. М. Райгородский, Системы общих представителей в комбинаторике и их приложения в геометрии; Ф. Харари, Теория графов; S. Jukna, Extremal Combinatorics With Applications in Computer Science; B. Bollobás, Random Graphs; А. А. Глибичук, А. Б. Дайняк, Д. Г. Ильинский и др., Элементы дискретной математики в задачах.

Оценивание

Действующая открытая БРС для данного варианта курса не найдена.

Источники и актуальность

Весенняя программа 2022/23, страница курса кафедры, план 01.03.02, набор 2025.