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

Паспорт

• Где и когда. III семестр программы 01.03.02 «Прикладная математика и информатика», профиль «Математика», набор 2025. В официальном плане дисциплина называется единым годовым курсом «Дискретный анализ».
• Объём. 90 часов, 2 з.е.: 60 аудиторных часов (30 лекций и 30 семинаров) и 30 часов самостоятельной работы.
• Кафедра. Кафедра дискретной математики.
• Преподаватель. В опубликованной осенней программе ФПМИ 2022 года преподаватель не назван. В старом варианте 2017/18 лектором был А. М. Райгородский; это историческая справка, а не данные текущего потока.
• Итоговый контроль. Форма промежуточной аттестации на III семестр уточняется по текущему плану и расписанию.

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

Название «Дискретный анализ — 1» — редакционное деление сайта; ниже помещён полный список основных (зачётных) вопросов из программы ФПМИ, осень 2022, для 2 курса ПМИ.Информатика. Документ отдельно содержит 16 вопросов «на отлично» — они также перечислены после основной программы.

1. Графы с петлями и кратными рёбрами, орграфы, лемма о рукопожатиях, пути, циклы и критерии эйлеровости.
2. Последовательности и графы де Брёйна; двоичный алфавит, подслова и правило «0 лучше 1».
3. Плоские и планарные графы, формула Эйлера, непланарные графы и критерий Понтрягина—Куратовского.
4. Гамильтоновы пути и циклы, достаточное условие Дирака.
5. Хроматическое число, число независимости и кликовое число, соотношения между ними.
6. Теорема Турана, асимптотика максимального числа рёбер без \(k\)-клик и её уточнение для дистанционного графа.
7. Оценки факториалов и биномиальных коэффициентов, формула Стирлинга и асимптотика центрального биномиального коэффициента.
8. Асимптотики \(\ln n!\) и \(\sqrt[n]{n!}\) без формулы Стирлинга.
9. Асимптотические оценки биномиальных и полиномиальных коэффициентов.
10. Асимптотика \(\binom nk\) при \(k^2=o(n)\) и при больших \(k\).
11. Случайные графы, неравенства Маркова и Чебышёва, случайное блуждание.
12. Связность случайного графа при \(p=c\ln n/n\), гигантская компонента.
13. Теоремы Боллобаша о хроматическом числе случайного графа и специальные режимы \(p\).
14. Сравнение оценок хроматического числа через кликовое число и число независимости.
15. Графы Кнезера, оценки хроматического и кликового чисел, независимые множества.
16. Теорема Ловаса о хроматическом числе графа Кнезера.
17. Гиперграфы пересечений и теорема Эрдёша—Ко—Радо.
18. Последующие обобщения: теоремы Франкла, Уилсона и Алсведе—Хачатряна.
19. Величина \(m(n,k,t)\), точное значение \(m(n,3,1)\) и линейно-алгебраическая оценка.
20. Оценка \(m(n,5,2)\) и её асимптотическая точность.
21. Теорема Франкла—Уилсона для \(m(n,k,k-p)\) при \(k<2p\).
22. Хроматическое число пространства и связь с дистанционными графами.

Вопросы «на отлично» в программе 2022

23. Точная формула и асимптотика числа унициклических графов.
24. Проблема изоморфизма графов и алгоритм, работающий почти на всех графах.
25. Связность случайного графа при \(p=c\ln n/n\), \(c>1\).
26. Отклонения липшицевых случайных величин и теорема Боллобаша при \(p=n^{-\alpha}\).
27. Другой вариант вывода теоремы Боллобаша при \(p=n^{-\alpha}\).
28. Отклонения по рёбрам и техническая оценка для теоремы Боллобаша при \(p=1/2\).
29. Полный вариант теоремы Боллобаша при \(p=1/2\).
30. Точность жадной раскраски случайного графа и теорема Кучеры.
31. Теорема Эрдёша о графе с большим обхватом и большим хроматическим числом.
32. Теорема Борсука—Улама—Люстерника—Шнирельмана и теорема Ловаса.
33. Частные случаи теоремы Борсука—Улама—Люстерника—Шнирельмана для замкнутых множеств.
34. Теорема Франкла—Уилсона при \(k\geq2p\).
35. Точность теорем Франкла—Уилсона, величина \(h(n,k,t)\), связь с кодированием и теорема Рёдля.
36. Экспоненциальная нижняя оценка хроматического числа пространства.
37. Проблема Борсука на прямой и плоскости.
38. Экспоненциальная нижняя оценка числа Борсука.

Оценивание

В программе осени 2022 опубликованы правила зачёта — это историческая БРС, не гарантия для набора 2025. Семинарская оценка \(S\) — от 0 до 10. Оценка за зачёт \(E\) — от 2 до 10; при \(E=2\) итог сразу равен 2, иначе \(I=0{,}5S+0{,}5E\) с округлением к ближайшему целому вверх для полуцелых.

Билет содержал два теоретических вопроса и задачу, всего 18 баллов, на ответ отводилось 100 минут. После первой части: до 7 баллов — \(E_1=2\), 8–9 — 3, 10–11 — 4, 12–14 — 5, 15–16 — 6, 17–18 — 7. При 15–18 баллах можно было взять дополнительный вопрос «на отлично» и получить \(E_2\) от 0 до 3; тогда \(E=E_1+E_2\).

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

Программа и правила зачёта ПМИ.Информатика, осень 2022, страница этой программы, архивный вариант 2017/18, план 01.03.02, набор 2025.