Зміст
Вступ 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, отже знову виконується твердження.
|