ТЕМАТИКА РЕФЕРАТОВ, КУРСОВЫХ РАБОТ

Дискретная математика

2 курс 2 семестр

Преподаватель: Стеценко В.А., доцент кафедры ТИДМ, к.ф.м.н., доцент

Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 4 зачетных единицы, 144 часа, в том числе 72 аудиторных часа

№п/п	Наименование раздела дисциплины	Содержание раздела (дидактические единицы)
	Введение	Различие между дискретной и непрерывной математикой. Понятие дискретного множества. Счет и перечисление (перебор) как основные методы дискретной математики.
	Конечные суммы	Способы записи конечных сумм. Основные правила преобразования конечных сумм. Понятие явной формулы. Вычисление конечных сумм: метод выделения, суммирование разностей, метод двойного суммирования.
	Элементы комбинаторики	Понятие перечислительной задачи, примеры. Основные свойства конечных множеств: правило суммы, правило произведения; его комбинаторная интерпретация. Решение простейших перечислительных задач. Основные комбинаторные конфигурации: выборки, размещения, перестановки, перестановки с повторениями, сочетания, сочетания с повторениями. Явные формулы для их числа. Простейшие задачи на размещение шаров по ящикам. Метод включения-исключения. Число элементов конечного множества, не удовлетворяющих ни одному из n заданных на этом множестве свойств. Число размещений m различимых шаров по n различимым ящикам, при условии того, что ящики не могут быть пустыми. Число размещений m различимых шаров по n неразличимым ящикам, при условии того, что ящики не могут быть пустыми. Разбиения множеств. Лемма Бернсайда. Применение леммы Бернсайда при комбинаторных подсчетах. Теорема Шпернера. Теорема Эрдеша - Ко - Радо. Теорема о выборе Холла.
	Рекуррентные соотношения	Понятие рекурсивной процедуры и рекуррентного соотношения. Числа Фибоначчи. Примеры задач, приводящие к рекуррентному соотношению. Рекуррентные соотношения и конечные суммы. Решение рекуррентного соотношения вида . Биномиальные коэффициенты. Рекуррентное соотношение для биномиальных коэффициентов. Треугольник Паскаля. Явная формула для биномиальных коэффициентов. Бином Ньютона. Комбинаторная интерпретация биномиальных коэффициентов. Полиномиальная формула. Метод траекторий. Числа Стирлинга первого и второго рода, их свойства. Теорема обращения.
	Производящие функции	Производящие функции. Применение производящих функций для решения рекуррентных соотношений (явная формула для чисел Фибоначчи). Алгебра Коши. Применение производящих функций для комбинаторных подсчетов. Применение производящих функций для вычисления комбинаторных сумм. Правильно построенные скобочные структуры. Последовательность Каталана. Явная формула для чисел Каталана. Примеры задач, приводящих к числам Каталана.
	Элементы теории графов	Основные понятия теории графов. Способы задания графа. Изоморфизм графов. Понятие инварианта графа. Примеры простейших инвариантов графа. Степень вершины графа. Лемма о рукопожатиях и ее следствие. Связные графы. Подграфы. Компоненты связности. Число компонент связности у графа, имеющего p вершин и q ребер. Необходимое условие связности графа. Достаточное условие связности графа Деревья. Характеризационная теорема. Теорема Кэли о числе деревьев, заданных на фиксированном n -множестве. Соответствие Прюфера. Число деревьев с фиксированным числом висячих вершин. Эйлеровы графы. Критерий эйлеровости. Полуэйлеровы графы. Критерий полуэйлеровости. Уникурсальные кривые. Гамильтоновы графы. Теорема Дирака. Укладка графа в топологическое пространство. Планарные и плоские графы. Теорема Эйлера для связных плоских графов, ее следствия. Понятие эйлеровой характеристики. Непланарность графов и . Теорема Понтрягина – Куратовского (без док-ва). Раскраска вершин графа. Хроматическое число и хроматический многочлен графа. Двудольные графы. Теорема Кенига. Понятие карты. Раскрашивание карт. Теорема о четырех красках (без док-ва). Неравенство Хивуда. Теорема Вагнера. Гипотеза Хадвигера. Теорема Турана. Числа Рамсея. Теорема Эрдеша – Шекереса. Существование чисел Рамсея (теорема Рамсея).

ТЕМАТИКА РЕФЕРАТОВ, КУРСОВЫХ РАБОТ

1. Арифметика чисел Фибоначчи.

2. Комбинаторика чисел Каталана.

3. Обобщения треугольника Паскаля.

4. Алгоритм Евклида и его модификации.

5. Алгоритм Евклида и числа Фибоначчи; теорема Ламэ.

6. Суммы и рекуррентности; числа Бернулли.

7. Рекуррентные формулы в задачах на разбиения.

8. Производящие функции и разбиения чисел.

9. Графы и метрики.

10. Алгоритмы на графах.