Название: Комбинаторные алгоритмы: множества, графы, коды
Автор: Быкова В.В.
Издательство: Красноярск: Сибирский федеральный университет
Год: 2015
Формат: pdf/djvu
Страниц: 152
Для сайта: litgu.ru
Размер: 10 mb
Язык: русский
Рассмотрены машинные способы представления множеств, графов, кодов, важнейшие операции, отношения и алгоритмы. Дана оценка вычислительной сложности алгоритмов.
Предназначено для студентов, обучающихся по направлению 02.03.01 «Математика и компьютерные науки».
Предисловие
Перечисление простейших комбинаторных объектов
Множества: представления и операции
Основные понятия и обозначения
Битовая шкала множества
Теоретико-множественные операции и их реализация битовыми шкалами
Отношения над множествами
Расстояние между множествами
Порядок выполнения задания
Генерация всех подмножеств конечного множества
Формулировка задачи
Счет в двоичной системе счисления
Бинарные коды Грея
Порядок выполнения задания
Пересчет и перечисление сочетаний и перестановок
Определение комбинаторных объектов
Генерация сочетаний
Генерация перестановок
Порядок выполнения задания
Алгоритмы на графах
Графы: представления и операции
Основные понятия и обозначения
Отношения и операции
Родственные графам объекты
Способы машинного представления
Порядок выполнения задания
Базовые задачи и алгоритмы на графах
Обход вершин графа в глубину или ширину
Базовые задачи на графах
Порядок выполнения задания
Построение минимального остова
Формулировка задачи
Алгоритм Краскала
Алгоритм Прима
Некоторые замечания
Порядок выполнения задания
Построение кратчайших путей
Формулировка задачи
Случай неотрицательных весов. Алгоритм Дейкстры
Дерево кратчайших путей
Случай произвольной матрицы весов. Алгоритм Флойда
Кратчайшие контуры и транзитивное замыкание
Порядок выполнения задания
Алфавитное кодирование
Однозначность декодирования
Основные понятия и обозначения
Формулировка задачи
Критерии однозначного декодирования
Порядок выполнения задания
Оптимальное кодирование и сжатие текстов
Средняя длина элементарного кода
Формулировка задачи
Свойства оптимальных кодов
Алгоритм Хаффмена
Сжатие текстов
Порядок выполнения задания
Варианты заданий в конце каждой темы
Библиографический список
Приложения
Алгоритмы и сложность
Выбор представления данных и тестов
Алфавитный указатель