| Головна » Статті » Математика | [ Додати статтю ] |
Оптимальні програми - реферат українською
|
Зміст Вступ 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, отже знову виконується твердження. | |
| Переглядів: 453 | |
| Всього коментарів: 0 | |