Введение к работе
Актуальность темы. Проблема сравнения вычислительной силы двух модификаций графовых машин - машин Колмогорова - Успенского (МКУ), построенных А.Н.Колмогоровым и В.А.Успенским в 1958 году, и машин с модифицируемой памятью (SMM), предложенных А.Шенхаге в 1970, - в классе реального времени была впервые поставлена А.Шенхаге в 1980 году.
Считается, что МКУ являются более слабой моделью, чем SMM, однако доказать этого до настоящего времени не удалось.
В работе рассматриваются древесные машины, являющиеся модификациями графовых машин, которые могут считаться частными случаями МКУ, и исследуется их вычислительная сила по отношению к SMM.
Древесные машины являются весьма мощным вычислительным инструментом. Они часто используются при решении задач из области структур данных.
Классической задачей теории структур данных является задача построения динамического словаря. Под динамическим словарем понимается множество объектов, называемых ключами, вместе с тремя операциями: поиска, вставки и удаления ключей в словаре.
Стандартной структурой данных для построения динамического словаря являются сбалансированные деревья. В литературе рассматривается три основных вида сбалансированных деревьев. Это АВЛ-деревья (Г.М.Адельсон-Вельский и Е.М.Ландис, 1962), 2-3-деревья (Дж.Хопкрофт, 1970) и В-деревья (Р.Байер, 1972). Все три структуры данных гарантируют логарифмическое время выполнения трех операций для словарей в древесной вычислительной модели.
При построении таких деревьев считается, что все ключи в словаре имеют одинаковый вес (размер, длину), что может приводить к значительной потере памяти при представлении множества ключей переменной длины.
, Динамические словари с ключами переменной длины до настоящего времени систематически не рассматривались. В настоящей работе предлагается новая структура данных, обобщающая 2-3-деревья и В-деревья для случая ключей переменной длины.
Цель работы. Исследовать вычислительную силу древесных машин по отношению к SMM в классе реального времени.
Построить структуру данных, обеспечивающую компактное хранение ключей переменной длины при сохранении логарифмического времени выполнения операций поиска, вставки и удаления ключей.
Научная новизна. В диссертации получены следующие основные результаты.
-
Определены три модификации древесных машин: слабые древесные машины (СлДМ), сильные древесные машины (СиДМ) и древесные машины Тьюринга (ТТМ). Построен язык L запросного типа. Доказано, что L распознается в реальное время на SMM.
-
Показано, что ни одна из трех введенных моделей - СлДМ, СиДМ, ТТМ - не распознает запросный язык в реальное время.
-
Сформулировано два новых условия сбалансированности деревьев, на основании которых определены классы 5(b)-деревьев и >5(6)-деревьев, предназначенные для представления динамических словарей с ключами переменной длины.
-
Исследована взаимосвязь между введенными классами сбалансированных деревьев. В частности показано, что 2-3-деревья и В-деревья являются частными случаями 5(0)-деревьев и 1)5(0)-деревьев, а также установлено, что 5(6)-деревья образуют сжимающуюся иерархию относительно параматра Ь.
-
Определена мера емкостной сложности деревьев Д(Т), называемая заполненностью. Построена нижняя оценка заполненности S(b)- и DS(b)-деревьев, которая показывает, что новые деревья обладают оптимальной заполненностью:
Д(Т) > 1 - є
где г обратно пропорционально Ь.
6. Разработаны логарифмические по времени алгоритмы по
иска, вставки и удаления ключей в словаре. Доказана кор
ректность алгоритмов.
Все основные результаты работы являются новыми, их достоверность подтверждается подробными доказательствами.
Научно-практическая ценность работы. Результаты диссертации могут найти применение в теории алгоритмов (в частности, для построения нижних оценок сложности вычислений), а также в теории структур данных.
Практическое применение сбалансированных деревьев в системах хранения и управления большими объемами данных (в частности, в системах баз данных) позволяет существенно снизить затраты на хранение и использование информации.
Апробация. Материалы диссертации докладывались на ряде семинаров и конференций, в том числе:
на колмогоровском семинаре кафедры математической логики механико-математического факультета МГУ,
на семинаре по теоретической информатике института программных систем РАН,
на 16-м международном симпозиуме "Математические основания информатики" (Mathematical Foundations of Computer Science), 9-13 сентября 1991 года, Казимерш-Дольный, Польша.
на 4-й международной конференции "Теория баз данных" (Database Theory), 14-16 октября 1992, Берлин, Германия.
на международном конгрессе "Компьютерные системы и прикладная математика" (Computer Systems and Applied Mathematics), 19-23 июля 1993 года, Санкт-Петербург.
на XI международной Конференции "Логика, методология и философия науки", 11-15 апреля 1995, Обнинск.
Практическое апробирование алгоритмов для 5(1)-деревьев осуществлено при реализации языка программирования STARSET, в котором проблема поддержки больших упорядоченных множеств играет ключевую роль.
Публикации. Основные результаты диссертации опубликованы в работах 1-5.
Структура диссертации. Диссертация состоит из введения, двух глав и списка литературы из 53 названий. Общий объем диссертации 167 страниц.