Тип заняття: Самостійне вивчення
Мета заняття:
  • · познайомити з поняттям алгоритма, його властивостями;
  • · виховувати прагнення до отримання нових знань; узагальнювати знання з різних областей життя; виховувати критичне відношення до загальноприйнятих істин
  • · розвивати логічне мислення, пізнавальний інтерес; формувати вміння аналізувати, узагальнювати, порівнювати, абстрагуватися, синтезувати знання, отримані при вивченні різних предметів
Знати: навчитись розпізнавати алгоритми навколо себе; розрізняти правильно та неправильно сформульовані алгоритми дій
Література Б.Пахомов. MS Visual C++ для начинающих. С.Пб.: БХВ-Петербург. 2009. ст. 100-110, Пауэрс Л., Снелл М. Microsoft Visual Studio 2008 С.Пб.: БХВ-Петербург. 2009. ст. 77-79, http://uk.wikipedia.org/wiki/Алгоритм

 

 

Короткі теоретичні відомості.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Першій спосіб — це словесний опис алгоритму.

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

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

Четвертий спосіб — алгоритмічні мови (псевдокоди). Ці мови мають жорстко визначений синтаксис і вже максимально наближені до машинної мови (мови програмування).

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

 

Приклад алгоритму

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

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

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

 

Питання для самостійної перевірки знань:

  1. Що таке алгоритм?
  2. Які ви знаєте властивості алгоритмів?
  3. Що таке аргумент?
  4. Що таке результат виконання алгоритму?
  5. Для чого використовуються проміжні величини?
  6. Які ви знаєте методи запису алгоритмів?
About these ads