Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів icon

Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів




Скачати 115.28 Kb.
НазваТема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів
Дата конвертації20.02.2013
Розмір115.28 Kb.
ТипДокументи


Дата:

Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів.

Мета:

Тип уроку: засвоєння нових знань.


Хід уроку

  1. Організаційний етап

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


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

Алгоритмом називається скінчена послідовність вказівок, виконання яких призводить до досягнення поставленої мети.

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

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

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

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

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

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

У 30-х роках XX століття виникла теорія алгоритмів. До цього часу поняття алгоритму зводилось до набору елементарних кроків: арифметичних дій, перевірки рівностей, нерівностей та інших відношень такого типу.

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

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

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

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

  • знайомство із засобами створення алгоритмів;

  • знайомство з алгоритмами для розв'язування типових задач;

  • порівняння алгоритмів, що розв'язують однакові задачі.

Приклади алгоритмів

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

Наприклад, вам відомі алгоритми проведення фізичних та хімічних експериментів, дослідження різних явищ. На уроках з гу­манітарних предметів ви вивчали безліч різних правил правопису.

З алгоритмами ви зустрічаєтеся і у повсякденному житті. Наприклад, у розпорядку робочого дня учня день від дня мало чим відрізняється: прокинутися вранці, вмитися, вдягнутися, поснідати, піти до школи, відвідати уроки, повернутися додому, пообідати, зробити домашнє завдання, відпочити до вечора, повечеряти, лягти спати. І так щодня.

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

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

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

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

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

^ Дискретність - будь-який алгоритм зображується у вигляді окремих вказівок.

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

^ Скінченність - виконання алгоритму завершується після завершення кінцевої кількості кроків.

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

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

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

^ Зрозумілість - формулювання дій алгоритму повинно бути орієнтоване на конкретного виконавця.

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

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

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

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

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

Способи запису алгоритмів

Ми познайомилися з поняттям алгоритму. Тепер нам необ­хідно домовитися, яким чином ми будемо його записувати.

Існує чотири способи запису алгоритмів, вибір яких залежить від того, хто його складає або на кого він орієнтований:

  • словесний спосіб запису алгоритмів;

  • запис алгоритмів за допомогою схем;

  • описування алгоритмів мовою псевдокодів;

  • запис алгоритмів мовою програмування.

Словесний спосіб запису алгоритмів орієнтований на людину-виконавця.

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

Повертаючись до історії трансформації поняття алгоритм, слід зазначити, що ще до 1950 року під цим словом частіше за все розуміли викладений в «Елементах» Евкліда алгоритм Евкліда - процес знаходження найбільшого спільного дільника (НСД) двох натуральних чисел. Тому буде корисно навести для прикладу опис цього алгоритму.

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

Порівняти два числа і вибрати більше з них.

Більше з двох чисел замінити різницею більшого і меншого.

Перейти до пункту 1.

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

Наведений алгоритм застосуємо до конкретної пари чисел.

Нехай задані два числа: 45 та 12.

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

45 12 9 З

33 12 6 З

21 12 3 3

9 12

Отже, за сім кроків ми одержали результат: НСД(45,12)=3. Перевірка роботи алгоритму є суттєвим кроком на шляху до його розуміння. Надалі слід домовитися, що кожний алгоритм, наведений в посібнику, повинен бути розібраний по кроках. Це найпрості­ший і найефективніший спосіб розуміння будь-якого алгоритму.

^ Схеми дозволяють зобразити алгоритм в наочній графічній формі.

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

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

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

Блоки початку і кінця алгоритму використовуються при записові повного алгоритму задачі. Ми ж надалі вважатимемо, що алгоритми, які розглядаються в посібнику як базові, можуть бути самі використані в інших алгоритмах як їх фрагменти. Тому блоки початку і кінця алгоритму в таких випадках нами використовува­тись не будуть. Для запису алгоритмів, з якими ми матимемо справу, даної інформації цілком достатньо. Зобразимо у визначених позначеннях алгоритм Евкліда.

Погодьтеся, що наочність схематичного представлення алго­ритму має свої переваги!

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

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

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

Наприклад, у мові псевдокодів використовуються спеціальні службові слова та правила запису для вибору напрямку подальшого виконання алгоритму в залежності від виконання чи невиконання сформульованої умови ЯКЩО...ТО...ІНАКШЕ, повторення визна­ченої групи дій певну кількість разів ^ ПОКИ... ПОЧА­ТОК...КІНЕЦЬ тощо. Разом з тим мова псевдокодів дозволяє використовувати дещо довільну форму представлення математич­них записів, умов тощо. Розглянемо як приклад алгоритм Евкліда:

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

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

^ Найбільш високий професійний рівень для запису алгоритмів визначається знанням мов програмування.

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

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

Ви звернули увагу на подібність запису алгоритму мовою псевдокодів та мовою програмування Паскаль? Це дійсно так, але для запису алгоритму на Паскалі потрібно орієнтуватися в англійській мові та вміти використовувати усі можливості цього потужного засобу програмування.



Схожі:

Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconПрактична робота №1 Способи представлення алгоритмів. Базові алгоритмічні структури. Типи алгоритмів в-1
Назвіть всі базові структури алгоритмів і дайте їм означення
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconТ. Основні поняття алгоритмізації (4 год.)
Базові алгоритмічні структури. Типи алгоритмів. Виконавець та система команд виконавця
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconТ. 1 Комп’ютерне моделювання. Основи алгоритмізації (6 год.)
Базові структури алгоритмів: слідування, розгалуження, повторення. Графічні схеми базових структур алгоритмів
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconІнформації в базі даних. Внесення змін до інформації в базі даних. Поняття про мову програмування. Алфавіт мови. Основні поняття мови: ідентифікатори, числа, рядки, описи. Основні вказівки та їх опис
Базові структури алгоритмів. Основна властивість базових структур. Структурний підхід до конструювання алгоритмів
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconТема: Поняття програмування та алгоритм. Властивості алгоритмів
Програмування — процес створення комп'ютерних програм або програмного забезпечення. Програмування поєднує в собі елементи інженерії...
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconТема: Базові алгоритмічні структури, типи алгоритмів. Виконавець та система команд виконавця
Після ознайомлення з різними формами запису алгоритмів зможемо розпізнати різні за типами команди, а відповідно і алгоритми, які...
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconПрограма для запису алгоритмів; б спеціально створена мова для запису алгоритмів; в мова програмування
Мова, призначена для запису алгоритмів розв’язування задач І вхідних даних для еом, – це
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів icon1. Побудова і аналіз алгоритмів Формалізація алгоритмів
Процес створення комп’ютерної програми для вирішення будь-якої практичної задачі складається з декількох етапів
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconУрок №3. За темою „Табличні величини Тема: Алгоритм пошуку в таблицях елементів з деякою властивістю
Мета уроку: формування навичок розробки алгоритмів пошуку в таблицях елементів за деякими властивостями; виховання інформаційної...
Тема: Алгоритм та основні поняття алгоритмізації, властивості алгоритмів, способи представлення алгоритмів iconПрограма для запису алгоритмів; б спеціально створена мова для запису алгоритмів; в мова програмування
В завданнях 1-11 підкресліть правильну відповідь. Розв’язки задач вставте після задачі
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи