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

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

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

К О Н С П Е К Т

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

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

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

И 7.080203

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

Содержание

Стр.

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

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

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

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

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

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

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

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

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

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

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

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

На графе . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

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

Введение

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

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

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

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

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