Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



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

Скачати 108.2 Kb.

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




Скачати 108.2 Kb.
Сторінка1/2
Дата конвертації19.03.2017
Розмір108.2 Kb.
  1   2


Дата:

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

Мета:

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

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

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

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

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

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

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

Конструюва́ння - процес створення конструктором проекту певного об'єкта техніки, що полягає у визначенні форми, розмірів, взаємного розташування й параметрів частин й елементів конструкції об'єкта, його складових (агрегатів, систем, вузлів тощо), способу їхнього з'єднання, вибору матеріалів окремих елементів та розробки конструкторської документації.
Елеме́нт (лат. elementum - стихія, первинна речовина) - нерозкладний (у даній системі) компонент складних тіл, матеріальних систем, теоретичних побудов; будь-який об'єкт, пов'язаний певними відношеннями з іншими об'єктами в єдиний комплекс.
Принцип (лат. principium - начало, основа) - це твердження, яке сприймається як головне, важливе, суттєве, неодмінне або, принаймні, бажане. У повсякденному житті принципами називають внутрішні переконання людини, ті практичні, моральні та теоретичні засади, якими вона керується в житті, в різних сферах діяльності.

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

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

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

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

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

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



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

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

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

  • виведення результату обчислення арифметичного виразу.
    Фрагмент (лат. fragmentum - уламок, шматок, скалка) - яка-небудь частина цілого.
    Дискриміна́нт (від лат. discriminar - «розбирати», «розрізняти») многочлена p ( x ) = a 0 + a 1 x + . . . + a n x n +a_x+...+a_x^} - за визначенням це добуток
    Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.
    Обчи́слення - є гілкою математики, зосередженою на функціях, похідних, інтегралах, і нескінченному ряду чисел. Цей предмет являє собою важливу частину сучасної математичної освіти. Воно складається з двох основних галузей - диференціального і інтегрального численнь, які пов'язують основні теореми обчислення.
    Харам (араб. ‎ حرام‎‎, "заборонене") - в ісламі вчинки й речі, що є забороненими (протилежність халяль). Всі ці заборони обґрунтовуються однозначними і беззаперечними доказами з ісламських першоджерел.
    Квадра́т - чотирикутник, у якого всі сторони рівні і всі кути прямі. Для задання квадрата необхідно і достатньо задати дві точки на координатній площині, які відповідатимуть будь-яким двом кутам та врахувати їх суміжність.
    Арифме́тика (дав.-гр. ἀριϑμητική - мистецтво лічби, вчення про числа, від дав.-гр. αριθμός - число) - наука про числа, їх властивості й операції над ними.


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

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

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

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

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

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


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

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

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

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

Циклічним елементом алгоритму називається така операція, за допомогою якої здійснюється визначена кількість повторень однієї або декількох дій згідно сформульованої умови.
Знаменник - число, або алгебраїчний вираз, який стоїть під рискою у записі дробу.
Кількість - в Арістотелівській логіці друга з 10 категорій (класів, розрядів, які спрощують процес розумового визначення будь-якої речі), побічна обставина матеріальних речей , за допомогою якої вони поширюються в просторі, вимірюються якоюсь математичною нормою і здатні бути поділеними на окремі частини.
Більшість алгоритмів містить серії дій, які повторюються декілька разів. Для їх визначення використовують циклічну конструкцію, яка ще носить назву «повторення».
Озна́чення, ви́значення чи дефіні́ція (від лат. definitio) - роз'яснення чи витлумачення значення (сенсу) терміну чи поняття. Слід зауважити, що означення завжди стосується символів, оскільки тільки символи мають сенс що його покликане роз'яснити означення.

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

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

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

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

Цикл (лат. cyclus, від грец. kuklos - круг) - завершена послідовність функціонування матеріально-технічних компонентів об'єкта (явища) в просторі та часі. Коло подій, явищ, частин.

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



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

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


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

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

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

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

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

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

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

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

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

Найпростіші (лат. Protozoa, від дав.-гр. πρῶτος «перший» і ζῷα, форми множини ζῷον - «жива істота») - парафілетична або поліфілетична група одноклітинних або колоніальних еукаріотів, які мають гетеротрофний тип живлення.

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

Програма (фр. programme письмове оголошення, порядок денний, від грец. prógramma вказівка) - заздалегідь затверджена (визначена) дія.
Мабуть, краще буде говорити про окремі лінійні фрагменти цих програм.



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

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

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

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

Парасо́ля, парасо́ль, парасо́лька, рідко зонт, доща́р - пристрій, призначений для захисту від опадів (дощу чи снігу) або від сонячних променів.
Користува́ння - добування з речей їхніх корисних властивостей (наприклад, збирати врожай, вживати продукти харчування, носити одяг і взуття). Одна з трьох класичних правомочностей власника (нарівні з володінням і розпорядженням).
Необхідність - система зв'язків і відносин, що зумовлює зміну, поступальний рух, розвиток у жорстко визначеному напрямку з жорстко визначеними результатами. Іншими словами, необхідність - це такий зв'язок, що обов'язково призводить до певної події.
Анало́гія - (грец. αναλογια - «відповідність») - подібність, схожість у цілому відмінних предметів, явищ за певними властивостями, ознаками або відношеннями.
По́бут - позавиробнича сфера діяльності людей, пов'язана з задоволенням ними своїх власних матеріальних та культурних потреб (житло, одяг, їжа, відпочинок тощо). Побут також охоплює звичаї, обряди, традиції, які відображають особливості життя конкретного класу, нації, народності, етнічної групи.
Математи́чна моде́ль - система математичних співвідношень, які описують досліджуваний процес або явище. Математична модель має важливе значення для таких наук, як: економіка, екологія, соціологія, фізика, хімія, механіка, інформатика, біологія та ін.
Під час виконання цих частин алгоритму здійснюється діалог з користувачем алгоритму. Переклад з англійської мови слова Шефісе означає узгодження, зв'язок.
Кори́стува́ч - той, хто користується чим-небудь - майном, землею, комп'ютером тощо.
Узго́дження - тип підрядного зв'язку між головним і залежним словами у словосполученні, коли форма залежного слова відповідає формі головного, тобто узгоджується з ним у роді, числі, відмінку. Наприклад, червона троянда.
Англі́йська мо́ва (English, the English language) - мова, що належить до германської групи індоєвропейської сім'ї мов. Одна з найпоширеніших мов у світі, особливо як друга мова та мова міжнародного спілкування.
Саме тому ми, говорячи про розгалужені алгоритми, будемо мати на увазі безпосередньо сам алгоритм, а не його інтерфейсні частини.

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

Коефіціє́нт - характеристика процесу, явища, речовини або поля, яка має відносно сталий характер.
Існува́ння (від екзистенція) - центральне поняття екзистенціалізму, унікальна особистісна сутність людини, що втілює в собі духовну, психоемоційну неповторність особи.


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

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

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


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

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

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


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

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

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

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


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

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

Зовнішні допоміжні алгоритми частіше за все об'єднуються у так звані бібліотеки. Для користування цими бібліотеками повинні існувати інструкції з описом всіх допоміжних алгоритмів, які входять до них, та правила користування ними.
Інструкція - правовий акт, який створюється органами державного управління для встановлення правил, що регулюють організаційні, науково-технічні, технологічні, фінансові та інші спеціальні сторони діяльності та відносин установ, закладів, підприємств, службових осіб.
Бібліоте́ка або книгозбі́рня (грец. βιβλιον - книжка і θηκη - сховище, скриня) - культурно-освітній заклад, що здійснює збирання друкованих і рукописних матеріалів, проводить їх опрацювання і відображення у каталогах, організовує відповідне їх зберігання, збереження і обслуговування ними читачів.

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

Тригономе́трія (від грец. τρίγονο - трикутник та μετρειν - вимірюю, тобто буквально вимірювання трикутників) - розділ елементарної математики, що лежить на перетині алгебри та геометрії і вивчає співвідношення між сторонами й кутами трикутників, дозволяючи проводити кутові обчислення через спеціально визначені функції кутів.
використання значень відомих фізичних одиниць для розв'язування задач з фізики тощо.

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

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

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

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

При́стрій (англ. device, appliance, нім. Vorrichtung f, Einrichtung f) - обладнання, конструктивно завершена технічна система, що має певне функціональне призначення і за допомогою якої виконується яка-небудь робота або спрощується, полегшується певний процес.
Інструме́нт (лат. instrumentum - знаряддя) - технологічне оснащення (знаряддя або пристрій), які в процесі праці безпосередньо стикаються з предметом праці з метою зміни чи контролю його форми, стану, властивостей тощо.

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

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

Тури́зм - тимчасовий виїзд особи з місця постійного проживання в оздоровчих, пізнавальних, професійно-ділових чи інших цілях без здійснення оплачуваної діяльності в місці перебування.
Поведі́нка - родовий термін, який охоплює різні реакції живого організму чи групи організмів.
Програмне забезпечення Програ́мне забезпе́чення (програ́мні за́соби) (ПЗ; англ. software) - сукупність програм системи обробки інформації і програмних документів, необхідних для експлуатації цих програм.
Якщо користувач набирає текст, тобто виконує певну послідовність вказівок щодо підготовки тексту, то виконавцем цього алгоритму є

  1   2


Скачати 108.2 Kb.

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