Оптимальні програми - реферат українською
Зміст
Вступ 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, отже знову виконується твердження.
Вступ 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, отже знову виконується твердження.
Скачати реферат Оптимальні програми
Схожі українські реферати
|
1. Реферат: Опозиція однократності / багатократності у сучасній аспектології Аспектуальність як понятійна категорія є предметом постійного вивчення науковців (Н. Арутюнової, Б. Баліна, О. Бондарка, В. Гака, І. Долініної, О.Кубрякової, Ю. Маслова, Н. Слюсарєвої, С. Швачко, Б. Комрі, О. Єсперсона, А.Хорнбі, Дж. Лакофа, З. Венд... 2. Реферат: Опорно-рухова система. Значення опорно-рухової системи Опорно-рухова система. Значення опорно-рухової системи 1.Захисна функція. Кістки скелету захищають внутрішні органи від механічних пошкоджень (кістки черепа, хребта, грудної клітки, таза). 2.Рухова функція. Виконують кістки кінцівок та хребта. ... 3. Реферат: ОПОРНО-РУХОВИЙ АПАРАТ Одним з важливих моментів пристосування організму до навколишнього середовища є рух. Він здійснюється системою органів, до яких належать кістки, їх з'єднання і м'язи, що об'єднані в єдине ціле — апарат руху, або опорно-рухову систему. Усі кістки, з'є... 4. Реферат: Опорядження будівельних конструкція в заводських умовах Щоб зменшити трудові витрати на опоряджувальні роботи на будівельних об'єктах і скоротити строки їх виконання, будівельні конструкції (стінові панелі, перегородки, панелі перекриття, віконні і дверні блоки тощо) повинні надходити на об'єкти максималь... 5. Реферат: Опоряджувальні роботи в будівництві Опоряджувальні роботи в будівництві Вступ Капітальне будівництво є однією з найвагоміших галузей народного господарства. Від якої залежить ефективність функціонування всієї системи господарювання в країні. Від розвитку будівництва залежить тако... 6. Реферат: Опрацювакння плану використання засобів масової інформації в рекламних цілях Рекламодавці або на їх доручення рекламні агенції використовують бюджет маркетингових комунікацій у частині витрат на засоби масової інформації, ураховуючи ефективність цих засобів. Цілі рекламування й бюджетні кошти визначають основні напрями ро... 7. Реферат: Опрацювання плану маркетингових комунікацій підприємства Опрацювання плану маркетингових комунікацій підприємства Під поняттям «менеджмент маркетингових комунікацій» фахівці! розуміють аналіз проблем, а також планування, організацію, проведення та контроль заходів, спрямованих на вирішення цих проблем. ... 8. Реферат: Оприлюднена бухгалтерська звітність та методика її читання Оприлюднена бухгалтерська звітність та методика її читання Зміст практичного заняття: перевірка обчислення та сплати ПДВ і акцизного збору; прибуткового податку з громадян та ін. (див. дод. 9,10,11). Розділ 2. Техніка аудиту. Аудиторський ризик ... 9. Реферат: Оптимальна технологія вирощування столових буряків За калорійністю столовий буряк перевищує всі інші соковиті овочі. У його коренеплодах містяться вуглеводи, вітаміни (С, В, РР), органічні кислоти, солі Са, Мg, Fе, пектин. За вмістом фосфору та калію він посідає одне з перших місць серед овочевих ку... 10. Реферат: Оптимальне керування в рівняннях еліптичного типу Нехай G - обмежена область в Rn з кусково-гладкою границею Розглянемо в G рівняння Будемо також вважати, що вектор u належить множині керувань U, а коефіцієнти вимірні майже всюди обмеженіфункції, причому майже всюди невід’ємні і існує...
11. Реферат: Оптимальні програми
Зміст Вступ 3 § 1. Основні положення 4 § 2. Перевірка правильності виразів 13 § 3. Оцінка складності алгоритмів 16 § 4. Оптимізація програм 19 § 5. Результати і висновки 23 Література... 12. Реферат: Оптимізація грошових потоків вугільних шахт на основі моделі максимізації чистого грошового потоку Вугільна промисловість України знаходиться в складному стані, що викликано рядом факторів – накопиченням і вчасним нерозв’язанням проблем, починаючи з 1980-х років, надважкими умовами видобутку вугілля в регіоні Донбасу, затягненою і неоптимальною ре... 13. Реферат: Оптимізація оподаткування як засіб запобігання ухилення від сплати ПДВ Лише зовсім недавно в українській науковій літературі з’явилися нові терміни: “податкове планування”, “податковий менеджмент”, “оптимизація оподаткування”. При цьому податкові органи і платники податків зайняли практично діаметральні позиції щодо пит... 14. Реферат: Оптимізація фізичного стану учнів ліцею засобами військово-фізичної підготовки Сьогодні, одним з найбільш ефективних шляхів вирішення завдань фізичного виховання у загальноосвітніх навчальних закладах, переважна більшість фахівців [2, 3, 8] вважає розробку і реалізацію на практиці відповідних педагогічних технологій. Це пов’яз... 15. Реферат: ОПТИМІЗМ ТА ПЕСИМІЗМ НА ЕТАПІ СТАНОВЛЕННЯ ЗАГАЛЬНОСВІТОВОЇ ЦИВІЛІЗАЦІЇ Проблема світової цивілізації — це проблема співвідношення універсального та локального, центру та периферії нового рівня суспільного розвитку. Проблема універсального дедалі частіше опиняється в центрі уваги сучасних дослідників, що пов'язано з о... 16. Реферат: Оптична система ока Око як жива камера Обскура Часто око називають живою камерою Обскура, але як більшість аналогій і ця аналогія вірна лише частково. Око являє собою нескінченно більш тонкий і складний прилад, чим найкращий фотоапарат, хоча в принципі вони однаков... 17. Реферат: Оптові ціни, їх різновиди Оптові ціни, їх різновиди Оптова ціна виробника утворюється приєднанням до повної собівартості продукції нормального прибутку, тобто такої, котра забезпечує підприємствам можливість розширеного відтворення в основному за рахунок власних коштів. ... 18. Реферат: Опукла оболонка Означення. Афінна геометрія складається з множини скалярів S (дійсних чисел), множини точок P та множини вільних векторів V (або просто векторів). Точки використовуються для задання положення, а вектори – для задання напрямку та величин, хоча вони і ... 19. Реферат: Опуклі множини У курсі “Математичне програмування” та в деяких економічних дослідження використовуються поняття опуклої лінійної комбінації векторів та опуклої множини. Спочатку ознайомимось з поняттям опуклої лінійної комбінації векторів. Нехай на площині задані... 20. Реферат: Опуклість та гнучкість функції. Екстремуми функції. Необхідна та достатні умови екстремуму. Метод найменших квадратів 1. Найбільше та найменше значення функцій у заданій області. Контрольні запитання 1. Що називається екстремумом функції. 2. Яка необхідна умова екстремуму функції. 3. Яка точка називається стаціонарною. 4. Які достатні умови екстремуму функції ... 21. Реферат: ОПУСТЕЛЮВАННЯ Один із найзагрозливіших, глобальних і швидкоплинних процесів сучасності — розширення опустелювання, падіння, повне знищення біологічного потенціалу Землі, що приводить до умов, аналогічних умовам природної пустелі. Природні пустелі і напівпустелі... |
|