Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 17 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

Пример. Рассмотрим задачу об отыскании квадратного корня
из числа a > 0. Будем использовать соотношение
x
n+1
=
1
2
µ
x
n
+
a
x
n
, x
0
> 0,
до тех пор пока |x
n+1
− x
n
| < ε, где a, ε, x
0
— заданные числа.
Является ли это соотношение описанием алгоритма? Посколь-
ку его можно реализовать в виде программы вычислений на ком-
пьютере, то можно предположить, что ответ положительный.
Однако, начальное значение x
0
> 0 нельзя брать произволь-
ным (так например, при программировании на языке Си или на
Паскале нельзя брать x
0
иррациональным числом), при вычисле-
ниях, возможно, придется использовать "машинную арифметику"
с присущими ей правилами округления и учитывать другие огра-
ничения (на первый взгляд кажется, что использование обыкновен-
ных дробей позволило бы отказаться от округления, но это привело
бы к быстрому исчерпанию ресурсов по памяти и быстродействию).
Таким образом, результат будет зависеть от свойств использу-
емой вычислительной системы (разрядности, правил округления и
т. п.) и программного окружения; однако, упомянутые свойства (во
всем многообразии деталей), как правило, пользователю неизвест-
ны, так что "разработать алгоритм решения" поставленной задачи,
строго говоря, не удастся (на это обстоятельство указывал Н.Вирт).
В приведенном примере упомянутые действия не имеют чет-
кого конструктивного определения. При изучении вопросов распа-
раллеливания подобная неопределенность значительно возрастает
и с этим приходится мириться, но при гигантской сложности со-
временных задач подобная неопределенность требует повышенной
устойчивости параллельных версий алгоритмов.
Будем называть псевдоалгоритмом (с указанной областью
определения) однозначно понимаемую совокупность указаний о вы-
полняемых действиях, считая, что сами действия не обязательно
имеют четкое конструктивное определение. При уточнении опреде-
ления упомянутых действий исходный псевдоалгоритм можно за-
менить новым, называемым уточнением предыдущего. В результа-
те получается цепочка уточняющих псевдоалгоритмов, последним
звеном которой является алгоритм реализации вычислений. Учет
возможных изменений свойств используемой вычислительной си-
стемы (или ее замены) и программного окружения приводит к де-
18

Страницы