- •Глава 16. Специальные циклы и метрика графов 345
- •Глава 17. Графовые инварианты 404
- •Введение
- •Цели и задачи преподавания дисциплины «дискретная математика»
- •Модуль 1. Основы Теории множеств (2 кредита)
- •Комплексная цель и задачи изучения модуля
- •Глава 1. Исчисление множеств
- •1.1. Понятие множества
- •1.2. Способы задания множеств
- •1.3. Подмножество
- •2. Пустое множество не имеет собственных и истинных подмножеств.
- •3. Одноэлементное множество имеет два подмножества - сaмo себя и , т.Е. Не имеет собственных подмножеств.
- •Множество – это многое, мыслимое как единое.
- •Глава 2. Операции над множествами
- •2.1. Объединение множеств
- •2.2. Пересечение множеств
- •2.3. Разность множеств
- •2.4. Дополнение множества
- •2.5. Тождества алгебры множеств
- •2.6. Доказательства тождеств с множествами
- •Глава 3. Упорядоченные множества
- •3.1. Кортеж (Упорядоченное множество)
- •3.2. Декартово произведение
- •3.3. Операция проектирования множеств
- •3.4. График
- •Декартово произведение множеств позволяет перейти к графическому представлению упорядоченных множеств.
- •Глава 4. Отношения
- •4.1. Основные понятия отношений
- •4.2. Основные свойства отношений
- •4.3. Операции над отношениями
- •4.4. Основные свойства специальных отношений
- •4.5. Разбиение множеств
- •4.6. Отношение порядка
- •Использование отношений позволяет строить модели взаимосвязей между любыми обьектами в природе.
- •5. Соответствия
- •5.1. Определение соответствия
- •5.2. Операции над соответствиями
- •5.3. Понятия образа и прообраза при соответствии
- •5.4. Доказательства тождеств с соответствиями
- •5.5. Основные свойства соответствий
- •5.6. Функция
- •Глава 6. Упорядоченные бесконечные множества
- •6.1. Основные сведения об упорядоченных бесконечных множествах
- •6.2. Проблема континуума
- •Глава 7. Основные понятия теории мультимножеств
- •7.1. Понятие мультимножества
- •7.2. Операции над мультимножествами
- •Возможность многократного вхождения элементов в мультимножество создает новое качество и позволяет расширить класс описываемых, анализируемых и синтезируемых математических объектов.
- •8. Нечеткие множества
- •8.1. Нечеткие высказывания
- •8.2. Операции над нечеткими множествами
- •8.3. Нечеткие отношения и соответствия
- •Тестовые задания к модулю 1
- •24. Множество называется графиком, если каждый его элемент ...
- •25. Соответствие может быть задано … способом.
- •Критерии оценки
- •Нечеткие и приближенные высказывания, множества, соответствия и отношения позволяют формально задавать расплывчатую информацию в виде, удобном для обработки на эвм.
- •Глоссарий к модулю 1
- •Глава 1.
- •Глава 2.
- •Глава 3.
- •Глава 4.
- •Глава 5.
- •Глава 6.
- •Глава 7.
- •Глава 8.
- •Галилей Модуль 2. Основы теории алгоритмов (1,5 кредита) Комплексная цель и задачи изучения модуля
- •Глава 9. Введение в теорию алгоритмов
- •9.1. Понятие алгоритма
- •9.2. Основные свойства алгоритмов
- •9.3. Классификация алгоритмов
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •10.1. Преобразование слов в произвольных абстрактных алфавитах
- •10.2. Числовые функции
- •10.3. Построение алгоритмов по принципу «разделяй и властвуй»
- •10.4. Представление алгоритма в виде детерминированного устройства
- •10.5. Универсальные схемы алгоритмов
- •10.5. “Жадные” алгоритмы
- •10.6. Нечеткие (расплывчатые) алгоритмы
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •11.1. Анализ алгоритмов
- •11.2. Сложность алгоритмов
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Тестовые задания к модулю 2
- •Критерии оценки
- •Модуль 3. Алгебра логики (1,5 кредита) Комплексная цель и задачи изучения модуля
- •Глава 12. Элементы алгебры логики
- •12.1. Логические функции
- •12.2. Основные логические тождества и законы
- •12.3. Булевы функции одной и двух переменных
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •13.1. Дизъюнктивная и конъюнктивная нормальные формы
- •13.2. Способы перехода от нормальных к совершенным нормальным формам
- •2. Графический способ.
- •13.4. Функциональная полнота бф
- •13.3. Алгебра Жегалкина
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •14.1. Реализация булевых функций
- •14.2. Минимизация булевых функций
- •14.3. Карты Карно
- •14.4. Метод Квайна - Мак-Класски
- •14.5. Переход от бф к простейшим комбинационным схемам
- •Контрольные вопросы
- •Задания для самостоятельной работы
- •Критерии оценки
- •Глоссарий к модулю 3
- •Модуль 4. Основы Теории графОв (2 кредита) Комплексная цель и задачи изучения модуля
- •Глава 15. Введение в теорию графов
- •15.1. Способы задания графов и виды графов
- •15.1.1. Способы задания графов
- •15.1.2. Виды графов
- •15.1.3. Нечеткие неориентированные графы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •15.2. Маршруты, цепи, циклы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •При моделировании систем модели и алгоритмы нахождения маршрутов, цепей, циклов, разрезов, связности графов позволяют строить эффективные алгоритмы преобразования графов.
- •15.3. Нахождение кратчайших маршрутов (цепей)
- •15.3.1. Алгоритм Форда
- •15.3.2. Алгоритм Дейкстры
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Алгоритмы Форда и Дейкстры являются эффективным способом определения кратчайшей по стоимости цепи между двумя вершинами графа.
- •Глава 16. Специальные циклы и метрика графов
- •16.1. Эйлеровы и гамильтоновы цепи и циклы
- •16.1.1. Связь между эйлеровыми и гамильтоновыми графами
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.2. Алгоритмы построения гамильтонова цикла
- •16.2.1. Алгоритм Робертса ─ Флореса
- •16.2.2. Алгебраический метод
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.3. Задача о коммивояжере и алгоритмы ее решения
- •16.3.1. Алгоритм Хелда и Карпа
- •16.3.2. Геометрический метод решения
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.4. Расстояния на графах
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •16.5. Деревья
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Глава 17. Графовые инварианты
- •17.1. Цикломатическое и хроматическое числа графа
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •17.2. Числа внутренней и внешней устойчивости графа
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Числа внутренней и внешней устойчивости относятся к инвариантам графа. Они позволяют определить специальные группы вершин в графах.
- •17.3. Планарность графов
- •17.3.1. Плоские и планарные графы
- •17.3.2. Эвристики для определения планарности
- •17.3.3. Минимизация пересечений ребер графов
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •17.4. Ориентированные графы
- •17.4.1. Способы задания
- •17.4.2. Решение стандартных графовых задач с использованием орграфов
- •17.4.3. Выделение сильносвязных компонент
- •17.4.4. Нечеткие ориентированные графы
- •Примеры решения задач
- •Вопросы
- •Задания для самостоятельной работы
- •175 Гиперграфы
- •Примеры решения задач
- •Вопросы для самоконтроля
- •Задания для самостоятельной работы
- •Тестовые задания к модулю 4
- •Критерии оценки
- •Глоссарий к модулю 4 Глоссарий к главе 1
- •Глоссарий к главе 2
- •Глоссарий к главе 3
- •Библиографический комментарий
- •Литература
- •Заключение
- •Приложение 1
- •Учебное издание Гладков Леонид Анатольевич, Курейчик Владимир Викторович, Курейчик Виктор Михайлович
Заключение
В данном учебнике приводятся материалы интенсивно развивающейся области дискретной математики. Рассмотрены элементы теории множеств, алгоритмов и алгебры логики, теории графов и гиперграфов. Использование теории множеств позволяет абстрактно и формально описывать основные модели информатики и вычислительной техники, доказывать тождества с множествами и строить оптимальные схемы устройств цифровой техники. Теория множеств является первым, но основным звеном в общей теории дискретной математики.
Вместе с теорией множеств, математическая логика и теория алгоритмов образуют теоретический фундамент современных вычислительных наук. Знание элементов теории алгоритмов и оценки временной сложности позволяют строить эффективные схемы алгоритмов на основе которых создаются современные программные комплексы. Это дает возможность выполнять анализ и синтез устройств автоматики и вычислительной техники.
Решение задачи минимизации булевых функций позволяет решать задачи синтеза комбинационных устройств и логических схем, проблемы представления булевых функций в виде логических элементов.
Теория графов и гиперграфов является основой моделирования и разработки современной цифровой вычислительной техники и информационных систем.
В настоящее время применение дискретной математики является повсеместным во всех областях науки и техники. Поэтому она является не только фундаментом современной математики, но и основным звеном современного математического образования.
Авторы стремились показать широкие возможности применения дискретной математики, теории алгоритмов и алгебры логики, их универсальность и специализированность для решения задач науки и техники. Авторы тщательно подобрали примеры и рисунки, которые сопровождаются подробными решениями с пояснениями.
Основная задача учебника вместо простого получения фактических знаний обеспечить развитие навыков распознавания, формулирования и решения проблем. Использование учебника позволит организовать обучение в пространстве знаний, упорядоченных по направлению развития качества предметной области. Творческое построение процессов получения знаний позволит обеспечить практическую реализацию изученного материала.
Знание аппарата теории множеств, алгоритмов и алгебры логики позволяет студенту с помощью языка математики формировать новые понятия и повышает интеллектуальный потенциал студента. Практически все последующие курсы направлений «Информатика и вычислительная техника» и «Информационные системы» используют основные понятия и положения дискретной математики.
Приложение 1
оСНОВНЫЕ ПОЛОЖЕНИЯ гост 19.701-90 (исо 5807-85) «сХЕМЫ АЛГОРИТМОВ, ПРОГРАММ, ДАННЫХ И СИСТЕМ. уСЛОВНЫЕ ОБОЗНАЧЕНИЯ И ПРАВИЛА ВЫПОЛНЕНИЯ»
1. Введение
Схема программы отображает последовательность операций в программе и состоит:
1) из символов процесса, указывающих фактические операции обработки данных (включая символы, определяющие путь, которого следует придерживаться с учетом логических условий);
2) линейных символов, указывающих поток управления;
3) специальных символов, используемых для облегчения написания и чтения схемы.
2. Символы
2.1. Процесс
Символ отображает функцию обработки данных любого вида.
2.2. Предопределенный процесс
Символ отображает предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте (в подпрограмме, в модуле).
2.3. Ручная операция
Символ отображает любой процесс, выполняемый человеком.
2.4. Подготовка
Символ отображает модификацию команды или группы команд с целью воздействия на некоторую последующую функцию (установка переключателя, модификация индексного регистра или инициализация программы).
2.5. Решение
Символ отображает решение или функцию переключательного, типа, имеющую один вход и ряд альтернативных выходов, только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа. Соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути.
2.6. Линия
Символ отображает поток данных или управления.
2.7. Соединитель
Символ используется для обрыва ЛИНИИ и продолжения ее в другом месте. Соответствующие символы-соединители должны содержать одно и тоже уникальное обозначение.
2.8. Терминатор
Символ отображает выход во внешнюю среду и вход из внешней среды (начало или конец программы, внешнее использование и источник или пункт назначения данных).
2.9. Комментарий
Символ используют для добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний. Пунктирные линии в символе комментария связаны с соответствующим символом или могут обводить группу символов. Текст комментариев или примечаний должен быть помещен около ограничивающей фигуры.
3. Правила применения символов
3.1. Символ предназначен для графической идентификации функции, которую он обозначает, независимо от текста внутри этого символа.
3.2. Символы в схеме должны быть расположены равномерно. Следует придерживаться разумной длины соединений и минимального числа длинных линий. Символы должны быть, по возможности, одного размера.
3.3. Текст для чтения должен записываться слева направо и сверху вниз независимо от направления потока. Если объем текста, помещаемого внутри символа, превышает его размеры, следует использовать символ комментария.
4. Правила выполнения соединений
4.1. Направление потока слева направо и сверху вниз считается стандартным.
4.2. В схемах следует избегать пересечения линий. Изменение направления в точках пересечения не допускается.
4.3. Линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа.
4.4. При необходимости линии в схемах следует разрывать для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит их нескольких страниц. Соединитель в начале разрыва называется внешним соединителем, а соединитель в конце разрыва - внутренним соединителем.
Ссылки к страницам могут быть приведены совместно с символом комментария для их соединителей.
5. Специальные условные обозначения
Несколько выходов из символа следует показывать:
1) несколькими линиями от данного символа к другим символам;
2) одной линией от данного символа, которая затем разветвляется в соответствующее число линий.
Каждый выход из символа должен сопровождаться соответствующими значениями условий, чтобы показать логический путь, который он представляет, с тем, чтобы эти условия и соответствующие ссылки были идентифицированы.
ДЛЯ ЗАМЕТОК
