Тема: Алгоритми. Властивості алгоритмів. Форми подання алгоритму.
Мета: розглянути поняття алгоритму,висвітлити властивості алгоритму, ознайомити з різними формами подання алгоритму; розвинути пам'ять, увагу, мислення; виховати послідовність у діях, уважність, дисциплінованість.
Тип уроку: лекція.
Обладнання: ПК, інтерактивна дошка, програмне забезпечення.
Наочність: презентація.
Тривалість: 45 хвилин.
План уроку:
1. Поняття алгоритму.
2. Властивість алгоритмів.
3. Форми алгоритмів.
4. Виконавець алгоритму.
Хід уроку.
І. Пояснення нового матеріалу.
Ми з вами закінчили розділ основи Інтернету, а сьогодні розпочинаємо великий і дуже складний розділ «Основи програмування». На сьогоднішній день майже 90% техніки не могло б існувати без програм, а саме без програмування. Програма замінює більшість наших операцій в різних сферах нашого життя, а програмування починається з складання послідовності дій тобто алгоритму.
На сьогоднішньому уроці ми з вами розглянемо нове поняття в інформатиці – це алгоритм. Давайте запишемо, що таке алгоритм. Отже, дістали свої зошити, записали число, класна робота, тема уроку.
Тепер давайте запишемо саме поняття алгоритму.
Алгоритм – це конструктивно задане правило, за яким вхідні інформації (умовам задачі) ставиться у відповідність нова вихідна інформація (розв’язок задачі). Інакше кажучи, алгоритм – це деякий скінчений набір операцій, виконання яких одна за однією через скінчене число кроків приводить до поставленої мети (розв’язку задачі). Поняття алгоритму належить до основних не означуваних понять і не означається через простіші поняття.
Алгоритм повинен мати такі властивості:
1. Масовість. Алгоритм повинен бути застосованим до будь-яких елементів з множини вхідних даних.
2. Визначеність. Описання множини операцій, якою визначається алгоритм, не повинні допускати двояких тлумачень. При виконанні операцій не повинно виникати питань, що саме і як треба робити. Строго визначеним повинен бути і порядок виконання операцій.
3. Дискретність. Процес, який визначається алгоритмом, повинен мати дискретний (перервний) характер, тобто являти собою послідовність окремих завершених в собі кроків. У зв’язку з цим повідомленням проте, яку саме операцію треба виконати на кожному кроці, подають у вигляді речень наказової форми доконаного виду (“Виконати ...”, а не “Виконувати ...”). такі повідомлення називають вказівками (або командами). Кожна операція алгоритму повинна виконуватися за скінчений час, а виконання наступної операції повинно починатися після завершення попередньої.
4. Результативність. Виконання послідовності операцій, якою визначається алгоритм, через скінчене, можливе досить значне, число кроків приводить до цілком певного результату. Виконання алгоритму не може закінчуватися не визначеною ситуацією або ж зовсім не закінчуватися. Кожен алгоритм передбачає наявність деяких вихідних даних і його виконання за скінчений час приводить до цілком певних результатів.
5. Формальність. Будь-який виконавець, здатний сприймати і виконувати вказівки алгоритму (навіть не розуміючи їх змісту), діючи за алгоритмом, може виконати поставлене завдання. Ця властивість має особливе значення для автоматизації виконання алгоритму. Очевидно, електронно-обчислювальні машини не можуть розуміти суть завдання і окремих вказівок алгоритмів, хоча успішно виконують різні алгоритми.
Існують різні форми подання алгоритмів:
· Словесні.
· Словесно-формульні
· Графічні
· У вигляді послідовностей кодів
При складанні алгоритмів часто поєднують різні форми.
При конструюванні алгоритму методом покрокової деталізації кожна операція може подаватися у вигляді лише трьох типів сукупностей простіших операцій, так званих базових алгоритмічних структур.
Слідування. Операція S подається у вигляді послідовності двох (або більше) виконуваних одна за однією простіших S1, S2, …, Sn.
Розгалуження (Вибір). Для виконання операції S треба спочатку визначити, хибне чи істинне деяке твердження Р (чи справджується умова Р). Якщо твердження Р істинне, то виконується операція S1 і на цьому виконання операції S закінчується. Якщо ж твердження Р хибне, то виконується операція S2 і на цьому виконання операції S закінчується (мал. 2).
Окремим випадком розгалуження є неповне розгалуження, коли в разі хибності твердження Р ніякі операції взагалі не виконуються (мал. 3). Повне розгалуження завжди можна подати у вигляді слідування двох неповних (мал. 4).
Повторення (цикл). Розрізняють два типи циклів – цикл – ПОКИ і цикл – ДО. У структурі цикл – ПОКИ для виконання операції S спочатку треба визначити, істинне чи хибне твердження Р. Якщо Р – істинне, то виконують операцію S1 і знову повертаються до визначення істинності твердження Р. Якщо ж твердження Р хибне, то виконання операції S вважається закінченим. Отже, поки твердження Р істинне, треба повторювати виконання операції S1 і повертається до визначення істинності твердження Р.
У структурі цикл – ДО спочатку виконується операція S1, а потім визначається істинність твердження Р. Якщо твердження Р хибне, то знову виконується операція S1 і визначається істинність твердження Р. Якщо ж твердження Р істинне, то виконання вказівки S вважається закінченим. Отже, операція S1 і визначення істинності твердження Р повторюються до настання істинності Р.
Зазначимо що в структурі цикл-ПОКИ операція S1 може не виконуватися жодного разу. У структурі ж цикл-ДО операція S1 буде виконуватись при наймі один раз.
Кожна з операцій S1, S2, ..., Sn операція про перевірку істинності твердження Р, в свою чергу можуть бути подані як сукупності найпростіших операцій, об’єднаних у структури розглянутих типів.
Важливою особливістю розглянутих структур є те, що кожна з них має єдиний вхід і єдиний вихід. При конструюванні алгоритму вихід кожної базової структури приєднуються до входу іншої. Таким способом весь алгоритм подається у вигляді лінійної послідовності базових алгоритмічних структур. Така послідовність може складатися з єдиної базової алгоритмічної структури.
Алгоритми в яких використовуються тільки структура “слідування”, називають лінійними. Алгоритми, в основі яких лежить структура “розгалуження”, називають розгалуженнями. Алгоритми, в основі яких лежить структура “повторення”, називають циклічними. На практиці, як правило, алгоритми містять усі три типи основних структур алгоритмів.
Алгоритм виконання певного завдання, поданий як деяка скінчена послідовність операцій із системи операцій комп’ютера, називають програмою.
ІV. Засвоєння нового матеріалу.
1. Що називається алгоритмом ?
2. Які властивості алгоритму?
3. Що означає властивість масовість?
4. Що означає властивість визначеність?
5. Що означає властивість дискретність?
6. Що означає властивість результативність?
7. Що означає властивість формальність?
8. Назвіть основні типи сукупностей простіших операцій?
9. На які типи діляться цикли?
10. Яка структура використовується в лінійному алгоритмі?
11. Яка структура використовується в алгоритмах розгалуження?
12. Яка структура використовується в циклічних алгоритмах?
V.Домашнє завдання.
Скласти алгоритм,
Може в когось є запитання то я вас слухаю. Якщо ж немає то підведемо підсумок уроку.
На сьогоднішньому уроці ми вивчили, що таке алгоритми, їхні властивості. Форми подання алгоритмів.
Урок закінчено. До побачення.