Из методических coq6pameHHii мы, в основном, сконцентрировали свое внимание на связях между информационными структурами и их компьютерным представлением, а не рассматривали эти вопросы по отдельности. Однако для углубленного понимания полезно рассмотреть предмет с более абстрактной точки зрения, отделив идеи, которые могут быть изучены самостоятельно. Был разработан ряд достойных внимания подходов такого типа; особо могут быть рекомендованы для ознакомления следующие ранние работы: G. Mealy, "Another look at data", Proc. AFIPS Fall Joint Computer Conf. 31 (1967), 525-534; J. Earley, "Toward an understanding of data structures", CACM 14 (1971), 617-627; C. A. R. Hoare, "Notes on data structuring", in Structured Programming by O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare (Academic Press, 1972), 83-174; Robert W. Engles, "A tutorial on data-base organization". Annual Review in Automatic Programming 7 (1972), 3-63.

Материал этой главы не охватывает предмет информационных структур во всей полноте. Как минимум не рассматривались три важных вопроса.

a) Часто необходимо найти узел (или множество узлов, обладающих некоторым значением) в таблице. Такая операция нередко оказывает серьезное влияние на структуру таблицы. Этот вопрос детально описывсьется в главе 6.

b) В основном, нами рассматривалось внутреннее представление структур в компьютере; однако это всего лишь одна часть темы, поскольку структуры должны быть также представлены как внешние входные или выходные данные. В простых случаях с внешними структурами можно работать, по сути, при помощи тех же технологий, которые были здесь рассмотрены. Однако очень важен процесс преобразования строк символов в более сложные структуры и обратно. Такие процессы анализируются в главах 9 и 10.

c) В основном, в главе обсуждалось представление структур данных в высокоскоростной памяти с произвольным доступом. При использовании медленных устройств, таких как диски и ленты, все структурные проблемы обостряются и все более важными становятся эффективные алгоритмы и эффективные схемы представления данных. Узлы, связанные один с другим, в этих случаях должны располагаться в близких областях памяти. Обычно эти проблемы трудно обсуждать в общем виде, так как они сильно зависят от характеристик конкретных машин. Простейшие примеры из этой главы должны помочь читателю подготовиться к решению сложных проблем, возникающих в связи с использованием менее идеальных устройств хранения информации. Некоторые из этих проблем детально обсуждаются в главах 5 и 6.

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

Поэтому представляется разумным продолжить разработку теории о связанных множествах узлов по сравнению с тем, что известно в настоящее время. Возможно,

наиболее очевидный путь создания такой теории состоит в определении нового вида абстрактной машины или "автомата" для работы со связанными структурами. Например, подобное устрой&тво может быть неформально определено следующим образом. Имеются числа к, I, г и s, такие, что автомат обрабатывает узлы, содержащие к полей связи и г информационных полей. Он имеет / регистров связи и s информационных регистров, обеспечивающих управление выполняемыми процессами. Информационные поля и регистры могут содержать любые символы из некоторого заданного набора информационных символов. Каждое из полей связи и регистров связи содержит либо Л, либо указатель на узел. Машина может (i) создавать новые узлы (помещая связи с узлом в регистр), (ii) проверять равенство символов или значений связей и (iii) переносить инфор.мационные символы или значения связей между регистрами и узлами. Непосредственно доступны то.тько узлы, на которые указывают регистры связей. Соответствующие ограничения на поведение машины делают ее эквивалентом ряда других видов автоматов.

Аналогичная модель вычислений была предложена А. Н. Колмогоровым в 1952 году. Его машина, по сути, работала с графом G, имеющим специально созданную стартовую вершину vq. Действия на каждом шаге зависят только от подграфа G, состоящего из всех вершин на расстоянии < п от fo в G, и заключаются в замещении G в G другим графом G" = f{G), где G" включает vo и вершины на расстоянии, в точности равном п от wq, и, возможно, другие (вновь созданные) верип1ны. Остаток графа G является неизменным. Здесь п - фиксированное число, определяющееся отдельно для каждого конкретного алгоритма, которое может быть произвольно большим. Каждой вершине назначается символ из некоторого конечного алфавита с тем ограничением, что у вершины не может быть двух соседних вершин с одинаковыми символами. (См. А. Н. Колмогоров, Успехи мат. наук 8,4 (1953), 175-176; Колмогоров и Успенский, Успехи мат. наук 13,4 (1958), 3-28; Атег. Math. Soc. Translations, series 2, 29 (1963), 217-245.)

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

Самыми интересными проблемами, которые предстоит решить для такого рода устройств, являются определение скорости решения поставленных ими задач, т. е. подсчет количества узлов, требуемых для решения той или иной задачи (например, для трансляции какого-либо формального языка). В то время, когда автор приступил к работе над настоящей главой, были получены интересные результаты такого рода (отметим работы Ю. Хартманиса (J. Hartmanis) и Р. Э. Стирнса (R. Е. Stearns)), но только для специальных классов машин Тьюринга с множеством лент и головок чтения/записи. Модель машины Тьюринга сравнительно нереальна, а потому полученные результаты имеют мало общего с решением практических задач.

Следует признать, что при стремлении количества созданных связывающим автоматом узлов п к бесконечности неизвестно, как построить такое устройство фи-

зически, поскольку желательно, чтобы операции машины вьгаолнялись за одно и то же время независимо от размера п. Если связывание представлено с использованием адресов в машинной пяти, необходимо определить границу для количества узлов, поскольку поля связей имеют фиксированный размер. Многоленточная машина Тьюринга поэтому представляет собой более реалистичную модель при стремлении п к бесконечности. Представляется также обоснованной уверенность в том, что описанные выше связывающие автоматы приведут к созданию более приемлемой теории сложности алгоритмов, чем машина Тьюринга, даже при рассмотрении асимптотических формул для больших п, так как эта теория больше подходит для практических значений п. Кроме того, когда п станоаится больше, чем Ю" или около того, даже сщясшенточная машина Тьюринга не явлиется реалистичной; она никогда не будет построена. Принципы важнее реалий.

Со времени первого написания автором большинства из приведенных выше комментариев утекло много воды, и можно порадоваться, что в теории связывающих автоматов (сегодня называемых машинами указателей (pointer machtnes)] достигнут определенный прогресс, хотя, конечно же, предстоит еще немало сделать в этой области.

Разработаны общие принципы программирования.

Большинство из них давно использувтся нз станции Канзас-Сортировочная...

- ДЕРРИК ЛЕМЕР (DERRICK LEHMER) {1Э49)

Я уверен, вы согласитесь со мноИ ... что если со страницей 534 мы встречаемся только во второй главе, то первая глава должна быть невыносимо длинной.

- ШЕРЛОК ХОЛМС (SHERLOCK HOLMES). Аллея страха {Ttre Valley of Fear) (1388)