1.4 Комп’ютерне та імітаційне моделювання

 

     1.4.1 Алгоритми і програмування

 

Термін «алгоритм» («алгорифм», «алгоризм») походить від імені узбецького математика Ал-Хорезмі, який в IX сторіччі розробив правила арифметичних дій над числами в десятковій системі.

Алгоритм (algorithm) – це правило, яке сформульовано на певній мові та визначає процес переробки допустимих вихідних даних в результати пошуку. Алгоритм характеризується: детермінованістю (визначеністю) – однозначністю результату процесу при заданих вихідних даних; дискретністю – розподіленням алгоритмічного процесу на окремі елементарні акти, можливість виконання яких людиною або машиною не викликає сумнівів; масовістю – вихідні дані для алгоритму можна вибирати з певної безлічі даних (потенційно безкінечних); зрозумілістю для виконавця.

У структурі алгоритмів можна виділити ряд блоків, що є сукупністю елементарних операцій, що виконують певну функцію. Типовими блоками в структурній схемі алгоритму є: процес, рішення, модифікація, попередньо визначений процес, введення-виведення, з'єднувач, пуск-зупинка. Їх умовні позначення представлені у табл. 1.3.

Алгоритм може мати лінійну, розгалужену та циклічну структури. Лінійна структура характеризується відсутністю умовних блоків. На рис.1.3 наведений приклад алгоритму для вирішення завдання зміни місць вмісту двох елементів пам'яті комп’ютера R і Р. Причому, виявляється необхідним використання третьої комірки С.

Рисунок 1.3 - Приклад алгоритму

Таблиця 1.3

Типові блоки у структурній схемі алгоритму

Процес – обчислювальний блок

Арифметичний вираз

Розв’язок – умовний блок

Модифікація – зміна команди або програми

Наперед визначений процес – використання готових алгоритмів або програм

Введення – виведення даних

З’єднувач – вказівник зв’язку між перерваними схемами

Пуск-зупинка – початок або кінець алгоритму

В якості прикладу розгалуженої структури алгоритму, яка має хоч один умовний блок, може слугувати алгоритм вибору найбільшого значення змінних N і М (рис. 1.4). Широко розповсюдженою при вирішенні інженерних завдань є циклічна структура (рис. 1.5), де 1 – підготовка до першого виконання тіла циклу; 2 – тіло циклу, яким називається частина обчислювального процесу, що багато разів повторюється; 3 – підготовка до чергового виконання тіла циклу; 4 – управління циклом, яке виконує перевірку на закінчення циклу.

Рисунок 1.4 – Розгалуджена структура алгоритму

Рисунок 1.5 – Циклічна структура алгоритму

Розрізняють наступні види циклів: із заданим або обчислюваним числом повторень; ітераційні, в яких число повторень заздалегідь невідоме; складні, з розгалуженням у тілі циклу і вкладеними циклами (кратні).

Також існують інші способи запису алгоритмів – у вигляді операторної або граф-схеми.

Для зображення операторної схеми алгоритму використовуються арифметичні і логічні оператори. Арифметичні оператори виконують дії, пов'язані з обчисленнями.

Позначимо операторів заголовними буквами латинського алфавіту з індексами, які вказують номер оператора. Після виконання операцій, передбачених арифметичним оператором, процес обчислень може бути продовжений єдиним шляхом, незалежно від результатів, що видаються оператором. Передача управління від арифметичного оператора позначається номером того оператора, якому передається управління, та записується справа вгорі від символу даного оператора. Наприклад, запис означає, що від оператора управління передається операторові з номером S.

Логічні оператори призначені для перевірки виконання заданих умов. Позначимо їх буквою Р зі вказівкою номера оператора. Після реалізації логічного оператора управління передається одному з двох операторів залежно від виконання умови, що перевіряється. Передача управління від логічного оператора позначається стрілками з номерами тих операторів, яким передається управління. Наприклад, означає, що від логічного оператора керування передається операторові з номером i, якщо умова, яка перевіряється оператором, виконана, або ж оператору з номером j, якщо вона не виконана. Для операторів, як арифметичних, так і логічних, позначення передачі від одного оператора до іншого, наступного за ним, опускається.

Передача управління даному оператору від інших позначається номером того оператора, від якого передається управління, та записується зліва зверху від символу даного оператора. Наприклад, запис означає, що оператору управління передається від оператора з номерами l і n. В цьому випадку алгоритм, структура якого представлена на рис. 1.4, може бути записаний таким чином (блоки позначаються цифрами):

Граф-схема

Операторна схема

У наш час велику популярність набули методи структурного програмування (structured programming), де в якості єдиних трьох видів структур алгоритмів застосовуються ЗЧЛЕНУВАННЯ, ВИБІР і ПОВТОРЕННЯ. Основним методом створення програм при цьому є алгоритм покрокової деталізації, в якому без складання блок-схеми програміст поступово пересувається по тексту програми, послідовно організовуючи і деталізуючи шари, які відповідають різним рівням абстракції, використовуючи при цьому спеціальну універсальну мову структурного програмування, наприклад PDL. Складена таким чином програма може бути легко і однозначно переведена на будь-яку, зручну для користувача, мову програмування.

Знаходження алгоритмів вирішення різних класів завдань – одна з цілей математики. Мета ж прикладної математики стосовно використання комп’ютерів – знаходження комп’ютерних алгоритмів вирішення практичних (інженерних) завдань.

 

     1.4.2 Особливості комп’ютерного моделювання

 

Багато явищ і процесів різної природи описуються аналогічними співвідношеннями, наприклад, електроакустична аналогія, електро-, магнітно- і гідродинаміка. Тому для аналізу (розв’язання, розрахунку) математичних моделей необхідно володіти розвиненим математичним апаратом, що охоплює всі види типових завдань прикладної математики. Стосовно використання комп’ютерів основним етапом розрахунку математичних моделей є їх алгоритмізація, тобто розробка структури алгоритму, представленого у вигляді блок-схеми, граф-схеми або програмно-реалізованого з використанням принципів структурного програмування.

Комп’ютерне моделювання – метод розв’язування задачі аналізу або синтезу складної системи, що ґрунтується на використанні її комп’ютерної моделі. Сутність комп’ютерного моделювання полягає у відшуканні кількісних і якісних результатів із залученням наявної моделі.

Комп’ютерна модель складної системи має якомога повніше відбивати всі основні фактори й взаємозв’язки, що характеризують реальні ситуації, критерії та обмеження. До того ж модель має бути настільки універсальною (щоб охоплювати якнайширше коло близьких за призначенням об’єктів) настільки й простою (щоб сприяти виконанню необхідних досліджень із мінімальними витратами).

Комп'ютерний напрям моделювання в науці отримав назву обчислювального експерименту.

Обчислювальний експеримент (computational experiment) – це методологія дослідження, засновані на вивченні математичної (інформаційної) моделі за допомогою логіко-математичних алгоритмів на комп'ютері.

Комп'ютерне моделювання (обчислювальний експеримент) має істотні переваги перед натурним експериментом.

По-перше, не потрібно проводити експеримент на реальних фізичних, економічних чи інших об'єктах, тому затрати на різні комп'ютерні експерименти набагато менші, ніж на натурні експерименти. Масштаби експериментів можна вибрати на свій розсуд, при цьому є можливість проведення багатократних дослідів із поступовими змінами вхідних даних задачі.

По-друге, проведення реальних експериментів у деяких галузях науки небезпечне (екологія, ядерна фізика) або неможливе (астрофізика).

По-третє, у процесі побудови математичних моделей для проведення обчислювального експерименту і під час її дослідження можна проаналізувати і зрозуміти характеристики досліджуваного об'єкта.