3 Ахо А., Хопкрофт Д., Ульман Д. - Построение и анализ вычислительных алгоритмов (1979) (1162194), страница 2
Текст из файла (страница 2)
Дерево позиционное296, 387- позиционное (position) 296, 387- - уплотненное (compact) 397- помеченное (labeled) 103- решений (decision) 37- сбалансированное (balanced) 169,194- - ограниченное (bounded) 194- сливаемое см. Сливаемое дерево170- сортирующее см. Сортирующеедерево 106- упорядоченное (ordered) 68Диаграмма (переходов) (diagram) 357Диагонализировать (diagonalize) 453Диагональ главная (main diagonal)259ДКА (DFA) 361- скелетный (skeletal) 367ДЛИНА (LENGTH) 99Длина (length)- внешних путей (external path) 194- внутренних путей (internal path) 194- пути (of a path) 64- регулярного выражения (of a regularexpression) 359- цепочки (of a string) 3551дма, 1dpda, 4012дма, 2dpda, 373- k-головчатый (k-head) 400ДОБАВСЫНА (ADDSON) 173Доминатор (dominator) 239- непосредственный (immediate) 239Допускаться (be accepted)- конечным автоматом (by a finiteautomaton) 166, 357- магазинным автоматом (by apushdown store automaton) 376- машиной Тьюринга (by a Turingmachine) 41, 42, 406- РАМ (by a RAM) 19Зависимость линейная по модулю(linear dependence modulo) 480Задача (problem) — легкоразрешимая (tractable) 404- об упаковке (package placement) 447- - устойчивом бракосочетании (stablemarriage) 87- о коммивояжере (travellingsalesman) 447- - кратчайшем пути (shortest path)223- - потоке (flow) 447—448- - разбиении (partition) 447- - ранце (knapsack) 446- - расписании работ (scheduling) 448- определения глубины (depthdetermination) 164- пустоты дополнения (emptiness ofcomplement) 457- сортировки (sorting) 94- трудно разрешимая (intractable) 404ЗАДНИЙ (REAR) 62Замыкание (closure) 225- Клини (Kleene) 355- рефлексивное и транзитивное(reflexive and transitive) 223- транзитивное (transitive) 120, 223ЗАТОЛКНУТЬ (PUSH) 61Значение переменной (в вычислении)(valuation of a variable) 477Значение операнда (the value ofoperand) 17Идемпотентность (idempotence) 224Идентификатор (identifier) 386Идентифицировать (позицию)(identify) 386Идентифицироваться (match) 399Иерархия (hierarchy) — временнаясм.
Иерархия по времени 471- емкостная см. Иерархия по емкости452- по времени (time) 471- - емкости (space) 452- - памяти см. Иерархия по емкости522ИЗВЛЕЧЬ_МИН (EXTRACT_MIN)162, 191Изоморфизм (isomorphism) —деревьев (of trees) 102- подграфу (subgraph) 446ИМПЛАНТАЦИЯ (IMPLANT) 176,177ИМЯ (NAME) 58, 153Имя переменной (в вычислении)(variable name) 477Индекс (index) 50Интерполяция (interpolation) 286Исток (в графе) (source vertice) 497Источник (source) 235Итерация см. Замыкание Клини- позитивная (positive) 355Китайская теорема об остатках(Chinese remaindering) 329Класс эквивалентности (equivalenceclass) 206Клетка (cell) 40Клика (clique) 418КНФ (CNF) 427Код операции (operation code) 16Кольцо (ring) 256- коммутативное (commutative) 256КОНЕЦ (HEAD) 66Конец ребра (head of the edge) 64Конец составного ребра (head of acomposite edge) 242Конец цепочки (suffix of a string) 355Конкатенация (concatenation)- множеств (of sets) 225- списков (of lists) 50- цепочек (of strings) 355- языков (of languages) 355Конфигурация (configuration) 378- С' выводима из С (С derives С') 379- поверхностная (surface) 378- терминальная (terminal) 379Команда (instruction) — РАМ (of aRAM) 16—18- РАСП (of a RASP) 26КОМПОНЕНТА (ELEMENT) 58Компонента (component) —двусвязная (biconnected) 206- связная (connected) 202- сильно связная (strongly connected)216КОРЕНЬ (ROOT) 153Корень (root) — графа (of a graph) 67,239- дерева (of a tree) 67- из единицы (of unity) 285- - - примитивный (principal) 285- сильно связной компоненты (of astrongly Connected component)216КОРРЕКТОР (UPDATE) 380, 382Критерий весовой (cost criterion)- логарифмический (logarithmic) 23,24- равномерный (uniform) 23Левое двойственное (множествовыражений) (left dual) 496ЛЕВЫЙСЫН (LEFTSON) 68Легко разрешимый (tractable) 404Лента (tape) 39- входная (input) 15, 41, 165, 374- выходная (output) 15, 44Лес (forest) 67- остовный (spanning) 130- - глубинный (depth-first) 203- - построенный поиском в глубинусм.
Лес остовный глубинный203Лист (leaf) 67Литерал 16Литерал (literal) 417, 427Магазин (pushdown store) 61Маркер (marker) — дна (bottom) 375- нижний см. Маркер дна 375Массив (array) 58Матрица (matrix) — булева (Boolean)274- единичная (identity) 256- невырожденная (nonsingular) 258- нормированная (unit) 259- обратная (inverse) 257- перестановки (permutation) 259- положительно определенная(positive definite) 282- смежностей (adjacency matrix) 64- тёплицева (Toeplitz) 282- транспонированная (transpose) 259- треугольная (triangular)- - верхняя (upper) 258- - нижняя (lower) 258Машина (machine) — адресная 31- равнодоступная адресная см.Машина с произвольнымдоступом к памяти 26- - - с хранимой программой см.Машина с произвольнымдоступом к памяти и хранимойпрограммой 26- с произвольным доступом к памяти(random access) 26- - - - - - и хранимой программой(stored program) 26- Тьюринга (Turing) 39- - многоленточная (multitape) 39- - недетерминированная(nondeterministic) 405, 406Мгновенное описание (instantaneousdescription) 42, 356, 375- - допускающее (accepting) 356- - - для of, a, 2дма, 2dpda, 376- - of, a, 2дма, 2dpda, 375- - MT (of a TM) 42, 406- - HKA (of a NDFA) 356- - HMT (of a NDTM) 406- - начальное (initial) 42, 356, 376, 406- - - of, a, 2дма, 2dpda, 376- - - HKA (of a NDFA) 356- - - HMT (of a NDTM) 406Метка пути (path label) 225Метод расстановки (hashing) 132, 196Минимизация конечного автомата(minimization of a finiteautomaton) 187- безопасное для разбиения (safe for apartition) 183- пустое (empty) 355- ребер, разрезающих циклы(feedback edge) 421- регулярное (regular) 355- узлов, разрезающих циклы(feedback vertex) 421- универсальное (universal) см.
Базаданных 132, 147, 188МНОЖИТЕЛЬ (FACTOR) 264, 267Моноид (monoid) 224Мощность (cardinality) 64Мультиграф (multigraph) 249МО (ID) — см. Мгновенное описаниеНаибольший общий делитель(greatest common divisor) 336,339Наименьшее общее кратное (leastcommon multiple) 352НАИМЕНЬШИЙ (SMALLEST) 175НАЙТИ (FIND) 128НАЙТИ-ГЛУБИНУ (FIND_DEPTH)164НАЙТИ-ПУТЬ (FIND _ PATH) 249Начало отсчета (origin) 164Начало ребра (tail of the edge) 64- - составного (composite) 242Начало цепочки (prefix of a string)355НВП-разложение (LUPdecomposition) 264НВ-разложение (LU decomposition)264Независимость линейная по модулю(linear independence modulo) 480НЕПУСТОЙ (NONEMPTY) 99Ниже (отношение на поверхностныхконфигурациях) (below) 380НИЖНИЙ (LOW) 210НИЖНЯЯСВЯЗЬ (LOWLINK) 217HKA (NDFA) 356HMA (NPDA) 4001HMA, (NPDA) 401НОВ (NEW) 380НОД (GCD) 336, 344HOK (LCM) 352НОМЕР (NUMBER) 71О (порядок величины — order ofmagnitude) 12Од (порядок величины дляневетвящихся программ) 35ОБ (порядок величины при битовыхвычислениях) 35Одв (порядок величины приприменении модели сдвоичными векторами) 37Омт (порядок величины прииспользовании в качествемодели машины Тьюринга) 44Ос (порядок величины прииспользовании модели деревьеврешений) 38Область действия переменной (thescope of a variable) 48Обозревать (scan) 40Обработка предварительная(preconditioning) 490, 491Образ (pattern) 363ОБРАТНОЕ (RECIPROCAL) 314, 315ОБРАТНЫЙ (RECIPROCAL) 321ОБЪЕДИНИТЬ (UNION) 128, 148Операнд (operand) 16Оператор (statement) — COMMENT52- FOR 49- GOTO 51- IF 49- READ 52- REPEAT 49- WHILE 49- WRITE 52- определения процедур (proceduredifinition) 51- помеченный (labeled) 50- присваивания (assignment) 49Операция (operation) — активнаямультипликативная (activemultiplicative) 490- битовая (bit) 35- ассоциативная (associative) 224- дистрибутивная (distributive) 224- коммутативная (commutative) 224- с двоичными векторами (bit vector)37- элементарная (scalar) 230Определитель (determinant) 258ОТЕЦ (FATHER) 153Отец (father) 67Отображение памяти (memory map)16, 26ОЧЕРЕДЬ (QUEUE) 96Очередь (queue) 62- сцепляемая (concatenable) 170- с приоритетами (priority) 170Палиндром (palindrome) 42Пара лежит ниже (pair is below) 380Параметр (parameter) — фактический(actual) 51- формальный (formal) 51Паросочетание (pairing) 87- устойчивое (stable) 87ПЕРЕДНИЙ (FRONT) 62Переменная (variable) см.
Адрессимволический 33Переменная (вычисления) (variable)477- входная (input) 33- выходная (output) 33- глобальная (global) 52- локальная (local) 52, 53Переменная формальная(indeterminate) 476ПЕРЕСЕЧЕНИЕ (INTERSECTION)186Перестановка (permutation) —нечетная (odd) 258- четная (even) 258ПЕРЕСЫПКА (HEAPIFY) 108ПНОД (HGCD) 339, 340Подграф полный (complete subgraph)см. Клика 418Поддерево (subtree) 67- левое (left) 68- правое (right) 68Подматрицa (submatrix) 259- главная (principal) 259Подпоследовательность(subsequence) 402Подцепочка (substring) 355ПОЗИЦИЯ (POSITION) 59Позиция (в цепочке) (position) 386ПОИСК (SEARCH) 135, 138, 173, 203Поиск (search) — в глубину (depthfirst) 202- двоичный (binary) 135ПОИСКЕ (SEARCHB) 212ПОИСКВ (SEARCHC) 220Покрытие (cover) — множествами(set) 421—422- точное (exact) 422- узельное (vertex) 421Поле (field) 256, 475Полином (polynomial) — плотный(dense) 348- разреженный (sparse) 348Полиномиально (polynomially) —связанные (related) 39- трансформируемый (transformable)416- эквивалентные см.
Полиномиальносвязанные 39Полнота (completeness) — NP (NPcompleteness) 416- для NP-TIME (for (NP-TIME) 416- - P-SPACE (for P-SPACE) 440Полукольцо замкнутое (closedsemiring) 223Полустепень исхода (out-degree) 64Порядок (order) — внутренний (in-)68- лексикографический (lexicographic)95- линейный (linear) 94- обратный (post-) 68- полный (total) см. Порядоклинейный 94- прямой (рге-) 68- частичный (partial) 94Последовательность остатков(remainder sequence) 336Постоянная (вычисления) (constant)477ПОСТРДЕРЕВА (BUILDTREE) 144Построение сортирующего дерева(construction of a heap) 108ПОСТРСОРТДЕРЕВА(BUILDHEAP) 109Потомок (descendant) 67- подлинный (proper) 67Правило Горнера (Horner's rule) 34ПРАВЫЙСЫН (RIGHTSON) 68ПРИНАДЛЕЖАТЬ (MEMBER) 128ПРЕД (PRED) 163, 380Предок (ancestor) 67- подлинный (proper) 67Предшественница (predecessor) 380- непосредственная (immediate) 380ПРЕДЫДУЩАЯ (PREVIOUS) 61Преобразование Фурье (Fouriertransform) — быстрое (fast) 294- дискретное (discrete) 285- обратное (inverse) 286Префикс (prefix) 355Префиксный (режим, алгоритм) (online) 129ПРОВЕРКА (TEST) 412Программа (program)- для РАМ (for RAM) 16- на Упрощенном Алголе (PidginALGOL) 48- неветвящаяся (straight-line) 32Программирование динамическое(dynamic programming) 83Продукция (production) 91Прохождение дерева (traversal of atree) 68- - во внутреннем порядке (inorder) 69- - в обратном порядке (postorder) 69- - в прямом порядке (preorder) 69Процедура (procedure) 51- рекурсивная (recursive) 70Путь (path) 64- внешний (external) 194- внутренний (internal) 194- простой (simple) 64Разбиение (partitioning) 181Разбиение грубейшее (coarsestpartition) 181Разветвление (branching) см.
gotoоператор 51Разделяй и властвуй (divide andconquer) 75РАЗМЕР (SIZE) 147, 312Разность циклическая (cyclicdifference) 309Разрез (cutset) 447РАМ (RAM) 15РАМ-программа (program) 16- недетерминированная(nondeterministic) 415Ранг (rank) — матрицы (of a matrix)259- по столбцам (column) 481- - строкам (row) 481- узла (of a vertex) 155РАСП (RASP) 26РАСП-программа (program) 26- недетерминированная(nondeterministic) 415Расстановка (hashing) 132Расширение поля формальнымипеременными (extension of afield by indeterminates) 476РАСЩЕПИТЬ (SPLIT) 129Ребро (edge) 64- древесное (tree) 203, 215- обратное (back) 203, 215- поперечное (cross) 215- прямое (forward) 215- составное (composite) 242Регистр (register) 15Редукция транзитивная (transitivereduction) 249Режим — префиксный (on-line) 129- свободный (off-line) 129Рекурсия (recursion) 70Свертка (convolution) 287- отрицательно обернутая (negativewrapped) 289- положительно обернутая (positivewrapped) 289СВОБОДНАЯ (FREE) 59Свободный (режим, алгоритм) (offline) 129Сводимый (язык) (reducible) 416Свойство сортирующего дерева (heapproperty) 108СВЯЗАТЬ (LINK) 164Связность (графа) (connectedness) 253СВЯЗЬ (LINK) 66Сеть логическая (logic circuit,network) 35, 55, 498- - комбинационная (combinational) 55Сжатие путей (path compression) 152Символ (symbol) — входной (input)40- ленточный (tape) 40- на ленте, см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
