Лекція № 7.

Тема : “Поняття алгоритму. Властивості алгоритмів. Засоби опису алгоритмів. Базові структури алгоритмів. Інформаційна модель. “

Основні запитання лекції :

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

2. Поняття про базові алгоритмічні структури.

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

4. Цикли.

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

6. Засоби опису алгоритму.

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

8. Що таке алгоритмічна мова? Службові слова.

9. Лінійний алгоритм. Приклад.

10. Розгалужений алгоритм. Приклад

11. Поняття циклу. Особливості. Види циклів.

12. Цикл-поки(з передумовою), приклад.

13. Поняття величини. Типи величин.

14. Прості величини. Змінні та постійні величини.

15. Структура опису величин.

16. Інформаційна модель.

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

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

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

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

1. Прямокутником позначається дія, яку необхідно виконати.

Виконати дію

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

2. Ромбом позначається перевірка значення логічного виразу . У логічних виразах можуть використовуватися логічні операції “і”, “або”, “ні”. Логічний вираз може набувати одне з двох значень  істина або фальш. Іноді замість “істина” пишуть “так”, замість “фальш”  “ні”. Перевірка значення логічного виразу звичайно зводиться до перевірки виконання чи невиконання деяких умов.

Засоби опису алгоритмів.

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

1. Словесний опис : алгоритм у вигляді інструкції написаної словами (рідною мовою).

2. Формульний : у вигляді формули розв’язується задача (одне рівняння або система рівнянь, з фізики наприклад закон Ома і т .п.).

3. Блок-схема : наочний графічний спосіб подання алгоритму, який входить в ЄСКД та ЄСТПД.

4. Табличний : запис алгоритму у вигляді таблиці.

Дуже зручно зображувати алгоритм у вигляді блок-схем. Схема алгоритму  це графічне зображення алгоритму за допомогою окремих блоків, що позначають ту чи іншу дію. У блок-схемах окремі дії зображуються геометричними фігурами, що мають стандартні призначення і вигляд.

Початок або кінець алгоритму

Блок введення даних або виведення результату

Блок обчислень

Блок перевірки умови

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

Базові структури.

Базові структури алгоритмів (керуючі структури)  це способи керування процесами обробки даних.

1. Проходження означає, що дії повинні виконуватися одна за одною.

Вхід Виконати Виконати Виконати Вихід

дію a дію b дію c

2. Розвилка, що її називають також “ЯКЩО – ТО – ІНАКШЕ” , означає вибір одного з двох варіантів дій залежно від значення логічного виразу, що знаходиться в цій структурі.

Істина Виконати

дію a

Вхід Вихід

Перевірити значення

значення логічного

виразу

Виконати

Фальш дію b

Може статися так, що при якомусь із значень логічного виразу не потрібно буде виконувати ніяких дій. У такому випадку структура розвилки називається “ ЯКЩО – ТО” і може бути подана у вигляді :

Істина Виконати

дію a

Вхід Вихід

Перевірити

значення логічного

виразу

Фальш

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

Існує три основні види циклів :

• Цикл із передумовою;

• Цикл із післяумовою;

• Цикл із заданою кількістю повторень.

Вхід

Перевірити значення Істина

логічного виразу Виконати

дію a

Фальш

Вихід

Цикл, зображений на малюнку, називається “ЦИКЛ – ДОКИ”( з передумовою). Спочатку  на першому кроці циклу  відбувається перевірка значення логічного виразу. Якщо він істинний, то виконується тіло циклу. Потім  на другому кроці циклу  знову робиться перевірка значення логічного виразу і, якщо він все ще залишається істинним, знову виконується тіло циклу. Цикл завершується, коли значення логічного виразу стає фальшивим.

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

Циклічні процеси також називають ітераційними ( ітерація  повторення), а кожний крок циклу  ітерацією.

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

Кожний алгоритм можна побудувати з трьох базових структур  проходження, розвилки та циклу.