Москва - 2004

По дискретной математике

Лекции

Ю.А. Зуев

Для студентов специальности 230102

всех форм обучения

www.msta.ru

УДК 519.8

Ó Зуев Ю.А. Дискретная математика. – Лекции. М., МГУТУ, 2004.

В лекциях доктора физико – математических наук профессора Зуева Ю.А. изложены основные разделы дискретной математики: перечислительная комбинаторика, теория графов и алгоритмов на графах, помехоустойчивое кодирование и криптография. Каждый раздел заключают тесты, позволяющие контролировать степень усвоения материала. Тесты снабжены ответами. Представлен словарь основных терминов.

Курс лекций предназначен для студентов специальностей 230102 всех форм обучения.

Автор: д.ф. – м.н. Зуев Юрий Анатольевич

Рецензент: д. ф. – м.н. Кузюрин Н.Н.

Редактор: Свешникова Н.И.

ÓМосковский государственный университет технологий и управления, 2004.

109004, Москва, Земляной вал, 73.

Содержание

Стр.

Введение 4

Глава I. Перечислительная комбинаторика 5

1.1. Перестановки, размещения, сочетания и разбиения 5

1.2. Формула бинома и полиномиальная формула 7

1.3. Формула включения и исключения 9

1.4. Приложения к теории вероятностей 11

1.5. Производящие функции и рекуррентные соотношения 14

1.6. Перечисление в присутствии группы. Лемма Бернсайда и

теорема Пойа 17

Глава II.Графы и алгоритмы 21

2.1. Основные понятия теории графов 21

2.2. Алгоритмы в дискретной математике 23

2.3. Минимальное остовное дерево 25

2.4. Кратчайший путь между двумя вершинами 27

2.5. Задача коммивояжера. Метод «ветвей и границ» 29

2.6. Паросочетания в двудольных графах 35

2.7. Потоки в сетях 39

Глава III. Кодирование 45

3.1. Основные задачи теории кодирования 45

3.2. Помехоустойчивое кодирование 46

3.3. Криптография 49

Итоговый тест 56

Рекомендуемая литература 57

Словарь основных терминов 58

Ответы к тестам 59

Введение.

Бурно развивавшаяся на протяжении XX века дискретная математика заняла в последнее десятилетие важное место в общем курсе математической подготовки студентов технических вузов и университетов. Владение её элементами стало обязательной составной частью математического образования инженеров, экономистов, специалистов по вычислительной технике. Причина возросшего спроса на дискретную математику заключается в бурном развитии вычислительной техники, расширившем возможности работы с дискретными структурами, что привело к качественным изменениям в математических методах решения прикладных задач в целом ряде областей человеческой деятельности.

В то же время изучение дискретной математики может вызвать определенную трудность у лиц, чьё математическое образование базируется исключительно на классическом математическом анализе. Цельность математического анализа обеспечивается единым подходом к решению широкого круга задач, основанным на использовании производной и первообразной – понятий, существенно использующих свойства континуума. В дискретной математике, занимающейся изучением конечных и счетных множеств, подобного единства не достигнуто. Она распадается на множество разделов со своими собственными задачами и методами, овладение которыми требует определенной математической культуры, умственного напряжения и упорства. Аппарат современной алгебры широко используется в дискретной математике.

В лекциях представлено ядро сложившегося к настоящему времени курса дискретной математики, рассматриваются её важнейшие теоретические и прикладные вопросы. Изложение весьма сжатое. Цель курса – дать общее представление о задачах и методах дискретной математики, познакомить с основными структурами и алгоритмами, показать их прикладное значение, а также привить навыки самостоятельной работы. Рассматриваются задачи перечисления, графы и алгоритмы на графах, помехоустойчивое кодирование и криптография.

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

Глава I. Перечислительная комбинаторика.

Дата добавления: 2014-01-03