Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Сэвидж Д.Э. — Сложность вычислений
Сэвидж Д.Э. — Сложность вычислений



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Сложность вычислений

Автор: Сэвидж Д.Э.

Аннотация:

Монография содержит систематическое изложение важнейших аспектов теории сложности вычислений. Ее автор — известный американский ученый, крупный специалист в области теории сложности и ее приложений. В книге на высоком научном уровне последовательно и во взаимосвязи рассмотрены основные модели вычислений: схемы, формулы, последовательностные машины (автоматы), машины Тьюринга и др. Обсуждаются такие темы, как сети сортировки, сложность умножения матриц и yvF-полные проблемы. Большой интерес представляет предложенный автором подход к описанию работы реальных ЭВМ, основанный на моделях и методах теории сложности. Особое внимание уделено выводу вычислительных неравенств, связывающих сложность вычислений на различных моделях. Книга содержит большое количество задач и упражнений различного уровня сложности. Книга предназначена для специалистов в области дискретной математики и математической кибернетики, информатики и вычислительной техники, аспирантов и студентов соответствующих специальностей; она будет также полезна всем, интересующимся этими областями знания.


Язык: ru

Рубрика: Математика/

Серия: Сделано в холле

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1998

Количество страниц: 368

Добавлена в каталог: 04.04.2011

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
$U_{B}$ -дескриптор ($U_{B}$-descriptor)      181 183
$\varepsilon$-приближение ($\varepsilon$-approximation)      336
(k, s)-представление Лупанова ((k, s)-Lupanov representation)      118 120
0-1 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ (задача) (0-1 INTEGER PROGRAMMING)      см. "БУЛЕВО ПРОГРАММИРОВАНИЕ"
0-множество (0-set)      96
0-множество минимальное (minimal 0-set)      96
1-множество (1-set)      96
1-множество минимальное (minimal 1-set)      96
3-ВЫПОЛНИМОСТЬ (задача) (3-SATISFIABIUTY PROBLEM)      328
j-разделимое множество (j-separable set)      229
JK-триггер (J-K flip-flop)      208
k-клика (k-clique)      16 322
NP-полная задача (NP-complete problem)      17 319
NP-полный язык (NP-complete language)      322
RS-триггер (S-R flip-flop)      207
RS-триггер тактируемый (clocked S-R flip flop)      208
T-программа для функции f (T-program for f)      192
Автомат конечный      см. "Функция последовательностная"
Адрес возврата из подпрограммы (subroutine return address)      255
Адресация косвенная (indirect addressing)      254
Аккумулятор (AC) (accumulator)      246
АЛГОЛ-60 (ALGOL-60)      184
Алгоритм (algorithm)      176
Алгоритм двоичной вставки (binary insertion algorithm)      304
Алгоритм исключения Гаусса (Gaussian elimination algorithm)      81
Алгоритм Квайна — Мак-Класки (Quine — Mc-Cluskey algorithm)      31
Алгоритм Офмана умножения чисел (Ofman integer multiplication algorithm)      265
Алгоритм сортировки безусловный (nonadaptive sorting algorithm)      297 302
Алгоритм сортировки условный (adaptive sorting algorithm)      297 302
Алгоритм умножения матриц стандартный (standard algorithm for matrix multiplication)      309
Алгоритм универсальный (universal algorithm)      324
Алгоритм Штрассена умножения матриц (Strassen's matrix multiplication algorithm)      22 93 94 128 310 341
Алфавит входной (input alphabet)      133
Алфавит выходной (output alphabet)      133
Алфавит ленточный (tape alphabet)      170
Базис (basis)      21 30 32
Базис монотонный (monotone basis)      83
Базис полный (complete basis)      30 33
Барабан (drum)      219 268 см.
Бит статуса (one-bit status indicator)      198
БЛИЖНЯЯ ВСТАВКА (алгоритм) (NEARINSERT)      336
Блок логический      см. "Устройство логическое"
Блок памяти      см. "Устройство запоминающее"
БУЛЕВО ПРОГРАММИРОВАНИЕ (задача) (0-1 INTEGER PROGRAMMING)      328
Буфер ввода-вывода (IOBFR) (input/output buffer)      246
Буфер выходной (output buffer)      273
Вершина внутренняя      см. "Вершина вычисляющая"
Вершина входная (source node)      33 34
Вершина вычисляющая (computation node)      33
Вершина начальная (initial node)      91 92
Вершина терминальная (terminal node)      34
Вес (weight)      79
Ветвление входное (fan-in)      34
Ветвление выходное (fan-out)      21 34
Ветвление схемы (fan-out of the chain)      34
Время выборки (cycle)      212
Вход внешний (external input)      156
Выполнение и распечатка содержимого памяти (running and dumping)      205
Выражение регулярное (regular expression)      141 142
Выражение условное (conditional expression)      184
Выражение условное неопределенное (undefined conditional expression)      184
Выход внешний (external output)      156
Вычисление      см. "Схема вычисления"
Вычисление набора функций (computation)      33
Вычитание (subtraction)      187 233
Генератор тактовых импульсов (central clock)      208
Глубина схемы (depth of combinational machine, depth of chain)      21 35
Глубина функции (delay complexity of function)      21 35 228
Головка (head, tape head)      20 169
Гомоморфизм (homomorphic mapping)      130
Граф вычисления (graph of a chain)      см. "Машина комбинационная" "Схема
Граф неориентированный (undirected graph)      322
Граф ориентированный (directed graph)      322
Граф полный (complete graph)      322
ДАННЫЕ (DATA)      32
Декомпозиция машин (machine decomposition)      133
Дерево решений (decision tree)      303
Дескриптор      см. "Функция дескрипторная"
Детерминант      см. "Определитель"
Дешифратор двоичный (binary-to-positional transformer)      52 73
Диаграмма переходов (диаграмма состояний) (state diagram)      134
Дизъюнкция (ИЛИ) (disjunction, Boolean OR)      28 188
Диск (disk)      219 268 см.
Длина T-программы (length of a T-program)      192
Длина пути (length of path)      35
Длина формул (formula size)      21 38
ДНФ-ТАВТОЛОГИЯ (задача) (DNF-TAUTOLOGY)      342
Дополнение (Complementation)      142 188
Дополнение булево (Boolean complement, negation)      28
Забивание (obstruction)      57
Зависимость существенная (essential dependence)      42
Задача булева программирования (0-1 integer programming problem)      17 319
Задача коммивояжера (traveling salesman problem)      17 319
ЗАДАЧА КОММИВОЯЖЕРА НЕОРИЕНТИРОВАННАЯ (UNDIRECTED TRAVELING SALESMAN)      329
ЗАДАЧА КОММИВОЯЖЕРА ОРИЕНТИРОВАННАЯ (DIRECTED TRAVELING SALESMAN)      329
ЗАДАЧА КОММИВОЯЖЕРА ПРИБЛИЖЕННАЯ (APPROXIMATE TRAVELING SALESMAN)      329
Задача о k-клике (k-clique problem)      16 319 323
Задача о выполнимости (satisfiability problem)      325
Задача о выполнимости КНФ (POS-satisfiability problem)      325
Задача о клике (clique problem)      322
Задача о назначениях (о свадьбах) (marriage problem)      104
Задача о рюкзаке (knapsack problem)      320 335
Задача умножения матриц      308
Задержка задачи (delay complexity of task)      339
Задержка сети (delay of the network)      339
Закон Гроша (Grosch's law)      294
Запись постфиксная (postfix notation)      204
Запись префиксная (prefix notation)      23 190
И, булево И      см. "Конъюнкция"
ИЛИ, булево ИЛИ      см. "Дизъюнкция"
Импликанта (implicant)      61
Импликанта монотонная (monotone implicant)      83
Импликанта монотонная простая (monotone prime implicant)      83
Импликанта простая (prime implicant)      61
Инвертор (inverter)      210
ИСКЛЮЧАЮЩЕЕ ИЛИ (EXCLUSIVE-OR)      28 см.
Исчезновение порядка (underflow of exponent)      244
Итерация (star operation)      141 142
Карта Карно (Karnaugh map)      22 62
Класс NP (class NP)      23 321
Класс P (class P)      23 321
Класс эквивалентности (equivalence class)      137
КЛИКА (задача) (CLIQUE)      328
КНФ-ВЫПОЛНИМОСТЬ (задача) (POS-SATISFIABILITY)      328
Код операции (OP CODE) (operation code)      246
Кольцо (ring)      309
Кольцо коммутативное (commutative ring)      309
Команда безадресная      см. "Команда с подразумеваемым адресом"
Команда многоадресная (multiaddress instruction)      257
Команда одноадресная (single-address instruction)      257
Команда прямого доступа (direct access instruction)      254
Команда с подразумеваемым адресом (implied address instruction)      257
Компаратор (comparator)      86
Конкатенация (string concatenation)      141 142
Константа свободная (free constant)      103
Контроллер (controller)      206
Конъюнкция (И) (conjunction, Boolean AND)      28 188
Конъюнкция элементарная (minterm)      29 62
Критерий Нечипорука (Nechiporuk test)      104
Кэш-память (cache memory)      206
Лента (машины Тьюринга) (tape)      20 169
Литерал (literal)      31 96
Магазин      см. "Стек"
Мантисса (fraction)      243
Маршрут      330
Матрица Адамара (Hadamard matrix)      314
Матрица тёплицева (Toeplitz matrix)      313
Машина вычислительная универсальная (general-purpose computer)      205
Машина комбинационная (combinational machine)      16 33 133 см.
Машина комбинационная синхронная (synchronous combinational machine)      21 123
Машина Мили (Mealy machine)      133 166
Машина Мура (Moore machine)      133 166
Машина последовательностная (sequential machine)      16 18 133
Машина последовательностная приведенная (reduced sequential machine)      137
Машина последовательностная тактируемая (clocked sequential machine)      18 156
Машина Тьюринга (Turing machine)      16 20 169 170
Машина Тьюринга детерминированная (ДМТ) (deterministic Turing machine)      320
Машина Тьюринга многоленточная (multitape Turing machine)      174
Машина Тьюринга недетерминированная (НДМТ) (nondeterministic Turing machine)      320
Машина Тьюринга универсальная (universal Turing machine)      178
Мера числа шагов (step-counting measure)      61
Метод Лупанова      122
Метод Шнорра (Scnorr method)      61
Микрокоманда (microinstruction)      246
Микропрограмма (microprogram)      249
Микропрограммирование (microprogramming)      246
Множество билинейных форм дизъюнктное (disjoint set of monotone bilinear forms)      87
Множество пустое (empty set)      142
Множество рекурсивно перечислимое (recursively enumerable set)      176
Множество рекурсивное (recursive set)      176
Множество состояний (state set)      133 170
Мощность вычислительная (computing power)      293
Накопитель на магнитной ленте (НМЛ) (tape memory, TAM)      215
Накопитель на магнитном барабане (НМБ) (drum memory)      220
Накопитель на магнитном диске (НМД) (disk memory)      220
Неравенства вычислительные (computational inequalities)      267
Неравенства вычислительные второго рода (computational inequalities of the second kind)      24 272—280
Неравенства вычислительные первого рода (computational inequalities of the first kind)      24 269—272
Неравенства Маркова (Markov's inequality)      126
Неравенства Чебышёва (первое)      см. "Неравенство Маркова"
Неравенства Шварца (неравенство Коши — Буняковского) (Schwarz inequality)      99 131
Несогласованность вычислительных мощностей (mismatch of computing powers)      293
Нижняя оценка Нечипорука (Nechiporuk lower bound)      102 103 107
Нижняя оценка Храпченко (Krapchenko lower bound)      94 114
НОВАЯ ПИРАМИДА (алгоритм) (NEWHEAP)      307
Обход постфиксный (postorder traversal)      204
Обход префиксный (preorder tra versal)      190
Объединение (union)      142
Операции векторные (vector operations)      224
Операции сравнения (comparison tests)      226
Определитель (determinant)      80 100
Организация машины байтовая (byte oriented machines)      257
Отношение эквивалентности (equivalent relation)      137
Отрицание (complement)      188
ОТРИЦАНИЕ (НЕ) (NEGATION, NOT, Boolean complement, inversion)      28
Палиндром (palindrome)      171
Память (memory)      205
Память ассоциативная (associative memory)      223
Память ленточная (storage tapes)      169
Пара значащая (valid pair)      87 89
Переменные (variables)      28
Переполнение (overflow)      228 244
ПЕРЕСЕЧЕНИЕ (INTERSECTION)      142
Перестановка (permutation)      78
ПЕРЕСТРОЙКА (алгоритм) (REHEAP)      306
Пересылка параллельная (parallel transfer operation)      211
Пирамида (heap)      305
ПИРАМИДАЛЬНАЯ СОРТИРОВКА (алгоритм) (HEAPSORT)      306
Подмножество принимаемое (accepted subset)      170
Подфункция (subfunction)      44
Поле (field)      310
Полином Жегалкина (полином по модулю 2) (sum-of-product expansion, SOPE)      30 70
Порт ввода (input port)      205
Порядок (exponent)      243
Последовательность битонная (bitonic sequence)      340
Последовательность характеристическая (weight vector)      79
Правила де Моргана (de Morgan's rules)      28 95 96
Правило копирования (copy rule)      185
Предикат (predicate)      184
Представление (representation)      133
Представление в виде величины со знаком (sign-and-magnitude notation)      234
Представление в виде дополнения до двух (2's complement notation)      234
Представление в виде дополнения до единицы (1's complement notation)      234
Представление с плавающей запятой (floating-point representation)      243
Представление с фиксированной запятой (fixed-point representation)      242
Преобразование Фурье (Fourier transform)      315
Преобразование Фурье обратное (inverse transform)      317
Прерывание (interrupt)      258
ПРИБЛИЖЕННЫЙ РЮКЗАК, ПР (алгоритм) (Ak)      338
Принцип нулей и единиц (zero-one principle)      299
Принцип ящиков (принцип Дирихле) (pigeonhole principle)      140
Проблема остановки (halting problem)      181
Программа (program)      267 273
Программа вычисления функции f на машине T (program for f on T)      192
Программа для машины Тьюринга (program for the Turing machine)      192
Программа линейная (straight-line code)      285
Программа неветвящаяся (straight-line algorithm)      269
Произведение матриц кронекерово (Kronecker product)      314
Производная регулярного выражения (derivative of regular expression)      143
Процедура (procedure)      176
Процедура Квайна — Мак-Класки (Quine—Mc-Cluskey procedure)      22 см.
Процедура рекурсивная (recursive procedure)      185
Процессор, центральный процессор (ЦП) (central processing unit, CPU)      19 205 244
Путь (path)      34
Работа вычислительная (computational work)      164
Разбиение (partition)      137
РАЗБИЕНИЕ (задача) (PARTITION)      342
Ранг (rank function)      123
Распознавание (набора состоянием) (recognition)      149
Распознавание за полиномиальное время (accepting in polynomial time)      321
Распознавание за полиномиальное время на недетерминированной машине Тьюринга (accepting in polynomial time on NDTM)      321
Регистр (register)      207 210
Регистр адреса (MAR) (memory address register)      246
Регистр адресный ввода-вывода (IOAR) (input/output address register)      246
Регистр данных (MDR) (memory data register)      246
Регистр индексный (index register)      257
Регистр команд (IR) (instruction register)      246
Регистр команд (микропрограммный) (MIR) (instruction register)      252
Регистр малый кольцевой (MCR) (minor cycle ring)      252
Регистр множителя-частного (MQ) (multiplier-auotient register)      246
Регистр общего назначения (general register)      257
Регистр сдвига (shift register)      137 210
Регистр состояния ввода-вывода (FIO)      см. "Флаг ввода-вывода"
Режим состязаний (race condition)      123
Рекурсия (recursion)      172
РЮКЗАК (задача) (KNAPSACK)      329
Свертка (convolution)      317
Сводимость (одной функции к другой) (reduction)      61
Сводимость полиномиальная (polynomial transformability)      321
Сдвиг (shifting, shift function)      225
Сдвиг влево логический (shift-left logical)      76 225
Сдвиг вправо логический (shift-right logical)      76 225
Сдвиг циклический (cyclic shift function)      225
Семантика формализма Мак-Карти (semantics of the McCarthy formalism)      186
Сеть (s, t)-слияния ((s, t)-merging network)      298
Сеть нечетно-четного слияния (odd-even merging network)      298
Сечение (break set)      113
Символ пустой (blank symbol)      170
Система операционная (operating system)      206
Система счисления остаточных классов (residue arithmetic, residue form)      264
Система счисления унарная (unary notaHon)      177
Слово значащее (valid word)      159
Слово принимаемое (accepted string)      170
Слово принимаемое машиной Тьюринга (string accepted by Turing machine)      320
Слово пустое (empty string)      142
Сложение (sum)      187
Сложение по модулю 2 (Addition modulo 2)      55 см.
Сложение по модулю 3 (addition modulo 3)      78
Сложение целых чисел (integer addition)      74
Сложность комбинационная (функции) (combinational complexity)      21 38
Сложность комбинационная без учета инверсий (combinational complexity not including the number of inversions)      42 47
Сложность комбинационная с ветвлением в (combinational complexity with fan-out s)      35
Сложность комбинационная синхронная (synchronous combinational complexity)      21 23 73 122 123 271
Сложность комбинационная, нелинейные нижние оценки (nonlinear lower bounds to combinational complexity)      73
Сложность правильных схем      122 см.
Сложность программ (для машины Тьюринга) (program complexity)      23 169 192 272 273
Соотношение инвариантное (invariant relation)      187
Сортировка (sorting)      291 297
Сортировка вставками (insertion sorting)      298 303
Сортировка двоичная (binary sorting, binary sorting function)      22 76
1 2
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2020
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте