Математический ликбез
для слушателей Computer Science Center:
Множества, комбинаторика, вероятность
(А. И. Храбров, осень 2011 года)
Тренировочное домашнее задание по комбинаторике
Обязательное домашнее задание по комбинаторике и теории графов
(нужно набрать 20 баллов)
Программа ликбеза
- Лекция 1.
Основные понятия теории множеств. Бинарные отношения и функции.
Рефлексивность, симметричность, транзитивность. Взаимно-однозначные
соответствия. Счетные множества.
- Лекция 2.
Логика высказываний. Таблицы истинности. Пропозициональные
формулы. Кванторы. Предикаты. Языки логики первого порядка. Интерпретация
языков.
Успенский В. А., Верещагин Н. К., Плиско В. Е.
Вводный курс математической логики. М., ФИЗМАТЛИТ, 2004.
Верещагин Н. К., Шень А. Х.
Начала теории множеств. М., МЦНМО, 2002.
Верещагин Н. К., Шень А. Х.
Языки и исчисления. М., МЦНМО, 2002.
- Лекция 3.
Основные комбинаторные величины и простейшие комбинаторные формулы.
Числа сочетания (с повторениями и без повторений), числа размещения
(с повторениями и без повторений), перестановки. Треугольник Паскаля.
Бином Ньютона и биномиальные коэффициенты.
Виленкин Н. Я. Комбинаторика. М., Наука, 1969.
Риордан Д. Введение в комбинаторный анализ. М., ИЛ, 1963.
- Лекция 4. Формула включений-исключений. Задача о беспорядках.
Задача о разбиении множеств. Мультиномиальные коэффициенты. Задачи
о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения.
Диаграммы Юнга.
Холл М. Комбинаторика. М., Мир, 1970.
Эндрюс Г. Теория разбиений. М. Наука, 1982.
- Лекция 5.
Оценки и асимптотики для комбинаторных величин. Элементарные оценки
факториалов, биномиальных коэффициентов и пр. Формула Стирлинга (б/д).
Понятие об энтропии. Асимптотики для биномиальных коэффициентов и пр.
Оценки сумм биномиальных коэффициентов.
Грэхем Р., Кнут Д., Паташник О.
Конкретная математика. Основание информатики. М. Мир, 1998.
- Лекция 6.
Производящие функции. Числа Фибоначчи. Формула Бинэ и матричное
представление чисел Фибоначчи. Линейные рекуррентные соотношения с
постоянными коэффициентами. Применение производящих функций для решения
рекуррентных соотношений. Производящие функции и разбиения чисел.
Теорема Харди-Рамануджана (б/д). Производящие функции для биномиальные
коэффициентов.
- Лекция 7.
Экспоненциальные производящие фунцкии. Числа Каталана,
Стирлинга, Белла, Бернулли и др. Их применения.
Ландо С.К. Лекции о производящих функциях. М. МЦНМО, 2004.
Грэхем Р., Кнут Д., Паташник О.
Конкретная математика. Основание информатики. М. Мир, 1998.
- Лекция 8.
Основы теории графов. Пути, циклы, матрица инцидентности,
связность. Дополнительный граф. Задача Рамсея. Изоморфизмы графов.
- Лекция 9.
Деревья. Двудольные графы. Эйлеровы и Гамильтоновы пути и циклы.
Харари Ф.
Теория графов М. Мир, 1973.
- Лекция 10.
Лемма Холла и ее переформулировки. Теорема Кенига и ее переформулировки.
Планарные графы. Формула Эйлера (б/д). Теорема Куратовского (б/д).
Холл М. Комбинаторика. М., Мир, 1970.
Харари Ф.
Теория графов М. Мир, 1973.
- Лекция 11.
Дискретная вероятность. Классическое определение вероятности. Условные вероятности.
Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли.
Полиномиальная схема. Случайные графы и множества. Приложение к комбинаторике:
нижняя оценка в теореме Рамсея, теорема Эрдеша-Хайнала, нижняя оценка в теореме
ван дер Вардена.
-
Лекция 12.
Случайные величины. Функции распределения. Независимые случайные величины.
Математическое ожидание и дисперсия. Неравенства Маркова и Чебышёва.
Случайный выбор двудольного подграфа.
-
Лекция 13.
Закон больших чисел для схемы Бернулли. Локальная и интегральная предельные
теоремы Муавра–Лапласа для схемы Бернулли. Теорема Пуассона. Приложения
к комбинаторике.
Ширяев А. Н.
Вероятность. М. Наука, 1989.
Грэхем Р., Кнут Д., Паташник О.
Конкретная математика. Основание информатики. М. Мир, 1998.
Алон Н., Спенсер Дж. Вероятностный метод. М. Бином, 2009.
