Author(s): Трауб Дж., Васильковский Г., Вожьняковский Х.(Traub)
Publisher: Мир
Year: 1988
Language: Russian
Pages: 185
Обложка ......Page 1
Титульный лист оригинала ......Page 3
Титульный лист перевода ......Page 4
Аннотация ......Page 5
От редактора перевода ......Page 6
Предисловие к русскому изданию ......Page 7
Предисловие ......Page 9
Обзор содержания книги ......Page 10
1.1. Введение ......Page 18
1.2. Основные определения ......Page 19
1.3. Нижние оценки ......Page 22
1.4. Верхние оценки ......Page 28
2.1. Введение ......Page 33
2.2. Приближённая информация ......Page 34
2.3. Нижние оценки ......Page 35
2.4. Верхние оценки ......Page 41
3.1. Введение ......Page 44
3.2. Реализуемые алгоритмы ......Page 45
3.3. Нижние оценки ......Page 46
3.4. Верхние оценки ......Page 54
4.1. Введение ......Page 56
4.2. Оптимальная точная информация ......Page 57
4.3. Адаптивность в сравнении с неадаптивностью ......Page 64
4.4. Оптимальная приближённая информация ......Page 69
5.1. Введение ......Page 73
5.2. Модель вычислений ......Page 74
5.3. Понятия сложности ......Page 75
1. ......Page 76
2. ......Page 78
3. ......Page 80
5.5. Три класса алгоритмов ......Page 82
6.2. Алгебраическая теория кодирования ......Page 84
6.3. Распределённые вычисления ......Page 87
6.4. Непрерывный бинарный поиск ......Page 89
6.5. Упаковка в контейнеры ......Page 91
1. Бисекция ......Page 94
2. Уравнения с липшицевыми функциями ......Page 96
3. Полиномиальные уравнения ......Page 99
6.7. Линейные уравнения ......Page 100
1. Большие линейные системы ......Page 101
2. Фиксированная точность ......Page 104
3. Переменная точность ......Page 106
1. Защита баз данных ......Page 108
2. Булевы функции ......Page 110
3. Линейные уравнения ......Page 111
6.9. Модель среднего случая: теория информации и теория принятия решений ......Page 112
1. Теория информации ......Page 113
2. Теория принятия решений ......Page 115
Дополнение А. Интерполяционные алгоритмы ......Page 118
Дополнение В. Внутренние алгоритмы ......Page 126
Дополнение С. Диаметр информации ......Page 132
Дополнение D. Недетерминированные алгоритмы ......Page 136
Дополнение Е. Обобщённая линейная НЛП-задача ......Page 147
Дополнение F. Обобщённая мера погрешности ......Page 155
Дополнение G. Поточечная аппроксимация ......Page 159
Дополнение Н. Дальнейшие результаты о нижних оценках ......Page 170
Литература ......Page 174
Именной указатель ......Page 177
Предметный указатель ......Page 179
Оглавление ......Page 183
Выходные данные ......Page 185
