Введение к работе
Актуальность темы- Вопрос о представлении комбинаторных объектов является главным в проблеме структуризации данных, которая составляет основу любых комбинаторных вычислений. Графы принято относить к наиболее сложным комбинаторным объектам. В диссертации рассматривается проблема представления графов в традиционной для теории кодирования постановке: представление словами в конечном алфавите.
Одним из главных аспектов проблемы кодирования является оптимизация длины кода. При этом выделяют два основных направления исследований данной проблемы.
Первое направление связано с поиском оптимальных представлений для графов из некоторых специальных классов. В диссертации данный вопрос рассматривается для графов из наследственных классов с нулевой энтропией. Алексеевым В.Е. предложен алгоритм универсального кодирования, асимптотичэски оптимальный для любого наследственного класса с ненулевой энтропией. Однако, асимптотическая оптимальность данного алгоритма не распространяется на классы графов с энтропией равной нулю. Для этих классов известны лишь отдельные примеры оптимальных кодирований. Вместе с тем, семейство этих классов весьма представительно, оно континуально и включает такие известные классы как леса, планарные, интервальные графы и многие другие. Эти классы интересны как с практической, так и с теоретической точек зрения, им посвящена обширная литература. Таким образом, разработка специальных методов кодирования для графов из этих классов представляет собой актуальнр проблему.
Второе направление исследований относится к изучению различных методов кодирования и поиску областей оптимальности для них.
Поскольку для любого метода область оптимальности ограничена, актуальным является вопрос об изучении некоторого представительного семейства кодирований. В качестве такого семейства в диссертации рассматривается класс вершинных кодирований. Он включает такие известные представления как матрица инцидентности, векторные представления, графы пересечений и многие другие.
Цель работы. Целью работы является исследование и разработка методов оптимального кодирования графов из наследственных классов.
Научная новизна- Научная новизна работы определяется как постановкой задач, так и полученными результатами. Традиционно проблема кодирования рассматривается относительно некоторого класса графов либо некоторого способа представления. В настоящей работе поставлен вопрос о систематическом изучении данной проблемы применительно к континуальному семейству наследственных классов графов (классов с нулевой энтропией) и семейству кодирований (вершинных кодирований). В диссертации исследованы представительные фрагменты этих семейств.
Теоретическая и практическая ценность работы. Теоретическую основу проблемы оптимизации кодирования- составляет разработка эффективных методов кодирования, достигающих мошностной границы сжатия. Для методов, описанных в диссертации, эта граница достигается в асимптотическом смысле либо го порядку. Применительно к наследственным классам с ненулевой энтропией эти метода улучшают известное универсальное кодирование, а для представительного семейства классов с нулевой энтропией данный вопрос решен впервые.
Разработка методов оптимального кодирования основана на исследовании структурных свойств графов, что имеет самостоятельное теоретическое значение.
Все описанные в диссертации методы кодирования могут быть использованы в практической вычислительной деятельности.
Апробация работы- Основные результаты диссертационной работы докладывались на семинарах кафедры математической логики и высшей алгебры факультета ВМК ННГУ и 3 отдела НИИ ПМК при ННГУ. на Всесоюзных конференциях по теоретической кибернетике (Нижний Новгород, 1988 г., Саратов 1993 г.), на 1-ой Международной конференции "Математические алгоритмы" (Нижний Новгород.1994 г.). на xvi цикле расширенных заседаний Одесского научно-исследовательского семинара по дискретной математике, посвященного теории графов и гиперграфов (Одесса.1994 г.). на межгосударственной школе-семинаре "Синтез и сложность управляющих систем" (Нижний Новгород. 1994 г.). на 3-ей конкурсной конференции факультета ВМК ННГУ (1995 г.). на 5-ом межгосударственном семинаре по дискретной математике и ее приложениями (Москва, 1995 г.).
Публикации. По теме диссертации опубликовано 8 работ.
Структура и объем работы. Диссертация состоит из введения, дар глав и списка литературы. Общий объем работы - 102 машинописные страницы, библиография - 44 наименования.
