Лекций: 34

Практических: 17

Лабораторных: 0

DM.2

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

ECTS: 2

Лектор

Кандидат физико-математических наук, доцент кафедры уравнений математической физики

Цель курса

ознакомление с базовыми разделами дискретной математики и ее

приложениями

Базовые курсы

введение в математику (начала теории множеств и теории

отображений).

Содержание

Введение в комбинаторный анализ.

Правила суммы и произведения. Перестановки и сочетания.

Биномиальная теорема. Свойства биномиальных коэффициентов.

Полиномиальная теорема. Метод включения и исключения.

Рекуррентные соотношения. Числа Фибоначчи. Системы различных

представителей. Теорема Холла. Системы общих представителей.

Введение в теорию графов.

Изоморфизм графов. Помеченные графы. Связь между числами

вершин, ребер и компонент графа. Двудольные графы. Теорема

Кенинга. Волновой алгоритм. Деревья. Нахождение остова

минимального веса. Независимость и покрытия. Оценка числа

независимости. Вершинные и реберные покрытия. Паросочетания в

двудольных графах. Эйлеровы графы. Критерий эйлеровости.

Гамильтоновы графы. Достаточные условия гамильтоновости.

Вершинные и реберные раскраски графов.

Элементы теории кодирования.

Понятие кодирования. Общая схема. Алфавитное кодирование.

Теорема Макарова о взаимной однозначности алфавитного

кодирования. Самокорректирующиеся коды.

Методика преподавания

Лекции и практические занятия.

Литература

1. , ,

Лекции по теории графов. М.: Наука, 1990.

2. Рыбников в комбинаторный анализ. М.: Изд-во

МГУ, 1972.

3. Яблонский в дискретную математику. М.: Наука,

1986

Экзаменационная методика

зачет

Рекомендуется

для студентов первого курса ММФ специализации математические методы в экономике

Примечания

Данная литература необходима в течение всего курса.