Тема 6. Алгоритмізація.

Основи програмування

Алгоритмізація

		Алгоритм — скінчена однозначно визначена послідовність операцій, фор­
		мальне виконання яких приводить до розв’язання певної задачі за кінцеве
		число кроків.
	Поняття			Означення
	Виконавець алгоритму			Жива чи нежива істота, яка може виконати всі вказівки заданого
				алгоритму
	Припустимі команди			Команди, які можуть бути виконані виконавцем
	Неприпустимі команди			Команди, які не можуть бути виконані виконавцем
	Система команд виконавця			Сукупність припустимих команд виконавця

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

Властивість		Пояснення
Дискретність		Процес розв’язування задачі має складатися з окремих кроків. Алго­
		ритм складається із сукупності відокремлених одна від одної команд
		(вказівок), кожна з яких виконується за скінченний час. Тільки закін­
		чивши виконання однієї команди, виконавець переходить до виконан­
		ня іншої
Визначеність (однознач­		Кожна команда алгоритму однозначно визначає дії виконавця і не при­
ність)		пускає подвійного тлумачення. Суворо визначеним є й порядок вико­
		нання операцій
Формальність		Будь який виконавець, який володіє заданою системою команд вико­
		навця, може виконати заданий алгоритм, не вдаючись до суті задачі
Масовість		Алгоритм має передбачати можливість зміни початкових (вхідних) да­
		них у деяких припустимих межах (універсальність алгоритму)
Результативність		Виконання алгоритму не може закінчуватися невизначеною ситуацією
		або зовсім не закінчуватися. Будь який алгоритм передбачає, що його
		виконання при допустимих початкових даних за число кроків приведе
		до очікуваного результату
Поняття алгоритму
			139

139 3945У Інформатика в таблицях

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

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

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

	Базовий тип			Альтернативна назва					Означення
	алгоритму
	Лінійний			Алгоритм послідов­					Алгоритм, який забезпечує отримання результату шляхом од­
				ного виконання,					норазового виконання послідовності дій, незалежно від вхід­
				структура сліду­					них даних і проміжних результатів. Дії в таких алгоритмах
				вання					виконуються послідовно, одна за однією, тобто лінійно
	Розгалужений			Галуження,					Алгоритм, який у класичному варіанті розглядається як вибір
				умова,					дій у разі виконання або невиконання заданої умови.
				структура вибору					Розгалуження бувають повними і неповними.
									Повне розгалуження — це розгалуження, в якому різні дії
									визначені й у разі виконання, і в разі невиконання умови.
									Неповне розгалуження — це розгалуження, в якому дії визна­
									чені тільки в разі виконання (або в разі невиконання) умови.
									Структура вибору (узагальнене галуження) — це структура,
									яка передбачає вибір можливих варіантів дій залежно від де­
									кількох умов
	Циклічний			Цикл,					Алгоритм, у якому передбачено повторення деякої серії ко­
				структура повто­					манд (однотипних дій). Такі алгоритми забезпечують виконан­
				рення					ня довгої послідовності дій, які записані порівняно короткою
									послідовністю команд. Саме використання циклів дозволяє
									повною мірою реалізувати швидкодію комп’ютерів
Способи запису алгоритмів
						Процес алгоритмізації — визначення елементарних дій та порядку їх ви­
						конання для розв’язання поставленої задачі.
						Різні способи записування алгоритмів застосовуються для подання алго­
						ритму у вигляді, який однозначно розуміється і розробником, і виконавцем
						алгоритму.
	Способи запису алгоритмів								Приклади
	Словесний						Природні мови: усна, письмова
	Формульно-словесний						Мова математичних формул, мова хімічних процесів, навчальна
							алгоритмічна мова тощо
	Графічний						Метод блок-схем, метод структурних схем
	Програмний						Мови програмування
	Інші						Нотна грамота
									Тема 6. Алгоритмізація. Основи програмування
140

140 3945У Інформатика в таблицях

Блок схеми алгоритмів

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

Позначення блоку

Опис

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

Блок введення виведення визначає введення даних в програму або виведен­ ня на пристрій

Блок процес визначає зміну значення, форми подання або розташування даних

Блок перевірки умови визначає подальші кроки виконання алгоритму за­ лежно від виконання умови

Блок покрокового повторення

Блок схеми базових типів алгоритмів

Так

ЛВ

Ні

Так

ЛВ

Ні

Серія

Серія 1

Серія 2

Серія

Серія

Лінійний алгоритм

Алгоритм із розгалуженням

Алгоритм із розгалуженням

(структура «слідування»)

(повне галуження)

(неповне галуження)

ЛВ	Ні	Серія
			ПЦ: = НЗ, КЗ, К
Так			Так
		ЛВ
Серія
		Ні	Серія

	Цикл із передумовою	Цикл із післяумовою
	(цикл ДОКИ)	(цикл ДО)	Цикл із параметром
Поняття алгоритму
					141

141 3945У Інформатика в таблицях

Скорочення		Опис		Скорочення		Опис
Серія		Серія команд — один або декілька		НЗ		Початкове значення параметру
		операторів				циклу
ЛВ		Логічний вираз або умова		КЗ		Кінцеве значення параметру циклу
ПЦ		Параметр циклу		К		Крок зміни параметру циклу

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

Основні етапи розв’язання прикладної задачі з використанням комп’ютера

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

Поняття інформаційної моделі

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

Від поставленої задачі залежить повнота розробки та аналізу моделі.

		Призначення			Створення			Опис
Для розуміння структури,				Визначаються			За допомогою
основних­		властивостей, законів		•	основні характеристики		•	природної мови;
взаємодії складових об’єкта,					об’єкта та їх допустима		•	мови математики, хімії, біо­
що аналізується; набуття нави­					погрішність­	,		логії тощо;
чок керування ним та прогно­				•	вхідні характеристи­		• мови графічних структур;
зування наслідків реалізації					ки та взаємовідносини		•	інших способів
керування					між ними
						Тема 6. Алгоритмізація. Основи програмування
142

142 3945У Інформатика в таблицях

Структурний підхід до конструювання алгоритмів

Структурний підхід до створення алгоритмів — один із способів розробки алгоритмів, при якому структура алгоритму реалізується в структурі тек­

	Структурний підхід забезпечує		Структурний підхід передбачає
•	Легкість читання алгоритму		• Конструювання алгоритму з використанням трьох базо­
•	Простоту перевірки правиль­		вих алгоритмічних структур
	ності виконання алгоритму		• Використання методу покрокової деталізації
• Зручність в його модифікації			• Використання допоміжних алгоритмів, які оформлю­
			ються у вигляді підпрограм — процедур та/або функцій
			• Об’єднання даних, які зв’язані за значенням, у складні
			структури даних
			• Аналіз алгоритму, тобто контроль правильності кожної
			структури алгоритму і взаємозв’язків структур

Метод покрокової деталізації (проектування алгоритму «зверху вниз»)

Крок		Опис дії
1 й		Розділити складну задачу на декілька простих задач
2 й		Якщо задачі чергового рівня стають досить простими для незалежного розв’язання,
		­закінчити процес деталізації
3 й		Скласти для кожної допоміжної задачі свій допоміжний алгоритм, при необхідності
		об’єднати дані в структури
4 й		Скомпонувати результати проектування простих задач
5 й		Проаналізувати роботу алгоритму

Допоміжні алгоритми

Основний		Допоміжний
Алгоритм для виконання основної задачі		Алгоритм для розв’язання підзадачі, виділеної
		в окрему підструктуру

Призначення та особливості допоміжних алгоритмів

	Призначення	Особливості
	• Полегшення розробки складних задач	• Унікальне ім’я, за яким його можна роз­
		пізнати серед інших допоміжних алгоритмів
	• Наочність, зрозумілість основного алго­
		і викликати з іншого алгоритму за допомогою
	ритму	команди виклику допоміжного алгоритму
	• Лаконічність і ефективність основного	• Параметри, за допомогою яких здійснюється
	алгоритму (у випадку, коли деяка послі­	виконання алгоритму з необхідними початко­
	довність команд зустрічається в алгоритмі	вими даними і/або передавання результатів до
	кілька разів)	основного алгоритму
Поняття алгоритму
			143

143 3945У Інформатика в таблицях

Параметри допоміжного алгоритму

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

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

Види допоміжних алгоритмів

Опис	Алгоритм процедура		Алгоритм функція
Означення	Допоміжний алгоритм, результатом ви­		Допоміжний алгоритм, результатом ви­
	конання якого може бути одна або декіль­		конання якого є єдиний результат, який
	ка результуючих величин, які містяться		надається імені функції
	в списку параметрів, або деяка дія
Об’єкти	Усі описані в допоміжному алгоритмі об’єкти є локальними і можуть використо­
	вуватися лише в цьому алгоритмі. Об’єкти, описані в основному алгоритмі і непе­
	реозначені в допоміжному алгоритмі, називаються глобальними та доступні для
	використання як в основному, так і в допоміжному алгоритмі
Спосіб	• Виклик допоміжних алгоритмів здійснюється за їхніми іменами.
виконання	• Команда виклику допоміжного алгоритму має різний вигляд у випадку викли­
	ку алгоритму функції та алгоритму процедури, однак виконання обох команд
	відбувається в такий спосіб:

•Формальні аргументи допоміжного алгоритму замінюються фактичними значеннями, що вказані в списку фактичних параметрів в команді викли­ ку алгоритму; якщо в списку фактичних аргументів присутні вирази — вони попередньо обчислюються

•Виконуються всі команди допоміжного алгоритму з використанням ­фактичних аргументів

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

•Після виконання допоміжного алгоритму виконується команда основного алгоритму, записана після команди виклику допоміжного алгоритму

Виклик		За допомогою спеціальної інструкції		За допомогою безпосередньої вказівки
				імені функції з фактичними аргумента­
				ми в деякому виразі
			Тема 6. Алгоритмізація. Основи програмування
144

144 3945У Інформатика в таблицях