На главную
Расписание занятий
Дискретная математика. 2012/2013 учебный год.
- Введение: о чем этот курс.
- Метод производящих функции.
- Ящики и шары: двенадцатиричный путь.
- Рациональные производящие функции.
- Числа Каталана. Пути Дика и Моцкина.
- Графы. Матрица смежности графа. Производящие функции путей в графах.
- Производящие функции нескольких переменных. Числа Бернулли-Эйлера.
- Принцип включения-исключения. Производящие функции Дирихле.
- Частично упорядоченные множества и общая формула обращения Мебиуса.
- Разбиения. Пентагональная формула Эйлера.
- Действие группы на множестве. Теорема Полиа. Перечисление графов.
- Перечисление деревьев (помеченных и нет). Теорема Кэли о числе деревьев.
- Инварианты графов. Хроматический многочлен, потоковый многочлен, сложность.
- Циклы и коциклы, цикломатическое число графа.
- Соотношение удаление-стягивание, теорема Татта об универсальном инварианте.
- Матричная теорема о деревьях.
- Собственные числа матрицы смежности и инварианты графов.
- Случайные графы.
- Графы и перестановки. Числа Гурвица.
- Языки. Конечные автоматы и языки, ими порождаемые.
- Контекстно-свободные грамматики, регулярные языки и автоматы со стеком.
