Название: Информация, неопределённость, сложность
Автор: Дж. Трауб, Г. Васильковский, Х. Вожьняковский
Издательство: Мир
Год: 1988
Формат: djvu
Страниц: 186
Размер: 4,6 Мб
Язык: русский

В книге «Общая теория оптимальных алгоритмов» мы изучали модель наихудшего случая, предполагая, что информация точна, а неопределённость решения измеряется при помощи нормы. В данной книге по-прежнему рассматривается модель наихудшего случая, но допускается, что информация может быть приближённой. Как правило, в результате физических измерений и машинных вычислений получается именно приближённая информация. Мы показываем, как можно измерять неопределённость решения, не вводя нормы. Это дает возможность охватить более широкий круг задач.
Мы развиваем общую теорию, на основе которой можно строить оптимальные алгоритмы и изучать их сложность для любых задач, у которых имеется приближённое решение. Эту науку мы решили назвать теорией е-сложности, потому что неопределённость приближённого решения обычно характеризуется параметром е. Это— вторая монография, посвящённая теории е-сложности. В первой, носящей название «Общая теория оптимальных алгоритмов»!, неопределённость измерялась с помощью нормы. Этот способ подходит для рассмотрения «непрерывных» задач. В данной книге вводится более общая мера неопределённости и строится единая теория, охватывающая как непрерывные, так и дискретные задачи.