Тема уроку: Алгоритми. Властивості алгоритмів. Побудова алгоритмів.

Урок з інформатики
11 клас

Тема «Алгоритми. Властивості алгоритмів. Побудова алгоритмів.»

Тема. Алгоритми. Властивості алгоритмів.

„Алгоритм не розкіш, а засіб досягнення мети”

Епіграф до уроку:

Коль кругом все будет мирно,

Так сидеть он будет смирно;

Но лишь чуть со стороны

Ожидать тебе войны,

Иль набега силы бранной,

Иль другой беды незваной,

Вмиг тогда мой петушок

Приподымет гребешок,

Закричит и встрепенется

И в то место обернется.

А.С.Пушкин

Мета.

Навчальна:

• дати поняття про алгоритм, його властивості;

• навчити розпізнавати алгоритми навколо себе;

• вміти розрізняти правильно та неправильно сформульовані алгоритми;

• формувати цілісну уяву про картину всесвіту;

• формувати науковий світогляд;

• синтезувати знання, отримані при вивченні різних шкільних предметів.

Розвивальна:

• розвивати логічне мислення, пізнавальний інтерес;

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

Виховна:

• виховувати прагнення до отримання нових знань;

• узагальнювати знання з різних областей життя;

• виховувати почуття товариськості, взаємовиручки;

• виховувати комунікативні якості, вміння слухати;

• виховувати критичне відношення до загальноприйнятих істин;

• виховувати культуру між особистісних взаємовідносин, акуратність в роботі.

Задачі:

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

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

• Показати значення інформатики для інших наук.

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

Хід уроку.

І. Вступна бесіда.

Багато хто вважає, що інформатика потрібна тільки для того, щоб навчитися працювати на комп’ютерах. Але цю помилкову думку ми постараємося спростувати на нашому уроці.

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

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

Саме слово алгоритм походить від algorithmi – латинської форми написання імені великого математика ІХ ст. аль-Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмами і розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами. В подальшому це поняття стали використовувати взагалі для позначення послідовності дій, які приводять до розв’язання задачі.
Алгоритмом називають зрозуміле і точне розпорядження виконавцю про виконання послідовності дій, спрямованих на досягнення зазначеної мети чи на вирішення поставленої задачі.

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

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

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

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

Отже, сформулюємо основні властивості алгоритму.

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

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

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

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

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

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

6. Ефективність - кожний крок алгоритму повинен бути виконаний точно за скінчений проміжок часу.

Примітка: У процесі та по закінченні викладання матеріалу дітям пропонується навести приклади інструкцій, що не відповідають визначенню алгоритму чи не володіють властивостями алгоритму.

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

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

Результати - це величини, значення яких одержуються внаслідок виконання алгоритму.

При складанні багатьох алгоритмів виникає необхідність окрім аргументів та результатів використовувати ще додаткові величини. Введення в алгоритм таких величин залежить від самого автора алгоритму.

Проміжні величини — це величини, які додатково вводяться в ході розробки алгоритму.

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

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

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

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

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

Приклади алгоритмів

1. Знайти найбільший спільний дільник двох натуральних чисел m і n (алгоритм Евкліда). Складемо алгоритм розв’язання цієї задачі, який базується на тій властивості, що якщо mn, то найбільший спільний дільник чисел m,n такий самий, як і чисел m-n, n.

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

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

2. визначити більше із чисел;

3. замінити більше число різницею більшого і меншого чисел;

4. почати алгоритм спочатку.

1. Алгоритм «відгадування» задуманого числа. Нехай хто-небудь задумає довільне натуральне число. Йому пропонується провести з цим числом слідуючі дії і потім повідомити результат:

1. помножити задумане число на 5;

2. додати 8;

3. суму помножити на 2.

Необхідно за результатом «відгадати» задумане число.

Розв’язання даної задачі зводиться до розв’язання рівняння (х∙5+8)∙2=a, де х – невідоме задумане число, а – отриманий результат.

«Відгадування» х можна доручити виконавцю, зовсім незнайомому із змістом задачі. Для цього достатньо повідомити йому слідуючий алгоритм:

1. відняти від результата 16;

2. в отриманій різниці відкинути крайню праву цифру, отримане число і буде шуканим.

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

IV. Підсумок уроку.

Домашнє завдання:

• прочитати сторінки запропонованого підручника;

• вивчити означення, що прочитані на лекції (що таке алгоритм, властивості алгоритму, способи подачі алгоритму);

• придумати будь-який алгоритм на побутову тему (кулінарний, прибирання кімнати, виконання уроків тощо);

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

• записати алгоритм знаходження середини відрізка за допомогою циркуля лінійки.

• скільки разів буде виконуватися крок 3 алгоритму Евкліда для m=100, n=18?

Самоаналізу уроку

Клас: _11_____________

Тема уроку: Алгоритми. Властивості алгоритмів. Побудова алгоритмів.

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

1. На тему «Алгоритми» відводиться 12 годин, цей урок 1. Цей урок є базовим для вивчення подальшого матеріалу з теми.

2. У даному класі 14 учнів, які мають навчальні досягнення здебільшого достатнього та середнього рівнів, учні вміють працювати індивідуально та в парах.

3. Мета:

Навчальна:

• дати поняття про алгоритм, його властивості;

• навчити розпізнавати алгоритми навколо себе;

• вміти розрізняти правильно та неправильно сформульовані алгоритми;

• формувати цілісну уяву про картину всесвіту;

• формувати науковий світогляд;

• синтезувати знання, отримані при вивченні різних шкільних предметів.

Розвивальна:

• розвивати логічне мислення, пізнавальний інтерес;

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

Виховна:

• виховувати прагнення до отримання нових знань;

• узагальнювати знання з різних областей життя;

• виховувати почуття товариськості, взаємовиручки;

• виховувати комунікативні якості, вміння слухати;

• виховувати критичне відношення до загальноприйнятих істин;

• виховувати культуру між особистісних взаємовідносин, акуратність в роботі.

Мета досягнута в повному обсязі.

4. Зміст, форми і методи навчання підібрані відповідно до мети уроку. Головний етап уроку – пояснення нового матеріалу. Були застосовані такі види робіт: до пояснення нового матеріалу учні було послідовно підведено за допомогою бесіди. На уроці було використано наочність. Учні виконали практичні завдання для закріплення нового матеріалу

5. Час, відведений на всі етапи уроку було розподілено раціонально. За допомогою бесід було встановлено логічні "зв'язки" між цими етапами.

6. На уроці панувала доброзичлива робоча атмосфера.

7. Вдалося реалізувати всі поставлені завдання уроку. Урок пройшов цікаво. Діти з захопленням працювали.

7