Рекомендуем

Дискретная математика для инженеровПономарев В.Ф. Дискретная математика для инженеров
Дискретная математика для бакалавриатаШептунов М.В. Дискретная математика для бакалавриата
Математическая логика и теория алгоритмовЗюзьков В.М., Шелупанов А.А. Математическая логика и теория алгоритмов

Книга

Дискретная математика

Дискретная математика

Учебное пособие для вузов
2008 г.
136 стр.
Тираж 0 экз.
Формат 60х90/16 (145x215 мм)
Исполнение: в мягкой обложке
ISBN 978-5-9912-0020-2
ББК 22.176
УДК 519.1
Гриф УМО
Рекомендовано УМО по образованию в области телекоммуникаций в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению «Телекоммуникации»
Аннотация
Изложены сведения из четырёх разделов дискретной математики: теории множеств – множества и операции над ними, отношения и их классификация, отображения, алгебраические системы и их морфизмы; математической логики – высказывания, булевы формулы и булевы функции, нормальные формы, минимизация булевых формул, предикаты и их выполнимость, предикатные формулы, соответствие между булевыми формулами и булевыми теоретико-множествен-ными операциями; теории графов – рассматриваются основные задачи теории графов с упором на оптимизацию и алгоритмический подход к решению задач, в том числе контактные схемы, задача оптимизации путей с весами из полугруппы (инструмент многокритериальной оптимизации), задача о максимальном потоке в транспортной сети с простым и эффективным алгоритмом её решения; теории конечных автоматов, с рассмотрением таких задач, как инимизация числа состояний автомата, распознавание множеств, синтез автоматов. Для студентов вузов, обучающихся по направлению подготовки бакалавров и магистров 550400 – «Телекоммуникации».

Оглавление

Введение

Г л а в а 1. Основные понятия теории множеств
1. Предварительные сведения из теории множеств
2. Операции на множествах и их специальные свойства

Г л а в а 2. Элементы математической логики
1. Высказывания. Операции над высказываниями
2. Зависимости между операциями
3. Функции алгебры логики
4. Булевы формулы. Логическая оболочка системы булевых функций
5. Разложение функций по переменным
6. Совершенная дизъюнктивная нормальная форма
7. Совершенная конъюнктивная нормальная форма
8. Двойственность
9. Полнота и замкнутость
10. Многочлены Жегалкина
11. Классы Поста. Теорема Поста
12. Импликанты и минимизация ДНФ
13. Предикаты и кванторы
14. Предикатные формулы и операции над множествами
15. Задача выполнимости предиката

Г л а в а 3. Основные определения и задачи теории графов
1. Основные определения
2. Сети, контактные схемы и булевы формулы
3. Задача, с которой началась теория графов
4. Задачи об оптимальных путях
5. Простые циклы в графах. Цикломатическое число графа
6. Эйлерова характеристика плоского графа
7. Потоки в транспортных сетях
8. Теорема о системе различных представителей и её приложение
к теории графов
9. Поток, насыщающий выходные дуги

Г л а в а 4. Элементы теории конечных автоматов
1. Понятие автомата
2. Варианты автоматов
3. Автоматы и графы
4. Минимизация числа состояний автомата
5. Распознавание множеств автоматами
6. Детерминизация источников и синтез автоматов

Список литературы

Приложение: задания для домашних контрольных работ

Список основных обозначений

Предметный указатель