Наверх

С.В. Яблонский, 1986 (Rus)
Введение в дискретную математику

Книга является введением в дискретную математику - раздел прикладной математики, бурно развивающийся в последние годы и являющийся базой для математической кибернетики. Она написана на основе курса лекций, читавшегося автором в течение ряда лет на факультете вычислительной математики и кибернетики Московского государственного университета. Предназначается студентам факультетов прикладной математики, аспирантам, а также инженерам и специалистам, работающим в области прикладной математики


ОГЛАВЛЕНИЕ

ЧАСТЬ 1. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
ГЛАВА 1. АЛГЕБРА ЛОГИКИ
   1. Функции алгебры логики
   2. Формулы. Реализация функций формулами
   3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности
   4 Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
   5. Полнота и замкнутость 
   6. Важнейшие замкнутые классы. Теорема о полноте
   7. Представление о результатах Поста

ГЛАВА  2. k-значная логика
   1. Функции k-эначной логики. Формулы и реализация функций формулами
   2. Примеры полных систем
   3. Распознавание полноты. Теорема о полноте
   4. Некоторые свойства существенных функций. Критерий полноты
   5. Особенности k-значных логик

ГЛАВА 3. Ограниченно-детерминированные (автоматные) функции с операциями
   1. Детерминированные функции
   2. Задание детерминированных функций при помощи деревьев. Вес дерева
   3. Ограниченно-детерминированные функции в способы их задания
   4. Операции над ограниченно-детерминированными функциями
   5. Примеры полных систем
   6. Q соотношений операций С и О

ГЛАВА 4. Вычислимые функция
   1. Машины Тьюринга
   2. Один метод построения машин Тьюринга
   3. Машинные коды и их преобразования
   4. Вычислимые функции
   5. Операции С, Пр и µ
   6. Вычислимые функции и операции С, Пр, µ
   7. Формула Клини. Частичная рекурсивность вычислимых функций. Примеры полных систем


ЧАСТЬ 2. КОМБИНАТОРНЫЙ АНАЛИЗ
   1. Комбинаторные объекты и комбинаторные числа
   2. Простейшие свойства комбинаторных объектов и чисел
   3. Методы изучения комбинаторных объектов и чисел
   4. Оценки и асимптотики для комбинаторных чисел


ЧАСТЬ 3. ГРАФЫ И СЕТИ

ГЛАВА 1. ГРАФЫ
   1. Реализация в евклидовом пространстве. Изоморфизм
   2. Оценка числа графов

ГЛАВА 2. СЕТИ
   1. Сети и их свойства .......... 227
   2. Оценка числа сетей .......... 232
   3. Двухполюсные сети из двухобъектных наборов
   4. ¶-сети


ЧАСТЬ 4. ТЕОРИЯ КОДИРОВАНИЯ

   1. Критерий однозначности декодирования
   2. Алгоритм распознавания однозначности декодирования
   3. Об одном свойстве взаимно однозначных кодов
   4. Коды с минимальной избыточностью
   5. Самокорректирующиеся коды


ЧАСТЬ 5. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ

ГЛАВА 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
   1. Понятие д.н.ф. Проблема минимизации булевых функций 
   2. Упрощение д.н.ф. и тупиковые д.н.ф. (относительно упрощения)
   3. Постановка задачи в геометрической форме
   4. Сокращенная д.п.ф
   5. Тупиковость на основе геометрических представлений. Методы построения тупиковых д.н.ф.
   6. Некоторые однозначно получаемые д.н.ф.
   7. Понятие локального алгоритма

ГЛАВА 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ
   1. Понятие схемы из функциональных элементов
   2. Проблема синтеза схем из Ф.Э.
   3. Элементарные методы синтеза
   4. Нижняя оценка для L(n)
   5. Оптимальный по порядку метод синтеза схем из Ф.Э. (метод Шеннона)
   6. Асимптотически наилучший метод синтеза схем из Ф.Э. (метод Лупанова)
   7. Синтез сумматора
   8. Синтез схем из Ф.Э., реализующих симметрические функции


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