Розділ 1. Обчислювальний метод та обчислювальний алгоритм

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

Людська мова є дуже надлишковою та неоднозначною. Тому наступним етапом опанування задачі є її формулювання у математичній формі, тобто складання математичної моделі задачі. Неважко записати формулу підрахунку:

кількість зерен . (1.1)

Отриманий вираз є окремим випадком степеневого поліному

. (1.2)

Вираз (1.1) утворюється з (1.2) при n=64, a_i=1, x=2.

Отже, розглянемо задачу підрахунку значення степеневого поліному (1.2). Така задача часто виникає в обчисленнях, зокрема в нашому курсі.

Майже завжди розв’язувати задачу за математичною моделлю можна по різному, різними методами. Щоби правильно обрати метод розв’язування задачі, треба знати різні методи та вміти вибрати такий, що найкраще відповідає умовам розв’язування.

Значення степеневого полінома можна обрахувати безпосередньо за формулою (1.2). Для цього потрібно (n-1) операцій множення, (n-2) операцій піднесення до цілого степеня та (n-1) операцій додавання.

Англійський математик початку 19-го сторіччя Вільямс Горнер (Horner) запропонував підрахунок степеневого полінома за формулою

(1.3)

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

До речі, першим застосував формулу (1.3) геніальний Ньютон ще за півтора століття до Горнера. Але так історично склалось, що цю формулу називають іменем Горнера. Втім, на всесвітній авторитет Ньютона це ніяк не вплинуло.

Вибираючи метод розв’язування задачі, треба керуватись такими основними ознаками:

– громіздкість обчислень, тобто потрібна кількість арифметичних операцій;

– необхідний об’єм оперативної пам’яті;

– гарантована точність результату .

Наступний етап, близький до вибору методу, – це складання алгоритму розв’язування, тобто впорядкованої однозначної послідовності дій для досягнення мети. Майже кожну математичну задачу можна записати різними алгоритмами. “Мистецтво” програмування власне полягає у вмінні вибрати найкращий алгоритм за ознаками, подібними до ознак вибору методу розв’язування.

Складні алгоритми зручно подавати у вигляді блок-схем. Широко розповсюджені алгоритмічні мови, що є проміжними між математичною мовою та мовою машинних команд. На відміну від математичної мови алгоритмічні мови є строго однозначними. Алгоритмічні мови розрізняють за функціональним призначенням та рівнем, тобто умовним розміщенням між математичною мовою та мовою машинних команд. Чим ближча алгоритмічна мова до математичної, тим вище її рівень. Найвищі рівні мають, наприклад, мови MATHCAD та MATLAB. Найнижчі рівні у мов-асемблерів. Кожній алгоритмічній мові надається транслятор, тобто спеціальна програма, що перекладає тексти програм на мову машинних команд.

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

Відлагоджена програма нарешті готова до розв’язування задачі, для якої була написана. Однак отримані результати розрахунків ще не означають завершення роботи. Ці результати треба інтерпретувати, тобто зрозуміти і використати.

Часто на етапі інтерпретації виявляється, що задача була неточно або взагалі невірно сформульована, або обрано невідповідний метод чи алгоритм розв’язування. Тоді треба повертатись до попередніх етапів.

Отже, розв’язування задачі на ЕОМ складається з таких послідовних етапів:

– словесне формулювання задачі;

– створення математичної моделі задачі;

– вибір методу та алгоритму розв’язування;

– запис алгоритму розв’язування на обраній алгоритмічній мові;

– відлагодження програми;

– розрахунки на ЕОМ;

– інтерпретація результатів розв’язування;

– в разі необхідності повернення до початкових етапів.