Новини освіти і науки:

G+

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

Визначення алгоритму

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

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

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

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

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

Істотно, що, порівняно з програмою, алгоритм може перебувати на вищому рівні абстракції, бути вільним від тих або інших деталей реалізації, пов'язаних з особливостями мови програмування та конкретної обчислювальної системи. Засоби, прийняті для зображення алгоритмів, за традицією називають алгоритмічною мовою. До речі, так називалися також перші мови програмування високого рівня, наприклад, Алгол – це просто скорочення ALGOrithmic Language - алгоритмічна мова. Але, загалом, жодна мова програмування не може цілком замінити алгоритмічну мову, оскільки консервативна за своєю суттю. Стабільність - один з необхідних компонентів якості мови програмування. Повинні існувати Гарантії, що всі програми, складені вчора, в минулому році, десять років тому, не втратять значення ні сьогодні, ні завтра. Модифікація мови програмування призводить до небажаних наслідків: вимагає перероблення системи програмування, знецінює напрацьоване програмне забезпечення. У той же час алгоритмічна мова може створюватися спеціально для певної предметної області, певного класу задач або навіть окремої задачі. Вона може розвиватися навіть при створенні алгоритму, вбираючи в себе новітні результати.

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

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

Приклад 1.1. Обчислити (х+у)/(а-b)

А = (A₁, А₂, А₃)

A₁:х+у

А₂: а-b

А₃: A₁/А₂

Слово алгоритм походить від algorithmic – латинської форми написання імені великого математика IX ст. Аль-Хорезмі, який сформулював правила виконання арифметичних дій.

Приклад 1.2. Розглянемо відому задачу про людину з човном (Л), вовком (В), козою (Кз) і капустою (Кп). Алгоритм її розв'язання можна подати так:

{ Л, В, Кз, Кп → } - початковий стан,

пливуть Л, Кз, Кп

{ В →Л, Кз, Кп } - 1 - ий крок,

пливуть Л, Кз

{ Л, В, Кз → Кп } - 2-ий крок,

пливуть Л, В

{ Кз → Л, В, Кп } - 3-ій крок,

пливуть Л

{ Л, Кз → В, Кп } - 4-ий крок,

пливуть Л, Кз

{→Л, В, Кз, Кп } - кінцевий стан.

3 Виконавці алгоритмів

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

Кожен виконавець може виконати певну кількість команд. Ці команди називаються допустимими командами виконавця.

Виконавцем ми будемо називати пристрій, здатний виконувати дії із заданого набору дій. Команду на виконання окремої дії називають оператором або інструкцією. Приклади виконавців: пральна машина, телефон, мікрокалькулятор, магнітофон, комп'ютер тощо. Приклади інструкцій: перемотати плівку, встановити з'єднання із вданим номером, виконати прання бавовняної білизни, зіграти партію у реверсі і т.ін.

Зазначимо особливості виконавців. По-перше, людина далеко не єдиний виконавець алгоритмів. По-друге, будь-який виконавець складається з пристрою керування й «робочого інструменту». По-третє кожний виконавець алгоритмів має обмежений набір допустимих дій (описати виконавця означає вказати його допустимі дії). Кожний виконавець може розуміти і виконувати якусь порівняно невелику кількість різних елементарних команд. Із цих команд складаються алгоритми. Як із 33 літер українського алфавіту можна написати і шкільний твір, і поему ≪Мойсей≫, так і з цієї невеликої кількості команд можна скласти невелику навчальну програму, а можна - і складну програму з тисячами команд. По-четверте, для розв'язування одних і тих самих задач виконавці з ≪біднішим≫ набором допустимих дій вимагають складніших і докладніших алгоритмів. По-п'яте, різні класи задач вимагають різних наборів допустимих дій, різних виконавців.

Розглянемо приклади найпростіших виконавців.

Виконавець ≪Обчислювач≫.Він вміє: множити число на 2 (*2); збільшувати число на 1 (+1). Треба скласти алгоритм отримання числа 100 з одиниці. Скільки дій у найкоротшому з таких алгоритмів? Розглянемо простішу задачу отримання з одиниці числа 4. Для її розв'язання можна використати алгоритм вигляду 1(+1)(+1)(+1) або 1(*2)(*2). Очевидно, що другий алгоритм коротший. Повернемося до попередньої задачі. Для отримання найкоротшого алгоритму перетворюємо число 100 у 1, використовуючи ділення на 2 і віднімання 1. Маємо

100 - > 50 - > 25 - ≫ 24 - > 12 - ≫ 6 - > 3 - > 2 - > 1.

Отже, для нашого виконавця алгоритм

1 (*2) (+1)(*2) (*2) (*2) (+1) (*2) (*2)

буде найкоротшим і містить 8 дій.

Виконавець ≪Маляр≫. ≪Маляр≫ може переміщуватися плоским полем, що розбитий на клітинки однакового розміру. Між клітинками поля можуть бути розташовані стіни, деякі клітинки можуть бути зафарбовані. Під час переміщення ≪Маляр≫ може зафарбовувати клітинки. Отже, виконавець може виконувати команди:

вгору

вниз

ліворуч

праворуч

зафарбувати.

Треба скласти алгоритм, при виконанні якого ≪Маляр≫ переміститься з клітинки А у клітку В і зафарбує клітинки, позначені крапками в полі:

А		•	В
	•	•

Алгоритм розв'язування поставленої задачі такий:

вниз → праворуч → зафарбувати → праворуч → зафарбувати → вгору → зафарбувати → праворуч .

І, нарешті, складання програми для комп'ютера — це кінцевий етап розв’язування задачі. Якщо перший в більшій мірі абстрактно-математичний, то в останньому переважають моменти конкретно-виробничого характеру. Як влучно зазначив А.П.Єршов, ≪програміст мусить мати здатність першокласного математика до абстракції і логічного мислення в поєднанні з едісонівським талантом до створення чогось із нуля й одиниці≫ [21].

Якщо алгоритмічну мову вибирають, виходячи з власних бажань, то вибір мови програмування може диктувати певна реальність: замовник, комп'ютер, попередній досвід. У цьому посібнику розглядається одна з найбільш розповсюджених мов програмування — мова Сі. Створена 1972 року як мова для системного програмування, мова Сі дістала поширення у всьому світі. Сьогодні Сі має багатьох наступників серед виробничих мов програмування: C++, Java, C#. Приклади у курсі розглядаються з використанням системи Borland C++ v.3.1.

Іншою мовою, використаною у нашому посібнику, буде мова Паскаль, названа на честь великого французького вченого, який першим в світі 1642 року виготовив автоматичний пристрій для додавання чисел. Мова Паскаль створена у 1969 році Ніклаусом Віртом у Швейцарському технічному інституті у Цюріху спеціально для вивчення програмування. Сьогодні існує декілька варіантів мови Паскаль. Ми будемо дотримуватися версії системи Borland Pascal v.7.0.

4 Способи описання алгоритмів

Існують такі способи описання алгоритмів:

• словесний,

• формульний,

• графічний,

• алгоритмічною мовою.

Першій спосіб - це словесний опис алгоритму. Словесний опис потребує подальшої формалізації.

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

Третій спосіб - запис алгоритмів за допомогою блок-схеми. Цей метод був запропонований в інформатиці для наочності подання алгоритму за допомогою набору спеціальних блоків. Основні з цих блоків подані на рисунку 1.

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

Рисунок 1 – Блоки для подання блок-схем.

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

Розглянемо такі властивості алгоритмів: визначеність, скінченність, результативність, правильність, формальність, масовість.

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

Приклад 1.3. Невизначеність виникне в алгоритмі (х+у)/(а-b), якщо в знаменнику буде записано, наприклад, 92 - 92 (ділення на нуль неприпустиме).

Невизначеність виникне, якщо деяка команда буде записана неправильно, бо така команда не належатиме до набору допустимих команд виконавця, (х+у)/(а-b).

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

Приклад 1.4. Алгоритм (х+у)/(а-b ) — скінченний. Він складається з трьох дій. Кожна дія, у свою чергу, реалізується скінченною кількістю елементарних арифметичних операцій. Нескінченну кількість дій передбачає математичне правило перетворення деяких звичайних дробів, таких як 5/3, у нескінченні десяткові дроби.

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

Наведені вище алгоритми є результативними. Прикладом не результативного алгоритму буде алгоритм для виконання обчислень, в якому пропущена команда виведення результатів на екран тощо.

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

Приклад 1.5. Наведені вище алгоритми є правильними. Помінявши місцями в алгоритмі з прикладу 1.2 будь-які дві команди, отримаємо неправильний алгоритм.

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

Приклад 1.6. Наведені алгоритми задовольняють цю умову, їх можуть виконати багато виконавців.

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

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

6 Поняття обчислювальної складності

Основними мірами обчислювальної складності алгоритмів є:

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

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

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

Складність алгоритму описується функцією f(n), де n — розмір вхідних даних.

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

Контрольні питання

1. Яке походження терміну ≪алгоритм≫?

2. Що ми розуміємо під поняттям ≪алгоритм≫?

3. Що таке допустимі команди виконавця?

4. Які є способи описуваннявання алгоритмів?

5. Які властивості повинен мати алгоритм?

6. Що означає скінченність (дискретність) алгоритму?

7. Що таке формальність алгоритму?

8. Що означає масовість алгоритму?

Тести для закріплення матеріалу

1. Оберіть визначення інформатики:

а) це наука про методи подання, накопичення, передавання та опрацювання інформації за допомогою електронно-обчислювальних машин;

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

в) це наука про відображення реальних об'єктів, процесів, подій тощо на комп'ютерних носіях;

г) це одних із видів програмування та проектування.

2. Визначте поняття загальної інформатики:

а) блок-схема;

б) задача;

в) функція мети;

г) алгоритм.

3. Визначте поняття алгоритму:

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

б) скінчена послідовність машинних команд для розв'язебання конкретної задачі;

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

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

д) скінченна послідовність команд, які треба виконати над вхідними даними для отримання результату.

4. Дати поняття виконавця:

а) пристрій, здатний виконувати дії із заданого набору дій;

б) команда на виконання окремої дії;

в) складається з пристрою керування і ≪робочого інструмента≫;

г) може розуміти і виконувати якусь порівняно невелику кількість різних елементарних команд;

д) алгоритмічна мова високого рівня.

5. Способи описування алгоритмів:

а) словесний;

б) схематичний;

в) табличний;

г) формульний;

д) графічний;

о) алооритмічною мовою.

6. Властивість алгоритму ≪скінченність≫ інакше ще називають:

а) результативність;

б) формальність;

в) масовість;

г) дискретність;

д) правильність.

ЛЕКЦІЯ № 2

Тема: Класи алгоритмів

Ціль: розглянути класифікацію алгоритмів за типами складності, основні визначення теорії алгоритмів: машина Тьюринга, рекурсія, теза Чорча

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Визначення алгоритму	\|	Поняття структури даних

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.015 сек.