Рекомендуем

Теоретические основы информатикиСтариченко Б.Е. Теоретические основы информатики
Математическая логика и теория алгоритмовЗюзьков В.М., Шелупанов А.А. Математическая логика и теория алгоритмов
Дискретная математикаДанилов В.Г., Дубнов В.Л., Лакерник А.Р., Райцин А.М. Дискретная математика

Книга

Дискретная математика для инженеров

Дискретная математика для инженеров

Учебное пособие для вузов
2009 г.
320 стр.
Тираж 500 экз.
Формат 60х90/16 (145x215 мм)
Исполнение: в мягкой обложке
ISBN 978-5-9912-0089-9
ББК 22.176
УДК 519.45
Гриф УМО
Рекомендовано УМО вузов по образованию в области прикладной информатики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 080801 – «Прикладная информатика (по областям)» и другим экономическим специальностям.
Аннотация
Дискретная математика нашла широкое применение в исследованиях больших систем и проектировании дискретных устройств автоматики, в защите и передаче информации, в управлении организационно-экономическими системами, в математической лингвистике и языках программирования. В книге изложены основы теории множеств и отношений, общей и булевой алгебр, комбинаторики и математической логики, теории графов, алгоритмов и автоматов. Основные разделы изложены для "четких" и "нечетких" множеств и отношений. Каждый раздел иллюстрирован многочисленными примерами. Книга сопровождается вычислительными алгоритмами по всем разделам и будет полезна инженерам различных специальностей в проектировании и управлении технологическими процессами и их информационном обеспечении. Особый интерес она представляет для студентов университетов в изучении таких разделов дискретной математики, как "теория графов", "математическая логика", "теория алгоритмов" и "теория автоматов". Для студентов вузов, обучающихся по специальности 080801 - "Прикладная информатика" и другим экономическим специальностям, будет полезна специалистам в области проектирования и управления технологическими процессами.

Оглавление

Введение

1. Алгебраические системы
1.1. Множества
1.1.1. Четкие множества
1.1.2. Нечеткие множества
1.2. Соответствия, отображения и функции
1.2.1. Четкие отображения и функции
1.2.2. Нечеткие отображения
1.3. Отношения
1.3.1. Четкие отношения
1.3.2. Нечеткие отношения
1.4. Элементы общей алгебры
1.5. Булева алгебра
1.5.1. Булевы операции
1.5.2. Законы булевой алгебры
1.5.3. Формула булевой функции
1.5.4. Описание булевой функции
1.5.5. Суперпозиция булевых функций
1.5.6. Свойства булевых функций
1.5.6.1. Самодвойственные булевы функции
1.5.6.2. Монотонные булевы функции
1.5.6.3. Линейные булевы функции
1.5.6.4. Функции, сохраняющие 0
1.5.6.5. Функции, сохраняющие 1
1.5.7. Разложение булевых функций
1.5.7.1. ДНФ булевой функции
1.5.7.2. КНФ булевой функции
1.5.8. Минимизация булевых функций
1.5.8.1. Минимизация ДНФ булевой функции
1.5.8.2. Минимизация КНФ булевой функции
1.6. Алгебра четких множеств
1.6.1. Операции над множествами
1.6.2. Законы алгебры множеств
1.6.3. Эквивалентные преобразования формул
1.6.4. Композиция отображений и отношений
1.6.5. Поиск неизвестного множества
1.7. Алгебра нечетких множеств
1.7.1. Операции над нечеткими множествами
1.7.2. Композиция нечетких отображений
1.7.3. Композиция нечетких отношений
1.7.4. Свойства нечетких отношений
Вопросы и задачи
Литература

2. Элементы комбинаторики
2.1. Размещение из n элементов по k
2.2. Перестановка элементов
2.3. Сочетание из n элементов по k
2.4. Разбиение множества
2.5. Правила комбинаторики
Вопросы и задачи
Литература

3. Теория графов
3.1. Граф и его характеристики
3.2. Описание графа
3.3. Числа графа
3.4. Операции над графами
3.4.1. Унарные операции
3.4.1.1. Поиск дополнительного графа
3.4.1.2. Введение и удаление вершин графа
3.4.1.3. Стягивание вершин графа
3.4.1.4. Введение и удаление ребер графа
3.4.1.5. Поиск плотности и неплотности графа
3.4.1.6. Поиск числа компонент связности графа
3.4.1.7. Поиск устойчивости графа
3.4.1.8. Поиск цикломатического числа графа
3.4.1.9. Поиск хроматического числа графа
3.4.2. Бинарные операции
3.4.2.1. Объединение графов
3.4.2.2. Пересечение графов
3.4.2.3. Композиция графов
3.4.2.4. Соединение графов
3.4.2.5. Прямое произведение графов
3.4.2.6. Изоморфизм графов
3.5. Некоторые алгоритмы на графах
3.5.1. Построение покрывающего остова
3.5.2. Построение остова минимального веса
3.5.3. Поиск кратчайших путей в сети
3.5.4. Поиск максимального потока в сети
3.5.5. Метод критического пути в управлении
3.6. Нечеткие графы
Вопросы и задачи
Литература

4. Математическая логика
4.1. Логика высказываний
4.1.1. Алгебра высказываний
4.1.1.1. Логические операции
4.1.1.2. Правила записи сложных формул
4.1.1.3. Законы алгебры высказываний
4.1.1.4. Эквивалентные преобразования формул
4.1.1.5. Нормальные формы формул
4.1.2. Исчисление высказываний
4.1.2.1. Интерпретация формул
4.1.2.2. Аксиомы и правила введения и удаления связок
4.1.2.3. Метод дедуктивного вывода
4.1.2.4. Принцип резолюции
4.2. Логика предикатов
4.2.1. Алгебра предикатов
4.2.1.1. Законы алгебры предикатов
4.2.1.2. Предваренная нормальная форма формулы
4.2.1.3. Сколемовская стандартная форма формулы
4.2.2. Исчисление предикатов
4.2.2.1. Правила подстановки и унификации
4.2.2.2. Правила введения и удаления кванторов
4.2.2.3. Правила заключения
4.2.2.4. Метод дедуктивного вывода
4.2.2.5. Принцип резолюции
4.2.3. Логическое программирование
4.3. Реляционная логика
4.3.1. Реляционная алгебра
4.3.1.1. Унарные операции
4.3.1.2. Бинарные операции
4.3.1.3. Правила реляционной алгебры
4.3.2. Реляционное исчисление
4.3.3. Языки реляционной логики
4.4. Нечеткая логика
4.4.1. Нечеткое исчисление
4.4.2. Экспертные системы
Вопросы и задачи
Литература

5. Теория алгоритмов
5.1. Рекурсивные функции
5.1.1. Базовые функции
5.1.2. Элементарные операции
5.2. Машина Тьюринга
5.2.1. Описание машины Тьюринга
5.2.2. Примеры машин Тьюринга
5.2.3. Композиция машин Тьюринга
5.3. Нормальные алгоритмы Маркова
5.4. Сложность вычислений
Вопросы и задачи
Литература

6. Конечные автоматы
6.1. Абстрактный автомат
6.1.1. Типы конечных автоматов
6.1.2. Описание автоматов
6.1.3. Автоматное моделирование алгоритмов
6.1.4. Микропрограммный автомат
6.1.5. Магазинный автомат
6.1.6. Эквивалентность автоматов
6.1.7. Эквивалентность внутренних состояний автомата
6.1.7.1. Детерминированный автомат
6.1.7.2. Недетерминированный автомат
6.2. Структурный автомат
6.2.1. Произведение автоматов
6.2.1.1. Последовательное соединение автоматов
6.2.1.2. Параллельное соединение автоматов
6.2.2. Обратная связь автоматов
6.2.3. Сумма автоматов
6.2.4. Структурный автомат и кодирование
6.3. Логическое проектирование автоматов
6.3.1. Кодирование алфавитов автомата
6.3.2. Комбинационные автоматы – автоматы без памяти
6.3.2.1. Логическое проектирование оператора 
6.3.2.2. Логическое проектирование системы операторов 
6.3.2.3. Логические схемы комбинационного автомата
6.3.3. Конечные автоматы –– автоматы с памятью
6.3.3.1. Проектирование оператора конечного автомата
6.3.3.2. Проектирование оператора  конечного автомата
6.3.3.3. Логическая схема автомата с памятью
Вопросы и задачи
Литература