Алгоритми та їх властивості. Форми подання алгоритмів

Пригадайте!

1. Які речення називаються спонукальними?

2. Чи готували ви якусь страву, користуючись рецептом її приготування? Як ви це робили?

3. На яких уроках ви користувалися інструкціями? Якими саме?

4. Наведіть приклади правил української мови, в яких використана конструкція якщо..., то....

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

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

Так для приготування яєчні потрібно виконати послідовність команд:

1. Поставити сковороду на плиту.

2. Покласти на сковороду шматочок вершкового масла.

3. Увімкнути конфорку.

4. Чекати, поки масло на сковороді розтане.

5. Розбити два яйця і вилити їх вміст на сковороду.

6. Посолити.

7. Чекати, поки загусне білок.

8. Вимкнути конфорку.

А для того, щоб визначити вид трикутника за його кутами, якщо відомі його три сторони, потрібно виконати таку послідовність команд:

1. Визначити сторону трикутника, яка не менша кожної з двох інших.

2. Обчислити косинус кута трикутника, що лежить проти сторони, визначеної як результат виконання команди 1.

3. Якщо визначений косинус кута від’ємний, то повідомити, що даний трикутник тупокутний, якщо ні, то якщо визначений косинус кута дорівнює нулю, то повідомити, що даний трикутник прямокутний, якщо ні, то повідомити, що даний трикутник гострокутний.

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

 

Запам’ятайте!

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

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

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

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

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

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

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

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

Цікаві факти з історії!

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

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

Властивостями алгоритму є дискретність, визначеність, виконуваність, скінченність, результативність і масовість.

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

Розглянемо алгоритми розв’язування такої задачі.

Задача 1. Є повна посудина рідини місткістю 8 літрів і дві порожні посудини місткістю 5 літрів і 3 літри. Потрібно одержати в одній з посудин 1 літр рідини.

Розглянемо виконавця, який має таку систему команд:

1. Узяти вказану посудину.

2. Перелити вміст вказаної посудини в іншу вказану посудину.

3. Наповнити вказану посудину рідиною з іншої вказаної посудини.

Для такого виконавця алгоритм розв’язування цієї задачі буде таким:

1. Узяти повну 8–літрову посудину.

2. Наповнити 3-літрову посудину рідиною з 8-літрової.

3. Перелити вміст 3-літрової посудини в 5-літрову.

4. Наповнити 3-літрову посудину рідиною з 8-літрової.

5. Наповнити 5-літрову посудину рідиною з 3-літрової.

6. Узяти 3-літрову посудину.

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

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

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

 

Таблиця 2.1. Деякі елементи (блоки) блок-схеми алгоритму

Найменування	Позначення	Призначення
Термінатор		Початок або кінець алгоритму
Процес		Виконання однієї або кількох команд
Дані		Введення вхідних даних (аргументів) або виведення вихідних даних (результатів)
Рішення		Прийняття рішення залежно від результату перевірки вказаної умови

 

Ось як виглядає блок-схема алгоритму розв’язування задачі 1 (рис. 2.4).

Запам’ятайте!

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

Розглянемо ще одну задачу – задачу на обчислення значення виразу, і складемо алгоритм її розв’язування.

Задача 2. Обчислити значення виразу (a – b) * (c – d), де a, b, c, d – дійсні числа

 

Розглянемо виконавця, який вміє отримувати значення змінних, виконувати арифметичні операції над дійсними числами, запам’ятовувати результати арифметичних операцій і повідомляти результат. Передавання даних виконавцеві називається уведенням даних, а повідомлення виконавцем результатів виконання алгоритму – виведенням даних (результатів).

 

Запишемо алгоритм розв’язування задачі 2 для такого виконавця в словесній формі.

1. Увести значення змінних a, b, c, d. (У результаті виконання цієї команди виконавець запам’ятовує введені дані як значення відповідних змінних).

2. Обчислити значення виразу a – b і результат присвоїти змінній х (запам’ятати як значення цієї змінної).

3. Обчислити значення виразу c – d і результат присвоїти змінній у (запам’ятати як значення цієї змінної).

4. Обчислити значення виразу х*у і результат присвоїти змінній z.

5. Повідомити значення змінної z.

У командах 2, 3 і 4 обчислюється значення виразу і результат обчислення присвоюється (запам’ятовується як значення) певній змінній. Такі команди називаються командами присвоювання. Для них прийнято використовувати таку форму запису:

2. х:= a – b (читається: змінній х присвоїти значення виразу a – b)

3. у:= c – d (читається: змінній y присвоїти значення виразу c – d)

4. z:= х* у (читається: змінній z присвоїти значення виразу x * y)

Знак := називається знаком присвоювання і складається з двох символів: двокрапка і дорівнює, які записуються без пропуску між ними.

Наведемо блок-схему цього алгоритму (рис. 2.5).

Цей алгоритм також є лінійним, бо при кожному наборі значень змінних a, b, c, d кожна його команда обов’язково виконується, причому тільки 1 раз.

 

Проілюструємо виконання алгоритму розв’язування задачі 2 для значень змінних a = 3; b = 4; c = –2; d = –5.

Команда	Результат виконання
Увести значення змінних a, b, c, d	a = 3; b = 4; c = –2; d = –5
х: = a – b	х = 3 – 4 = –1
у:= c – d	у = –2 – (–5) = 3
z:= x*y	z = –1*3 = –3
Повідомити значення змінної z	z = –3

Аналогічно можна виконати цей алгоритм при іншому наборі значень змінних a, b, c, d.

Перевірте себе

1. º Наведіть приклади речень, які є командами, і приклади речень, які не є командами.

2. º Що таке алгоритм? Наведіть приклади.

3. º Що таке система команд виконавця? Наведіть приклади виконавців і системи їх команд.

4. ^· Назвіть властивості алгоритму. Поясніть кожну з них.

5. *Наведіть приклад послідовності команд, яка не є виконуваною.

6. Наведіть приклад послідовності команд, яка не є результативною.

7. ^· Поясніть різницю між словесною і графічною формами подання алгоритму.

8. ^· Назвіть елементи блок-схеми алгоритму і поясніть їх призначення.

9. ^· Який алгоритм (фрагмент алгоритму) називається лінійним?

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

11. ^·Що таке команда присвоювання? Як вона позначається?

Виконайте завдання

1. ^· Вкажіть команди серед наступних речень:

а) Закрий вікно.

б) Котра година?

в) 3 + 2 = 5.

г) Не заважай читати.

д) Якщо йде дощ, візьми парасольку.

е) Я живу в Києві.

2. * Сформулюйте лінійні правила–алгоритми, які ви вивчали на уроках:

а) української мови;

б) математики;

в) (ДЗ) інших предметів.

Подайте ці алгоритми блок-схемами.

3. º Виконайте алгоритм:

1. Знайти суму чисел 1 і 3.

2. Додати до одержаної суми число 5.

3. Додати до одержаної суми число 7.

4. Додати до одержаної суми число 9.

5. Додати до одержаної суми число 11.

6. Повідомити результат.

Яку б назву ви дали цьому алгоритму? Складіть його блок-схему.

4. º (ДЗ) Виконайте алгоритм:

1. Накреслити відрізок АВ.

2. Поставити ніжку циркуля в точку А.

3. Побудувати коло, радіус якого дорівнює довжині відрізка АВ.

4. Поставити ніжку циркуля в точку В.

5. Побудувати коло, радіус якого дорівнює довжині відрізка АВ.

6. Провести пряму через точки перетину побудованих кіл.

Яку б назву ви дали цьому алгоритму? Які геометричні задачі можна розв’язувати за цим алгоритмом? Складіть його блок-схему.

5. º Складіть алгоритм приготування бутерброду з сиром. Подайте його в словесній формі.

6. º (ДЗ) Складіть алгоритм приготування вашого улюбленої страви. Подайте його в словесній формі.

7. ^· Є координатна пряма з позначеними на ній цілими числами. На цій прямій мешкає виконавець Коник, якийвміє переміщуватися по ній, виконуючи команди: 1) стрибни на 3 одиниці праворуч; 2) стрибни на 2 одиниці ліворуч. Початкове положення Коника – точка 0. Складіть блок-схему алгоритму, за яким Коник за найменшу кількість стрибків опиниться в точці: а) 24; б) 7; в) –3.

8. ^· Є повна посудина місткістю 8 літрів і дві порожні посудини місткістю 3 літри і 5 літрів. Складіть алгоритм одержання в одній з посудин 2 літри рідини для виконавця, система команд якого описана в даному пункті. Подайте його в словесній формі і у формі блок-схеми.

9. * Необхідно приготувати суп з концентрату. У нашому розпорядженні є пісочні годинники на 3 хвилини і 8 хвилин. Складіть блок-схему алгоритму відліку часу для приготування супу, якщо його треба готувати рівно: а) 5 хвилин; б) 7 хвилин; в) 10 хвилин.

10. ^· Візнику потрібно перевезти в човні через річку вовка, козу і капусту. У човні, крім візника, вміщується або тільки вовк, або тільки коза, або тільки капуста. На березі не можна залишати козу з вовком або козу з капустою. Складіть алгоритм перевезення. (Ця старовинна задача вперше зустрічається в математичних рукописах VIII століття). Подайте його в словесній формі.

11. ^· (ДЗ) Двом солдатам потрібно переправитися з одного берега річки на інший. Вони побачили двох хлопчиків на маленькому човні. У ньому можуть переправлятися або один солдат, або один чи двоє хлопчиків. Складіть алгоритм переправлення солдатів. (Після переправлення солдатів човен повинен залишитися в хлопчиків) Подайте його в словесній формі.

12. ^· Складіть блок-схему алгоритму побудови бісектриси кута з використанням циркуля і лінійки.

13. ^· (ДЗ) Складіть блок-схему алгоритму побудови трикутника за трьома його сторонами з використанням циркуля і лінійки.

14. * Потрібно підсмажити 3 скибки хліба на сковороді, що вміщує одночасно тільки 2 такі скибки. На смаження однієї сторони витрачається 2 хвилини. Складіть систему команд для виконавця, який би зміг досягти поставленої мети. Складіть алгоритм для цього виконавця. Подайте його в словесній формі. Який час витрачається при виконанні вашого алгоритму? Складіть алгоритм, на виконання якого витрачається 6 хвилин.

15. * (ДЗ) Придумайте виконавця. Задайте його систему команд. Сформулюйте задачу і складіть алгоритм її розв’язування для цього виконавця.

16. ^· Складіть блок-схему алгоритму обчислення на калькуляторі значення виразу: 52 + (69 – 35) × 5.

17. ^· (ДЗ) Складіть блок-схему алгоритму обчислення на калькуляторі значення виразу: (81–12) × (58+84).

18. º Складіть блок-схему алгоритму обчислення значення виразу: (a + b) – c × a. Виконайте його при різних значеннях a, b, c.

19. ^· Складіть блок-схему алгоритму знаходження x з рівняння: 2 x + a = c. Виконайте його при: 1) a = 5; c = 7; 2) a = –15; c = 105; 3) a = 5; c = 5.

 

2.3. Комп’ютерні програми і мови програмування. Етапи розв’язування задач з використанням комп’ютера

Пригадайте!

1. Для чого призначене і з чого складається програмне забезпечення комп’ютера?

2. Що таке алгоритм? Що таке система команд виконавця алгоритму? У чому полягає формальність виконання алгоритму виконавцем?

3. У чому полягає процес кодування даних? Для чого воно використовується? Що таке двійкове кодування?

4. Що таке модель об’єкта? Які види моделей ви знаєте?

5. Назвіть основні галузі застосування сучасних комп’ютерів.

Комп’ютерні програми

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

 

Запам’ятайте!

Програма - це набір команд (вказівок, інструкцій), призначений для виконання комп’ютером у певній послідовності.

 

Програми складаються для виконання комп’ютером алгоритмів. Ці алгоритми утворюють логіку програми (програмну логіку).

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

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

 

Цікаві факти з історії!

Першим у світі програмістом вважається Ада Лавлейс (1815 – 1852) (рис. 2.6), дочка відомого англійського поета Джорджа Гордона Байрона. Вона працювала з Чарльзом Беббіджем (1791 – 1871) (рис. 2.7), розробником механічної обчислювальної машини (аналітичної машини), і вперше описала основні принципи розробки програм для обчислювальних машин. На жаль, ця обчислювальна машина так і не була створена. На честь Ади Лавлейс одна з мов програмування названа Ada..

 

Мови програмування

Складаючи алгоритми, призначені для виконання людиною, користуються мовою спілкування людей: українською, російською, англійською, німецькою тощо.

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

 

Запам’ятайте!

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

 

Кожна мова програмування має такі компоненти:

1) алфавіт – множину символів, з яких можна утворювати слова і речення цієї мови;

2) словник – набір спеціальних (зарезервованих, ключових) слів.

3) синтаксис – правила складання і запису мовних конструкцій (не словникових слів і речень);

4) семантику – встановлене однозначне тлумачення мовних конструкцій, правил їх виконання.

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

Мови програмування є прикладами так званих штучних мов. Іншими прикладами штучних мов є, наприклад, мова запису хімічних реакцій, мова запису розв’язування математичних рівнянь і нерівностей, мова запису поштових індексів на конвертах і листівках, мова запису ходу шахової партії та багато інших.

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

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

 

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

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

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

 

Для тих, хто хоче знати більше!

Описаний вище спосіб виконання програм, написаних не машинною мовою програмування, є не єдиний, що використовується в сучасних комп’ютерах.

Для деяких мов програмування створено інші спеціальні програми – інтерпретатори. Ці програми не створюють виконуваних файлів, а аналізують програму покомандно і одразу ж ці команди виконують. Тому виконати програму, яка інтерпретується, а не компілюється, можна лише на тому комп’ютері, де встановлена відповідна програма-інтерпретатор.

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