Перейти к списку | Аннотация | Содержание

Дискретная математикаАннотация

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

Содержание

Предисловие
Основные обозначения
 
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.  Алгебраические свойства кс-языков
  Вопросы и задачи
 
Список рекомендуемой литературы
Предметный указатель