Алгоритм і способи його подання

Обговорення повідомлення

Ім'я аль-Хорезмі ми згадуємо під час вивчення математики у зв'язку з поняттям алгоритму. Як вважають, слово «алгоритм» походить від імені відомого середньоазіатського вченого Мухаммеда аль-Хорезмі. Близько 825 року аль-Хорезмі написав твір, у якому вперше виклав теорію десят­кової системи числення, започаткованої в Індії. На жаль, арабський ори­гінал книги не зберігся, тож нам невідома її первісна назва.

Аль-Хорезмі сформулював правила обчислення в новій системі і, мож­ливо, вперше використав цифру 0 для позначення пропущеної позиції в запису числа (індійську її назву араби переклали як аs-sift або просто sift, звідси такі слова, як «цифра» і «шифр»). Відтоді індійські цифри почали використовувати й інші арабські вчені. У першій половині XII ст. книга аль-Хорезмі в латинському перекладі дійшла до Європи.

Розв'язування будь-яких задач зводиться до вико­нання певних дій, команд згідно з деякою схемою. В інформатиці таку послідовність команд називають алгоритмом. Які бувають ал­горитми? Як їх записують? У чому відмінність математичних алго­ритмів від інформаційних? На ці та інші запитання ми спробуємо дати відповіді на уроці.

Алгоритм

Алгоритм— це точний і зрозумілий опис послідов­ності дій над заданими об'єктами, що дозволяє одержати кінцевий результат.

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

Залежно від цілей, початкових умов задачі, шляхів її вирі­шення алгоритми поділяються на:

Механічні — задають певні дії, позначаючи їх у єдиній послі­довності, забезпечуючи тим самим однозначний результат.

Імовірнісні — дають програму вирішення задачі кількома шля­хами, що приводить до ймовірнісного досягнення результату.

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

Ви вже не раз зустрічалися з алгоритмами в інших шкільних предметах. Наприклад, у хімії отримання тієї чи іншої сполуки можна описати за допомогою алгоритму. Але найбільше прикладів алгоритмів у математиці — науці, у якій власне й зародилося це по­няття. По суті, математика вивчає різні алгоритми і створює нові. До алгоритмів зі шкільного курсу математики належать правила виконання арифметичних дій, правила знаходження розв'язків рівнянь тощо. У вигляді алгоритмів можна сформулювати правила побудови різних геометричних фігур (згадайте задачу на побудо­ву), а також рекомендації щодо розв'язування типових задач.

До слова «алгоритм» близькі за значенням слова: спосіб, ре­цепт. Однак алгоритми в інформатиці — це не тільки рецепти роз­в'язування задач. Алгоритми розробляють, насамперед, із метою автоматизації дій виконавця.

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

Виконавець і властивості алгоритму

Алгоритм розв'язування однієї й тієї самої задачі можна подати по-різному. Якщо ви навчаєте чогось собаку, ви будете давати усні команди зрозумілою для неї мовою. Якщо ж ви навчаєте свого при­ятеля їздити на велосипеді, то система команд, які він може вико­нати, буде, звичайно, ширшою. Алгоритм їзди ви можете описати усно або на папері.

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

Алгоритми складаються з урахуванням можливостей вико­навця.

Виконавець алгоритму — об'єкт (людина, комп'ютер), що здатний правильно зрозуміти й точно виконати всі дії алго­ритму.

Розбіжності між виконавцями алгоритмів: якщо люди роб­лять багато справ, навіть не усвідомлюючи, що при цьому вони використовують якісь алгоритми, то комп'ютери не можуть фун­кціонувати без програм, накази яких вони точно виконують.

Механічний (машинний) алгоритм — алгоритм, для якого виконавцем є ЕОМ. Такий алгоритм повинен відповідати низці вимог.

Властивості алгоритмів

1. Зрозумілість — алгоритм повинен бути заданий за допомогою таких вказівок, які входять у систему команд виконавця.
2. Результативність — досягнення виконавцем результату після проходження скінченної кількості кроків.
3. Визначеність — точні відомості про те, яку наступну команду виконувати виконавцеві після завершення поточної ко­манди.
4. Дискретність — послідовність команд, кожна з яких приводить до виконання одного кроку виконавцем.
5. Масовість — можливість за допомогою одного алгоритму розв'язання цілого класу однотипних задач.

СПОСОБИ  ТА ФОРМИ  ОПИСУ АЛГОРИТМІВ

1.      Словесні

2.      Словесно-формульні

3.      Графічні (схеми)

4.      Однією з мов програмування

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

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

Схема — це графічне зображення алгоритму за допомогою геометричних блоків, які позначають ту або іншу команду. Графічне зображення алгоритму дає змогу наочно простежити й осмислити процес виконання алгоритму. Використовувані гео­метричні фігури відповідають одному кроку алгоритму й мають стандартний зміст.

Схема складається з елементів двох типів:

•     1-й тип — графічні фігури, кожна з яких відображає один з етапів процесу рішення задачі та містить у собі текст відповідної команди;

•     2-й тип — лінії зі стрілками, які вказують послідовність (порядок) виконання етапів. У цілому такий спосіб запису алго­ритмів можна розглядати як своєрідну алгоритмічну мову — сис­тему позначень і правил для однотипного запису алгоритмів та їх виконання.

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

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

План складання алгоритму

1. Уважно прочитати умову задачі.
2. Визначити: а) що дано (аргументи);  б) що потрібно знайти (результати); в) у якому вигляді (тип аргументів і результатів).
3. Записати заголовок алгоритму.
4. Визначити шляхи вирішення задачі та виявити необхідні проміжні величини.
5. Записати алгоритм алгоритмічною мовою.
6. Перевірити правильність складання алгоритму при конк­ретних значеннях аргументів

Приклад різних форм подання алгоритму

Наприклад, скласти алгоритм, який перевіряє, чи може існува­ти трикутник із кутами А, В, С.

Словесний запис алгоритму

1.                    Задаємо конкретні числові значення кутів А, В, С.

2.                    Якщо сума кутів дорівнює 180°, то трикутник існує, в іншому випадку не існує.

Словесно-формульний запис алгоритму

1.                    Задаємо конкретні числові значення кутів А, В, С.

2.                    Якщо А + В + С = 180° , то трикутник існує, в іншому випадку не існує.

Графічний запис алгоритму (блок-схема)

Реалізація алгоритму у вигляді програми

Код програми на мові Паскаль

Program Z1;

var a, b, c: Real;

begin

write(‘ Введіть значення кутів трикутника ‘);

readln(a, b, c);

if a+b+c=180 then

   writeln(‘Існує’)

else writeln(‘ Не існує’);

end.