Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів
Скачати 115.28 Kb.
|
| Дата: Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів. Мета: Тип уроку: засвоєння нових знань. Хід уроку
Поняття алгоритму Алгоритмом називається скінчена послідовність вказівок, виконання яких призводить до досягнення поставленої мети. У далекому ІХ-му столітті жив та працював відомий середньоазіатський мудрець, вчений, філософ, математик Мухаммед ал-Хорезмі. У своїх наукових трактатах він детально пояснив правила виконання арифметичних дій. При перекладі цих наукових робіт на латину вперше з'явився термін "алгоритм» (ал-Хорезмі-Аогійіті) і використовувався він спершу для визначення правил обчислень у десятковій позиційній системі числення. Сучасне поняття слова «алгоритм» більш широке. Воно для багатьох співзвучне зі словами метод, спосіб, процедура, програма. Можна сказати, що алгоритм - це чітко сформульована інструкція, а інструкції зустрічаються практично у всіх сферах нашого життя. Алгоритм є фундаментальним поняттям інформатики. Науковці виділяють три основних класи алгоритмів: обчислювальні, інформаційні та керуючі. Обчислювальні алгоритми - це такі, в ході виконання яких проводяться обчислення. Обчислювальні алгоритми працюють з числами або з їх наборами - векторами, матрицями, множинами. Інформаційні алгоритми працюють з великими об'ємами інформації. Як приклад можна навести алгоритм пошуку необхідної числової або символьної інформації, що відповідає певним ознакам. Ефективність роботи цих алгоритмів залежить від організації даних, прикладом чого можуть бути відомі сьогодні всім бази даних. Керуючі алгоритми характерні тим, що дані до них надходять від зовнішніх процесів, якими вони керують. Результатами роботи цих алгоритмів є вироблення своєчасного необхідного керуючого сигналу як реакції на швидку зміну вхідних даних. Саме тому значення даних у ході виконання керуючих алгоритмів змінюються, подекуди навіть досить швидко, і алгоритм повинен своєчасно правильно прореагувати на це, тобто видати потрібний керуючий сигнал у потрібний момент часу. У 30-х роках XX століття виникла теорія алгоритмів. До цього часу поняття алгоритму зводилось до набору елементарних кроків: арифметичних дій, перевірки рівностей, нерівностей та інших відношень такого типу. Але на початку XX століття об'єкти, з якими оперували алгоритми, почали ускладнюватися, з'явилась необхідність виконувати операції над векторами, таблицями, множинами тощо. Постали питання щодо трактування поняття елементарності кроків, тлумачення однозначності алгоритму, виникла думка, що не для всяких математичних задач можна знайти алгоритм розв'язання за кінцевий проміжок часу. Теорія алгоритмів досліджує питання побудови конкретних алгоритмічних моделей, кожна з яких містить конкретний набір елементарних кроків, способів визначення наступного кроку. Завданням теорії алгоритмів є також дослідження питання про існування чи не існування ефективних алгоритмів розв'язання окремих задач. Найбільшу цінність представляють моделі, які одночасно були б і універсальними, і простими. Бурхливий розвиток обчислювальної техніки, використання її в дослідженнях багатьох наук привів до створення великої кількості різноманітних алгоритмів в різних прикладних галузях. Зрозуміло, що всякому алгоритму відповідає задача, яку він призначений розв'язувати, але разом з тим може існувати не один алгоритм, що розв'язує дану задачу. Такі алгоритми називаються еквівалентними, і, зрозуміло, постає питання вивчення ефективності цих алгоритмів. Дослідники цих питань створили новий розділ теорії алгоритмів - теорію складності алгоритмів. Складність алгоритму - це кількісна характеристика. Вона визначається часом, за який виконується алгоритм (часова складність), та об'ємом пам'яті комп'ютера, необхідного для його виконання (ємкісна складність). Тому про складність алгоритму логічно вести мову стосовно саме машинних алгоритмічних моделей. Оскільки подолання обмежень на пам'ять комп'ютера - технічна проблема, що вирішується на рівні його вдосконалення майже що півроку, то часова складність алгоритму, яка в більшій мірі залежить від обраної алгоритмічної моделі, методу реалізації задачі - творча, евристична проблема. На практиці користувачів більше цікавлять не самі алгоритми, а задачі, які можна розв'язувати за їх допомогою. А оскільки для розв'язування задачі існують різні алгоритми, тому природно серед всіх визначити той, який має найменшу складність. Саме такі питання в межах даного посібника будуть цікавити нас найбільше:
Приклади алгоритмів Як зазначалося вище, виникнення поняття алгоритмів пов'язане з математикою. І саме у шкільному курсі математики ви часто зустрічалися з алгоритмами. На уроках з арифметики вивчалися алгоритми покрокового додавання, множення, ділення, добування квадратного кореня, пізніше на уроках з математики вас знайомили з правилами побудови бісектриси кута, ділення відрізка навпіл та на задану кількість рівних частин за допомогою олівця, циркуля та лінійки. Не обійшлося без правил та законів у таких науках, як фізика та хімія. Наприклад, вам відомі алгоритми проведення фізичних та хімічних експериментів, дослідження різних явищ. На уроках з гуманітарних предметів ви вивчали безліч різних правил правопису. З алгоритмами ви зустрічаєтеся і у повсякденному житті. Наприклад, у розпорядку робочого дня учня день від дня мало чим відрізняється: прокинутися вранці, вмитися, вдягнутися, поснідати, піти до школи, відвідати уроки, повернутися додому, пообідати, зробити домашнє завдання, відпочити до вечора, повечеряти, лягти спати. І так щодня. В техніці добре відомі алгоритми обробки деталей, в побуті - складання меблів, користування електричними приладами тощо. Отже, мало того, що ми живемо у суцільному інформаційному просторі, та ще й виявляється навколо нас багато алгоритмів, які усе життя нам доводиться виконувати! Властивості алгоритму Визначивши основне поняття алгоритму, можна зробити висновок, що будь-який алгоритм є послідовністю деяких вказівок. Але не кожна така послідовність може називатися алгоритмом. Отже, сформулюємо основні властивості алгоритму. ^ Виконання команд алгоритму повинно бути послідовним, з точною фіксацією моментів завершення виконання однієї команди і початку виконання наступної. ^ В математиці існують обчислювальні процедури, які мають алгоритмічний характер, але не володіють властивістю скінченності. Прикладом такої процедури може бути обчислення значення числа п. Така процедура описує нескінченний процес і ніколи не завершиться. Але якщо обмежитися певною кількістю знаків після коми, то ми отримаємо алгоритм обчислення числа л з заданою точністю. ^ Тобто алгоритм розрахований на механічне виконання. Якщо один і той самий алгоритм доручити для виконання різним виконавцям, то вони повинні дійти одного і того ж результату. ^ Якщо виконавець є некомпетентною людиною в питаннях, що вирішуються даним алгоритмом, то необхідно вибрати доступнішу для його формулювання форму, якою є словесний спосіб. Наприклад, якщо алгоритм передбачає обчислення коренів деякого квадратного рівняння, то для учня початкових класів необхідно самим детальним чином описати всі виконувані дії на рівні, що відповідає його знанням математики: додавання, відніманні, множення, ділення, добування квадратного кореня за допомогою калькулятора тощо. Для учня старших класів цей алгоритм буде містити математичну формулу для обчислення коренів рівняння та аналіз їх існування та відсутності. Якщо ж виконання алгоритму буде запропоновано комп'ютеру, то алгоритм потрібно зобразити насамкінець відповідною машинною мовою. ^ Цим самим забезпечується його використання для розв'язування цілого класу однотипних задач. ^ Способи запису алгоритмів Ми познайомилися з поняттям алгоритму. Тепер нам необхідно домовитися, яким чином ми будемо його записувати. Існує чотири способи запису алгоритмів, вибір яких залежить від того, хто його складає або на кого він орієнтований:
Словесний спосіб запису алгоритмів орієнтований на людину-виконавця. Мабуть, поки що важко уявити собі інший спосіб запису. Це найбільш проста і доступна форма представлення алгоритму. Словесна форма зазвичай використовується для алгоритмів, орієнтованих на виконавця - людину і цей спосіб є найбільш доступним будь-кому незалежно від його спеціальної підготовки. Повертаючись до історії трансформації поняття алгоритм, слід зазначити, що ще до 1950 року під цим словом частіше за все розуміли викладений в «Елементах» Евкліда алгоритм Евкліда - процес знаходження найбільшого спільного дільника (НСД) двох натуральних чисел. Тому буде корисно навести для прикладу опис цього алгоритму. Взяти два натуральних числа. Якщо вони рівні, то перше з них і є найбільшим спільним дільником, якщо ж ні, то перейти до пункту 2. Порівняти два числа і вибрати більше з них. Більше з двох чисел замінити різницею більшого і меншого. Перейти до пункту 1. Зверніть увагу, що у першому пункті конкретно сказано, яке саме число необхідно вибрати у випадку співпадання двох чисел. Саме це і є характерною рисою алгоритму, виконавцем якого може бути навіть не підготовлена в даній галузі людина. Наведений алгоритм застосуємо до конкретної пари чисел. Нехай задані два числа: 45 та 12. Продемонструємо процес знаходження НСД за наведеним алгоритмом у вигляді таблички, де на кожному кроці більше число, від якого віднімається друге (менше) число, виділятимемо жирним шрифтом. 45 12 9 З 33 12 6 З 21 12 3 3 9 12 Отже, за сім кроків ми одержали результат: НСД(45,12)=3. Перевірка роботи алгоритму є суттєвим кроком на шляху до його розуміння. Надалі слід домовитися, що кожний алгоритм, наведений в посібнику, повинен бути розібраний по кроках. Це найпростіший і найефективніший спосіб розуміння будь-якого алгоритму. ^ Цей спосіб вже вимагає деяких знань. Вони полягають у знайомстві зі спеціальними стандартами графічних зображень блоків, в середину яких поміщаються команди алгоритму. Наведемо таблицю деяких з цих блоків. При створенні схеми алгоритму блоки із записаними в них командами з'єднуються між собою стрілками, які визначають черговість виконання дій алгоритму. Для запису команд всередині блоків використовується природна мова з елементами математичної символіки. В результаті перевірки умови під час вибору напрямку виконання алгоритму виникають два можливі шляхи для його продовження. Ці шляхи зображуються стрілками з позначеннями «так» (+) та «ні» (-). Перехід по стрілці з позначенням «так» відбувається у випадку, коли умова виконується, а перехід по стрілці з позначенням «ні» - у протилежному випадку. Блоки початку і кінця алгоритму використовуються при записові повного алгоритму задачі. Ми ж надалі вважатимемо, що алгоритми, які розглядаються в посібнику як базові, можуть бути самі використані в інших алгоритмах як їх фрагменти. Тому блоки початку і кінця алгоритму в таких випадках нами використовуватись не будуть. Для запису алгоритмів, з якими ми матимемо справу, даної інформації цілком достатньо. Зобразимо у визначених позначеннях алгоритм Евкліда. Погодьтеся, що наочність схематичного представлення алгоритму має свої переваги! Однак ця наочність швидко втрачається, коли зображується великий алгоритм. В таких випадках в схемі алгоритму виділяються і відокремлюються її окремі частини - модулі, основною умовою яких є один вхід і один вихід. Згодом вони включаються у схему алгоритму як окремі блоки. Такий підхід до складання алгоритму відображає ідею структурного програмування, про яке ще не один раз буде далі йти мова. ^ У мові псевдокодів прийняті певні синтаксичні правила для запису команд, що полегшує запис алгоритму на стадії його проектування і дає можливість використання більш широкого набору команд, розрахованого на абстрактного виконавця. Наприклад, у мові псевдокодів використовуються спеціальні службові слова та правила запису для вибору напрямку подальшого виконання алгоритму в залежності від виконання чи невиконання сформульованої умови ЯКЩО...ТО...ІНАКШЕ, повторення визначеної групи дій певну кількість разів ^ тощо. Разом з тим мова псевдокодів дозволяє використовувати дещо довільну форму представлення математичних записів, умов тощо. Розглянемо як приклад алгоритм Евкліда: У наведеному алгоритмі зовсім неважко розібратися. Мова псевдокодів максимально наближена до звичайної розмовної мови. Усі службові слова, що використовуються для запису алгоритму, виділені жирним шрифтом, їх необхідно записувати тільки таким чином, як це передбачено правилами мови. Окремі блоки алгоритму виділені вертикальними лініями і означають певні дії. Внутрішній блок визначає вибір тієї чи іншої дії в залежності від відношення між значеннями величин п та т. Середній блок визначає дію повторення внутрішніх дій до того часу, поки значення величин п та т не стануть рівними. Зовнішній блок визначає повністю весь алгоритм, в якому передбачені також дії введення та виведення відповідно вхідної та результуючої інформації. Як видно із наведених прикладів мову псевдокодів можна вважати проміжною між природною і формальною мовою. Для запису алгоритмів мовою псевдокодів необхідно знати всі службові слова цієї мови та правила запису деяких дій алгоритму. ^ На практиці частіше за все виконавцями алгоритмів є комп'ютери. Тому алгоритми, призначені для виконання на комп'ютерах, повинні бути записані мовами, зрозумілими їм. Надалі ми познайомимося з можливостями мови програмування Паскаль, тому розглянемо запис алгоритму пошуку найбільшого спільного дільника двох натуральних чисел саме цією мовою, Ви звернули увагу на подібність запису алгоритму мовою псевдокодів та мовою програмування Паскаль? Це дійсно так, але для запису алгоритму на Паскалі потрібно орієнтуватися в англійській мові та вміти використовувати усі можливості цього потужного засобу програмування. |
Схожі:
 | Практична робота №1 Способи представлення алгоритмів. Базові алгоритмічні структури. Типи алгоритмів в-1 Назвіть всі базові структури алгоритмів і дайте їм означення | | Т. Основні поняття алгоритмізації (4 год.) Базові алгоритмічні структури. Типи алгоритмів. Виконавець та система команд виконавця |
| Т. 1 Комп’ютерне моделювання. Основи алгоритмізації (6 год.) Базові структури алгоритмів: слідування, розгалуження, повторення. Графічні схеми базових структур алгоритмів | | Інформації в базі даних. Внесення змін до інформації в базі даних. Поняття про мову програмування. Алфавіт мови. Основні поняття мови: ідентифікатори, числа, рядки, описи. Основні вказівки та їх опис Базові структури алгоритмів. Основна властивість базових структур. Структурний підхід до конструювання алгоритмів |
| Тема: Поняття програмування та алгоритм. Властивості алгоритмів Програмування — процес створення комп'ютерних програм або програмного забезпечення. Програмування поєднує в собі елементи інженерії... | | Тема: Базові алгоритмічні структури, типи алгоритмів. Виконавець та система команд виконавця Після ознайомлення з різними формами запису алгоритмів зможемо розпізнати різні за типами команди, а відповідно і алгоритми, які... |
| Програма для запису алгоритмів; б спеціально створена мова для запису алгоритмів; в мова програмування Мова, призначена для запису алгоритмів розв’язування задач І вхідних даних для еом, – це | | 1. Побудова і аналіз алгоритмів Формалізація алгоритмів Процес створення комп’ютерної програми для вирішення будь-якої практичної задачі складається з декількох етапів |
| Урок №3. За темою „Табличні величини Тема: Алгоритм пошуку в таблицях елементів з деякою властивістю Мета уроку: формування навичок розробки алгоритмів пошуку в таблицях елементів за деякими властивостями; виховання інформаційної... | | Програма для запису алгоритмів; б спеціально створена мова для запису алгоритмів; в мова програмування В завданнях 1-11 підкресліть правильну відповідь. Розв’язки задач вставте після задачі |