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