3 Ахо А., Хопкрофт Д., Ульман Д. - Построение и анализ вычислительных алгоритмов (1979) (1162194), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Символ ленточный 40- несущественный (don't care) 399- нетерминальный (nonterminal) 91- пустой (the blank) 40- терминальный (terminal) 91СЛЕД (SUCC) 163СЛЕДУЮЩАЯ (NEXT) 58СЛЕДУЮЩИЙ (NEXT) 66, 147Сливаемое дерево (mergeable heap)170СЛИТЬ (MERGE) 195СЛИЯНИЕ(MERGE) 82Словарь (dictionary) 129, 170Слово (word) см. Цепочка —машинное (computer) 14, 25См. также Число, хранимое врегистре 14, 25, 37Сложность (complexity) —арифметическая (arithmetic) 476- асимптотическая (asymptotic) см.Сложность временная,Сложность емкостная 21, 22, 27,44- временная (time) 22, 27, 44- - в среднем (expected) 22- - - худшем случае см.

Сложностьвременная 22, 27, 44- - НМТ (NDTM) 407- в худшем случае (worst case) 22- емкостная (space) 21, 44- - логарифмическая (logarithmic) 24,27- - НМТ (NDTM) 409- реализации булевой функции(realization of a Boolean function)498, 499- средняя (expected) 22- усредненная см. Сложность средняя22Смежный (adjacent) 64Смещение (displacement) 164Содержимое регистра (the contents ofa register) 16СОРТ (SORT) 82СОРТВЗБАЛТЫВАНИЕМ(BUBBLESORT) 123Сортдеревом (heapsort) 106, 110Сортировка (sorting) 93- внешняя (external) 94- внутренняя (internal) 99- вставками (insertion) 126- вычерпыванием (bucket) 95- лексикографическая (lexicographic)96, 98- слиянием (merge) 82- с помощью сравнений (bycomparisons) 104- топологическая (topological) 87- цифровая (radix) 95Сортирующее дерево (heap) 106СОСТОЯНИЕ (STATUS) 53Состояние (state) 40- допускающее (accepting) 41, 166,356, 375- заключительное (final) 41- - of, a, 2дма, 2dpda, 375- начальное (initial) 40- начальное (start) 166, 356, 375- управляющего устройства (of afinite control) 375СОЧЕТ (COMB) 89СПИСОК (LIST) 147Список (list) 58- дважды связанный (doubly linked)61- свободный (free) 60- смежностей (adjacency) 66Способность пропускная (capacity)448, 497Сравнение (comparison) 38- ключевое (key) 121CT (DEG) 312Стабильный (метод сортировки)(stable) 126Статистики порядковые (orderstatistics) 93, 117Стек (stack) 61Степень (degree)- полинома 312, 491- полинома от несколькихпеременных (of a multivariatepolynomial) 491- узла 64Стоимость (cost) 223, 225- пути (of a path) 223Структура данных (data structure) 58СУММАСТРОК (ROWSUM) 278Сумматор (accumulator) 16Суффикс (suffix) 355Схема логическая (logic circuit) см.Сеть логическая 35, 55, 498- сдвигающая (shifting network) 497Сцепление см.

Конкатенация 50, 225,355СЧЕТ (COUNT) 71, 153Счетчик команд (location counter) 16,26Сын (son) 67- a 386- левый (left) 68- правый (right) 68Тавтология (tautology) 446Теорема о свертке (convolutiontheorem) 288ТЕРМ (TERM) 380Терминатор (terminator) 379Тип данных (data type) 48Точка сочленения (articulation point)206Тройка допустимая (admissable triple)309Трудно разрешимый (intractable) 404УДАЛИТЬ (DELETE) 128УЗЕЛ (VERTEX) 71Узел (vertex, node) 64- смежный (adjacent) 64Умножение (multiplication) —активное (active) 484- векторов (of vectors) 493- и/или (and/or) 352, 399- комплексных чисел (of complexnumbers) 478, 479, 489- матриц (of matrices) 259, 495- матрицы на вектор (of a matrix by avector) 486, 494- полиномов (of polynomials) 480, 487,492, 493- целых чисел (of integers) 77—80,304Уровень узла (level of a vertex) 68Устройство управляющее (finitecontrol) 40, 165, 356Форма (form) — билинейная (bilinear)495- конъюнктивная нормальная(conjunctive normal) 427- нормальная Хомского (Chomskynormal) 91Формула булева (Boolean expression)417- выполнимая (satisfiable) 419- Лагранжа интерполяционная(Lagrangian interpolationformula) 329Фрагмент стека (stack frame) 73Функция (function) 51- булева (Boolean) 498- логарифмическая (logarithmic) 23- конструируемая по времени (timeconstructable) 471- - - емкости (space) 411- - - памяти см.

Функция,конструируемая по емкости 411- отказов (failure) 368- переходов (next-move) 41- переходов (state transition) 356- расстановки (hashing) 130- стоимости (cost) 130- экспоненциальная (exponential) 39- элементарная (elementary) 466Ханойские башни (towers of Hanoi)88Характеристический (вектор)(characteristic) 63Цвет (color) 421ЦЕПОЧКА (STRING) 99Цепочка (string) 355- допускаемая (автоматом, машиной)(accepted) 166, 357, 376- пустая (empty) 165, 355- с несущественными символами(with don't cares) 399Цепочка-текст (text-string) 363Цепь (chain) 397ЦИКЛ (CYCLE) 457Цикл (cycle) 64- гамильтонов (Hamilton) 421- - ориентированный (directed) 421- эйлеров (Euler) 249Циркулянт (circulant) 310ЧАСТИЧНО НАЙТИ (partial FIND)158Черпак (bucket) 95ЧИС (NUM) 278Число (number)- Каталана (Catalan) 91- хранимое в регистре (stored in aregister) 14, 25, 37- хроматическое (chromatic) 421ЧН (PF) 158Шаг (вычисления) (step) 477Шаг (работы автомата, машины)(move) — by, a, 2дма, 2dpda, 376- НМТ (by a NDTM) 406Эквивалентность (equivalence) —автоматов (of automata) 166- векторов по модулю (of vectorsmodulo) 480- регулярных выражений (of regularexpressions) 356- отношение (relation) 206- состояний (of states) 166Элем (Item) 58ЭЛЕМЕНТ (ELEMENT) 153ЭЛЕМЕНТ (ITEM) 59Элемент единичный (identity) 224- k-й наименьший (the kth smallestelement) 117- обратный (inverse) 256Элементы смежные матрицы(adjacent entries of a matrix) 252Язык (language) 19, 355- бесконтекстный (context-free) 401- допускаемый автоматом (acceptedby an automaton) 166, 357- - by, a, 2дма, 2dpda, 376- - MT (by a TM) 42- - НМТ (by a NDTM) 407- - программой (by a program) 19- контекстный (context-sensitive) 449NP-полный (NP-complete) 416- полный для недетерминированногополиномиального времени (fornondeterministic polynomialtime) см.

Язык NP-полный 416- порождаемый грамматикой(generated by a grammar) 91- регулярный (regular) 356.

Характеристики

Список файлов книги