Оптимальні програми

Якщо це правильний арифметичний вираз, то повинна існувати можливість побудови його за допомогою правил 1- 5. Неважко переконатися, що така можливість дійсно існує. Але можливе і інше представлення цього арифметичного виразу - за допомогою кореневого бінарного дерева, як показано на малюнку 1.

Відмітимо, що всі кінцеві вершини цього дерева відповідають змінним або операндам, а всі внутрішні вершини відповідають арифметичним операціям. Дерево є бінарним (тобто кожна вершина має або дві дочірні вершини, або не має їх взагалі), оскільки ми домовилися використовувати у виразах лише бінарні (двохмісні) алгебраїчні операції. Кожному правильно записаному арифметичному виразу однозначно ставиться у відповідність дерево виразу. Якщо задано таке дерево, то вираз однозначно обчислюється при відомих значеннях змінних. Потрібно також відмітити, що деякі з проміжних обчислень, необхідних для отримання значення всього виразу, можна провести паралельно. Наприклад віднімання А-В можна виконувати паралельно з піднесенням до степеня E^F.

Мал. 1

Логічні вирази можна означити так само, як і арифметичні. А саме:

1.Будь яка логічна константа є логічним виразом.

2.Будь яка логічна змінна є логічним виразом.

3.Довільний предикат при заданих значеннях аргументів є логічним виразом.

4.Якщо Х – логічний вираз, то (Х) – теж логічний вираз.

5.Якщо Х і У – обидва є логічними виразами, то логічними виразами також будуть (X AND У), (X OR У) і (NOT X).

6.Жоден об’єкт не є логічним виразом, якщо той факт, що він є логічним виразом не слідує з скінченого числа застосувань правил 1 – 5.

Приклад правильно записаного логічного виразу

(((NOT A) AND B) OR (C AND (D OR E)))

Аналізуючи наведені вище приклади, можна відмітити, що означення арифметичних та логічних виразів містять, напевно, зайві дужки. Можна дати означення, що не потребують такої кількості дужок, але такі означення неминуче приводять до двозначності. Наприклад, вирази

A + B / C або NOT A AND B

повинні обчислюватися з використанням правил пріоритету, які встановлюють, що ділення ( / ) має більший пріоритет, ніж додавання ( + ), а NOT має більший пріоритет, ніж AND. З врахуванням цих пріоритетів, вираз A+B/C еквівалентний виразу (A+(B/C)), а NOT A AND B еквівалентний ((NOT A) AND B). В наших означеннях ми ввели дужки для більшої математичної строгості.

Необхідно відмітити, що три різні способи проходження дерева (мал.1) приводять до трьох різних способів запису відповідних виразів в вигляді лінійної послідовності символів. Розглянемо дерево простого арифметичного виразу (А+В), наведене на малюнку 2. Якщо ми почнемо з кореня (верхньої точки) (В) і запишемо +, потім перейдемо до лівої (Л) нижньої вершини і допишемо А, а далі повернемося знову в корінь і спустимося вправо (П) і напишемо В, то такий порядок проходу вершин дерева є прямим.

В

Мал. 2

ЛП