Урок 3. Поняття алгоритму. Властивості алгоритмів. Форми подання алгоритму

Урок 2. Практична робота №1 «Побудова інформаційної моделі»
Вересень 3, 2016
Урок 4. Базові структури алгоритмів
Вересень 4, 2016

Урок 3 (web-версія конспекту без зображень)

Тема: Поняття алгоритму. Властивості алгоритмів. Форми подання алгоритму. Виконавець алгоритму

Мета :

  • навчальна: ввести поняття алгоритму; властивості алгоритмів; способи представлення алгоритмів; виконавець та система команд виконавця; формальне виконання алгоритму; аргументи, результати, проміжні величини Домогтися засвоєння основних понять алгоритмізації, властивості алгоритмів, способи представлення алгоритмів;
  • розвиваюча: розвивати логічне мислення; формувати вміння діяти за інструкцією, планувати свою діяльність, аналізувати i робити висновки;
  • виховна:  виховувати інформаційну культуру учнів, уважність, акуратність, дисциплінованість

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

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

(конспект уроку та презентація розроблені на основі матеріалу підручника «Інформатика (Ривкінд, Лисенко, Чернікова, Шакотько) 11 клас рівень стандарту») 

ХІД УРОКУ

І. Організація класу до уроку

  1. Привітання із класом
  2. Повідомлення теми і мети уроку

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

Опитування:

  1. Назвіть етапи розв’язування задач на ПК.
  2. Що таке модель?
  3. На яких методах наукового дослідження базується моделювання?
  4. Наведіть приклади предметних моделей зовнішньої подібності. З якою метою їх створюють?
  5. Наведіть приклади функціональних моделей. З якою метою їх створюють?
  6. Наведіть приклади імітаційних моделей. З якою метою їх створюють?
  7. Наведіть приклади знакових моделей. З якою метою їх створюють?
  8. Що собою являє інформаційна модель?

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

Визначення алгоритму

Слово «алгоритм» походить від «algorith­mi» — латинської форми написання імені великого математика аль-Хорезмі, який сформулював правила виконання арифметичних дій. Тому спочатку під алгоритмом розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами в десятковій системі числення. Зараз він є одним із фундаментальних понять інформатики.

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

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

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

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

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

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

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

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

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

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

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

Саме через ці властивості часто дається визначення поняття алгоритму як скінченної однозначно визначеної послідовності операцій, формальне виконання якої приводить до розв’язання певної задачі за кінцеве число кроків.

Виконавець алгоритму

Виконавцем алгоритму може бути людина, тварина, ЕОМ, система людина-машина, верстат-автомат, робот тощо, тобто ті хто розуміє та може виконати команди алгоритму.

Точне визначення, що таке виконавець, дати дуже складно, та в цьому й немає потреби. Важливо зрозуміти основні харак­теристики виконавця: середовище, елементарні дії, систему команд, відмови. Середовище - це місце перебування виконав­ця. Кожен виконавець може виконувати команди лише з дея­кого строго заданого списку - системи команд виконавця. Для кожної команди повинні бути задані умови застосування, тоб­то в яких станах середовища може бути виконана команда, й описані результати її виконання.

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

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

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

Формальне виконання алгоритму

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

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

Способи представлення алгоритму

  1. Словесні.
  2. Словесно-формульні.
  3. Графічні.
  4. Скінчений набір кодів.

При складанні алгоритмів можна поєднувати різні форми подання алгоритмів.

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

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

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

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

Аргументи, результати, проміжні величини

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

Аргумент - це величина, значення якої необхідно задати для виконання алгоритму.

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

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

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

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

Ми вже достатньо наочно уявили собі алгоритм. Але як він виглядає з погляду звичайного користувача цього алгоритму? Найчастіше користувач не знає, яким чином цей алгоритм запи­саний, за допомогою яких команд, які методи були застосовані для його реалізації, якою мовою програмування. У даному ви­падку йдеться про виконання алгоритму на комп'ютері у вигля­ді готової програми. Виконавець алгоритму бачить лише його зовнішню сторону: які початкові дані необхідно задати і в якому вигляді отримується результат. Кожний, мабуть, може пригада­ти номер фокусника, коли той у чорну скриньку закладає одні предмети, а витягує зовсім інші. Від глядачів прихований вміст цієї чорної скриньки, і залишається таємницею, яким чином у ній відбувається «перетворення» предметів. Саме такою «чор­ною скринькою» для користувача і є програма, якою він корис­тується на комп'ютері. Це можна зобразити у такому вигляді

IV. Формування практичних умінь і навичок

Завдання 1.   Працюємо з підручником

Увага! Під час роботи з комп’ютером дотримуйтеся правил безпеки та санітарно-гігієнічних норм.  (Інструктаж з правил техніки безпеки)

Завдання № 1, 3, 5, 7, 10, 12  на с. 15-16  підручника

Додаткові матеріали для уроку розміщені в папці D:/11 клас/Тема 1

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

Обговорюємо

  1. Що таке алгоритм? З чого він складається?
  2. Що таке система команд виконавця?
  3. Наведіть приклади речень, які є командами,і приклади речень, які не є командами?
  4. Назвіть властивості алгоритму.

Рефлексія

  • Що нового сьогодні дізналися?
  • Чого навчилися?
  • Що сподобалось на уроці, а що ні?
  • Чи виникали труднощі?

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

Опрацювати параграф підручника п.1.2

Завантажити конспект