Главная Промышленная автоматика.

1.21. Выполните процедуру ВЗАИМОЗАМЕНА из разд. 1.8 с фактическими параметрами i и АШ, используя сначала вызов по наименованию, а затем вызов по ссылке. Будут ли результаты одинаковы?

Проблема для исследования

1.22. Можно ли улучшить верхнюю оценку О (Г? (л)) времени моделирования РАМ машиной Тьюринга, как в теореме 1.3?

Замечания по литературе

РАМ и РАСП получили формальную трактовку у Шепердсона, Стерджиса 11963], Элгота, Робинсона [1964 и Хартманиса [1971]. В изложении большей части результатов о РАМ и РАСП в этой главе мы следуем работе Кука, Рекхау [1973].

Идея машины Тьюринга принадлежит Тьюрингу [1936]. Более подробное изложение этого понятия можно найти у Минского [1967] и Хопкрофта, Ульмана [1969]; это же касается и ответа к упр. 1.8. Изучение временной сложности машин Тьюринга было начато Хартманисом, Стирнзом [1965], а емкостной сложности- Хартманисом, Льюисом, Стирнзом [1965] и Льюисом, Стирнзом, Хартманисом [1965] ). Начиная с работы Блюма [1967], делались попытки трактовать вычислительную сложность с гораздо более абстрактной точки зрения. Обзоры можно найти у Хартманиса, Хопкрофта [1971] и Бородина [1973а].

Рабий [1972] предложил одно интересное обобщение понятия дерева решений.

*) В СССР первые работы, в которых изучались временная и емкостная сложности (для моделей, отличных от рассматриваемых в гл. 1), были выполнены в 1956 г. Г. С. Цейтиным (см. С. А. Яновская. Математическая логика и основания математики. Математика в СССР за 40 лет, т. 1, М., Физматгиз, 1959, 44-45) и Трахтенбротом [1956].- Прим. перев.



РАЗРАБОТКА

ЭФФЕКТИВНЫХ АЛГОРИТМОВ

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

В гл. 1 мы рассмотрели основные модели вычислений. Хотя нашей простейшей моделью является РАМ, мы не хотим, как правило, описывать алгоритмы в терминах подобного устройства. Поэтому мы ввели Упрощенный Алгол (разд. 1.8). Но даже этот язык оказывается слишком примитивным, если не ввести в рассмотрение структуры данных, более сложные, чем массивы. В этой главе мы познакомим читателя с такими элементарными структурами данных, как списки и стеки; они часто используются в эффективных алгоритмах. Мы покажем, что с помощью этих структур можно представлять множества, графы и деревья.

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

Мы включили также раздел о рекурсии. Один из важных аспектов рекурсии - облегчить понимание алгоритмов. Хотя примеры, приводимые в этой главе, слишком просты, чтобы полностью подтвердить это заявление, но в последующих главах рекурсия очень поможет в учете организации информации при точном изложении сравнительно сложных алгоритмов. Рекурсия сама по себе не приводит к более эффективным алгоритмам. Но в сочетании с другой техникой, такой, как балансировка, прием "разделяй и властвуй", алгебраические упрощения, она, как мы увидим, часто дает алгоритмы, одновременно и эффективные, и элегантные.



2.1. СТРУКТУРЫ ДАННЫХ: СПИСКИ, ОЧЕРЕДИ И СТЕКИ

А\ы считаем, что читатель знаком с элементарными понятиями математики (такими, как множества и отношения) и основными типами данных - целыми числами, цепочками (словами) и массивами. В этом разделе мы дадим краткий обзор основных операций над списками.

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

Рассмотрим список

Элем 1, Элем 2, Элем 3, Элем 4. (2.1)

Простейшей его реализацией будет структура последовательно связанных компонент, изображенная на рис. 2.1. Каждая компонента в этой структуре состоит из двух ячеек памяти. Первая ячейка содержит сам элемент ), вторая - указатель следующего элемента. Это можно реализовать в виде двух массивов, которые на рис. 2.2 названы ИМЯ и СЛЕДУЮЩАЯ Если КОМПОНЕНТА - индекс в рассматриваемом массиве, то ИМЯI КОМПОНЕНТА]- сам элемент, хранящийся там, а СЛЕДУЮЩАЯ [КОМПОНЕНТА]- индекс следующего элемента в списке (если такой элемент существует). Если КОМПОНЕНТА - индекс последнего элемента в этом списке, то СЛЕДУЮЩАЯ[КОМПОНЕНТА]=0.

На рис. 2.2 СЛЕДУЮЩАЯЮ] означает постоянный указатель на первую компоненту в списке. Заметим, что порядок элементов в

ПЕРВЫЙ»-

Рлем 1

Элем 2

Элем 3

Элем 4

Рис. 2.1. Список со связями.

) Если, этот элемент сам является сложной структурой, то первая ячейка может содержать указатель ее местоположения.

) Другая (и эквивалентная) точка зрения такова: имеется «клетка» для каждой компоненты. Каждая «клетка» обладает адресом, который представляет собой номер первого (возможно, единственного) регистра памяти в группе регистров, зарезервированных для этой компоненты. Внутри каждой клетки находится одно или более «полей». У нас полями служат ИМЯ н СЛЕДУЮЩАЯ, а ИМЯ[КОМ-ПОНЕНТА] и СЛЕДУЮШ,АЯ[КОМПОНЕНТА] играют роль имен этих полей в клетке с адресом КОМПОНЕНТА.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 [15] 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0039