Дискретная математика, Белоусов А.И., Ткачев С.Б., 2004

Дискретная математика, Белоусов А.И., Ткачев С.Б., 2004.

    В девятнадцатом выпуске серии „Математика в техническом университете" изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам.
Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.
Для студентов технических университетов. Может быть полезен преподавателям, аспирантам и инженерам.




АЛГЕБРЫ: ГРУППЫ И КОЛЬЦА.
Предметом рассмотрения в абстрактной алгебре являются произвольные множества с заданными на них операциями. При этом природа множеств и операций может существенно отличаться от привычных числовых множеств и известных операций над числами. Мы уже сталкивались с операциями над множествами и бинарными отношениями (см. 1), которые оказались в чем-то похожими на операции над числами, но в то же время проявились и их существенные отличия.

В дискретной математике разрабатываются алгоритмы и вычислительные методы, позволяющие манипулировать сложно организованными нечисловыми структурами. Проблема работы с такими объектами возникла в связи с развитием современных информационных технологий и переходом от собственно вычислений (т.е. операций над числами) к обработке сложных структур данных. Так, проблемы программирования и машинного перевода привели к задачам работы с языковыми структурами, проблемы автоматизации проектирования — к задачам обработки графических объектов.

Оглавление.
Предисловие.
Основные обозначения.
1. Множества и отношения.
1.1. Множества.
1.2. Кортеж. Декартово произведение.
1.3. Соответствия и бинарные отношения.
1.4. Операции над соответствиями.
1.5. Семейства множеств.
1.6. Специальные свойства бинарных отношений.
1.7. Отношения эквивалентности.
1.8. Упорядоченные множества. Теорема о неподвижной точке.
1.9. Мощность множества.
Д.1.1. Об одном парадоксе теории множеств.
Д.1.2. Метод характеристических функций.
Вопросы и задачи.
2. Алгебры: группы и кольца.
2.1. Операции. Понятие алгебраической структуры.
2.2. Группоиды, полугруппы, группы.
2.3. Кольца, тела, поля.
2.4. Области целостности.
2.5. Модули и линейные пространства.
2.6. Подгруппы и подкольца.
2.7. Теорема Лагранжа.
2.8. Гомоморфизмы групп и нормальные делители.
2.9. Гомоморфизмы колец.
Д.2.1. Кватернионы.
Вопросы и задачи.
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. Построение минимальных ДНФ.
6.7. Теорема Поста.
6.8. Схемы из функциональных элементов.
Вопросы и задачи.
7. Конечные автоматы и регулярные языки.
7.1. Алфавит, слово, язык.
7.2. Порождающие грамматики.
7.3. Классификация грамматик и языков.
7.4. Регулярные языки и регулярные выражения.
7.5. Конечные автоматы. Теорема Клини.
7.6. Детерминизация конечных автоматов.
7.7. Минимизация конечных автоматов.
7.8. Лемма о разрастании для регулярных языков.
Д.7.1. Обоснование алгоритма детерминизации конечных автоматов.
Д.7.2. Конечные автоматы с выходом. Структурный синтез.
Д.7.3. Морфизмы и конечные подстановки.
Д.7.4. Машины Тьюринга.
Вопросы и задачи.
8. Контекстно-свободные языки.
8.1. КС-грамматики. Деревья вывода. Однозначность.
8.2. Приведенная форма КС-грамматики.
8.3. Лемма о разрастании для КС-языков.
8.4. Магазинные автоматы.
8.5. Алгебраические свойства КС-языков.
Д.8.1. О методах синтаксического анализа КС-языков.
Д.8.2. Семантика формальных языков.
Д.8.3. Графовое представление МП-автоматов.
Вопросы и задачи.
Список рекомендуемой литературы.
Предметный указатель.

Купить .





Теги: учебник по математике :: математика :: Белоусов :: Ткачев