умножения целых чисел, 269 уплотнения памяти, 356 эквивалентности, 160 Запись, 17 активационная, 61; 338 закрепленная, 316

Индекс

вторичный, 321

плотный, 320

разреженный, 319 Инкапсуляция, 14; 29 Исключение рекурсий, 62

полное, 62

Каталана числа, 266 Классы эквивалентности, 160 Коды Хаффмана, 84 Конечный автомат, 173 Конкатенация списков, 240 Корень

ациклического орграфа, 198

дерева, 69 Крускала алгоритм, 206 Курсор, 17 Куча, 236; 331

Лексикографический порядок, 244 Лес, 86

глубинный остовный, 190; 209 остовный, 190 Лист дерева, 70

Матрица

кратчайших путей, 188

смежности, 176; 202 Медиана, 250 Метод

альфа-бета отсечения, 287 близнецов, 351; 360 близнецов к-го порядка, 352 близнецов с числами Фибоначчи, 352 близнецов экспоненциального типа, 351

ветвей и границ, 288 декомпозиции, 268; 271

линейный нахождения порядковых

статистик, 251

поиска в глубину, 188; 209

поиска в ширину, 210

последовательного сдвига регистра, 119

сжатия путей, 165

чередующихся цепей, 215 Методы

анализа алгоритмов, 257

разработки алгоритмов, 268 Минимальный эквивалентный орграф, 199

Многоканальное слияние, 309 Множества

объединение, 96

пересечение, 96

разность, 96

слияние, 97 Множество, 95

атом, 95

линейно упорядоченное, 95 определение, 95

представление посредством 2-3 дерева, 157

представление посредством сбалансированного дерева, 150 пустое, 96 реализации, 101

реализация посредством двоичного вектора, 101

реализация посредством связанных списков, 102

с операторами MERGE и FIND, 159 универсальное, 101 •шаблон, 96 элемент, 95 Мода, 255

Морриса алгоритм, 357 Мультисписки, 131

Нагрркенное дерево, 173 представление узлов посредством списков, 148 узлы, 146

эффективность, 149 Наибольшая обшая подпоследовательность, 167 Наибольший обший делитель, 33 НОП. См. Наибольшая обшая подпоследовательность Нумерация глубинная, 191

Обход неориентированного графа, 209 Обход дерева

в обратном порядке, 71

в порядке уровней, 93

в прямом порядке, 71

в симметричном (внутреннем)

порядке, 71 Объединение множеств, 96 Оператор

ASSIGN, 59; 97; 120; 146

COMPUTE, 59; 120

CONCATENATE, 240

CREATE!, 75

DELETE, 38; 97; 140; 159; 236; 315

DELETEMIN, 121; 140; 236; 309

DEQUEUE, 54

DIFFERENCE, 97

EMPTY, 51; 54; 236

ENQUEUE, 54

EQUAL, 97

FIND, 97; 159; 207

FIRST, 15; 39; 178

FRONT, 54

GETNEW, 147

INITIAL, 207

INSERT, 15; 38; 97; 140; 154; 236; 309; 315

INTERSECTION, 97

LABEL, 75

LEFTMOST CHILD, 75

LOCATE, 38

MAKENULL, 15; 38; 50; 54; 59; 75; 97; 120; 147 MAX, 97

MEMBER, 97; 139 MERGE, 97; 159; 207 MIN, 97; 236 MODIFY, 315 NEXT, 15; 38; 178 PARENT, 75 POP, 50 PREVIOUS, 38 PRINTLIST, 39 PUSH, 51

RETRIEVE, 38; 315 RIGHT SIBLING, 75 ROOT, 75 SIZE, 15 SPLTT, 167 TOP, 50 UNION, 15; 97 VALUEOF, 146 VERTEX, 178

Операторы 2-3 дерева, 154 АТД MFSET, 163 дерева двоичного поиска, 139 деревьев, 75 для орграфов, 178 множеств, 97 отображений, 59; 120 очередей, 53

очереди с приоритетами, 124 просмотра смежных вершин, 179 работы с файлами, 315 списков, 38 стеков, 50

узлов нагруженного дерева, 146; 147 Организация выполнения процедур, 61 Орграф. См. Ориентированный граф Ориентированный граф, 175

ациклический, 192

ациклический, корень, 198

вершина, 175

длина пути, 175

дуга, 175

матрица смежности, 176 минимальный эквивалентный, 199 обратные дуги, 190 обход, 188

поиск в глубину, 188

помеченный, 176

поперечные дуги, 190

проверка ацикличности, 193

прямые дуги, 190

путь, 175

путь простой, 176

редуцированный, 195

сильная связность, 195

сильно связная компонента, 195

сильно связный, 195

списки смежности, 177

транзитивная редукция, 198

центр, 187

цикл, 176 Остовное дерево, 203

минимальной стоимости, 203 Остовный лес, 190

глубинный, 190 Отношение

линейного порядка, 138

многие-ко-многим, 129

строгого включения, 193

транзитивности, 95

частичного порядка, 192

эквивалентности, 159 Отображение

пустое, 59

реализация посредством хеширования, 120

Отображения, 58 определение, 58

реализация посредством массивов, 59 реализация посредством списков, 60 Очереди, 53 реализация посредством указателей, 54 реализация посредством циклических массивов, 55

с двухсторонним доступом, 66 Очередь с приоритетами, 121 реализации, 123

реализация посредством массива, 128 реализация посредством частично упорядоченных деревьев, 125

Память внешняя, 303 вторичная, 303 динамическая, 332; 344 оперативная, 303 основная, 303

управление блоками одинакового

размера, 335 Паросочетание, 215

максимальное, 215

полное, 215 Пересечение множеств, 96 Подграф индуцированный, 200 Поддерево, 69 Поиск

в глубину, 209; 337; 340

в мультисписке, 133

в ширину, 210

двоичный, 320

интерполяционный, 329

линейный, 319

локальный, 294

с возвратом, 283; 287 Порядковые статистики, 250 Правило

произведений, 24

сумм, 24 Практика программирования, 28 Преобразование Фурье, 302 Прима алгоритм, 204 Приоритет, 121 Программа

bfs, 210

binsort, 241

bubble, 24

create, 91

CREATE2, 82

dfs, 189; 337 Dijkstra, 180 EDIT, 51 END, 40 fact, 27 findpivot, 228 Eloyd, 184 greedy, 11 heapsort, 238 Huffman, 89 INORDER, 72 knapsack, 61 Kruskal, 207 EEETMOST CHIED, 79 merge, 306; 348 mergesort, 258 move, 48 mult, 270 NPREORDER, 76 nrdfs, 342 partition, 230 path, 186

PREORDER, 72; 76 Prim, 204 propagate, 100 PURGE, 39 pushdown, 237 quicksort, 230 radixsort, 245 rotate, 340 same, 39 search, 286 select, 252 Shellsort, 253 spell, 145 topsort, 194 tuna, 106 Warshall, 187

выделения процессам машинного времени, 123

вычисления адреса передачи, 357 вычисления вероятностей, 274 вычисления транзитивного замыкания, 187

НОП, 169

поиска в глубину, 189

поиска с возвратом, 286

форматирования текста, 33 Программа-инструмент, 29 Программы

анализ, 28

время выполнения, 19 Псевдопрограммы, 28 Псевдоязык, 7; 13; 28 Путь

в дереве, 70