Зміст
Вступ 3
§ 1. Основні положення 4
§ 2. Перевірка правильності виразів 13
§ 3. Оцінка складності алгоритмів 16
§ 4. Оптимізація програм 19
§ 5. Результати і висновки 23
Література 24
Додаток 1. Програмна реалізація алгоритмів POSTFIX та ІТР 25
Додаток 2. Програмна реалізація простого компілятора виразів 29
Вступ.
В наш час електронно-обчислювальні машини та інформаційні технології стали невід’ємною частиною промисловості та міцно ввійшли в побут простих громадян. І хоча сучасні комп’ютери здатні виконувати набагато складніші задачі ніж могли їхні пращури з 60-х років двадцятого століття, все рівно математична обробка інформації була, є і в майбутньому буде основою їх роботи. Кожен найсучасніший комп’ютер - чи він застосовується для обробки зображень, чи для проектування автомобілів, чи виступає в ролі ігрового автомату - все рівно, в першу чергу, він є обчислювальною машиною. Арифметичні та логічні вирази є невід’ємною частиною практично всіх, навіть вузькоспеціалізованих, комп’ютерних програм і тому потрібно мати у наявності алгоритми, які розпізнають і обчислюють їх якомога швидше і ефективніше. Тема обчислення виразів проходить через більшу частину програмування; з нею пов’язані синтаксис і семантика алгоритмічних мов, компіляція, формальні мови, структури даних, логіка, рекурсія і обчислювальна складність. Тому наукові розробки даного напрямку є важливими не тільки зараз - вони збережуть свою актуальність і в майбутньому.
Яка ж мета ставилася при написанні даної роботи ? Серед основних цілей можна назвати слідуючі:
Оскільки критерієм істини є практика, то не менш важливим моментом даної дипломної роботи є практична реалізація алгоритмів обчислення виразів на одній з мов програмування і перевірка на практиці ефективності методів оптимізації.
§1. Основні положення.
Існує принаймні три різні способи означення арифметичних виразів. Підручники з програмування для початківців, як правило, подають їх на прикладах. Цілком логічна основа цього підходу полягає в тому, що можна навчитися писати правильні вирази, переглянувши достатню кількість прикладів. Це у великій мірі схоже на навчання деякої не рідної для людини іноземної мови. Так як було відмічено, що більшість програмістів використовують в своїх програмах доволі прості вирази, то цей підхід у більшості випадків виявлявся цілком прийнятним.
Більш формальний підхід полягає в тому, що синтаксис і семантику арифметичних і логічних виразів задають за допомогою контекстно-вільних правил перетворення, як це зроблено в описі Алголу. Проміжний підхід, зберігаючи деяку долю математичної точності визначень і в значній мірі розрахований на інтуїцію, полягає у визначенні цих виразів індуктивно або рекурсивно.
Арифметичний вираз індуктивно визначається наступним чином:
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)))
Якщо це правильний арифметичний вираз, то повинна існувати можливість побудови його за допомогою правил 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
Л П
Послідовність записаних символів, +АВ називається префіксною формою арифметичного виразу, оскільки знак операції (+) передує операндам А і В. Якщо якась з нижніх вершин А або В сама є кореневою вершиною, тобто містить не операнд а операцію, то для обчислення загального виразу ми повинні обчислити цей підвираз, і тому до цієї вершини рекурсивно застосовуємо те ж саме правило (вважаючи цю нижню вершину кореневою): записуємо операцію в вершині (В), лівий операнд (Л), правий операнд (П). В результаті ми отримаємо лінійний бездужковий запис виразу по якому можна однозначно відтворити вихідне бінарне дерево. Вкажемо правило яке дозволяє це здійснити.
Читаємо префіксний запис виразу посимвольно (він обов’язково починається знаком операції), записуємо знак операції у вершину, зчитуємо два наступні символи і якщо вони є операндами (змінними чи константами) то для даної вершини будуємо дві дочірні вершини, записуючи в ліву перший операнд, а в праву - другий; якщо якийсь з двох символів є не операндом а операцією, то для цієї дочірньої вершини рекурсивно застосовуємо це ж саме правило.
Префіксна форма запису є вдалою в тому розумінні, що нам не потрібно використовувати дужки і вводити пріоритет операцій, хоч ми все рівно можемо однозначно обчислити вираз.