- •Введение в дискретный анализ
- •Глава 1. Введение в теорию множеств
- •Тема 1.1. Множества и операции над ними
- •1.1.1. Основные понятия
- •1.1.2. Операции над множествами
- •1.1.3. Векторы и прямые произведения
- •Вопросы для повторения
- •Резюме по теме
- •Тема 1.2. Отношения
- •1.2.1. Основные понятия и определения
- •1.2.2. Бинарные отношения. Основные определения
- •1.2.4. Эквивалентность и порядок
- •Вопросы для повторения
- •Резюме по теме
- •Тема 1.3. Соответствия и функции
- •1.3.1. Соответствия и их свойства
- •1.3.2. Взаимно однозначные соответствия и мощности множеств
- •1.3.3. Функции и отображения
- •1.3.4. Операции
- •1.3.5. Гомоморфизмы и изоморфизмы
- •Вопросы для повторения
- •Резюме по теме
- •Глава 2. Математическая логика
- •Тема 2.1. Логика высказываний
- •2.1.1. Логические связки
- •2.1.2. Основные схемы логически правильных рассуждений
- •2.2.2. Булева алгебра
- •2.2.3. Эквивалентные преобразования
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.3. Полнота и замкнутость
- •2.3.1. Функционально полные системы
- •2.3.2. Алгебра Жегалкина и линейные функции
- •2.3.3. Замкнутые классы и монотонные функции
- •2.3.4. Теоремы о функциональной полноте
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.4. Нечеткая логика
- •2.4.1. Основные понятия теории нечетких множеств
- •2.4.2. Логические операции над нечеткими множествами
- •2.4.3. Свойства логических операций над нечеткими множествами
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.5. Нечеткие модели управления
- •2.5.1. Нечеткие операторы
- •2.5.2. Нечеткая и лингвистическая переменные
- •2.5.3. Нечеткий логический вывод
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.6. Логика предикатов
- •2.6.1. Предикаты. Основные понятия
- •2.6.2. Кванторы
- •2.6.3. Выполнимость и истинность
- •2.6.4. Эквивалентные соотношения. Префиксная нормальная форма
- •Вопросы для повторения
- •Резюме по теме
- •Глава 3. Комбинаторика
- •Тема 3.1. Комбинаторные конфигурации
- •3.1.1. Принципы сложения и умножения
- •3.1.2. Перестановки
- •3.1.3. Размещения
- •3.1.4. Сочетания
- •3.2.2. Полиномиальная формула
- •3.2.3. Формула включений и исключений
- •Вопросы для повторения
- •Резюме по теме
- •Глава 4. Теория графов
- •Тема 4.1. Основные понятия и операции на графах
- •4.1.1. Основные понятия
- •4.1.2. Способы задания графов
- •4.1.3. Операции над частями графа. Графы и бинарные отношения
- •Вопросы для повторения
- •Резюме по теме
- •Тема 4.2. Маршруты и деревья
- •4.2.1. Маршруты, пути, цепи, циклы
- •4.2.2. Дерево и лес
- •5.1.2. Способы задания автоматов
- •5.1.3. Взаимосвязь между моделями Мили и Мура
- •Вопросы для повторения
- •Резюме по теме
- •Тема 5.2. Детерминированные конечные автоматы
- •5.2.1.Основные понятия детерминированных конечных автоматов
- •5.2.2. Схема доказательства правильности конечного автомата
- •5.2.3. Произведение автоматов
- •5.3.2. Детерминизация нка
- •Вопросы для повторения
- •Резюме по теме
Введение в дискретный анализ
Человек воспринимает информацию с помощью органов чувств. Процесс поступления сигналов с помощью этих чувств происходит непрерывно. Непрерывная величина может принимать любые значения в некотором диапазоне, которые могут быть сколько угодно близки, но все таки отличаться. Количество таких значений бесконечно велико. Дискретные величины принимают не все возможные, а только определенные значения, и их можно пересчитать.
В конце XVII века бурно развивающееся машинное производство постепенно стало превращать науку в производительную силу. С данного момента времени человечество встало на путь научно-технического прогресса (НТП). В XIX веке наука решает не только задачи, выдвигаемые производством, но и сама ставит проблемы, получающие в дальнейшем свое технико-производственное разрешение.
С середины XX века НТП вышел на уровень научно-технической революции (НТР). Революционные изменения охватили все разделы науки, техники и производства. НТР порождена поисками новых путей разрешения противоречий в различных областях, в наибольшей степени в развитии производительных сил.
В 1641-42 году Блез Паскаль сконструировал механический вычислитель, который позволил складывать и вычитать числа. В 1673 году немецкий ученый Готфрид Лейбниц построил первую счетную машину, способную выполнять все четыре действия арифметики. А в 1946 году в США уже была создана первая ЭВМ "Эниак". В группу создателей входил выдающийся ученый Джон фон Нейман, который и предложил основные принципы построения ЭВМ: переход к двоичной системе счисления для представления информации и принцип хранимой программы.
Требовались новые подходы и методы решения задач, а так же необходимо было переосмыслить уже существующие алгоритмы и адаптировать их к новым принципам реализации поставленных задач.
Все это положило начало бурного развития дискретной математики в ХХ веке. За рубежом часто дискретную математику называют компьютерной математикой.
Дискретная математика — область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях. В качестве синонима иногда употребляется термин «дискретный анализ».
Изначально дискретная математика рассматривалась как теоретические основы компьютерной математики. Затем модели и методы дискретной математики начали использоваться как средства для построения и анализа моделей в различных науках, таких как биология, экономика, экология и так далее.
Решение управленческих проблем на сегодняшний день является основной задачей, будь то управление производством, принятие управленческих решений или же управление персоналом. В первом случае система состоит из набора микроконтроллеров, датчиков и рабочих органов. Управление осуществляется построением либо автоматизированной системой управления (АСУ) либо автоматизированной системой регулирования (АСР) в зависимости от сложности контура управления. Здесь инженер задает законы работы системы в зависимости от требуемых показателей и учитывает возмущающие воздействия. В общем случае инженер знает все потенциальные воздействия на систему и может спрогнозировать реакцию системы на то или иное возмущение или же положительное воздействие. Управление персоналом является сложнейшей задачей, так как данная система состоит из людей. Каждый человек индивидуален, а так же может принимать различные решения в одних и тех же ситуациях в зависимости от личного состояния на данный момент.
Основная литература по дискретной математике ориентирована либо на специалистов в области математики либо же на инженеров технического профиля (программисты, автоматизация производства и так далее). В данных учебниках курс изложен на основе того, что читатель подготовлен к изучению дискретной математики, то есть имеет сильную математическую подготовку. Поэтому в громоздких математических выкладках без примеров, сопоставленных реальным объектам сферы деятельности менеджмента, зачастую менеджером теряется суть вопроса, что приводит к недостаточному усваиванию дисциплины специальностями гуманитарного направления.
Учебное пособие разработано для студентов специальности менеджмент с устранением вышеуказанных недостатков. В нем рассмотрены средства конструктивного анализа и моделирования в управлении. Изложены методы формализованного представления реальных управленческих ситуаций и процессов. Методы дискретной математики используются для описания и анализа многих проблемных ситуаций, таких которые не поддаются описанию традиционными средствами классической математики.
Дискретная математика предлагает менеджеру, владеющему дискретной информацией: универсальные средства (языки) формализованного представления; способы корректной переработки информации, представленной на этих языках; возможность и условия перехода с одного языка описания явлений на другой, сохраняя при этом содержательную целостность модели.
В XXI веке менеджер не владеющий компьютерной техникой является не жизнеспособным звеном информационного общества. На сегодняшний день персональный компьютер (ПК) предоставляет менеджеру средства для редактирования (текста, звука, видео и так далее), системы документационного обеспечения, системы поддержки принятия решений, маркетинговые исследования, информационные системы по разработке бизнес планов и так далее. Для быстрого освоения вышеуказанных возможностей, предоставляемых ПК, а так же для постановки проблемы на языке понятном машине (имеется ввиду не язык на котором написан программный продукт, а средства ввода информации в программу), менеджеру необходимо иметь представление о принципах работы программного продукта, которые основаны на методах дискретной математики.
Книга дискретная математика для менеджеров разработана, учитывая специфику гуманитарного образования, и может быть использована не только для подготовки менеджеров, но и для других гуманитарных специальностей.
Цель курса. Освоение обучаемым фундаментальных знаний в области дискретного анализа и выработка практических навыков применения этих знаний, а так же заложить понимание формальных основ дисциплины и выработать у студентов достаточный уровень интуиции, необходимый для формализации и решения дискретных задач в области менеджмента.
Задачи курса:
изложение основных положений и методов дискретного анализа;
сформировать представление о постановке задач в области дискретной математики;
изучение основ таких разделов дискретной математики, как теория графов, алгебры логики, алгебраических структур, комбинаторики, основ теории множеств, основ теории конечных автоматов.
Место курса в профессиональной подготовке выпускника. Дисциплина относится к циклу общепpофессиональных дисциплин (федеральный компонент), обеспечивающих общепpофессиональную подготовку. Изучение дисциплины «Дискретная математика» базируется на следующих дисциплинах: алгебра, математический анализ. Основные положения курса «Дискретная математика» должны быть использованы при изучении дисциплин: вычислительная математика, математика, инструментальные средства моделирования сложных систем.