Добавил:
Upload
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:full_v2.doc
X
- •Глава 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
- •Учебное издание Гладков Леонид Анатольевич, Курейчик Владимир Викторович, Курейчик Виктор Михайлович
Учебное издание Гладков Леонид Анатольевич, Курейчик Владимир Викторович, Курейчик Виктор Михайлович
Дискретная математика:
Теория множеств, алгоритмов и алгебры логики
УЧЕБНИК
Ответственный за выпуск Гладков Л.А.
Редактор Лунева Н.И.
Корректор Надточий З.И.
ЛР № 020565 от 23 июня 1997г.
Подписано к печати 10.05.11 Формат 60 х 84 1/16
Бумага офсетная Печать офсетная
Усл.п.л. – 19,5
Уч.-изд.л. – 20,0
Заказ № Тираж 500 экз.
«С»
Издательство Технологического института
Южного федерального университета
ГСП 17А, Таганрог, 28, Некрасовский, 44
Типография Технологического института
Южного федерального университета
ГСП 17А, Таганрог, 28, Энгельса, 1
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]