§ 3.7. Требования, предъявляемые к вычислительным алгоритмам

В § 3.4 и 3.5 были сформулированы два важнейших требования — корректность и хорошая обусловленность. Помимо них к алгоритмам предъявляется еще целый ряд существенных требований.

1. Требования к абстрактным алгоритмам.

К числу этих требований относятся: 1) экономичность; 2) надлежащая точность; 3) экономия памяти; 4) простота.

Экономичность алгоритма измеряется числом элементарных операций, необходимых для его реализации, и в конечном итоге сводится к затратам машинного времени. Это требование формулируют иногда как требование максимальной быстроты исполнения алгоритма. Экономичность особенно важна при массовых расчетах. Естественно, что при создании алгоритмов большое внимание уделяют минимизации числа операций. Для некоторых задач разработаны алгоритмы, требующие минимально возможного числа операций. Пример такого алгоритма — схема Горнера (см. пример 3.19). Отметим, что ряд математических алгоритмов, созданных в домашинный период, оказался удивительно неэкономичным. Приведем классический пример такого алгоритма.

Пример 3.34 (правило Крамера). Для решения системы

линейных алгебраических уравнений порядка по правилу Крамера предлагается вычислять компоненты вектора х как отношения специальным образом построенных определителей: Если вычислять определитель непосредственно по его определению, то нужно выполнить умножений и сложений. Пусть для вычислений используется ЭВМ с производительностью умножений в секунду и решается система с числом неизвестных весьма скромным для приложений. Тогда вычисление только одного определителя потребует умножений, в результате чего на вычисление решения уйдет около 10 лет непрерывной работы ЭВМ. Вместе с тем для решения той же системы на той же ЭВМ методом Гаусса (см. гл. 5) потребуется примерно 0.002 с. Естественно, что как вычислительный алгоритм правило Крамера следует забраковать.

Даже для самых простых задач выбор экономичного алгоритма может дать существенное уменьшение числа операций.

Пример 3.35. Пусть требуется вычислить где натуральное число. Вычисление этой величины последовательным умножением на предполагает выполнение операций умножения. Нетрудно убедиться в том, что этот способ не самый экономичный. Например, можно найти, выполнив не 63, а всего 6 операций умножения, если последовательным возведением в квадрат вычислить

В общем случае представим в виде разложения (2.25) по степеням двойки (именно так число хранится в памяти ЭВМ). Тогда

Заметим, что в произведении (3.24) следует учитывать при вычислении только те сомножители, для которых (т.е. Алгоритм, основанный на разложении (3.24), называется бинарным алгоритмом. Он позволяет найти не более чем за операций умножения.

Требование точности означает, что вычислительный алгоритм должен давать решение задачи с заданной или приемлемой для задачи точностью

Важным является требование экономии памяти. Хотя в последнее время доступная память ЭВМ существенно расширилась, для "больших" задач требование экономии памяти может в ряде случаев стать основным. Интерес к экономному размещению информации в памяти возрастает в связи с более широким использованием персональных ЭВМ для решения научно-технических и инженерных задач.

Учитывая необходимость дальнейшей программной реализации алгоритма, подчеркнем, что простота алгоритма также является весьма желательным его свойством.

2. Требования к программным реализациям алгоритмов.

К настоящему времени выработан ряд требований к программам, реализующим вычислительные алгоритмы и предназначенным для длительного и широкого использования. Перечислим некоторые из них: 1) надежность; 2) работоспособность (робастность); 3) переносимость (порта-бельность); 4) поддерживаемость; 5) простота в использовании и др Рассмотрим эти требования более подробно.

Надежность программы означает, что она не содержит ошибок и вычисляет именно тот результат, для которого она предназначена. Работоспособность (робастность) включает в себя надежность и предполагает, что программа способна выявлять недопустимые исходные данные, обнаруживать различные критические для задачи или алгоритма ситуации. Робастная программа реагирует на такие ситуации приемлемым для пользователя образом. Она составлена так, чтобы исключить какие-либо аварийные остановы, в том числе по переполнению, из-за деления на нуль, неудачной попытки применить операцию извлечения квадратного корня или взятия логарифма от отрицательного числа.

Алгоритм может "потерпеть неудачу" при решении задачи, если заданное входное данное не является для него допустимым. Конечно, в простых ситуациях пользователь должен сам различать допустимые для алгоритма входные данные от недопустимых. Однако чаще всего сделать это до вычислений очень трудно или невозможно, и в программе должен быть предусмотрен анализ данных и сообщение пользователю о недопустимых или сомнительных данных. Необходимо исключить ситуацию, характерную для некачественных программ, когда реакцией на задание данных, при которых алгоритм не может по объективным причинам найти решение задачи, является аварийный останов или же выдача внешне вполне правдоподобного, но совершенно бессмысленного результата.

Переносимость (портабельность) означает, что программа может работать на различных ЭВМ без изменения или с незначительными изменениями. Всякая характеристика ЭВМ, используемая в программе (например, значение машинного эпсилон должна или вычисляться самой программой, или задаваться пользователем.

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

Плохое описание программы в лучшем случае способно вызвать к ней недоверие, а в худшем — может не позволить пользователю правильно ее эксплуатировать. К сожалению, нередка ситуация, когда предназначенная для широкого использования программа настолько плохо документирована, что пользователь предпочитает потратить время на написание аналогичной программы (возможно, гораздо худшего качества) либо вообще отказаться от решения задачи.

Простота о использовании программы — весьма желательное, но трудно достижимое свойство. Зачастую добиться простоты в использовании можно только жертвуя надежностью или экономичностью. Существует ряд широко используемых программ, которые, в первую очередь, популярны, благодаря простоте в использовании.

3. Противоречивость требований.

Можно продолжить перечисление требований к вычислительным алгоритмам, добавив, например, требования универсальности и гибкости. Однако нетрудно понять, что сформулированные требования противоречивы. Большинство из них вступает в противоречие с экономичностью, выраженной через затраты машинного времени. В разных ситуациях на первый план может выступать то или иное требование и, удовлетворяя в большей степени одним требованиям, программа с неизбежностью в меньшей степени удовлетворяет другим. Это частично объясняет наличие большого числа программ, предназначенных для решения одной и той же задачи.

Естественно, что хорошая программа, которую можно предъявить для широкого использования, не может быть простой. Следует признать, что составление таких программ — это работа, требующая высокой квалификации и специальных знаний. Ее выполняют специалисты по созданию математического обеспечения ЭВМ. Рядовой пользователь должен по возможности стремиться максимально использовать стандартные программы, а не создавать новые.