Поняття алгоритму. Основні способи опису алгоритму.

Одним з базових понять інформатики є поняття алгоритму.

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

Н а п р и к л а д: ранком мама перед Вашим виходом до технікуму, дає вказівку: "Коли прийдеш із технікуму, відразу пообідай і вимий посуд. Після цього, сходи в магазин і можеш трохи погуляти. Гуляти дозволяю не більше години, а потім відразу за уроки". Ця інструкція складається з послідовності окремих вказівок, що і визначають твою поведінку після повернення із технікуму. Це і є алгоритм. Отже, після обговорення кількох прикладів алгоритмів, давайте спробуємо сформулювати визначення, що ж таке алгоритм.

Алгоритмом називається послідовність певних дій та правил, спрямованих на досягнення зазначеної мети чи на розв'язання поставленої задачі.

Алгоритм має задовільняти певним вимогам, серед яких потрібно виділити найважливіші.

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

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

Н а п р и к л а д: Мамі потрібно купити в магазині їжу. Виконавцем цього алгоритму може бути хтось із родини: батько, син, бабуся, маленька дочка тощо. Зрозуміло, що для тата достатньо сказати, які купити продукти, а далі деталізувати алгоритм не потрібно. Дорослому сину-підлітку необхідно детальніше пояснити в яких магазинах можна придбати потрібний товар, що можна купити замість відсутнього товару і таке інше. Маленькій дочці алгоритм необхідно деталізувати ще більше: де взяти сумку, щоб принести товар, яку решту грошей необхідно повернути з магазину, як дійти до магазину і як там поводитись (якщо дитина вперше йде за покупками).

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

Зрозумілий алгоритм все ж таки не повинен містити вказівки, зміст яких може сприйматися неоднозначно.

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

Н а п р и к л а д: вас послали за яким-небудь товаром у магазин, та ще попередили "без (хліба, цукру і таке інше) не повертайся", а що робити, якщо товар відсутній?

§ Результативність – за скінченну кількість кроків алгоритм має приводити до розв’язання задачі або зупинятися через неможливість її розв’язати.

Взагалі кажучи, очевидно, що виконання будь-якого алгоритму повинне завершуватися одержанням кінцевих результатів. Тобто ситуації, що в деяких випадках можуть призвести до так званого "зациклення", повинні бути виключені при написанні алгоритму. Наприклад, розглянемо таку ситуацію: роботу дано завдання залишити кімнату (замкнутий простір), не виконуючи руйнівних дій. У цьому випадку, якщо роботу не дати вказівки відкрити двері (що, можливо, закриті), то спроби залишити приміщення можуть бути безуспішними.

Взагалі кажучи, очевидно, що виконання будь-якого алгоритму повинне завершуватися одержанням кінцевих результатів. Тобто ситуації, що в деяких випадках можуть призвести до так званого "зациклення", повинні бути виключені при написанні алгоритму. Наприклад, розглянемо таку ситуацію: роботу дано завдання залишити кімнату (замкнутий простір), не виконуючи руйнівних дій. У цьому випадку, якщо роботу не дати вказівки відкрити двері (що, можливо, закриті), то спроби залишити приміщення можуть бути безуспішними.

§ Зв’язаність – на кожному наступному кроці використовуються результати попереднього;

§ Дискретність – кроки обчислювального процесу мають бути відокремлені один від одного.

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

§ Масовість – придатність до рішення всіх задач даного класу;

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

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

§ Ефективність – застосування алгоритму має давати деякий позитивний тимчасовий результат.

Є декілька способів опису алгоритму:

§ словесний опис послідовності дій;

Сьогодні на уроці розібрано вже кілька алгоритмів, і всі вони подавалися виконавцю за допомогою словесного опису.

§ алгоритмічна мова, аналітичний опис у вигляді набору формул;

 

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

§ графічний у вигляді блок – схеми.

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

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

Основні блоки, які використовуються для побудови блок – схем наступні:

Позначення	Назва символу	Пояснення
	Операція (процес)	Прямокутниками позначаються операторні блоки. Операторний блок може мати декілька входів і тільки один вихід.
	Рішення (умова)	Ромбами позначається перевірка умови. Тому блоки, що позначаються ромбами, називаються умовними.
	Введення - виведення	Паралелограми – позначаються введення і виведення даних.
	Пуск, зупинка	Заокругленими прямокутниками – позначається початок та кінець алгоритму. Початковий блок немає входів, а кінцевий блок – виходу.
	З'єднувач	Розрив ліній потоку. Вказання зв’язку між перерваними лініями потоку, що зв’язують символи.
	Модифікація	Виконання операцій, що змінюють команди або групи команд, які змінюють програму.
	Процедурний процес	Виклик підпрограми. Використання раніше створених і окремо описаних алгоритмів і програм.
	Міжсторінковий з’єднювач	Вказання зв’язку між роз’єднаними частинами схем алгоритмів і програми, розташованих на різних листах.
	Коментар	Зв'язок між елементами схеми і пояснення.

Класифікація алгоритмів.

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

Всього існують чотири базових структури алгоритмів:

• Алгоритми лінійної структури;
• Алгоритми розгалуження;
• Алгоритми повторення (циклічні);
• Змішані.