Cтраница 3
Приведенный выше отрицательный результат будет получен для модели а. Для той же модели а вводится понятие оптимального по точности алгоритма как алгоритма с погрешностью, минимальной среди погрешностей всех алгоритмов решения задачи 5, использующих информацию 9L Помимо того, введены понятия центрального алгоритма и интерполяционного алгоритма. Центральный алгоритм всегда оптимален по точности. Он обладает даже некоторым более сильным свойством оптимальности ( см. замечание 2.2 и гл. Погрешность интерполяционного алгоритма превосходит погрешность оптимального по точности алгоритма не более чем в два раза. Центральные и интерполяционные алгоритмы полезны как на практике, так и в общей теории; по поводу теоретических аспектов см. гл. [31]
Здесь центральный алгоритм посылает в местные алгоритмы значения входных и выходных переменных. Местный алгоритм - проводит оптимизацию / - го блока при фиксированных значениях входных и выходных переменных и посылает в центральный алгоритм значение местного критерия, полученное после местной оптимизации. Задача центрального алгоритма состоит в том, чтобы, управляя всеми входными и выходными переменными блоков, установить оптимальный режим работы всей схемы. [32]
Вы обнаружите, вероятно, что ваша программа тратит большую часть времени на ввод и вывод и совсем немного времени - на перемещение слов в строке. С учетом всего этого ясно, что львиную долю усилий по оптимизации программы следует направить на центральный алгоритм сканирования и на взаимодействие форматора с внешним миром. Обработка команд и алгоритм размещения слов должны быть запрограммированы так, чтобы все было понятно. Как правило, для ввода / вывода следует пользоваться стандартными языковыми средствами, но в данной задаче мы сталкиваемся с тем случаем, когда особенности вашей операционной системы можно употребить с пользой для дела. Важно помнить только, что использование этих особенностей должно быть сконцентрировано в пределах подпрограмм ввода-вывода, а не рассеяно по всему форматору. [33]
Трауб и Вожьняковский [77] положили в основу понятие информации. В их модели допускается рассмотрение линейных и нелинейных задач и информации. Этим было инициировано изучение в общей постановке оценок снизу на сложность. Было введено понятие центрального алгоритма. [34]
Составьте программы, реализующие описанные выше алгоритмы умножения и деления, и все необходимые им служебные подпрограммы. Проследите, чтобы ваши программы не оказались слишком тесно привязаны к вычислению я; библиотека программ для вычислений с высокой точностью может быть полезна и для других задач. Должна быть предусмотрена возможность увеличения точности счета без изменения программ, а лишь путем расширения памяти для результатов. Выходные данные должны включать статистику по использованию каждой программы, по числу выполнений каждого шага двух центральных алгоритмов и по использованию памяти. Сбор такой информации обойдется очень дешево в сравнении со всей работой. [35]