Поняття алгоритму. Властивості та способи представлення алгоритмів. Базові структури алгоритмів

Лекція № 1
Тема: Поняття алгоритму. Властивості та способи представлення алгоритмів. Базові структури алгоритмів.
Мета лекції: знайомство із поняттям алгоритму та можливістю його представлення у вигляді блок- схеми. Набуття навиків побудови лінійних та розгалужених алгоритмів.
План
1. Етапи розв’язку задач на комп’ютері.
2. Поняття алгоритму.
3. Властивості алгоритму.
4. Форми подання алгоритмів.
5. Базові структури алгоритмів
6. Приклади деяких типових найпростіших алгоритмів.
7. Контрольні питання.
8. Література.
1. Етапи розв’язку задач на комп’ютері.
Розв’язання задачі в будь-якій сфері діяльності – це завжди отримання деяких результатів.
Незважаючи на рiзноманiтнiсть задач у самому процесi їх розв’язку за допомогою комп'ютера можна виділити наступні основнi етапи.
Постановка задачі. Розв’язання задачі починається з її постановки, викладеної мовою чітко визначених математичних понять. При цьому слід зрозуміти суть поставленої задачі, визначити необхідні початкові дані та інформацію, що вважається результатом розв’язання.
Побудова математичної моделі. Не завжди умова сформульованої задачі містить у собі готові математичні формули, що пов’язують вихідні дані та результат. Для розв’язку задачі необхідно створити математичну модель об’єкта, і чим достовірніше вона відображає реальні сторони об’єкта, тим точнішими будуть одержані результати.
Розробка алгоритму. Створення алгоритму, тобто послідовності дій для розв’язання задачі, на основі побудованої математичної моделі. З метою знаходження способу розв’язання поставленої задачі можуть бути застосовані вже відомі методи, проведена їх оцінка, аналіз, відбір або розроблені нові методи. При створенні складних алгоритмів застосовується метод покрокової розробки, сутність якого полягає в тому, що алгоритм розробляється «зверху донизу». Такий підхід дозволяє розбити алгоритм на окремі частини, кожна з яких розв’язує свою самостійну підзадачу, і об’єднати ці підзадачі в єдине ціле.
Складання програми. Алгоритм має бути записаний мовою програмування. Процес розробки програми потребує знання вибраної мови програмування і може здійснюватися теж за принципом
«зверху донизу», що дозволяє одержати добре структуровану програму, читання і розуміння якої значно полегшене.
Компіляція програми. Переведення програми на машинну мову здійснюється за допомогою спеціальних програм — компіляторів. Однією з функцій компілятора є перевірка у програмі синтаксичних помилок і, за їх відсутності, побудова об’єктного модуля.
Компонування програми здійснюється компоновщиком (редактором зв’язків), який формує виконавчий модуль програми. На цьому етапі відбувається підключення бібліотек, з’єднання окремих модулів, тобто розв’язання зовнішніх посилань.
Налагодження програми. Окрім синтаксичних помилок, програма може мати помилки
іншого типу — змістовні, логічні. Вони з’являються під час помилкового трактування умови поставленої задачі через недосконалість математичної моделі або недоліки у побудованому алгоритмі. Процес налагодження програми полягає в підготовці системи тестів, які містять набір вихідних даних, що дають відомий результат. Якщо для всіх тестів результати роботи програми збіглися з розрахунками, то можна вважати, що логічних помилок немає.
Експлуатація програми. Програма, що має відповідну документацію, може бути тиражована і запропонована іншим користувачам.

2. Поняття алгоритму.
Походження слова «алгоритм» - від імені арабського вченого аль-Хорезмі, який приблизно у
825 році дав опис винайденій в Індії позиційній десятковій системі числення. У перекладі книжка містила ім‘я вченого, від якого пішло слово «алгоритм», а від оригінальної назви пішло слово
«алгебра». Саме він у своїх трактатах описав правила (алгоритми) додавання, віднімання, множення та ділення багатозначних чисел, якими ми користуємося сьогодні.
Єдиного «істинного» визначення поняття «алгоритм» немає:
Алгоритм – скінчений набір правил, який визначає послідовність операцій для розв’язку конкретної множини задач та володіє наступними важливими рисами: скінченістю, визначеністю, вводом, виводом, ефективністю.
Алгоритм – система обчислень, що виконується за чітко визначеними правилами, яка після деякої кількості кроків приводить до розв’язку поставленої задачі.
Алгоритм – чітко детермінована послідовність дій, яка описує процес перетворення об’єкту із початкового стану в кінцевий, записана за допомогою зрозумілих виконавцю команд.
Алгоритм - послідовність дій, направлених на отримання кінцевого результату за скінчену кількість крокіів.
Алгоритм- послідовність дій, яка або приводить до розв’язку задачі, або пояснює, чому такий розв’язок отримати не можливо.
Алгоритм- точна, однозначна, скінчена послідовність дій, яку необхідно виконати для досягнення конкретної мети за скінчену кількість кроків.
Алгоритм — це скінчена послідовність команд, які потрібно виконати над вхідними даними для отримання результату.
Спільним у цих визначеннях є те, що алгоритм – це набір команд. Алгоритм орієнтований на конкретного виконаві, а об’єкти, над якими він може виконувати дії утворюють середовище виконавця.
Вихідні дані та результати будь-якого алгоритму завжди належать середовищу того виконавця, для якого призначений алгоритм.
Розглянемо приклад алгоритму для знаходження середини відрізка за допомогою циркуля і лінійки.
Алгоритм розподілу відрізка АВ навпіл:

поставити ніжку циркуля в точку А;

встановити розмах циркуля рівним довжині відрізка АВ;

провести коло;

поставити ніжку циркуля в точку В;

провести коло;

через точки перетину кіл провести пряму;

відзначити точку перетину цієї прямої з відрізком АВ.
Можна сказати, що алгоритм описує процес перетворення вихідних даних у результат, оскільки для розв’язку будь-якої задачі необхідно:
1. Ввести вихідні дані.
2. Перетворити вихідні дані у результат (вихідні дані).
3. Вивести результат.
Алгоритм – це деяке правило перетворення інформації, застосування якого до заданої (вихідної)
інформації приводить до результату – нової інформації.
Аналіз прикладів різних алгоритмів показує, що запис алгоритму розпадається на окремі вказівки виконавцю виконати деяку закінчену дію. Кожна така вказівка називається командою.
Алгоритм
Вхід
Вихід
Алгоритм як правило перетворення інформації

Команди алгоритму виконуються одна за одною. Після кожного кроку виконання алгоритму точно відомо, яка команда повинна виконуватися наступною. Сукупність команд, які можуть бути виконані виконавцем, називається системою команд виконавця.
Приклад алгоритму додавання дробів можна задати наступною послідовністю команд:
Вихідна інформація A, B, C, D; {скласти A/B і C/D}
Результат E,F;
{E/F = A/B + C/D}
1. Обчислити Y = B*D;
{Перейти до наступної команди}
2. Обчислити X
1
= A*D;
{Перейти до наступної команди}
3. Обчислити X
2
= B*C;
{Перейти до наступної команди}
4. Обчислити X = X
1
+X
2
;
{Перейти до наступної команди}
5. Обчислити Z = НСД (X,Y);
{Перейти до наступної команди}
6. Обчислити Е = X div Z;
{Перейти до наступної команди}
7. Обчислити F = Y div Z.
{Закінчити роботу}.
Вихідна інформація алгоритму представлена чотирма цілими числами A, B, C, D. Це – чисельники і знаменники дробів, що додаються. Результат роботи алгоритму – числа E і F – чисельник і знаменник суми. Власне алгоритм складається з 7-ми команд, кожна з яких містить команду – виконати одну з арифметичних дій над цілими числами: додавання, множення, обчислення НСД і div (обчислення неповної частки). Крім виконання арифметичної дії, кожна команда запам'ятовує результат як значення величини, зазначеної в лівій частині рівності, що входить у команду. Нарешті, кожна команда (у неявному виді) містить вказівку на наступну виконувану команду – перейти до виконання команди з наступним номером.
Таким чином, алгоритм описує деталізований по кроках процес перетворення інформації.
Виконавець алгоритму не тільки виконує дії, але і запам'ятовує їхні результати. Для відображення цього факту в записі алгоритму ми використовуємо літерні позначення даних. Ці позначення називають іменами, а самі дані – величинами.
3. Властивості алгоритму.
Алгоритм не тільки задає послідовність виконання операцій при вирішенні конкретної задачі, а й повинен задовольняти ряду властивостей.
Властивості алгоритму:
Масовість. Алгоритм повинен бути застосованим до будь – яких елементів з множини вихідних даних.
Визначеність. Операції, які використовуються в алгоритмі, не повинні мати двоякого тлумачення; не повинно виникати питання: що саме і як треба робити? Порядок виконання опера- цій повинен бути чітко визначеним.
Дискретність. Процес розв’язування алгоритму повинен складатися з окремих завершених операцій, які виконуються послідовно і за скінчений час.
Результативність. Виконання послідовності операцій алгоритму повинно приводити до цілком конкретного результату.
Формальність. Будь – який виконавець, здатний сприймати і виконувати вказівки алгоритму
( навіть не розуміючи їх змісту), діючи за алгоритмом, може виконати постановлене завдання.
Елементарність.Кожна команда з набору команд Виконавця містить вказівку виконати деяку елементарну (не деталізовану більш детально) дію, яку розуміє, однозначно і точно виконує
Виконавець.
4. Форми подання алгоритму.
Можна виділити ряд форм подання алгоритму:
словесна форма – це запис алгоритму у вигляді послідовності занумерованих словесних команд;
таблична форма подання алгоритму – це запис алгоритму у вигляді розрахункової таблиці;

блок-схема – це запис алгоритму у графічній формі з використанням спеціальних геометричних фігур (блоків), які містять опис операцій, і направлених ліній, які показують напрями передавання управління від одного блоку до іншого.
алгоритмічна мова – це штучна мова, призначена для подання алгоритмів;
мова програмування – це алгоритмічна мова, конструкції якої однозначно перетворюються на команди комп’ютеру. Програма – це алгоритм, записаний на мові програмування;
Приклад опису алгоритму у словесній форміі.
Задача: знайти модуль величини х (тобто значення |х|)і присвоїти це значення змінній у. Під час побудови алгоритму скористаємося визначенням модуля: | х| = х при х ≥ О і |х| = -х при х < 0.
Алгоритм можна записати наступним чином
1 . Початок.
2. Ввести числове значення величини х.
3. Якщо х ≥ 0, то у присвоїти значення х, інакше у присвоїти значення -х.
4. Вивести значення у.
5. Кінець.
Словесний запис найчастіше застосовується на початковому етапі вивчення алгоритмів і призначається для використання алгоритму людиною. Ця форма запису недостатньо наочна і її важко безпосередньо перекласти мовою програми.
Приклад опису алгоритму у графічній формі
Для опису використовуються блок-схеми.
Блок-схема є найбільш наочною формою запису алгоритмів є блок-схеми (графічний спосіб запису алгоритму). Блок схема складається з блоків декількох видів:
1. Блок початку або кінця алгоритму:
2. Блоки введення- виведення:
3. Командний (операторний) блок:
4. Умовний блок:
Так Ні
5. Початок циклічного овлисленняУмовний блок:
6. Обчислення за підпрограмою:
7. Розрив лінії обчислювального потоку:

У оперторному блоці описують одну чи декілька команд присвоєння. Формули записують довільним чином (тобто, символ множення можна не писати).
Блоки зєднують лініями, які описують послідовність виконання команд. Ці лінії називають лініями потоків передавання інформації.Природні напрямки потоків зверху-вниз і зліва-направо.
Якщо напрямок потоку інший, то лінія повинна мати стрілку.
Приклад запису блок-схеми алгоритму розв’язку задачі:
Приклад опису алгоритму за допомогою структурної схеми
Усі команди записують у прямокутних блоках, один на одний. Порядок розміщення блоків визначає порядок виконання команд. Наприклад; ввести а,b,с р:=2
*
( а+b) d:= a* b* с вивести р,d
5. Базові структури (алгоритмічні конструкції) алгоритмів.
Всього можна виділити чотири базових структури алгоритмів:
· лінійні;
· розгалужені;
· циклічні;
· змішані.
Лінійні алгоритми
Лінійним називається алгоритм (фрагмент алгоритму), в якому окремі команди виконуються послідовно друг за другом, не залежно від значень вхідних даних і проміжних результатів.:

Розгалужений алгоритм
Часто хід обчислювального процесу залежить від вихідних даних або проміжних результатів; алгоритм реалізується в одному з декількох, заздалегідь передбачених (можливих) напрямків. Такі напрямки часто називаються гілками. Кожна гілка може бути будь-якого ступеня складності, а може взагалі не містити команд, тобто бути виродженою. Вибір тієї або іншої гілки здійснюється в залежності від результату перевірки умови з конкретними даними. У кожному випадку алгоритм реалізується тільки по одній гілці, а виконання інших виключається. Приклад розгалуженого алгоритму:
Циклічний алгоритм
Виконання деякої частини алгоритму багаторазово при різних значеннях деяких змінних називається циклічним обчислювальним процесом. Циклами називаються повторювані ділянки обчислень. Для організації циклів необхідно: задати початкове значення змінної, що визначає цикл
(параметр циклу), зміняти цю змінну перед кожним повторенням циклу, перевіряти умову продовження (закінчення) циклу. У циклічних алгоритмах виконання деяких операторів (груп операторів) здійснюється багаторазово з тими ж або модифікованими даними.
У залежності від способу організації кількості повторень циклу розрізняють три типи циклів:
1) цикл із заданою умовою закінчення роботи (ЦИКЛ - ДО);
2) цикл із заданою умовою продовження роботи (ЦИКЛ - ПОКИ);
3) цикл із заданою умовою повторень роботи (ЦИКЛ 3 ПАРАМЕТРОМ). Приклади циклічного алгоритму:

У багатьох задачах виникає необхідність повторювати ті самі обчислення в декількох місцях програми. Тоді зручніше ці обчислення виділити у вигляді процедури і звертатися до неї в будь- якій частині основної програми в міру необхідності. Процедура - це спеціальним образом оформлена послідовність команд, до якої можна звернутися: зажадати перервати виконання команд основної програми, виконати всю послідовність команд процедури, а потім продовжити виконання команд основної програми.. В якості процедури можуть використовуватись зовнішні функції
(підпрограми-функції) і зовнішні підпрограми.
6. Приклади деяких типових найпростіших алгоритмів.
Розглянемо деякі типові прийоми алгоритмізації, які на практиці використовуються або у вигляді окремих алгоритмів, або входять до складу більш складних алгоритмів. При цьому слід мати на увазі, що та ж сама задача може бути розв’язана різними способами.
Приклад 1. Обчислити значення функції у = а*х2- sinх, х є [-1; 2]; hx= 0,5; а= 10,5, та знайти кількість додатних значень функції.
У прикладі проста змінна х є аргументом функції, який змінюється з кроком hx.
На рисунку нижче представлено схему алгоритму розв’язання поставленої задачі, яка включає:

блок введення значень коефіцієнта а та кроку зміни аргументу - hx.

блоки присвоювання початкових значень змінній kol (kol = 0) та аргументу х (х = -1); змінна kol використовується для підрахунку кількості додатних значень функції;

реалізацію багаторазового обчислення значень функції у при різних значеннях аргументу х, яка здійснюється циклічною ділянкою алгоритму, що виконує такі дії, як обчислення значення функції, виведення значень х та у;

розгалуження, що міститься в тілі циклу за параметром х, реалізоване блоком перевірки умови у > 0. У випадку, коли у додатний, відбувається підрахунок кількості додатних значень функції —kol=kol + 1;


якщо додатний елемент функції підраховано або у від’ємний, значення аргументу х збільшу-
ється на крок —х=х+hх;

логічний блок, що керує циклом, містить перевірку нерівності х < 2 і, якщо х перевищить значення 2 забезпечує вихід з циклу.
Приклад 2. За один перегляд масиву c i
(і= 0...n-1), n=15 визначити значення і положення максимального та мінімального елементів і поміняти їх місцями. Схему алгоритму розв’язання задачі побудувати самостійно.
Для знаходження максимального та мінімального елементів одновимірного масиву використовується типовий прийомом — введення допоміжної змінної. Максимальний елемент позначено через mах, а його позицію —imах. Відповідно для мінімального елемента та його позиції використовуються змінні min та imin. Перед переглядом масиву як в max, так і в min записується значення першого елементу масиву, тобто елементу, розташованого в позиції і = 0 (max=с
0
та
min=с
0
), а його номер (0)запам’ятовується змінними іmах та imin (іmах=0; imin=0).
У процесі порівняння, якщо змінна max буде більше за поточний елем елемент масиву, то значення max залишається незмінним, у протилежному випадку max набуде значення поточного елементу масиву.
Таким чином, здійснюючи пошук максимального елемента серед сукупності чисел, необхідно послідовно їх переглянути і порівняти між собою. Для цього дії над елементами масиву слід реалізувати циклом, параметром якого є індекс і елемента масиву. По закінченні циклу одержимо значення та номери максимального і мінімального елементів. Для перестановки цих елементів місцями достатньо виконати дві дії, а саме: c imax
=min та cimax
=
max
Приклад 3. Упорядкувати за зростанням массив х i
(і=0...n-1), n = 12, з використанням обмінного сортування (методом «бульбашки»).
Сортування —це впорядкування масиву за деякою ознакою. Існують різні методи сортування, серед яких обмінне сортування (метод «бульбашки») — найбільш простий, але найменш ефективний метод сортування, і його доцільно застосовувати для сортування невеликих масивів. Алгоритм методу приведено нижче.

Метод «бульбашки» полягає в послідовному порівнянні пар чисел і перестановці їх за необхідності. В процесі впорядкування вихідний масив проглядається зліва направо. Наприклад, на першому кроці сортування за зростанням, якщо елементи задовольняють умові: x
і
>х
і+1
, то вони міняються місцями. При цьому і-тий елемент (крім першого й останнього) бере участь у двох порівняннях. Таким чином, найбільший елемент масиву буде переміщатися («спливати» як бульбашка) до правого кінця масиву і виявиться останнім.
На другому кроці сортування масиву виявиться наступний за значенням найбільший елемент, що «спливе» на передостаннє місце. Ці дії повинні повторюватися доти, поки залишиться менше двох невідсортованих елементів масиву. Для масиву з n елементів за один крок сортування виконується n-1 порівнянь. На кожному новому кроці сортування масиву кількість порівнянь зменшується на одиницю.
Таким чином, окрім блоків введення та виведення елементів масиву, алгоритм сортування методом «бульбашки» має два вкладених цикли:

зовнішній цикл за параметром k - цикл кроків сортування, який керує багаторазовим вико- нанням внутрішнього циклу;

внутрішній цикл за параметром і — цикл порівняння елементів та їх перестановки.
Розглянутий приклад наочно ілюструє застосування одного з типових прийомів алгоритмізації — робочої змінної (а), яка необхідна для перестановки місцями двох елементів.
Контрольні
питання:
1. Що таке алгоритм?
2. Які властивості алгоритмів Ви знаєте?
3. Що таке блок-схема?
4. Що таке вибір та цикл?
5. Які способи опису алгоритмів Ви знаєте?
6. Що означає скінченність (дискретність) алгоритму?
7. Що таке формальність алгоритму?
8. Що означає масовість алгоритму?
9. Які є три головні базові структури?
10. З чого складаються прості (лінійні) алгоритми?
11. Яке призначення команди розгалуження і як вона діє ?
12. Яке призначення команди циклу і як вона діє ?
13. Які є правила складання блок-схем?
14. Які види блоків використовують у блок-схемах?
15. Які є етапи створення програми?