Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів




Скачати 106.81 Kb.
НазваЛекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів
Дата конвертації05.07.2013
Розмір106.81 Kb.
ТипЛекція
skaz.com.ua > Математика > Лекція
ЛЕКЦІЯ 7

АЛГОРИТМИ. ТИПИ АЛГОРИТМІВ. СПОСОБИ ОПИСУ АЛГОРИТМІВ.

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

Назва "алгоритм" відбулася від латинської форми імені найбільшого середньоазіатського математика Мухаммеда ібн Муса ал-Хорезмі (Alhorithmi), що жив в 783 850 рр. У своїй книзі "Про індійській рахунок" він виклав правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними "стовпчиком", знайомі тепер кожному школяру. У XII столітті ця книга була перекладена на латинь і набула широкого поширення в Европе.

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

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

Алгоритм — заздалегідь задане зрозуміле і точне розпорядження можливому виконавцеві зробити певну послідовність дій для отримання рішення задачі за кінцеве число кроків.

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

Порядок виконання алгоритму:

  • Дії в алгоритмі виконуються в порядку їх запису

  • Не можна міняти місцями ніякі дві дії алгоритму

  • Не можна не закінчивши однієї дії переходити до наступної

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

Існує багато тлумачень алгоритму. Наприклад:

«Алгоритм — це всяка система обчислень, що виконуються по строго заданим правилам, яка після якого-небудь числа кроків свідомо приводить до рішення поставленої задачі.» (А. Колмогоров) 

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

«Алгоритм — строго детермінована послідовність дій, що описує процес перетворення об'єкту з початкового стану в кінцевий, записана за допомогою зрозумілих виконавцеві команд.» (Угріновіч Микола Дмитрович) 

«Алгоритм — це послідовність дій, направлених на отримання певного результату за кінцеве число кроків.» (Roxanstudio) 

«Алгоритм є формалізована послідовність дій (подій). Алгоритм може бути записаний словами і зображений схематично. Практично будь-яка невипадкова повторювана дія піддається опису через алгоритм.» ([grey_olli]) 

«Алгоритм — однозначно, доступно і коротко (умовні поняття — назви етапу) описана послідовність процедур для відтворення процесу з обумовленим завданням алгоритму результатом за заданих початкових умов. Універсальність (або спеціалізація) алгоритму визначається застосовністю і надійністю даного алгоритму для вирішення нестандартних завдань.» 

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

Виконавець алгоритму — це деяка абстрактна або реальна (технічна, біологічна або біотехнічна) система, здатна виконати дії, що наказують алгоритмом.

Виконавця характеризують:

  • середовище;

  • елементарні дії;

  • система команд;

  • відмови.

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

Система команд. Кожен виконавець може виконувати команди тільки з деякого строго заданого списку — системи команд виконавця. Для кожної команди мають бути задані умови застосовності (у яких станах середовища може бути виконана команда) і описані результати виконання команди. Наприклад, команда Робота "вгору" може бути виконана, якщо вище за Робота немає стіни. Її результат — зсув Робота на одну клітку вгору.

Після виклику команди виконавець здійснює відповідну елементарну дію.

Відмови виконавця виникають, якщо команда викликається при неприпустимому для неї стані середовища.

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

Основні властивості алгоритмів наступні:

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

2.   Дискретність (переривчатість, нарізність) — алгоритм повинен представляти процес рішення задачі як послідовне виконання простих (або раніше визначених) кроків (етапів).

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

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

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

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

На практиці найбільш поширені наступні форми представлення алгоритмів:

  • словесна (запис на природній мові);

  • графічна (зображення з графічних символів);

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

  • програмна (тексти на мовах програмування).

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

Наприклад. Записати алгоритм знаходження найбільшого загального дільника (НОД) двох натуральних чисел (алгоритм Евкліда).

Алгоритм може бути наступним:

  • задати два числа;

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

  • визначити більше з чисел;

  • замінити більше з чисел різницею більшого і меншого з чисел;

  • повторити алгоритм з кроку 2.

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

Словесний спосіб не має широкого розповсюдження, оскільки такі описи:

  • строго не формалізуються;

  • страждають багатослівністю записів;

  • допускають неоднозначність тлумачення окремих розпоряджень.

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

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

^ Використання блок-схем для побудови алгоритмів.

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



Типові блоки для формування блок-схем алгоритмів.

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



Основні алгоритмічні структури.

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

Структура "розгалуження" передбачає виконання однієї з двох груп дій залежно від виконання умови у блоці розгалуження. На рис. 3 знаком "+" показано виконання умови, а знаком "-" - його невиконання. Часто використовується неповна команда розгалуження, коли один з блоків дії відсутній.

Структура "цикл" має декілька різновидів. На рис. показаний цикл типу "доки" (while) з передумовою.

Тепер запишемо алгоритм розв’язання задачі 1 у графічному вигляді.



Блок-схема алгоритму знаходження коренів квадратного рівняння до задачі 1.

Задача Побудувати блок-схему алгоритму перевірки введено числа на невід’ємність.



Задача Побудувати блок-схему алгоритму зходження периметра та площі трикутника за формулою Герона.



Задача Побудувати блок-схему алгоритму порівняння двох чисел.


Приклади алгоритмів мовою блок-схем.




Поєднання базових алгоритмічних структур у схемах алгоритмів розв’язку задач

Схожі:

Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів iconАлгоритми. Властивості алгоритмів
Домогтися засвоєння основних понятть алгоритмізації, властивості алгоритмів, способи представлення алгоритмів
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів iconЛекція №12 Тема: Характеристика І типи облікових задач, що підлягають...
Мета: Ознайомитись з типами облікових задач; оглянути розділи опису постановки задач
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів icon1. Побудова І аналіз алгоритмів Формалізація алгоритмів
Процес створення комп’ютерної програми для вирішення будь-якої практичної задачі складається з декількох етапів
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів iconЛР. 0 2 – Символьні та рядкові величини. Одномірні та багатовимірні масиви
...
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів icon" Лінійні алгоритми в Turbo Pascal " Виконав
Мета: навчитись створювати та реалізовувати на еом програми лінійних алгоритмів, застосувати основні оператори: введення даних (read,...
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів icon" Алгоритми переведення з однієї позиційної системи числення в іншу "
Мета: Знайомство з позиційними системами числення, вивчення різних алгоритмів переведення з однієї позиційної системи в іншу, виконання...
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів iconПобудова І аналіз алгоритмів
Мета роботи: ознайомитись з роботами, що виконує програміст на кожному з етапів розв’язку задачі
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів iconТема 1: Основні поняття про паралельні обчислення
Загальні зауваження стосовно оцінки продуктивності паралельних алгоритмів та систем
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів iconТема: Створення програм, що містять двовимірні масиви
Мета завдання: Набуття навичок використання типових алгоритмів опрацювання табличної інформації
Лекція 7 алгоритми. Типи алгоритмів. Способи опису алгоритмів iconТеоретичні відомості
Мета роботи. Вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення
Додайте кнопку на своєму сайті:
Школьные материалы


База даних захищена авторським правом © 2015
звернутися до адміністрації
skaz.com.ua
Головна сторінка