Урок 23

Застосування ЕОТ в професії

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

Такі послідовності команд (вказівок) називають алгоритмами.

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

Слово алгоритм походить від імені видатного вченого середньовічного Сходу Мухаммеда бен-Муси аль-Хорезмі (783-850) (рис. 1), який у своїх наукових працях з математики, астрономії та географії описав і вико­ристовував індійську позиційну систему числення, а також сформулював у загальному вигляді правила виконання чоти­рьох основних арифметичних дій: додавання, віднімання, множення та ділення. Європейські вчені ознайомилися з його працями завдяки перекладам їх на латину. Під час пе­рекладу ім'я автора було подано як Algorithmus. Звідси й пішло слово алгоритм. А розроблені ним правила виконання арифметичних дій вважають першими алгоритмами.

                                      Властивостями алгоритму є:

                                  ¨     дискретність,

                                  ¨     визначеність,

¨     виконуваність,

¨     скінченність,

¨     результативність

¨     масовість.

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

Визначеність (або детермінованість (лат. determinans - визначальний)) алгоритму означає, що для заданого набору значень початкових (вхідних) даних алгоритм однозначно визначає порядок дій виконавця та результат цих дій. Алгоритм не повинен містити команди, які можуть сприйматися виконавцем неоднозначно, наприклад «Узяти 2-3 ложки цукру», «Трохи підігріти молоко», «Вимкнути світло через кілька хвилин», «Поділити число x на одне з двох даних чисел a або Ь» тощо. Крім того, в алгоритмах недопустимі ситуації, коли після виконання чергової команди виконавцю незрозуміло, яку команду він повинен виконувати наступною.

Виконуваність алгоритму означає, що алгоритм, призначений для певного виконавця, може містити тільки команди, які входять до систе­ми команд цього виконавця. Так, наприклад, алгоритм для виконавця «Учень першого класу» не може містити команду «Побудуй бісектрису даного кута», хоча така команда може бути в алгоритмі, який призначе­ний для виконавця «Учень восьмого класу».

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

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

1.   Взяти число 2.

2.   Помножити взяте число на 10.

3.   Додати до одержаного числа 5.

4.   Якщо одержане число додатне, то виконати команду 3, якщо ні, то припинити виконання алгоритму.

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

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

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

Однак, крім масових алгоритмів, складаються й застосовуються алго­ритми, які не є масовими. Таким, наприклад, є алгоритм розв'язування конкретного квадратного рівняння (наприклад, 2х² + 5х + 2 = 0) або алго­ритм приготування конкретного салату (наприклад, грецького) на кон­кретну кількість осіб.

Форми подання алгоритмів

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

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

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

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

Множину всіх команд, які може виконувати даний виконавець, нази­вають системою команд цього виконавця. Наприклад, у систему команд виконавця, що виконуватиме другий з наведених вище алгоритмів, по­винні входити такі команди:

§  Порівняти довжини сторін трикутника і вибрати з них не меншу.

§  Обчислити косинус кута трикутника за відомими трьома сторонами.

§  Порівняти число з нулем (більше за нуль, менше за нуль або дорів­нює нулю).

§  Вивести повідомлення.

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

Базові алгоритмічні структури

1)    Лінійний алгоритм, в якому всі його ко­манди виконуються в записаній послідовності, кожна команда алгоритму обов'язково виконується, причому тільки один раз.

2)    Розгалужений алгоритм, в якому при кожному його виконанні деякі команди будуть виконуватися, причому кожна по одному разу, а деякі — виконуватися не будуть. Це залежить від результату виконання команди перевірки умови (команди обчислення значення логічного виразу).

3)    Циклічний алгоритм,  що складається з команд, які можуть виконуватися більше одного разу.

 
КОНТРОЛЬНІ ПИТАННЯ:

 

1.     Що таке алгоритм?

2.     Хто може бути виконавцем алгоритму? Наведіть приклади.

3.     Назвіть відомі вам властивості алгоритмів.

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

5.     Наведіть приклади властивості масовості алгоритму.

6.     Назвіть відомі вам способи зображення алгоритмів.

7.     Які переваги графічного зображення алгоритмів перед словесним записом?

8.     Назвіть компоненти блок-схем алгоритмів.

9.     Укажіть команди серед наведених речень:

а) Закрий вікно.                                г) Не заважай читати.

б) Котра година?                              д) Якщо йде дощ, візьми парасольку.

в) 3 + 2 = 5.                                         е) Я живу в Хоролі.

10. Складіть блок-схему алгоритму знаходження х з рівняння 2х + а = c. Виконайте його при: а) а = 5, с = 7; б) а = -15, с = 105; в) а = 5, с = 5.

11. Назвіть базові структури алгоритмів.

12. Охарактеризуйте кожну із базових структур.