Комбинаторные алгоритмы: множества, графы, коды
ПРЕДИСЛОВИЕ ПЕРЕЧИСЛЕНИЕ ПРОСТЕЙШИХ КОМБИНАТОРНЫХ ОБЪЕКТОВЗАДАНИЕ 1 Множества: представления и операции Основные понятия и обозначения Битовая шкала множества Теоретико-множественные операции и их реализация битовыми шкалами Отношения над множествами Расстояние между множествами Порядок выполнения задания ВариантыЗАДАНИЕ 2 Генерация всех подмножеств конечного множества Формулировка задачи Счет в двоичной системе счисления Бинарные коды Грея Порядок выполнения задания ВариантыЗАДАНИЕ 3 Пересчет и перечисление сочетаний и перестановок Определение комбинаторных объектов Генерация сочетаний Генерация перестановок Порядок выполнения задания Варианты АЛГОРИТМЫ НА ГРАФАХЗАДАНИЕ 4 Графы: представления и операции Основные понятия и обозначения Отношения и операции Родственные графам объекты Способы машинного представления Порядок выполнения задания ВариантыЗАДАНИЕ 5 Базовые задачи и алгоритмы на графах Обход вершин графа в глубину или ширину Базовые задачи на графах Порядок выполнения заданияЗАДАНИЕ 6 Построение минимального остова Формулировка задачи Алгоритм Краскала Алгоритм Прима Некоторые замечания Порядок выполнения задания ВариантыЗАДАНИЕ 7 Построение кратчайших путей Формулировка задачи Случай неотрицательных весов. Алгоритм Дейкстры Дерево кратчайших путей Случай произвольной матрицы весов. Алгоритм Флойда Кратчайшие контуры и транзитивное замыкание Порядок выполнения задания Варианты АЛФАВИТНОЕ КОДИРОВАНИЕЗАДАНИЕ 8 Однозначность декодирования Основные понятия и обозначения Формулировка задачи Критерии однозначного декодирования Порядок выполнения задания ВариантыЗАДАНИЕ 9 Оптимальное кодирование и сжатие текстов Средняя длина элементарного кода Формулировка задачи Свойства оптимальных кодов Алгоритм Хаффмена Сжатие текстов Порядок выполнения заданияБИБЛИОГРАФИЧЕСКИЙ СПИСОК
