Перейти к списку | Аннотация | Содержание
Аннотация
В девятнадцатом выпуске серии «Математика в техническом университете» изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам.
Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.
Для студентов технических университетов. Может быть полезен преподавателям и аспирантам.
Содержание
| Предисловие | ||
| Основные обозначения | ||
| 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. | Алгебраические свойства кс-языков | |
| Вопросы и задачи | ||
| Список рекомендуемой литературы | ||
| Предметный указатель | ||