Викладання теми "Алгоритми"

Міністерство освіти і науки України

Полтавський національний педагогічний університет імені В.Г. Короленка

Кафедра математичного аналізу та інформатики

План-конспект уроку інформатики в 11 класі

загальноосвітньої школи універсального профілю

на тему: "Алгоритми"

Підготувала студентка

фізико-математичного факультету

групи Ф-52

Прудка Ірина Іванівна

Полтава-2010

Тема уроку: Алгоритми

Мета уроку:

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

виховувати інтерес до вивчення інформатики та інформаційно-комунікаційних технологій;

розвивати чіткість та конкретність логічного мислення школярів.

Обладнання: мультимедійна презентація "Алгоритми".

Тип уроку: урок вивчення нового навчального матеріалу.

Методи: пояснення, бесіда, розв’язування завдань.

Структура уроку із зазначенням часу

І. Організаційний момент (1 хв).

ІІ. Формулювання мети й завдань уроку (5 хв).

ІІІ. Вивчення нового матеріалу:

Поняття алгоритму (2 хв).

Властивості алгоритму (7 хв).

Способи подання алгоритмів (3 хв).

Базові структури алгоритмів (12 хв).

ІV. Первинне осмислення та закріплення вивченого навчального матеріалу (13 хв).

V. Підсумки уроку та домашнє завдання (2 хв).

Хід уроку

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

ІІ. Формулювання мети й завдань уроку.

Вчитель: Уявіть собі таку ситуацію. Ви прокинулись у неділю вранці, зайшли на кухню і на холодильнику побачили записку від мами: "Ти вже дорослий та розумний, тому можеш про себе подбати сам. Суп у холодильнику. Приготуй до сніданку грінки. Для цього:

за допомогою міксеру збий два яйця;

наріж батон;

обмочи його у кетчупі;

намаж шматочки батону фаршем;

обмочи їх у збитих яйцях;

обжар шматки з двох сторін;

зверху намаж грінки часниковим майонезом".

Що вам нагадує ця послідовність дій?

Це є чіткий алгоритм приготування грінок.

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

Кожен із нас використовує сотні різних алгоритмів. Спробуйте згадати деякі з них (алгоритми виконання арифметичних дій під час розв'язування задач; прибирання квартири; миття посуду; приготування їжі тощо).

Існують різні задачі, з якими людина стикається щодня. Для багатьох задач існують визначені певні вказівки чи команди, які пояснюють, як потрібно виконувати розв’язок даної задачі. Людина може вивчити ці правила, а може й сама скласти свої. Чим точніше сформульовані вказівки, тим точніше і правильніше можна буде виконати певне завдання. Тобто вміти складати алгоритми − важливе завдання не тільки під час розв’язування математичних задач, але й у повсякденному побуті. Ви зі мною згодні?

учень алгоритм графічна схема

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

ІІІ. Вивчення нового матеріалу.

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

Отже, давайте спробуємо сформулювати, що ж таке алгоритм.

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

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

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

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

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

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

Наприклад: мама доручила купити в магазині продукти. Виконавцем цього алгоритму може бути хтось із родини: батько, син, бабуся, донька. Ясно, що для тата достатньо сказати, які купити продукти, а далі деталізувати алгоритм не потрібно. Сину-підлітку необхідно детальніше пояснити в яких магазинах можна придбати потрібний товар, що можна купити замість відсутнього товару і таке інше. Маленькій доньці необхідно алгоритм деталізувати ще більше: де взяти сумку, щоб принести товар, яку решту грошей необхідно принести з магазину, як дійти до магазину і як там себе слід поводити.

2. Визначеність (однозначність). Зрозумілий алгоритм не повинен містити вказівок, зміст яких може сприйматися неоднозначно. Наприклад, "почисти картоплю", "посоли за смаком", "прибери в кімнаті" тощо є неоднозначними, тому що в різних випадках можуть призвести до різних результатів. Окрім того, в алгоритмах неприпустимі такі ситуації, коли після виконання чергового розпорядження алгоритму виконавцю не ясно, що потрібно робити потім. Наприклад, вас послали за якимось товаром у магазин, та ще й попередили: "без хліба (цукру тощо) не повертайся". А що робити, коли цей товар відсутній?

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

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

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

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

4) Способи подання алгоритмів.

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

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

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

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

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

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

4. Базові алгоритмічні структури.

Як вже говорилося, алгоритми можуть подаватися за допомогою спеціальних блок-схем. Основні з цих блоків такі (рис.1):

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

блок введення та виведення

- командний блок

блок умовного переходу (розгалуження)

Рис.1. Блоки алгоритмів

Рис.2. Лінійна базова структура алгоритму

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

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

Рис. 3. Відповідно повна та неповна форми розгалуженої структури алгоритму

Умовою називається таке речення, на яке можна дати відповідь "так" чи "ні". Як правило, кажуть, що в першому випадку (коли ми відповіли на речення "так") умова є істинною, а в другому - хибною.

Виходячи з цього, речення "Якого кольору твій піджак?" не можна вважати умовою, а речення "Твоє волосся русяве?" - можна.

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

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

Крім того, в циклах з умовою теж можна виділити два різних випадки (рис.4):

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

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

Рис. 4. Відповідно цикл з передумовою та цикл з післяумовою

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

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

ІV. Первинне осмислення та закріплення вивченого навчального матеріалу.

Спробуй за малюнками скласти алгоритми дій (рис.5,6).

Рис.5. Режим дня

Рис.6. Ханойська вежа

V. Підсумки уроку та домашнє завдання.

1. Запишіть алгоритми розв’язання таких завдань: приготувати чай; зателефонувати на певний номер мобільного телефону; прибрати в кімнаті.

Рис.7. Канал, яким проходять пароплави

2. На малюнку зображено вузький канал, яким можуть проходити пароплави тільки в одному напрямі (рис.7). Але дві трійки пароплавів в даний момент пливуть назустріч один одному. Складіть алгоритм, що дозволить їм якнайшвидше розійтися. Пароплави можуть рухатися не тільки вперед, а й назад, та користуватися спеціальним розгалуженням, у якому може перебувати одночасно тільки один пароплав.

Використана література

1. Володіна І.Л., Володін В.В., Дорошенко Ю.О. Основи інформатики.7 клас: експериментальний посібник. − Харків: Гімназія, 2007. − 384 с.

2. Інформатика. Програми для загальноосвітніх навчальних закладів. - Запоріжжя: Прем'єр, 2003. - 304 с.

3. Караванова Т.П.: Основи алгоритмізації та програмування: 750 задач з рек. та прикл.: Посіб. - К.: Форум, 2002. - 287 с.: іл. - Бібліогр.: с.281.

4. Лисенко Т.І.: Основи програмування на мові С++ в середовищі Borland C++ версії 3.1: Кременчук: Кременч. педуч. ім.А.С. Макаренка, 2001. - 50 с.

5. Скляр І.В.: Я готуюсь до уроку інформатики. Алгоритмізація та програмування. Конспекти уроків. - К.: Ред. загальнопед. газ., 2004. - 128 с. - (Бібліотека "Шкільний світ").

6. Федько В.В., Плоткін В.І.: Основи алгоритмізації та програмування.11 клас. - Харків: Веста: Видавництво "Ранок", 2003. - 192 с. - (Інформатика в школі).