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

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

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

4. Теорема Рамсея (конечный случай). Верхние и нижние оценки для чисел N (p,q,2). Теорема Эрдеша. Теорема Рамсея (бесконечный случай).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЛИТЕРАТУРА

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.