Оптимальні програми
Більш формальний підхід полягає в тому, що синтаксис і семантику арифметичних і логічних виразів задають за допомогою контекстно-вільних правил перетворення, як це зроблено в описі Алголу. Проміжний підхід, зберігаючи деяку долю математичної точності визначень і в значній мірі розрахований на інтуїцію, полягає у визначенні цих виразів індуктивно або рекурсивно.
Арифметичний вираз індуктивно визначається наступним чином:
1.Довільна змінна є арифметичним виразом.
2.Довільна константа є арифметичним виразом.
3.Довільне посилання на арифметичну функцію є арифметичним виразом.
4.Якщо Х – арифметичний вираз, то (Х) – теж арифметичний вираз.
5.Якщо Х і У обидва є арифметичними виразами, то арифметичними виразами також будуть (Х+У), (Х-У), (Х*У), (Х/У), (Х^У).
6.Жоден об’єкт не є арифметичним виразом, якщо той факт, що він є арифметичним виразом не слідує з скінченого числа застосувань правил 1 – 5.
Це означення дає набір ефективних правил, придатних для побудови довільного арифметичного виразу в термінах змінних, констант, посилань на функції і операцій +, -, *, /, ^.
Для спрощення подальшого викладу, ми до кінця даного параграфу накладемо наступні обмеження на арифметичні вирази:
•всі змінні та константи позначаються великими буквами латинського алфавіту;
•у виразах зустрічаються тільки бінарні алгебраїчні операції +, -, *, /, ^;
•у виразах немає викликів алгебраїчних функцій.
Ці обмеження дають змогу побудувати прості і очевидні алгоритми маніпуляцій з виразами. В наступних параграфах ці обмеження буде знято, а всі алгоритми узагальнено.
Твердження 1.
У правильно побудованому арифметичному виразі, що містить лише бінарні алгебраїчні операції, кількість операндів на 1 більше кількості операцій.
Доведення. Правильно побудований вираз найменшої довжини має вигляд А або (А), де А - деякий операнд. В цьому виразі кількість операндів 1, кількість операцій 0, отже твердження виконується. Найменший вираз, що містить операцію має вигляд (А операція1 В). Тут кількість операндів 2, а операцій - 1, отже знову виконується твердження.Припустимо, що твердження виконується для всіх правильно побудованих виразів довжини не більше k. Згідно означення, отримати арифметичний вираз довжини k+1 можна тільки з двох виразів довжини не більше k, і тільки в такий спосіб - (ВИРАЗ1 ОПЕРАЦІЯ1 ВИРАЗ2). Якщо ВИРАЗ1 містить n операцій і n+1 операндів, ВИРАЗ2 - m операцій і m+1 операндів, то їх об’єднання (ВИРАЗ1 ОПЕРАЦІЯ1 ВИРАЗ2), яке є правильно побудованим арифметичним виразом, відповідно буде містити n+m+1 операцій (додалася ще одна операція - ОПЕРАЦІЯ1) і n+1+m+1 операндів. Отже твердження виконується. Згідно принципу математичної індукції воно буде виконуватися для виразів довільної довжини.
Розглянемо вираз
(((А-В)*С)+(D/(E^F)))