13.5.2.Оптимизация линейных программ

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

Пример 3. Программа вычисления координат вектора, повернутого на угол Alfa.

Program Vector;

Var X, Y : Real;

Alfa : Real;

U, V : Real;

Begin

{ Ввод X, Y, Alfa }

U := X*Cos(Alfa) + Y*Sin(Alfa);

V := –X*Sin(Alfa) + Y*Cos(Alfa);

{ Вывод U, V }

End.

В этом варианте сложность программы T(U, V) есть T(U, V) = 4T_f + 4T_m + 2T_a

Осуществим предварительное вычисление функций Sin, Cos:

{ Описать вспомогательные переменные Fsin, Fcos }

Begin

{ Ввод X, Y, Alfa }

Fsin := Sin(Alfa); Fcos := Cos(Alfa);

U := X*Fcos + Y*Fsin;

V := –X*FSin + Y*Fcos;

{ Вывод U, V }

End.

Получим: T(U, V) = 2T_f + 4T_m + 2T_a

В результате преобразования сложность уменьшилась примерно вдвое. Можно еще уменьшить мультипликативную сложность, если вычислить U и V следующим образом:

A := (Fcos + Fsin)*(X + Y);

B := X*Fsin; C := Y*Fcos;

U := A – B – C;

V := C – B;

Тогда T(U, V) = 2T_f + 3T_m + 5T_a

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

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

Отметим в заключение, что рассмотренные оптимизационные приемы имеет смысл приме­нять тогда, когда вычисления повторяются в программе достаточно часто и время выполне­ния программы – критический параметр.

13.6. Ветвящиеся программы

13.6.1. Понятие условия. Тип данных Boolean (логический)

Условия используются в программах для организации ветвлений и повторяющихся действий. Условием в языке является логическое выражение – выражение типа Boolean. Булевские значения – это логические истинностные значения: True (истина) и False (ложь).

Этот тип данных, как и другие простые типы данных, упорядочен. На нем определены функции Ord, Succ, Pred. Таким образом, имеют место следующие соотношения:

False < True ,

Ord (False)=0, Ord (True)=1,

Succ (False)=True, Pred (True)=False.

На множестве {True, False} определены логические операции:

And – логическая коньюнкция (И)

Or – логическая дизньюнкция (ИЛИ)

 Not – логическое отрицание (НЕ)

Эти операции определяются следующими таблицами истинности:

And	False	True		Or	False	True		x	Not x
False	False	False		False	False	True		False	True
True	False	True		True	True	True		True	False

 Отношения, определенные ранее для простых стандартных типов являются операциями, результат которых имеет логический тип. Иными словами, булевское значение дает любая из операций отношений : =, < > , <= , < , > , >= , in.

Для типа Boolean определены стандартные функции, принимающие значения этого типа (логические значения):

Odd(Х) { Odd(Х) = True, если Х – целое нечетное число

Odd(Х) = False, если Х – целое четное число}

Eoln(F) { конец строки в текстовом файле}

Eof(F) { конец файла}

Функции Eoln(F) и Eof(F) будут определены при описании файлов.

Условия можно классифицировать как простые и сложные.

Простые условия определены диаграммой: 

Простое условие

Сложные условия конструируются из простых с помощью логических операций.

Приведем примеры простых и сложных выражений типа Boolean (условий). Простые выражения типа Boolean (условия):

Sin(2*x) > Ѕ,

(X + Y) mod Prime = 0,

 b*b > 4*a*c ,

 Number div Modulo = 2,

Odd(A*P + B),

Flag ;

Сложные выражения типа Boolean (условия):

а) (а + i > в) or ( х [Index] = с )

{ Здесь а, в, с – переменные типа Real, х – массив вещественных чисел , Index – переменная типа Integer }

б) Odd (n) And (n < 10е4)

в) Eof(f) Or (f^.data = 0) {f – файл действительных чисел}

г) Not(beta) And (gamma) {beta и gamma – переменные типа Boolean}

д) (A > B) = (C > D)

Логические выражения преобразуются по законам логики высказываний. Например,

Not((A > 0) And (B <> 0))  Not(A > 0) Or Not(B <> 0)  (A <= 0) Or (B = 0)

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