Поняття алгоритму, властивості алгоритмів. Форми подання алгоритмів. Графічне подання алгоритмів




Дата конвертації26.11.2018
Розмір0,51 Mb.
УРОК11.

ТЕМА: Поняття алгоритму, властивості алгоритмів. Форми подання алгоритмів. Графічне подання алгоритмів.


Тема: Поняття алгоритму, властивості алгоритмів. Форми подання алгоритмів. Графічне подання алгоритмів.

Мета: Актуалізувати знання учнів про моделі та типи моделей, моделювання як метод дослідження об’єктів. Ввести поняття алгоритму, описати основні властивості алгоритмів, форми подання алгоритмів.

Тип уроку: Комбінований урок.
План уроку:

Актуалізація опорних знань учнів.

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


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

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

  3. Форми подання алгоритмів.

Практичні завдання.

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


Актуалізація опорних знань учнів:

  1. Що таке модель? Наведіть приклади моделей.

  2. Поясніть, у чому полягає процес моделювання.

  3. Чим модель об’єкта відрізняється від реального об’єкта?

  4. Як класифікують моделі за способом представлення? Охарактеризуйте їх.

  5. Як класифікують інформаційні моделі? Опишіть різні види інформаційних моделей.

  6. Як класифікують моделі за галузями використання? Наведіть приклади.

  7. Як класифікують моделі за фактором часу? Наведіть приклади.

  8. Що таке комп’ютерне моделювання?


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

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

Термін «алгоритм» походить від назви середньоазіатського міста Хорезм. У цьому місті в IX ст. жив математик і астроном Мухамед, який сформулював правила чотирьох арифметичних дій. Арабський варіант його імені Аль-Хорезмі, що в Європі записувався латиною як Algorithmi, і став основою терміна "алгоритм". Однак пізніше під словом алгоритм стали розуміти правила знаходження найбільшого спільного дільника, які були викладені ще в працях великого давньогрецького математика Евкліда (III ст. до н.е.). За наших часів поняття алгоритму було узагальнено, і словом "алгоритм" стали позначати опис будь-якої послідовності дій. Поняття алгоритму є одним із фундаментальних у сучасній математиці й інформатиці.

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

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

До слова «алгоритм» близькі за значенням слова: спосіб, рецепт. Однак алгоритми в інформатиці – це не тільки рецепти розв'язання задач. Алгоритми розробляються, насамперед, із метою автоматизації дій виконавця.

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

Розглянемо як приклад алгоритм Евкліда, вигаданий ним для знаходження найбільшого спільного дільника (НСД) двох натуральних чисел т і п. Відомо, що НСД може бути отриманий шляхом послідовного ділення спочатку більшого числа на менше, потім меншого числа на отриманий залишок, першого залишку на другий залишок і т.д. Ділення триває доти, доки у залишку не утвориться нуль. Останній дільник і є НСД. Наведемо приклад знаходження НСД для пари чисел – 66 і 18:



66:18 = 3 +(12) 18:12 = 1 + (6) 12:6 = 2

Тут у дужках записаний залишок від ділення. В останній рівності залишок відсутній, тому НСД дорівнює дільнику, тобто 6.



Алгоритм розв'язання задачі про НСД для пари чисел т і п записується у такий спосіб:

  1. Якщо т > п, то перейти до 3., інакше перейти до 2.

  2. Якщо n > т, то перейти до 4., інакше перейти до 5.

  3. Від т відняти п і вважати цю різницю новим значенням т. Перейти до 1.

  4. Від п відняти т і вважати цю різницю новим значенням п. Перейти до 1.

  5. Вважати, що НСД дорівнює m. Кінець.

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

Алгоритми складаються з орієнтацією на певного виконавця алгоритму: дресированої тварини, людини, автомата, ЕОМ. До алгоритму мають входити команди, які виконавець може виконати, і неприпустимі команди, які він не може виконати. У кожного виконавця є свій кінцевий набір команд, які для нього зрозумілі і можуть бути виконані. Цей набір називають системою команд виконавця.
2. Властивості алгоритмів.

Властивостями алгоритму є дискретність, визначеність, виконуваність, скінченність, результативність і масовість.



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

Визначеність (або детермінованість (лат. determinans – визначальний)) алгоритму означає, що для заданого набору значень початкових (вхідних) даних алгоритм однозначно визначає порядок дій виконавця та результат цих дій. Алгоритм не повинен містити команди, які можуть сприйматися виконавцем неоднозначно, наприклад «Узяти 2–3 ложки цукру», «Трохи підігріти молоко», «Вимкнути світло через кілька хвилин», «Поділити число x на одне з двох даних чисел a або b» тощо. Крім того, в алгоритмах недопустимі ситуації, коли після виконання чергової команди виконавцю незрозуміло, яку команду він повинен виконувати наступною.

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

Зазначимо, що виконавець повинен лише вміти виконувати кожну команду зі своєї системи команд, і не важливо, розуміє він її чи ні. Говорять, що виконання алгоритмів виконавцем носить формальний характер: виконавець може не розуміти жодну з команд, може не знати мети виконання алгоритму, і все одно отримає результат. Так, наприклад, верстат з програмним керуванням не розуміє жодної з команд, які він виконує, але завдяки своїй конструкції успішно виготовляє деталі.



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

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

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

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


3. Форми подання алгоритмів.

Розглянемо алгоритми розв’язування такої задачі.



Задача. Є посудина місткістю 8 л, яка заповнена рідиною, і дві порожні посудини місткістю 5 л і 3 л. Потрібно одержати в одній з посудин 1 літр рідини і повідомити в якій.

Розглянемо виконавця, який має таку систему команд:

1. Перелити рідину з однієї посудини в іншу.

2. Наповнити одну з посудин рідиною з іншої посудини.

3. Вивести повідомлення.

Для цього виконавця алгоритм розв’язування цієї задачі буде таким:

1. Наповнити 3-літрову посудину з 8-літрової.

2. Перелити з 3-літрової посудини в 5-літрову.

3. Наповнити 3-літрову посудину з 8-літрової.

4. Наповнити 5-літрову посудину з 3-літрової.

5. Вивести повідомлення: «1 л одержано в 3-літровій посудині».

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



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

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

Наведемо деякі елементи (блоки) блок-схеми алгоритму (табл.).

Блок-схема алгоритму розв’язування задачі представлена на рисунку.



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

1. Укажіть команди серед наведених речень:

а) Закрий вікно. г) Не заважай читати.

б) Котра година? д) Якщо йде дощ, візьми парасольку.

в) 3 + 2  5. е) Я живу в Києві.



2*. Сформулюйте лінійні правила-алгоритми, які ви вивчали на уроках:

а) української мови; б) математики; в) інших предметів.

Подайте ці алгоритми у вигляді блок-схем.

3. Виконайте алгоритм:

1. Накреслити відрізок АВ завдовжки 5 см.

2. Поставити вістря циркуля в точку А.

3. Побудувати коло, радіус якого дорівнює довжині відрізка АВ.

4. Поставити вістря циркуля в точку В.

5. Побудувати коло, радіус якого дорівнює довжині відрізка АВ.

6. Провести пряму через точки перетину побудованих кіл.

Яку б назву ви дали цьому алгоритму? Які геометричні задачі можна розв’язувати за цим алгоритмом? Складіть його блок-схему.



4. Є координатна пряма з позначеними на ній цілими числами. На цій прямій мешкає виконавець Коник, який вміє переміщуватися по ній, виконуючи команди: 1) стрибни на 3 одиниці праворуч; 2) стрибни на 2 одиниці ліворуч. Початкове положення Коника – точка 0. Складіть блок-схему алгоритму, за яким Коник за найменшу кількість стрибків буде в точці: а) 24; б) 7; в) –3.

5. Човняру потрібно перевезти в човні через річку вовка, козу і капусту. У човні, крім човняра, вміщується або тільки вовк, або тільки коза, або тільки капуста. На березі не можна залишати козу з вовком або козу з капустою. Складіть алгоритм перевезення. Подайте його у словесній формі. (Ця старовинна задача вперше трапляється в математичних рукописах VIII ст.)

6. Двом солдатам потрібно переправитися з одного берега річки на інший. Вони побачили двох хлопчиків на маленькому човні. У ньому можуть переправлятися або один солдат, або один чи двоє хлопчиків. Складіть алгоритм переправлення солдатів. Подайте його у словесній формі. (Після переправлення солдатів човен повинен залишитись у хлопчиків.)

7. Придумайте виконавця. Задайте його систему команд. Сформулюйте задачу та складіть алгоритм її розв’язування для цього виконавця.

8. Складіть блок-схему алгоритму знаходження x з рівняння 2x + a = c.

Виконайте його при: а) a = 5, c = 7; б) a = –15, c = 105; в) a = 5, c = 5.


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

  1. Вивчити конспект.

  2. Опрацювати матеріал підручника на ст. 25-30. (Й.Я. Ривкінд, Т.І. Лисенко, Л.А. Чернікова, В.В. Шакотько).

  3. Складіть алгоритм приготування вашої улюбленої страви. Подайте його в словесній формі.

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

  5. Складіть блок-схему алгоритму обчислення на калькуляторі значення виразу (81 – 12)(58 + 84).


База даних захищена авторським правом ©uchika.in.ua 2016
звернутися до адміністрації

    Головна сторінка