ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ

Я пишу это предисловие ровно через 20 лет после выхода в свет первого американского издания. Поэтому уместно остановиться на перспективах развития излагаемого предмета. Сегодня я озаглавил бы свою книгу «Теория оптимальных итерационных методов». Такое название представляется более информативным. Кроме того, вместо вычислительной эффективности я использовал бы понятие вычислительной сложности. Эти понятия являются взаимно обратными и, следовательно, взаимозависимыми. В то же время термин «сложность» сегодня широко используется в вычислительной математике. Впервые термин «вычислительная сложность» появился в 1965 г., через год после выхода книги в свет.

Изучение сложности предполагает выявление связи между информацией, используемой алгоритмом, и его порядком. Ключевая роль в исследованиях по оптимальности итерационных алгоритмов принадлежит тому факту, что максимальный порядок алгоритмов некоторого класса определяется информацией, используемой алгоритмами, и не зависит от их структуры.

Данная монография положила начало исследованиям оптимальных итерационных алгоритмов, и за прошедшее время в этой области получено немало результатов. В 1975 г. Вожьняковский ввел понятие порядка информации, служащее универсальным средством нахождения порядка итерационных алгоритмов. В 1974 г. Кунг и Трауб высказали гипотезу о том, что итерационный алгоритм, который вычисляет значений функции и ее производных и не использует ранее вычисленную информацию, имеет порядок не выше Эта гипотеза доказана для важных частных случаев (например, эрмитовой информации), однако в общем случае вопрос остается открытым. Свежие результаты, относящиеся к этой проблематике, изложены в частях монографии Дж. Трауба и X. Вожьняковского «Общая теория оптимальных алгоритмов». — М.: «Мир», 1983.

Подход, при котором основное внимание уделяется свойствам используемой алгоритмами информации, а не структуре алгоритмов, оказался очень плодотворным и в областях, не связанных с решением нелинейных уравнений. Теорию оптимальных алгоритмов решения задач с неполной информацией мы недавно решили назвать теорией сложности информации (Information Based Complexity). Помимо указанной выше книги, эти вопросы рассматриваются в монографии J. F. Traub, G. W. Wa-silkowski, Н. Wozniakowski, Information, Uncertainty, Complex xity, Addison-Wesley, 1983 (см. также Information and Computation в книге Advances in Computers, Academic Pess, 1984).

В 1985 г. издательство Academic Press начнет издание журнала Journal of Complexity, в котором будут широко представлены исследования по проблемам сложности информации. Нью-Йорк, ноябрь 1984 Дж. Ф. Трауб