Тема: Базові алгоритмічні структури, типи алгоритмів. Виконавець та система команд виконавця icon

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




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


Дата:

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

Мета:

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


Хід уроку

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

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


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

знайомим алгоритмом Евкліда.

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

Визначають три базових структурних елементи:

лінійний, розгалужений, циклічний.

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

До таких операцій відносяться дії зміни значення деяких величин, введення та виведення інформації тощо.

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

У якості прикладів лінійних елементів можна навести такі:

  • натиснення кнопки POWER при вмиканні комп'ютера;

  • перехід вулиці, по якій заборонено рух транспорту;

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

  • виведення результату обчислення арифметичного виразу.

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

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

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

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




Прикладом розгалуженого елемента в алгоритмі Евкліда є вибір зміни значення величини п або величини т у залежності від співвідношення між ними (п>т - «так» або «ні»). У результаті вибору одна з дій (п:=п-т, т:=т-п) буде пропущена.

Прикладами розгалужених елементів можуть бути ще такі:

  • взяти парасольку за умови, якщо іде дощ (скорочена форма);

  • якщо загорілося зелене світло, то переходити вулицю, в протилежному випадку - зачекати (повна форма);

  • якщо електронний варіант тексту не містить помилок, то роздрукувати його (скорочена форма);

  • якщо знаменник дробу не дорівнює нулю, то обчислити його значення, у протилежному випадку повідомити про помилку (повна форма).

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

Є два типи повторення: з передумовою та з післяумовою.

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

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

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

До прикладів повторення з передумовою можна віднести такі:

  • поки є тісто виготовляти тістечка;

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

  • поки не завершиться список чисел знаходити їх суму.

Прикладами повторення з післяумовою можугь буги:

  • повторювати виконання фізичної вправи доки вчитель не дасть команду про її завершення;

  • продовжувати записи у зошиті до того часу, поки па закін­чаться в ньому аркуші;

  • продовжувати обчислення швидкості руху при різних значеннях відстані та часу доки результат не набуде наперед заданого значення.

^ Тепер перейдемо до визначення типів алгоритмів.

Лінійними алгоритмами називаються алгоритмів, які складаються з лінійних елементів.

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

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

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

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

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

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

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

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

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

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

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

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

  • дотримання розпорядку дня протягом робочого тижня;

  • заповнення таблиці значень sinх при заданих аргументах.

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

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

Стосовно допоміжних алгоритмів можна розглядати:

  • внутрішні, локальні, що створюються в межах даного алго­ритму і доступні для використання тільки у цьому алгоритмі;

  • зовнішні, глобальні, які можна використовувати у різних незалежних алгоритмах.

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

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

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

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

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

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

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

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

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

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

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

Слід зазначити, що при виконанні команд можуть виникати відмови їх виконання виконавцем. Ці відмови виникають під час виклику команди в неприпустимому для даної команди стані середовища. Ситуації, при яких виникає відмова, різні для різних команд виконавця. Наприклад, при обчисленні значення дробу можливе ділення на нуль. Але існують команди, при виконанні яких відмови ніколи не виникають. Наприклад, обчислення ком­п'ютером або калькулятором виразу «2+2» завжди є коректним.

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

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





Схожі:

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


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