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

Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. – 744 с.

В девятнадцатом выпуске серии «Математика в техническом университете» изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам.

Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.

Для студентов технических университетов. Может быть полезен преподавателям и аспирантам.


Содержание

Предисловие
Основные обозначения
 
1. Множества и отношения
1.1. Множества
1.2. Кортеж. Декартово произведение
1.3. Соответствия и бинарные отношения
1.4. Операции над соответствиями
1.5.  Семейства множеств
1.6. Специальные свойства бинарных отношений
1.7. Отношения эквивалентности
1.8. Упорядоченные множества
1.9. Мощность множества
Вопросы и задачи
 
2. Алгебры: группы и кольца
2.1. Операции. Понятие алгебраической структуры
2.2. Группоиды, полугруппы, группы
2.3. Кольца, тела, поля
2.4. Области целостности
2.5. Модули и линейные пространства
2.6. Циклические группы
2.7. Подгруппы и подкольца
2.8. Теорема Лагранжа
2.9. Гомоморфизмы групп и нормальные делители
2.10. Гомоморфизмы колец
Вопросы и задачи
 
3. Полукольца и булевы алгебры
3.1.  Полукольца. Основные примеры
3.2. Замкнутые полукольца
3.3. Решение систем линейных уравнений в замкнутых полукольцах
3.4. Булевы алгебры
3.5. Решетки
Вопросы и задачи
 
4. Алгебраические системы
4.1. Предикаты
4.2.  Алгебраические системы: модели и алгебры
4.3. Подсистемы
4.4. Конгруэнции и фактор-системы
4.5. Гомоморфизмы
4.6. Прямые произведения алгебраических систем
4.7.  Многосортные алгебры
Вопросы и задачи
 
5. Теория графов
5.1. Основные определения
5.2. Способы представления
5.3. Деревья
5.4. Остовное дерево наименьшего веса
5.5. Методы обхода вершин
5.6. Задача о путях
5.7.  Изоморфизм графов
5.8. Вычисление порядковой функции
5.9. Элементы цикломатики
Вопросы и задачи
 
6. Булевы функции
6.1. Понятие булевой функции. Таблицы
6.2. Формулы и суперпозиции
6.3. Дизъюнктивные и конъюнктивные нормальные формы
6.4. Построение минимальных ДНФ
6.5. Теорема Поста
6.6. Схемы из функциональных элементов
Вопросы и задачи
 
7. Конечные автоматы и регулярные языки
7.1. Алфавит, слово, язык
7.2. Порождающие грамматики
7.3. Классификация грамматик и языков
7.4. Регулярные языки и регулярные выражения
7.5. Конечные автоматы. Теорема Клини
7.6.  Детерминизация конечных автоматов
7.7. Минимизация конечных автоматов
7.8. Лемма о разрастании для регулярных языков
Вопросы и задачи
 
8. Контекстно свободные языки
8.1. КС-грамматики. Деревья вывода. Однозначность.
8.2.  Приведенная форма КС-грамматики
8.3.  Лемма о разрастании для кс-языков
8.4. Магазинные автоматы
8.5. Алгебраические свойства кс-языков
Вопросы и задачи
 
Список рекомендуемой литературы
Предметный указатель