Основи алгоритмізації та програмування Заняття 3. Поняття алгоритму

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

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

Exit Класи алгоритмів Науковці виділяють три основних класи алгоритмів: обчислювальні, інформаційні управляючі

Exit Обчислювальні алгоритми Обчислювальні алгоритми - це такі, які працюють з порівняно простими видами даних, наприклад, числами, векторами, матрицями.

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

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

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

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

Exit Еквівалентні алгоритми Зрозуміло, що всякому алгоритму відповідає задача, яку він призначений розв'язувати, але разом з тим може існувати не один алгоритм, що розв'язує дану задачу. Такі алгоритми називаються еквівалентними, і, зрозуміло, постає питання вивчення ефективності цих алгоритмів. Дослідники цих питань створили новий розділ теорії алгоритмів - теорію складності алгоритмів.

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

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

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

Exit Алгоритми у повсякденному житті З алгоритмами ви зустрічаєтеся і у повсякденному житті. Хіба ж частіше за все не доводиться нам виконувати послідовність одних і тих самих дій? Наприклад, у розпорядку робочого дня учня день від дня мало чим відрізняється: прокинутися вранці, вмитися, вдягнутися, поснідати, піти до школи, відвідати уроки, повернутися додому, пообідати, зробити домашнє завдання, відпочити до вечора, повечеряти, лягти спати. І так щодня. В техніці добре відомі алгоритми обробки деталей, в побуті - складання меблів, користування електричними приладами тощо. Отже, мало того, що ми живемо у суцільному інформаційному просторі, та ще й виявляється навколо нас багато алгоритмів, які усе життя нам доводиться виконувати!

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

Exit Основні властивості алгоритму Основними властивостями алгоритмів є: дискретність скінченність визначеність зрозумілість масовість результативність ефективність Отже, сформулюємо основні властивості алгоритму.

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

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

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

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

Exit Масовість Масовість - в алгоритмі повинна бути передбачена можливість виконання його для різних початкових значень. Цим самим забезпечується його використання для розв'язування цілого класу однотипних задач.

Exit Результативність Результативність - алгоритм повинен забезпечувати обов'язкове отримання результату після кінцевої кількості кроків.

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

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

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

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

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

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

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

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

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

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

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

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

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

Exit Питання для самоконтролю 1. Що ми називаємо алгоритмом? Як виник термін «алгоритм»? 2. Наведіть власний приклад алгоритму. 3. Назвіть основні властивості алгоритмів. 4. Що означає «дискретність алгоритму»? Наведіть приклад. 5. Що означає «скінченість алгоритму»? Наведіть приклад. 6. Що означає «визначеність алгоритму»? Наведіть приклад. 7. Що означає «зрозумілість алгоритму»?Наведіть приклад. 8. Що означає «масовість алгоритму»? Наведіть приклад. 9. Що означає «результативність алгоритму»? Наведіть приклад. 10. Що означає «ефективність алгоритму»? Наведіть приклад. 11. Що розуміється під формальним виконанням алгоритму? 12. Що ми називаємо аргументами алгоритму? 13. Що розуміється під результатами алгоритму? 14. Коли виникає необхідність введення проміжних даних?