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

Название: Компьютерная алгебра. Ч. 1. Дискретная математика. Теория алгоритмов: учебное пособие для вузов по направлению подготовки магистров "Системный анализ и управление"
Авторы: Васильев Николай Николаевич; Новиков Федор Александрович
Организация: Санкт-Петербургский государственный политехнический университет
Выходные сведения: Санкт-Петербург, 2011
Коллекция: Учебная и учебно-методическая литература; Общая коллекция
Тематика: Дискретная математика; Вычислительная математика; Алгоритмы; компьютерная алгебра
УДК: 512-37(075.8); 510.5(075.8); 519.1(075.8)
Тип документа: Учебное издание
Тип файла: PDF
Язык: Русский
Права доступа: Свободный доступ из сети Интернет (чтение, печать, копирование)

Разрешенные действия: Прочитать Загрузить (1,4 Мб) Для чтения документа необходим Flash Player

Группа: Анонимные пользователи

Сеть: Локальная сеть ИБК СПбПУ

Аннотация

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

Права на использование объекта хранения

Место доступа Группа пользователей Действие
-> Локальная сеть ИБК СПбПУ Все Прочитать Печать Загрузить
Интернет Все Прочитать Печать Загрузить

Оглавление

  • ВВЕДЕНИЕ
  • 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. Числа Каталана
    • ВЫВОДЫ
  • БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Статистика использования документа

stat Количество обращений: 1694
За последние 30 дней: 17
Подробная статистика