ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ

Согласно учебному плану курс «Дискретная математика» на заочном отделении изучается на 2 курсе в 4 семестре и 3 курсе 5 семестре, форма итогового контроля – экзамен. На изучение курса отводится 20 часов аудиторных занятий: 10 ч. лекций и 10 ч. практических занятий.

Предусматривается также выполнение итоговой домашней контрольной работы в соответствии с графиком проведения контрольных мероприятий.

Вид учебной работы	Всего часов	Семестры
Общая трудоемкость		4-5
Аудиторные занятия
Лекции
Практические занятия (семинары)
Лабораторные работы	–
Самостоятельная работа
Курсовые работы/рефераты	-
Вид итогового контроля		экзамен

Содержание дисциплины:

I. ВВЕДЕНИЕ

Различие между дискретной и непрерывной математикой. Счет и перечисление (перебор) как основные методы дискретной математики, примеры. Что такое дискретная математика?

II. КОНЕЧНЫЕ СУММЫ И РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

Способы записи конечных сумм. Преобразования сумм. Кратные суммы. Некоторые методы суммирования. Понятие рекуррентного соотношения. Примеры задач, приводящих к рекуррентным соотношениям. Числа Фибоначчи. Некоторые способы решения рекуррентных соотношений первого и второго порядка.

Символы ~, о, О. Основные правила использования этих символов. Асимптотические решения рекуррентных соотношений.

III. Основные понятия комбинаторики.

Правило произведения. Выборки, размещения, перестановки, сочетания; их пересчет. Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Треугольник Паскаля. Бином Ньютона. Некоторые применения бинома Ньютона. Полиномиальные коэффициенты. Полиномиальная теорема. Комбинаторный смысл биномиальных коэффициентов. Комбинаторный смысл полиномиальных коэффициентов. Метод включения-исключения и его применения.

IV. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

Понятие графа (неориентированного и ориентированного), его основные термины; различные способы их представления. Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие. Подграф. Цепь, простая (элементарная) цепь, цикл, простой (элементарный) цикл. Связные графы. Компоненты связности графа, их число. Изоморфные графы. Эйлеровы и полуэйлеровы графы. Критерий эйлеровости (полуэйлеровости). Гамильтоновы и полугамильтоновы графы. Достаточные условия гамильтоновости графа. Деревья и лес. Характеризационная теорема. Остовные деревья. Графы с весами ребер и алгоритм Краскала. Планарные графы. Укладка графа. Плоские графы. Не планарность графов K₅ и K_3,3. Раскраска вершин графа. Хроматическое число графа. Раскрашиваемость вершин планарного графа пятью красками. Теорема о четырех красках (без доказательства). Двудольные графы.