1. Выборки, перестановки, сочетания, перестановки с повторениями, сочетания с повторениями. Биномиальные коэффициенты, их свойства. Биномиальная теорема. Полиномиальные коэффициенты. Полиномиальная теорема.

2. Формулы обращения. Метод включений и исключений. Оценки для числа элементов, не обладающих ни одним из свойств. Формула для числа элементов, обладающих в точности r свойствами. Функция Мебиуса. Формула обращения Мебиуса. Перечисление циклических последовательностей.

3. Производящие функции. Примеры применения метода производящих функций для решения комбинаторных задач. Задача о расстановке скобок в неассоциативном произведении. Числа Каталана. Линейные рекуррентные соотношения с постоянными коэффициентами. Решение линейных рекуррентных соотношений. Числа Фибоначчи.

4. Конечные поля. Порядок и характеристика поля. Свойства конечных полей. Поле GF(p), p - простое. Неприводимые многочлены. Нумератор множества всех двоичных многочленов. Формула для числа неприводимых двоичных многочленов заданной степени. Поле GF(2^m) - поле двоичных многочленов степени не выше m-1. Построение поля GF(2^m).

5. Теорема Рамсея (конечный случай). Верхние и нижние оценки для чисел N (p,q,2). Теорема Эрдеша о нижней оценке для чисел N (p,q,2). Лемма об одноцветном решении уравнения: x + y = z. Теорема Шура о решении уравнения x + y = z (mod p), p - простое.

6. Графы. Основные понятия. Способы представления графов. Перечисление графов на занумерованных вершинах. Верхняя оценка для числа неизоморфных графов с q ребрами.

7. Эйлеровы циклы. Теорема Эйлера. Теорема Эйлера для ориентированных графов. Последовательности де Брейна. Алгоритм построения Эйлерова цикла специального вида ("обход выставки").

8. Деревья и их свойства. Оценка числа неизоморфных корневых деревьев с q ребрами. Теорема Кэли о числе деревьев на нумерованных вершинах. Алгоритм нахождения минимального остовного дерева.

9. Потоки в сетях. Минимальные разрезы. Максимальные потоки. Лемма о существовании максимального потока. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе. Алгоритм нахождения максимального потока. Теорема о целочисленности.

10 Двудольные графы. Рассекающие множества. Теорема Кенига-Эгервари о рассекающих множествах в двудольном графе. Частично упорядоченные множества. Линейно упорядоченные множества. Теорема Дилуорса о частично упорядоченных множествах.

11. Побуквенное кодирование. Разделимые коды. Префиксные коды. Неравенство Крафта-Макмиллана для разделимых кодов. Условие существования разделимого кода с заданными длинами кодовых слов. Критерий взаимной однозначности алфавитного кодирования.

12. Оптимальные коды. Свойства оптимальных двоичных кодов. Теорема редукции. Алгоритм Хаффмена построения оптимальных кодов.

13. Самокорректирующиеся двоичные коды. Коды Хэмминга, их свойства. Алгоритм декодирования для кодов Хэмминга. Геометрическая интерпретация. Граница сферической упаковки. Построение кодов, исправляющих t ошибок.

14. Линейные коды. Порождающие и проверочные матрицы линейных кодов. Параметры линейных кодов. Необходимое и достаточное условие существования линейных кодов с заданным минимальным расстоянием.

15. Двоичные коды Боуза-Чоудхури-Хоквингема (коды БЧХ). Построение кодов БЧХ, исправляющих t ошибок для любого натурального t. Алгоритм декодирования для кодов БЧХ, исправляющих двойные ошибки.

16. Детерминированные функции. Задание детерминированных функций при помощи деревьев. Вес функций. Ограниченно-детерминированные функции (о.д.-функции). Способы задания о.д.-функций.

17. Конечные автоматы. Автоматные функции. Состояния автомата. Эквивалентность состояний. Теорема Мура об эквивалентных состояниях автомата. Эквивалентность автоматов. Теорема об эквивалентности состояний автоматов. Сокращенный автомат. Метод построения сокращенного автомата.

18. События. Операции над событиями. Регулярные события. Представимые события. Теорема о событиях, представимых конечными автоматами. Обобщенные источники. Представление регулярных событий обобщенными источниками. Теорема Клини. Пример нерегулярного события. Источники. Регулярные выражения. Представление регулярных событий источниками и регулярными выражениями.

19. Дискретные экстремальные задачи в форме распознавания. Классы P и NP. Полиномиальное преобразование. NP-полные задачи. Примеры NP-полных задач. Теорема Кука (без доказательства). Подходы к решению NP-полных задач. Приближенный алгоритм для решения задачи коммивояжера с неравенством треугольника. Метод ветвей и границ.

ЛИТЕРАТУРА

1. Холл М. Комбинаторика. - М.: Мир. - 1970.
2. Рыбников К.А. Введение в комбинаторный анализ.-М.: изд-во Московского ун-та. - 1985.
3. Сачков В.Н. Введение в комбинаторные методы дискретной математики.-М.: Наука.- 1982.
4. Уилсон Р. Введение в теорию графов. - М.: Мир.- 1977.
5. Оре О. Теория графов. М.: Наука.- 1968.
6. Грэхэм Р. Начала теории Рамсея.- М.: Мир.- 1984.
7. Форд Л., Фалкерсон Д. Потоки в сетях.- М.: Мир. - 1966.
8. Ахо А., Хопкрофт Дж., Ульмант Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979.
9. Рейнгольд Э., Невергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.- М.: Мир.- 1980.
10. Яблонский С.В. Введение в дискретную математику. М.: Наука.- 1986.
11. Дискретная математика и математическая кибернетика/ Под ред. С.В.Яблонского и О.Б.Лупанова, т. 1. - М.: Наука. - 1974.
12. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики.- М.: Наука.- 1992.
13. Берлекэмп Э. Алгебраическая теория кодирования.- М.: Мир.- 1971.
14. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки.- М.: Связь, 1979.
15. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. - М.: Наука. - 1985.