Общая теория оптимальных алгоритмов

Трауб Дж., Вожьняковский Х.(Traub)128-132-136-2

Table of contents :
Обложка ……Page 1
Титульный лист оригинала ……Page 3
Титульный лист перевода ……Page 4
Аннотация ……Page 5
От редактора перевода и переводчика ……Page 6
Предисловие к русскому изданию ……Page 7
Предисловие ……Page 8
Рекомендации по чтению книги ……Page 10
Обзор содержания книги ……Page 11
Введение ……Page 16
1. Введение ……Page 18
2. Диаметр и радиус общей информации ……Page 20
Модель вычислений ……Page 29
4. Предмет теории аналитической вычислительной сложности ……Page 35
1. Введение ……Page 38
2. Кардинальность линейной информации ……Page 40
3. Индекс линейной задачи ……Page 43
4. Оптимальные линейные информационные операторы ……Page 48
5. Сходимость и минимальные подпространства для случая гильбертова пространства ……Page 53
6. Связь с $n$-поперечниками по Гельфанду ……Page 56
7. Адаптивная линейная информация ……Page 63
1. Введение ……Page 67
2. Предварительные замечания ……Page 69
3. Линейные оптимальные по точности алгоритмы для линейных функционалов ……Page 70
4. Линейные алгоритмы для линейных операторов ……Page 77
5. Оптимальные линейные алгоритмы и линейные $n$-поперечники по Колмогорову ……Page 82
1. Введение ……Page 86
2. Отклонение ……Page 88
3. Сплайны ……Page 89
4. Сплайновые алгоритмы ……Page 90
5. Гильбертов случай ……Page 94
6. Негильбертов случай ……Page 97
1. Введение ……Page 101
Модель вычислений в линейном случае ……Page 102
1. Введение ……Page 108
2. Линейные функционалы ……Page 110
i) Интерполяция: $Sf=f(x_0)$, $x_0 in [-1; 1]$ ……Page 111
ii) Дифференцирование: $Sf = f'(0)$ ……Page 114
iii) Интегрирование: $Sf=sumlimits_{-1}^{+1}zeta(x),f(x)partial x$ ……Page 116
3. Интерполяция ……Page 119
i) Интерполяция для $W_infty^r$ ……Page 120
ii) Интерполяция для аналитических функций ……Page 123
iii) Интерполяция для случая гильбертова пространства с воспроизводящим ядром ……Page 125
4. Интегрирование ……Page 128
i) Интегрирование функций из $W_p^r$ ……Page 130
ii) Интегрирование функций из $tilde{W}_infty^r$ ……Page 137
iii) Связь с $n$-поперечником по Гельфанду ……Page 140
i) Аппроксимация в абстрактном гильбертовом пространстве ……Page 143
ii) Аппроксимация для $tilde{W}_2^r$ в $L_2$ ……Page 145
iii) Аппроксимация для $W_2^r$ W в $L_2$ ……Page 148
iv) Аппроксимация для $tilde{W}_2^r$ в $C$ ……Page 149
v) Аппроксимация для $W_2^r$ W в $C$ ……Page 152
6. Линейные дифференциальные уравнения с частными производными ……Page 155
i) Линейный оператор в гильбертовом пространстве ……Page 156
ii) Параболические дифференциальные уравнения ……Page 160
iii) Эллиптические дифференциальные уравнения ……Page 164
iv) Гиперболические дифференциальные уравнения ……Page 167
7. Резюме и открытые вопросы ……Page 170
2. Кардинальность нелинейной информации ……Page 175
3. Оптимальная нелинейная информация ……Page 178
4. Связи с $n$-поперечниками по Колмогорову и энтропией ……Page 183
1. Введение ……Page 188
2. Оптимальная неадаптивная линейная информация для нелинейных скалярных уравнений ……Page 191
3. Адаптивная линейная информация для нелинейных скалярных уравнений ……Page 194
4. Нелинейная информация для нелинейных скалярных уравнений ……Page 196
5. Нелинейные операторные уравнения ……Page 199
6. Почти оптимальная неадаптивная линейная информация при поиске максимума унимодальных функций ……Page 203
7. Адаптивная линейная информация при поиске максимума унимодальных функций ……Page 206
2. Основные определения ……Page 212
3. Иерархия сложности для класса $psi_{f}^{non}$ ……Page 214
4. Иерархия сложности для класса $psi_{f}^{a}$ ……Page 216
5. Иерархия сложности для класса $psi_{L}^{non}$ ……Page 217
6. Иерархия сложности для класса $psi_{L}^{a}$ ……Page 218
7. Иерархия сложности для класса $psi_{NON}$ ……Page 219
8. Иерархия сложности для фиксированной задачи $S$ ……Page 220
1. Введение ……Page 221
3. Модель с относительной погрешностью ……Page 222
4. Модель с возмущениями ……Page 225
5. Асимптотическая модель ……Page 226
1. Введение ……Page 230
2. Диаметр и порядок информации ……Page 234
Модель вычислений ……Page 243
4. Кардинальность линейной информации ……Page 248
5. Когда класс итерационных алгоритмов пуст? ……Page 252
6. Индекс задачи $S$ ……Page 255
7. Итерации $m$-го порядка ……Page 260
Модель вычислений для итеративной линейной информации ……Page 264
9. Информационный оператор с памятью ……Page 269
10. Некоторые дополнения и открытые проблемы ……Page 277
Добавление ……Page 281
1. Введение ……Page 284
2. Краткий исторический очерк ……Page 286
3. Аннотированная библиография ……Page 288
К части А ……Page 346
К части В ……Page 359
К части С ……Page 361
К части А ……Page 362
К части В ……Page 369
Именной указатель ……Page 373
Предметный указатель ……Page 377
Оглавление ……Page 380