НГА Украины Методические материалы Кафедра СА и У Лекции по основам дискретной математики 16

Национальная горная академия Украины

Кафедра управления в технических системах

К О Н С П Е К Т

лекций по дисциплине

«Основы дискретной математики»

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

7.080401, 7.080403 и 7.080203

Днепропетровск

2000

Содержание

Стр.

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Раздел 1. Основы теории множеств . . . . . . . . . . . . . . .

1.1. Основные определения . . . . . . . . . . . . . . . . . . .

1.2. Операции с множествами . . . . . . . . . . . . . . . .

1.3. Декартово произведение множеств . . . . . . . . . . .

1.4. Отношения . . . . . . . . . . . . . . . . . . . . . . . . .

1.5. Свойства отношений . . . . . . . . . . . . . . . . . . .

1.6. Соответствие, отображения и функции . . . . . . . .

Раздел 2. Основы теории графов . . . . . . . . . . . . . . . . . .

2.1. Основные положения . . . . . . . . . . . . . . . . . . . .

2.2. Неориентированные графы. . . . . . . . . . . . . . . . . .

2.3. Изоморфизм графов. . . . . . . . . . . . . . . . . . . . . .

2.4. Отношение порядка и отношение эквивалентности

на графе . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5. Характеристики графов . . . . . . . . . . . . . . . . . . .

2.6. Эйлеровы графы и гамильтоновы циклы . . . . . . . . . .

2.7. Расчет сетевого графика . . . . . . . . . . . . . . . . . .

2.8. Оптимизация на сетях . . . . . . . . . . . . . . . . . . .

Введение

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

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

Основные объекты дискретной математики – множества, графы, логические функции и автоматы, формальные системы, алгебры и комбинаторика.

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

Логика и автоматы являются традиционными разделами курса дискретной математики. Рассматриваются основные законы математической логики и методики работы с логическими выражениями. Основы теории автоматов представлены для класса конечных автоматов. Подробно рассмотрены вопросы синтеза и минимизации автоматов. Алгебры и формальные системы являются центральным разделом курса дискретной математики. Знание принципов организации формальных систем, связанных с вычислениями, становится важным элементом математической культуры любого исследователя, имеющего отношение к алгоритмизации процессов управления. По существу оно дает понимание того, что можно и чего нельзя сделать с помощью вычислительных машин. Элементы комбинаторики представлены как необходимый элемент систем управления, связанных с генерированием вариантов принятия решений.