Детальная информация

Рассматриваются основные понятия дискретной математики, которая имеет широкий спектр приложений, прежде всего в областях, связанных с информационными технологиями и компьютерами. Важнейшими приложениями дискретных структур в программировании являются компьютерная алгебра и вычислительная геометрия. Основу рассмотрений составляет теория алгоритмов. Именно этот круг тем освещает данное пособие.

• ВВЕДЕНИЕ
• 1. МНОЖЕСТВА И ОТНОШЕНИЯ
  • 1.1. МНОЖЕСТВА
    • 1.1.1. Элементы и множества
    • 1.1.2. Задание множеств
    • 1.1.3. Парадокс Рассела
    • 1.1.4. Мультимножества
  • 1.2. АЛГЕБРА ПОДМНОЖЕСТВ
    • 1.2.1. Сравнение множеств
    • 1.2.2. Равномощные множества
    • 1.2.3. Конечные и бесконечные множества
    • 1.2.4. Добавление и удаление элементов
    • 1.2.5. Мощность конечного множества
    • 1.2.6. Операции над множествами
    • 1.2.7. Разбиения и покрытия
    • 1.2.8. Булеан
    • 1.2.9. Свойства операций над множествами
  • 1.3. ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ В ПРОГРАММАХ
    • 1.3.1. Битовые шкалы
    • 1.3.2. Генерация всех подмножеств универсума
    • 1.3.3. Алгоритм построения бинарного кода Грея
    • 1.3.4. Представление множеств упорядоченными списками
    • 1.3.5. Проверка включения слиянием
    • 1.3.6. Вычисление объединения слиянием
    • 1.3.7. Вычисление пересечения слиянием
    • 1.3.8. Представление множеств итераторами
  • 1.4. ОТНОШЕНИЯ
    • 1.4.1. Упорядоченные пары и наборы
    • 1.4.2. Прямое произведение множеств
    • 1.4.3. Бинарные отношения
    • 1.4.4. Композиция отношений
    • 1.4.5. Степень отношения
    • 1.4.6. Свойства отношений
    • 1.4.7. Ядро отношения
  • 1.5. ПРЕДСТАВЛЕНИЕ ОТНОШЕНИЙ В ПРОГРАММАХ
    • 1.5.1. Представление бинарных отношений булевыми матрицами
    • 1.5.2. Замыкания отношений
    • 1.5.3. Алгоритм Уоршалла
  • 1.6. ФУНКЦИИ
    • 1.6.1. Функциональные отношения
    • 1.6.2. Инъекция, сюръекция и биекция
    • 1.6.3. Образы и прообразы
    • 1.6.4. Суперпозиция функций
    • 1.6.5. Представление функций в программах
  • 1.7. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ
    • 1.7.1. Классы эквивалентности
    • 1.7.2. Фактормножества
    • 1.7.3. Ядро функционального отношения и множества уровня
  • 1.8. ОТНОШЕНИЯ ПОРЯДКА
    • 1.8.1. Определения отношений упорядоченности
    • 1.8.2. Минимальные и наименьшие элементы
    • 1.8.3. Алгоритм топологической сортировки
    • 1.8.4. Верхние и нижние границы
    • 1.8.5. Монотонные и непрерывные функции
    • 1.8.6. Наименьшая неподвижная точка функции
    • 1.8.7. Вполне упорядоченные множества
    • 1.8.8. Индукция
  • ВЫВОДЫ
• 2. ВЫЧИСЛИМОСТЬ И СЛОЖНОСТЬ
  • 2.1. ИНТУИТИВНАЯ ВЫЧИСЛИМОСТЬ
    • 2.1.1. Частичные функции
    • 2.1.2. Невычислимые функции
  • 2.2. РЕКУРСИЯ
    • 2.2.1. Простейшие функции
    • 2.2.2. Элементарные операции над частичными функциями
    • 2.2.3. Лемма об индуктивных определениях
  • 2.3. МАШИНА С НЕОГРАНИЧЕННЫМИ РЕГИСТРАМИ
    • 2.3.1. Описание МНР
    • 2.3.2. Вычисление на МНР
    • 2.3.3. Разрешимые предикаты
    • 2.3.4. Вычислимость в других областях
  • 2.4. ОПЕРАТОР МИНИМИЗАЦИИ
    • 2.4.1. Определения
    • 2.4.2. Частично рекурсивные функции
    • 2.4.3. МНР-вычислимость частично-рекурсивных функций
    • 2.4.4. Тезис Чёрча
  • 2.5. ВЫЧИСЛИМОСТЬ ПО ТЬЮРИНГУ
    • 2.5.1. Определение машины Тьюринга
    • 2.5.2. Языки, распознаваемые машиной Тьюринга
    • 2.5.3. Универсальная машина Тьюринга
    • 2.5.4. Меры сложности алгоритмов
    • 2.5.5. Функции, вычислимые по Тьюрингу
    • 2.5.6. Функция Аккермана
  • 2.6. ПЕРЕЧИСЛИМЫЕ И РАЗРЕШИМЫЕ МНОЖЕСТВА
    • 2.6.1. Перечислимые множества
    • 2.6.2. Разрешимые множества
    • 2.6.3. Диофантовы множества
    • 2.6.4. Полиномиальное представление множеств
  • 2.7. МЕРЫ СЛОЖНОСТИ
    • 2.7.1. Недетерминированные вычисления
    • 2.7.2. Детерминированное моделирование НМТ
    • 2.7.3. Классы P и NP
  • ВЫВОДЫ
• 3. АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ
  • 3.1. ОПЕРАЦИИ И АЛГЕБРЫ
    • 3.1.1. Алгебраические структуры
    • 3.1.2. Замыкания и подалгебры
    • 3.1.3. Системы образующих
    • 3.1.4. Свойства операций
  • 3.2. МОРФИЗМЫ
    • 3.2.1. Гомоморфизмы
    • 3.2.2. Изоморфизмы
  • 3.3. ПОЛУГРУППЫ И МОНОИДЫ
    • 3.3.1. Полугруппы
    • 3.3.2. Определяющие соотношения
    • 3.3.3. Моноиды
  • 3.4. ГРУППЫ
    • 3.4.1. Определение и основные свойства
    • 3.4.2. Гомоморфизмы групп
    • 3.4.3. Ядро и образ
    • 3.4.4. Нормальные делители и факторгруппы
    • 3.4.5. Теорема о гомоморфизме
    • 3.4.6. Действие группы на множестве
    • 3.4.7. Группа перестановок
    • 3.4.8. Простые группы
    • 3.4.9. Свободная группа
    • 3.4.10. Прямое произведение групп
  • 3.5. КАТЕГОРИИ И ФУНКТОРЫ
    • 3.5.1. Определение категории
    • 3.5.2. Свойства морфизмов
    • 3.5.3. Функторы
    • 3.5.4. Прямое произведение
    • 3.5.5. Прямая сумма
    • 3.5.6. Единственность сумм и произведений
  • 3.6. КОЛЬЦА И ПОЛЯ
    • 3.6.1. Кольца
    • 3.6.2. Области целостности
    • 3.6.3. Поля
    • 3.6.4. Гомоморфизмы колец
    • 3.6.5. Идеалы
    • 3.6.6. Факторкольца
    • 3.6.7. Прямые произведения колец
    • 3.6.8. Простые и максимальные идеалы
  • 3.7. ВЕКТОРНЫЕ ПРОСТРАНСТВА И МОДУЛИ
    • 3.7.1. Векторное пространство
    • 3.7.2. Свойства нуль-вектора
    • 3.7.3. Линейные комбинации
    • 3.7.4. Базис и размерность
    • 3.7.5. Модули
    • 3.7.6. Прямая сумма модулей
  • 3.8. РЕШЕТКИ
    • 3.8.1. Операции решётки
    • 3.8.2. Ограниченные решетки
    • 3.8.3. Решетка с дополнением
    • 3.8.4. Частичный порядок в решетке
    • 3.8.5. Булевы алгебры
  • 3.9. КОМПЬЮТЕРНАЯ АЛГЕБРА
    • 3.9.1. Системы компьютерной алгебры
    • 3.9.2. Длинные целые
    • 3.9.3. Длинные рациональные
    • 3.9.4. Представления полиномов
    • 3.9.5. Представление выражений
  • ВЫВОДЫ
• 4. КОМБИНАТОРИКА
  • 4.1. КОМБИНАТОРНЫЕ ЗАДАЧИ
    • 4.1.1. Комбинаторные конфигурации
    • 4.1.2. Размещения
    • 4.1.3. Размещения без повторений
    • 4.1.4. Перестановки
    • 4.1.5. Сочетания
    • 4.1.6. Сочетания с повторениями
  • 4.2. ПЕРЕСТАНОВКИ
    • 4.2.1. Циклы в перестановках
    • 4.2.2. Инверсии
    • 4.2.3. Генерация перестановок
    • 4.2.4. Двойные факториалы
  • 4.3. БИНОМИАЛЬНЫЕ КОЭФФИЦИЕНТЫ
    • 4.3.1. Элементарные тождества
    • 4.3.2. Бином Ньютона
    • 4.3.3. Свойства биномиальных коэффициентов
    • 4.3.4. Треугольник Паскаля
    • 4.3.5. Генерация подмножеств
    • 4.3.6. Мультимножества и последовательности
    • 4.3.7. Мультиномиальные коэффициенты
  • 4.4. РАЗБИЕНИЯ
    • 4.4.1. Числа Стирлинга второго рода
    • 4.4.2. Числа Стирлинга первого рода
    • 4.4.3. Число Белла
  • 4.5. ВКЛЮЧЕНИЯ И ИСКЛЮЧЕНИЯ
    • 4.5.1. Объединение конфигураций
    • 4.5.2. Формула включений и исключений
    • 4.5.3. Число булевых функций, существенно зависящих от всех своих переменных
  • 4.6. ФОРМУЛЫ ОБРАЩЕНИЯ
    • 4.6.1. Теорема обращения
    • 4.6.2. Формулы обращения для биномиальных коэффициентов
    • 4.6.3. Формулы для чисел Стирлинга
  • 4.7. ПРОИЗВОДЯЩИЕ ФУНКЦИИ
    • 4.7.1. Основная идея
    • 4.7.2. Метод неопределённых коэффициентов
    • 4.7.3. Числа Фибоначчи
    • 4.7.4. Числа Каталана
  • ВЫВОДЫ
• БИБЛИОГРАФИЧЕСКИЙ СПИСОК