відбуваються з цього джерела.
Як би не був отриманий алгоритм, він повинен бути обгрунтований; це означає, що якщо алгоритм створений для вирішення певної задачі, то необхідна впевненість в тому, що для всіх вихідних даних, для яких ця задача може бути вирішена, алгоритм дозволяє отримати рішення і ні для яких вихідних даних не дає неправильного результату. Це називається коректністю алгоритму.
Коректність емпіричних алгоритмів звичайно перевіряють експериментально. Якусь упевненість в їх коректності можна отримати, якщо їх багаторазове застосування завжди приводить до необхідного результату. Однак одне тільки багаторазове експериментальне підтвердження ще не вселяє повної впевненості.
Повна впевненість в коректності емпіричного алгоритму виникає лише в тому випадку, коли полученниеc його допомогою результати не тільки підтверджуються експериментально, але й узгоджуються з усіма іншими накопиченими і об'єднаними в наукову теорію фактами даній галузі науки або техніки.
Якщо хоча б один з даються алгоритмом результатів суперечить хоча б одному з раніше встановлених і отримали визнання фактів, емпіричний алгоритм не можна визнати коректним (хоча після перевірки може виявитися некоректним НЕ алгоритм, а той факт, якому він суперечить ). Коректність теоретично обумовлених алгоритмів гарантується наявністю відповідних доказів.
Дуже цікаве питання про встановлення коректності алгоритмів, отриманих на основі інших, раніше розроблених і свідомо коректних алгоритмів. Вирішення цього питання залежить від прийому, який був застосований для отримання нового алгоритму.
Перелічимо найбільш часто вживані прийоми.
) Конструювання алгоритмів. Цей прийом полягає в тому, що новий алгоритм отримують комбінуванням вже відомих алгоритмів як складових частин.
) Еквівалентні перетворення алгоритмів. Два алгоритму називають еквівалентними, якщо: а) всякий варіант вихідного даного, допустимий для одного з них, припустимо і для іншого; б) застосовність одного алгоритму до якого-небудь вихідного даного гарантує, що й інший алгоритм застосуємо до цього вихідного даному; в) результати, що даються цими алгоритмами для одного і того ж вихідного даного, між собою однакові.
Всяка зміна алгоритму, в результаті якого знову виходить алгоритм і при цьому еквівалентний вихідного алгоритму, називається еквівалентним перетворенням алгоритму. Прикладом еквівалентного перетворення алгоритму є його переклад з однієї мови на іншу.
) звужує перетворення. Вони призводять до алгоритмам вирішення завдань, є приватними випадками тих завдань, для вирішення яких були призначені вихідні алгоритми.
) Застосування формального методу до нематематичні проблемі. Цей прийом полягає в тому, що нематематичні проблему формулюють математично. При цьому може виявитися, що відомий алгоритм рішення вийшла математичної задачі. Цей алгоритм і приймається за шуканий. Якщо готового алгоритму не виявиться, то роблять спробу його розробки, тим самим звертаючись до другого із зазначених вище джерел для отримання алгоритмів.
Коректність алгоритмів, отриманих шляхом конструювання, не викликає сумнівів, якщо алгоритми, використані в якості «будівельного матеріалу», дають точні результати. Якщо ж їх результати є наближеними, як це часто буває на практиці, то обгрунтування коректності може вимагати складних досліджень.
Доказом коректності алгоритмів, отриманих за допомогою еквівалентних перетворень, є правильність перетворень
Коректність алгоритмів, отриманих шляхом сужающих перетворень, забезпечується перевіркою (доказом) того, що кожен результат, одержуваний звуженим алгоритмом, тотожний з результатом, який для того ж варіанта вихідного даного дає вихідний алгоритм.
Нарешті, коректність алгоритму, отриманого в результаті застосування формального методу, з'ясовується або так само, як для емпіричних алгоритмів, або а) оцінкою, так званої адекватності отриманої математичної задачі (т. е. можливості отримання при її рішенні результату, досить близького до шуканого результату) і б) доказом коректності алгоритму рішення математичної задачі [Криницький, 1984].
Алгоритми, отримані в результаті винахідливості розробника, також вимагають обгрунтування. Зазвичай з ними надходять або як з емпіричними, або (вже після їх отримання) проробляють всі дії, що передбачаються формальним методом.
. 2 Алгоритми в початковій школі на уроках математики
Навчання елементам алгоритмізації в початкових класах дуже важливо з пропедевтичної точки зору. Опис якого-небудь процесу по кроках, етапам доступно молодшим школяра...
