это не реальные компьютеры, а теоретические конструкции, использующиеся для доказательства того, что некоторые задачи нельзя решить с помощью алгоритмов. Программы-интерпретаторы в традиционном смысле упоминал в 1946 году Джон Мочли (John Mauchly) в своих лекциях, которые он читал в Школе Мура (Moore School). Самыми известными из первых интерпретаторов, главным назначением которых было обеспечение удобных средств выполнения операций с плавающей точкой, были программы для машины Whirlwind I (разработанные Ч. В. Адамсом (С. W. Adams) и др.) и для машины ИИас I (разработанные Д. Дж. Уилером (D. J. Wheeler) и др.). Тьюринг также принимал участие в их разработке; интерпретирующие системы для компьютера Pilot АСЕ были написаны под его руководством. Более подробно о положении дел с интерпретаторами в начале 50-х годов говорится в статье J. М. Bennett, D. G. Prinz, М. L. Woods, "Interpretative Sub-routines", Proc. ACM Nat. Conf. (1952), 81-87 [см. также различные статьи в журнале Proceedings of the Symposium on Automatic Programming for Digital Computers (1954), издаваемом Департаментом морских исследований (Вашингтон, федеральный округ Колумбия).

Наиболее широкоиспользуемой программой-интерпретатором, вероятно, была "IBM 701 Speedcoding system" Джона Бэкуса (John Backus) [см. JACM 1 (1954), 4-6]. Этот интерпретатор был несколько модифицирован и искусно переписан для IBM 650 В. М. Волонтисом (V. М. Wolontis) и другими из компании Bell Telephone Laboratories; их программа "Bell Interpretive System" приобрела широкую популярность. Интерпретирующие системы IPL, которые были разработаны в начале 1956 года А. Ньювеллом (А. Newell), Дж. К. Шоу (J. С. Shaw) и Г. А. Саймоном (Н. А. Simon) для совершенно других целей (см. раздел 2.6), широко использовались для обработки списков. Как уже упоминалось во введении к разделу 1.4.3, о современных способах применения интерпретаторов в компьютерной литературе, как правило, говорится "на ходу" [см. ссылки на статьи, перечисленные в этом разделе, в которых интерпретаторы обсуждаются более подробно].

Первая программа трассировки была разработана Стэнли Гиллом (Stanley Gill) в 1950 году [см. его интересную статью в журнале Proceedings of the Royal Society of London, series A, 206 (1951), 538-554]. В упомянутой выше книге Уилкса, Уилера и Гилла содержится несколько программ трассировки. Наверное, самая интересная из них - это подпрограмма С-10, написанная Д. Дж. Уилером, в которой предусмотрена возможность, позволяющая приостановить трассировку при входе в библиотечную подпрограмму, выполнить эту подпрограмму на полной скорости, а затем продолжить трассировку. Информация о программах трассировки довольно редко публикуется в общей компьютерной литературе. Это обусловлено, главным образом, тем, что данные методы по своей природе ориентированы на конкретную машину. Автору известна только одна ранняя работа на эту тему - статья Н. V. Meek, "An Experimental Monitoring Routine for the IBM 705", Proc. Western Joint Computer Conf (1956), 68-70. В ней обсуждается программа трассировки для машины, на которой было чрезвычайно трудно решить одну задачу. В настоящее время внимание к программам трассировки сместилось в сторону программ, обеспечивающих выборочный вывод результатов и оценок производительности программы; одна из лучших подобных систем была разработана Э. Сэттерсвейтом (Е. Satterthwaite) и описана в журнале Software Practice & Experience 2 (1972), 197-217.

Буферизация первоначально выполнялась аппаратным способом, аналогично тому, как это делалось в программе 1.4.4-(3). Внутренняя буферная область, недо-

ступная для программиста, играла роль ячеек 2000-2099, и команды 1.4.4-(3) выполнялись неявно и незаметно, когда выдавалась команда ввода. В конце 40-х годов первые программисты UNJVAC разработали программные методы буферизации, которые особенно полезны для сортировки (см. раздел 5.5). Хороший обзор основных принципов В/В, преобладавших в 1952 году, можно найти в Трудах конференции Восточного компьютерного объединения, которая проводилась в 1952 году.

В компьютере DYSEAC [Alan L. Leiner, JACM 1 (1954), 57-81] была реализована идея непосредственной передачи информации между устройствами ввода-вывода и памятью во время работы программы, а затем прерывания программы по ее завершении. Из существования подобных систем следует, что для них были разработаны алгоритмы буферизации, но подробности не были опубликованы. В первой опубликованной работе о методах буферизации в том смысле, в котором мы их описали, представлен крайне сложный подход к этой проблеме [см. О. Моек, С. J. Swift, "Programmed Input-Output Buffering", Proc. ACM Nat. Conf. (1958), paper 19, и JACM 6 (1959), 145-151]. (Должен предупредить читателя о том, что в обеих статьях широко используется местный жаргон, для понимания которого придется потратить некоторое время, но вам помогут в этом другие статьи из журнала JACM 6.) Система прерывания, которая позволяла осуществлять буферизацию ввода и вывода, была независимо разработана Э. В. Дейкстрой (Е. W. Dijkstra) в 1957 и 1958 годах для компьютера X - 1, созданного Б. Ж. Лупстрой (В. J. Loopstra) и К. С. Шолтеном (С. S. Scholten) [см. Сотр. J. 2 (1959), 39-43]. В докторской диссертации Дейкстры, "Communication with an Automatic Computer"* (1958), обсуждаются методы буферизации, которые в данном случае были рассчитаны на очень длинные кольца буферов, в то время как в программах рассматривался, в основном, В/В на перфоленты и терминал. В каждом буфере содержался либо один символ, либо одно число. Впоследствии Дейкстра развил эти идеи и пришел к важному общему понятию семафоров, которые лежат в основе управления параллельными процессами любого вида, а не только вводом-выводом [см. Programming Languages, ed. by F. Genuys (Academic Press, 1968), 43-112; BIT 8 (1968), 174-186; Acta Infor-matica 1 (1971), 115-138]. В статье David E. Ferguson, "Input-Output Buffering and FORTRAN", JACM 7 (1960), 1-9, рассматриваются буферные кольца и приводится подробное описание простой буферизации для многих устройств одновременно.

как представляется, примерно 1 ООО команд-это разумный верхний предел сложности задач.

- ГЕРМАН ГОЛДСТАЙН (HERMAN GOLDSTINE) и ДЖОН ФОН НЕЙМАН (JOHN VON NEUMANN) (1946)

"Связь с помощью автоматического компьютера". - Прим. перев.

ГЛАВА 2

ИНФОРМАЦИОННЫЕ СТРУКТУРЫ

Нет, не увижу, это ясно. Поэмы, дерева прекрасней.

ДЖОЙС КИЛМЕР (JOICE KILMER) (1913) (Перевод Л. Макаровой)

Ах, я с таблицы памяти моей Все суетные записи сотру.

- Гамлет (акт I, сцена 5, строка 98) (Перевод м. Лозинского)

2.1. ВВЕДЕНИЕ

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

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

В более сложных случаях таблица может иметь структуру двумерного массива (т. е. матрицы или решетки, состоящей из строк и столбцов) или даже п-мерного массива для п больше 2, древовидную структуру (tree structure) , которая представляет иерархические или разветвляющиеся связи, либо такую сложную многосвязную структуру (multilinked structure) с большим количеством соединений, которая устроена, как человеческий мозг.

Для правильного использования компьютера необходимо хорошо знать структурные взаимосвязи между данными, основные методы представления структур внутри компьютера, а также методы работы с ними.

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