Наверх

А.Белоус, С.Ткачев, 2003 (Rus)
Дискретная математика. Серия "Математика в техническом университете"

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ
ОСНОВНЫЕ ОБОЗНАЧЕНИЯ


ГЛАВА 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 Графовое представление МП-автоматов
Вопросы и задачи

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ