Алгоритм. Властивості алгоритмів. Форми подання алгоритму. Базові структури алгоритмів. Метод «покрокової деталізації»

Урок 2   

Тема: Алгоритм. Властивості алгоритмів. Форми подання алгоритму. Базові структури алгоритмів. Метод «покрокової деталізації»

Навчальна мета: Засвоїти відомості з основ алгоритмізації та програмування, навчатися створювати алгоритми, познайомитися з їх властивостями та базовими структурами, навчитися використовувати метод «покрокової деталізації»

Розвивальна мета: Розвивати координацію рухів, зорову пам’ять, вміння працювати з програмами

Виховна мета: Виховувати зосередженість, вміння активно сприймати новий матеріал.

Тип уроку:  Урок вивчення нового матеріалу (лекція)

Структура уроку

1. Організаційний момент
2. Етап орієнтації
3. Етап проектування
4. Етап навчальної діяльності
5. Робота за ПК
6. Контрольно-оцінювальний етап
7. Домашнє завдання                                                                                                                                                                                                                                                                                               

Хід уроку

І. Організаційний момент

Сьогодні ми з вами розглянемо тему: «Алгоритм. Властивості алгоритмів. Форми подання алгоритму. Базові структури алгоритмів. Метод «покрокової деталізації»».

II. Етап орієнтації

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

III. Етап проектування

План уроку

1. Алгоритм.
2. Властивості алгоритмів.
3. Форми подання алгоритму.
4. Базові структури алгоритмів.
5. Метод «покрокової деталізації»

ІV. Етап навчальної діяльності

Алгоритм

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

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

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

Поняття алгоритму в інформатиці є фундаментальним, тобто таким, котре не визначається через інші ще більш прості поняття (для порівняння у фізиці - поняття простору і часу, у математиці - крапка).

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

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

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

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

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

1.       Зрозумілість. Щоб виконавець міг досягти поставленої перед ним мети, використовуючи даний алгоритм, він повинен уміти виконувати кожну його вказівку, тобто розуміти кожну з команд, що входять до алгоритму.
   Наприклад: Мамі потрібно купити в магазині їжу. Виконавцем цього алгоритму може бути хтось із родини: батько, син, бабуся, маленька дочка тощо. Зрозуміло, що для тата достатньо сказати, які купити продукти, а далі деталізувати алгоритм не потрібно. Дорослому сину-підлітку необхідно детальніше пояснити в яких магазинах можна придбати потрібний товар, що можна купити замість відсутнього товару і таке інше. Маленькій дочці алгоритм необхідно деталізувати ще більше: де взяти сумку, щоб принести товар, яку решту грошей необхідно повернути з магазину, як дійти до магазину і як там поводитись (якщо дитина вперше йде за покупками).
   Подібних прикладів можна навести безліч і запропонувати дітям самостійно підібрати ситуацію, в якій в залежності від виконавця алгоритм буде набувати все більшої деталізації. Висновок з цього діти можуть зробити самостійно: зрозумілість - це властивість алгоритму, що полягає в тім, що кожен алгоритм повинен бути написаний у командах, зрозумілих даному виконавцю.
2. Визначеність (однозначність). Зрозумілий алгоритм все ж таки не повинен містити вказівки, зміст яких може сприйматися неоднозначно. Наприклад, вказівки "почисти картоплю", "посоли за смаком", "прибери в квартирі" є неоднозначними, тому що в різних випадках можуть призвести до різних результатів. Крім того, в алгоритмах неприпустимі такі ситуації, коли після виконання чергового розпорядження алгоритму виконавцю не зрозуміло, що потрібно робити на наступному кроці. Наприклад: вас послали за яким-небудь товаром у магазин, та ще попередили "без (хліба, цукру і таке інше) не повертайся", а що робити, якщо товар відсутній?
   Отож, точність - це властивість алгоритму, що полягає в тім, що алгоритм повинен бути однозначно витлумачений і на кожному кроці виконавець повинен знати, що йому робити далі.
3.  Дискретність. Як було згадано вище, алгоритм задає повну послідовність дій, які необхідно виконувати для розв'язання задачі. При цьому, для виконання цих дій їх розбивають у визначеній послідовності на прості кроки. Виконати дії наступного розпорядження можна лише виконавши дії попереднього. Ця розбивка алгоритму на окремі елементарні дії (команди), що легко виконуються даним виконавцем, і називається дискретністю.
4.  Масовість. Дуже важливо, щоб складений алгоритм забезпечував розв'язання не однієї окремої задачі, а міг виконувати розв'язання широкого класу задач даного типу. Наприклад, алгоритм покупки якого-небудь товару буде завжди однаковий, незалежно від товару, що купується. Або алгоритм прання не залежить від білизни, що переться, і таке інше. Отож, під масовістю алгоритму мається на увазі можливість його застосування для вирішення великої кількості однотипних завдань.
5. Результативність. Взагалі кажучи, очевидно, що виконання будь-якого алгоритму повинне завершуватися одержанням кінцевих результатів. Тобто ситуації, що в деяких випадках можуть призвести до так званого "зациклення", повинні бути виключені при написанні алгоритму. Наприклад, розглянемо таку ситуацію: роботу дано завдання залишити кімнату (замкнутий простір), не виконуючи руйнівних дій. У цьому випадку, якщо роботу не дати вказівки відкрити двері (що, можливо, закриті), то спроби залишити приміщення можуть бути безуспішними.
6. Скінченність.

Форми подання алгоритму

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

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

Першій спосіб - це словесний опис алгоритму. Сьогодні на уроці розібрано вже кілька алгоритмів, і всі вони подавалися виконавцю за допомогою словесного опису.
Другий спосіб - це подача алгоритму у вигляді таблиць, формул, схем, малюнків тощо. Наприклад, всіх вас вчили в дитячому садочку правилам поведінки на дорозі. І найкраще діти, вочевидь, сприймають алгоритм, що поданий у вигляді схематичних малюнків. Дивлячись на них, дитина, а потім і доросла людина, відпрацьовує ту лінію поведінки, що їй пропонується. Аналогічно можна навести приклади алгоритмів, що записані у вигляді умовних позначок на купленому товарі, щодо його користування (заварювання чаю, прання білизни тощо). В математиці наявність формул дозволяє розв'язати задачу, навіть "не використовуючи слів".

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

Четвертий спосіб - навчальні алгоритмічні мови (псевдокоди). Ці мови мають жорстко визначений синтаксис і вже максимально наближені до машинної мови (мови програмування). Але створені вони з навчальною метою, тому мають зрозумілий для людей вигляд. Таких псевдокодів зараз існує велика кількість, починаючи з графічних середовищ "Алгоритміка", "Роботландія", "Лого-світи", "Черепашка" тощо і закінчуючи текстовими "національними" реалізаціями алгоритмічних мов, подібних до Паскаля. Ці псевдокоди мають програмну реалізацію і дуже широко застосовуються на етапі навчання основам програмування.

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

Базові структури алгоритмів

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

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

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

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

Ромбом позначається перевірка значення логічного виразу (рис. 2) У логічних виразах можуть використовуватися логічні операції «не» «і», «або». Логічний вираз може набувати одного з двох значень — істина чи хиба.

Перевірка значення логічного виразу звичайно зводиться до пе­ревірки виконання чи невиконання певних умов.

Перейдемо до опису базових структур.

1. Проходження означає, що дії мають бути виконані по­слідовно одна за одною (рис. 3).

Наприклад, будь-який алгоритм можна подати як послідовність трьох дій (рис. 4).

2. Розвилка, яка також називається «якщо-то-інакше», озна­чає вибір одного з двох варіантів залежно від значення певного ло­гічного виразу (рис. 5). Може виявитися, що при одному зі значень логічного виразу не потрібно виконувати жодних дій. У цьому випадку структура роз­вилки називається «якщо-то» і може бути представлена у вигляді, що на рис. 7.

Така структура використовується в тих випадках, коли необ­хідність виконання дій залежить від певних умов. Наприклад, вико­нувати сортування послідовності з я елементів має сенс лише тоді, коли в ній більше, ніж один елемент (рис. 8).

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

Такий цикл називається «цикл-поки», або «цикл із передумо­вою» (умова перевіряється перед виконанням тіла циклу). Спочат­ку — на першому кроці циклу — перевіряється значення логічного виразу. Якщо воно є істинним, то виконується тіло циклу. Потім — на  другому  кроці  —  знову  перевіряється  значення  логічного виразу і, якщо воно досі є істинним, знову виконується тіло циклу тощо. Цикл завершується, коли значення логічного виразу стає хибним.

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

Наприклад, для обчислення суми п чисел а_1; а₂, ..., а_п (п > 2) слід користуватися структурою циклу. Позначимо через S шукану суму, а через і — номер числа в послідовності. До початку циклу S = 0 (ще нічого не підсумовували) та і = 1 (почнемо підсумовува­ти з першого члена) (рис. 10).

Отже, як ми вже зазначили базових структур написання алгоритму є чотири:

1. Проходження – означає, що дії мають бути виконані послідовно.
2. Розвилка (умова) – означає вибір одного з двох варіантів.
3. Цикл – означає повторне виконання дії, доки значення лишається істинним.
4. Змішана – означає, що використовується більше одної базової структури при написанні одного алгоритму.

Наприклад,  алгоритм обчислення суми двох чисел може бути таким:

Метод «покрокової деталізації»

Слово «метод» походить від грецького method’s, що в пе­рекладі означає «шлях дослідження, теорія, навчання». Стосовно задач метод — це загальний спосіб, сукупність прийомів, що використовуються для розв'язування задач певного типу. Для задач того самого типу може існувати багато різних методів розв'язування.

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

Алгоритми створюються за певними правилами. Для складання алгоритмів існують спеціально розроблені прийоми. Один з основ­них — метод покрокової деталізації. Він полягає в тому, що ви­хідна задача розбивається на кілька взаємозалежних підзадач, кожна з яких, натомість, розбивається на підзадачі і та ін. Цей про­цес завершується, коли розв'язування вихідної задачі зводиться до розв'язування ряду простих задач, для яких легко скласти ал­горитм. На кожному кроці цього процесу відбувається деталізація, тобто перехід від більш загальних задач до менш загальних, котрі, в свою чергу, допускають деталізацію до більш конкретних під­задач. Схему цього процесу можна зобразити у вигляді дерева.

VI. Контрольно-оцінювальний етап

Запитання для узагальнення

1. Що таке алгоритм?
2. Які властивості алгоритмів ви знаєте?
3. Які форми подання алгоритмів ви знаєте?
4. З чого складається базові структури алгоритмів?
5. Опишіть метод «покрокової деталізації». В чому його суть?
6. * Складіть алгоритм визначення оцінки в ВУЗах за к-стю балів і рейтинговою системою: якщо сумарний бал не менше 90% від максимального то ставиться 5, якщо не менше 75% то ставиться 4, якщо не менше 60%, то ставиться 3, а якщо нижче за 60% то ставиться 2.

VII.Домашнє завдання

Вивчити терміни, конспект  

§ 2, 3 пит.1, 3, 4, на с. 26 + пит.. 4 с. 27(самос)т + пит.. 1,5 с.41(самост.)

Розв’язання завдання 6*.