Алгоритми, їх властивості та базові структури

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

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

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

• лінійний
• розгалужений
• циклічний.

 

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

До таких операцій відносяться дії зміни значення деяких величин, введення та виведення інформації тощо.

Декілька лінійних елементів можуть об'єднуватися і утворювати складену лінійну структуру або лінійний фрагмент алгоритму. В алгоритмі Евкліда лінійними елементами є дії введення та виведення інформації, обчислення нових значень величин n та m.

У якості прикладів лінійних елементів можна навести такі:

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

До складених базових алгоритмічних структур відносяться розгалужені і циклічні алгоритми.

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

В тому випадку, коли умова справджується, продовження виконання алгоритму відбувається за стрілкою «+», в протилежному випадку - за стрілкою «-».

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

Скорочена форма розгалуженого елемента у випадку невиконання умови не передбачає ніяких дій. При цьому алгоритм переходить до виконання наступного базового елемента (блок «дія 2» буде відсутнім).

 

 

Прикладом розгалуженого елемента в алгоритмі Евкліда є вибір зміни значення величини п або величини т у залежності від співвідношення між ними (n > m - «так» або «ні»). У результаті вибору одна з дій (n:=n-m, m:=m-n) буде пропущена.

Прикладами розгалужених елементів можуть бути ще такі:

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

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

Є два типи повторення: з передумовою та з післяумовою.

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

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

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

До прикладів повторення з передумовою можна віднести такі:

• поки є тісто виготовляти тістечка;
• поки не втомився кидати цеглу у вантажівку;
• поки не завершиться список чисел знаходити їх суму.

Прикладами повторення з післяумовою можугь буги:

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

Типи алгоритмів

Лінійними алгоритмами , називаються алгоритмів, які складаються з лінійних елементів.

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

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

Розгалуженими , називаються алгоритми, які складаються з розгалужених елементів.

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

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

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

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

 

 

Декілька прикладів циклічних  алгоритмів:

• плетіння деякого складного узору за допомогою гачка чи спиць;
• дотримання розпорядку дня протягом робочого тижня;
• заповнення таблиці значень sinх при заданих аргументах.

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

Стосовно допоміжних алгоритмів можна розглядати:

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

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

 

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