Тема 15. Основні властивості і параметри алгоритмів . Основні поняття про алгоритмічну мову.
Властивості алгоритмів. Алгоритмічні проблеми.
Питання теми
1. Властивості алгоритмів.
2. Приклади правил, які не є алгоритмами.
3. Уточнення поняття алгоритму.
Основні терміни теми : дискретність, детермінованість, точність, зрозумілість.
1. Властивості алгоритмів
Розглянуті приклади показують, що виконання алгоритму розбивається на послідовність закінчених дій - кроків. Кожна дія повинна бути закінчена виконавцем перш, ніж він приступить до виконання наступної дії. Це властивість алгоритму називається дискретністю.
Зробити кожна окрема дія виконавцю пропонує спеціальна вказівка в записі алгоритму, називаний командою.
Запис алгоритму повинен бути такий, щоб на кожному кроці його виконання було відомо, яку команду треба виконати наступною. Ця властивість алгоритму називається точністю.
Алгоритм може бути виконаний тільки виконавцем, що розуміє кожну команду алгоритму і може її виконати в строгій відповідності з її призначенням. Ця властивість називається зрозумілістю (для даного виконавця).
Будучи зрозумілим, алгоритм не повинний усе-таки містити розпоряджень, зміст яких може сприйматися неоднозначно. Це означає, що те саме розпорядження після виконання повинне давати той самий результат.
У даному випадку мова фактично йде про те, що запис алгоритму повинен бути настільки чітким, настільки повним і продуманим в деталях, щоб у виконавця ніколи не могло виникати потреби в прийнятті яких-небудь самостійних рішень, не передбачених укладачем алгоритму. Говорячи інакше, алгоритм не повинний залишати місця, для сваволі виконавця.
Відзначена властивість називається властивістю визначеності, або детермінованості.
Зауваження. Часто під властивістю детермінованості алгоритму розуміється одночасне виконання властивостей точності і зрозумілості.
Важливою властивістю алгоритму є властивість результативності. Зміст цієї властивості полягає в тому, що при точному виконанні команд алгоритму процес повинний припинитися за кінцеве число кроків, і при цьому повинна бути отримана відповідь на питання задачі. У якості одної з можливих відповідей може бути і встановлення того факту, що задача рішень не має.
Вважається, що алгоритм найбільш цікавий, якщо він, крім того, має властивість масовості, тобто придатності для рішення будь-якої задачі з деякого класу задач. Цю властивість не слід розуміти як можливість вирішити багато задач. Властивість масовості припускає, що заданий алгоритм дозволяє вирішити будь-як задачу з визначеного класу, причому цей клас може складатися і тільки з однієї задачі.
Проілюструємо властивості алгоритму на прикладі алгоритму Евкліда.
Масовість алгоритму Евкліда полягає в тім, що його можна застосувати до будь-якої пари натуральних чисел. Результативність його полягає в тому, що він визначає процес, що приводить для будь-якої пари натуральних чисел до одержання їхнього найбільшого дільника. Зрозумілість алгоритму полягає в тім, що виконавець уміє виконувати дії, обумовлені командами алгоритму. Детермінованість алгоритму випливає з того, що кожна команда виконується виконавцем однозначно. Точність алгоритму забезпечується тим, що, по-перше, виконавцю відомо, з чого починати виконання алгоритму (з команди номер 1), і, по-друге, кожна команда постачена вказівкою, яку команду виконувати наступною.
2. Приклади правил, які не є алгоритмами.
Очевидно, не кожне правило, що приводить до рішення задачі, є алгоритмом. Розберемо з цих позицій кілька таких правил.
Приклад 2.1. Проведення перпендикуляра до прямій MN у заданій крапці A.
I. Відкласти в обидва боки від крапки A на прямій MN циркулем відрізки рівної довжини з кінцями B і C,
II. Збільшити розчин циркуля до радіуса, у півтора-два разу більшого довжини відрізків AB у AC.
III. Провести зазначеним розчином циркуля послідовно з центрами B і C дуги окружностей так, щоб вони охопили крапку A і утворили дві крапки перетинання один з одним D і E.
IV. Узяти лінійку і прикласти її до крапок D і E і з'єднати їх відрізком. При правильній побудові відрізок пройде через крапку А и буде шуканим перпендикуляром
Рис. 2.1. Проведення перпендикуляра до прямої в заданій крапці
Зазначене правило, мабуть, розраховано на виконавця-людину. Застосовуючи його, людина, зрозуміло, побудує шуканий перпендикуляр. Але, проте, це правило алгоритмом не є.
Насамперед, воно не має властивість детермінованості. Так, у пункті І потрібно від виконавця зробити вибір відрізка довільної довжини (для побудови крапок B і C треба провести окружність довільного радіуса r з центром у крапці A). У пункті ІІ потрібно зробити вибір відрізка в півтора-два разу більшого довжини відрізків AB і AC. У пункті 3 треба провести дуги, що також однозначно не визначаються їх описом. Людина-виконавець, що застосовує дане правило, до тим самим вихідним даних (прямій MN і крапці A) повторно, одержить незбіжні проміжні результати. Це суперечить вимозі детермінованості алгоритму.
Спробуємо пере формулювати це правило, щоб воно стало алгоритмом. Для цього необхідно у всіх розпорядженнях звільнити виконавця від проблеми вибору.
Для цього ми замість вибору довільного радіуса будемо вказувати в кожному випадку конкретний. Однак, цим невизначеність команд цілком не знімається. В інструкціях І і ІІ, крім проведення окружностей, потрібно знаходити крапки перетинання і якось їх позначати. Розберемо виникаючі при цьому проблеми.
У команді ІІ потрібно привласнити імена крапкам перетинання прямій MN і окружності . Тут можна домовитися позначати крапки, наприклад, так, щоб вектори і були однонаправлені.
У команді ІІІ потрібно позначити крапки перетинання окружностей і . Домовимося, наприклад, позначати через D ту з двох крапок перетинання, що знаходиться лівіше, якщо дивитися з центра B у напрямку центра C.
Крім того, замість дуг окружностей у пункті ІІІ, ми будемо проводити окружності, тому що тим самим знімається невизначеність інструкції "провести дугу, що охоплює крапку".
З обліком сказаного шуканий алгоритм може виглядати в такий спосіб.
Приклад 2.2. Алгоритм проведення перпендикуляра до прямій MN у заданій крапці A ( ).
1. Провести окружність радіуса 1 з центром у крапці A.
2. Позначити крапки перетинання окружності з прямій MN через B і C так, щоб .
3. Послідовно провести окружності і радіуса 2 з центром відповідно в крапках B і C.
4. Позначити крапки перетинання окружностей і через D і E так, щоб обхід багатокутника BDCE (послідовно від B через D і C до E) відбувався по годинній стрілці.
5. Провести пряму DE. Пряма DE - шуканий перпендикуляр.
Рис.2.2. Проведення перпендикуляра до прямої в заданій крапці
У шкільному підручнику приведений алгоритм перебування середини відрізка за допомогою циркуля і лінійки. У ньому використаний інший прийом рятування від невизначеності інструкцій при геометричних побудовах.
3. Уточнення поняття алгоритму
Точне математичне визначення поняття "алгоритм" було вироблено лише в тридцятих роках XX століття. Чому ж до цього часу математики задовольнялися інтуїтивним поняттям алгоритму? Це зв'язано з тим, що звичайно поняття алгоритму зустрічалося в зв'язку з конкретним рішенням задачі. Про алгоритм говорили лише тоді, коли пропонувався спосіб рішення якого-небудь класу задач. На початку XX століття в математиці нагромадилася велика кількість задач, що не піддавалися рішенню, незважаючи на те, що над ними думали першокласні вчені. Виникла підозра, що для деяких з цих задач узагалі не існує алгоритму, що дозволяє їх розв’язати. Твердження про нерозв'язність того або іншого класу задач можна було вивести, тільки маючи точне визначення алгоритму, треба було знати, неіснування чого потрібно довести.
Спроби дати строге математичне визначення алгоритму, що погодиться з інтуїтивним представленням про алгоритм, привели до вироблення відразу декількох визначень (Черч, Посада, Тьюринг, Марков і ін.). Згодом з'ясувалося, що всі ці визначення рівносильні між собою і, отже, визначають те саме поняття. Як основу для уточнення поняття алгоритму ми вибираємо так називані машини з необмеженими регістрами, або, коротше, МНР. Виклад на базі МНР привабливо через близькість цих машин до реальних ЕОМ.
Кожний алгоритм має справу з даними - вхідними, проміжними і вихідними. Оскільки ми збираємося уточнювати поняття алгоритму, потрібно уточнити і поняття даних. Як дані для МНР ми обмежуємося безліччю Z0 ненегативних цілих чисел. Таке обмеження не є істотним, оскільки інші види об'єктів і операції над ними можуть бути закодовані натуральними числами і представлені як операції над натуральними числами.
Нижче ми перелічимо всі команди зі списку розпоряджень МНР (для уточнення властивості "зрозумілість"), однозначно визначимо дію кожної команди (для уточнення властивості "визначеність") і опишемо механізм реалізації алгоритму (для уточнення властивості "точність").
Машина з необмеженими регістрами є виконавцем, що представляє собою простий "ідеалізований комп'ютер". Ідеалізація полягає в тому, що кожний окремий реальний комп'ютер обмежений як величиною чисел, що надходять на вхід, так і розміром пам'яті (необхідної для запам'ятовування проміжних результатів), МНР позбавлена цих обмежень. Машина з необмеженими регістрами має необмежено велику пам'ять, осередки якої будемо називати регістрами і позначати Кожний регістр у будь-який момент часу містить ненегативне ціле число.
...
...
Рис. 3.1. Регістри МНР
При цьому тільки кінцева безліч регістрів містить числа, відмінні від нуля. Всі інші регістри заповнені нулями. Це допущення припускає, що кожний алгоритм використовує тільки кінцевий обсяг пам'яті.
У список розпоряджень МНР входить чотири команди: команда обнуління Z(n); команда додатка одиниці S(n); команда переадресації T(m, n) і команда умовного переходу J(m, n, q). Команди обнуління, додатка одиниці і переадресації називаються арифметичними.
Позначення
команди
Позначення
команди Дія, вироблена МНР
по даній команді
Z(n)
S(n)
T(m, n)
J(m, n, q) Якщо , то перейти до
обчислення команди алгоритму
з номером q.
Рис. 3.2. Список розпоряджень МНР
Алгоритмом називається кінцева непорожня послідовність команд зі списку розпоряджень МНР, що починається з команди з номером 1.
Роблячи обчислення по даному алгоритму, МНР змінює вміст регістрів пам'яті в точній відповідності з командами алгоритму. Вихідний стан пам'яті, тобто послідовність чисел у регістрах перед початком обчислень, називається початковою конфігурацією.
Припустимо, що деякий алгоритм P складається з послідовності команд I1, I2, ..., Is. МНР починає обчислення з команди I1, потім виконуються команди I2, I3 і т.д. доти, поки не зустрінеться команда виду J(m, n, q). У цьому випадку МНР переходить до виконання команди, запропонованої J(m, n, q) і поточним змістом регістрів Rm і Rn
МНР виконує алгоритм P: I1, I2, ..., Is доти, поки це можливо. Обчислення зупиняється тоді і тільки тоді, коли немає наступної команди, тобто коли МНР тільки що виконала команду Ik і наступна команда в обчисленні є Iv, де v > s. Це може відбутися одним зі способів:
I) якщо Ik = Is (виконана остання команда в P) і Ik - арифметична команда;
2) якщо Ik = J(m, n, q), Rm = Rn і q > s.
3) якщо Ik = J(m, n, q), Rm Rn і q = s.
У цьому випадку будемо говорити, що обчислення зупинилося після виконання команди Ik, і заключна конфігурації є послідовність r1, r2, r3, ... умісти регістрів на цьому кроці.
Результатом застосування алгоритму до деякої початкової конфігурації будемо вважати число r1 з регістра R1 заключної конфігурації.
Бувають, звичайно, обчислення, що ніколи не закінчуються, наприклад, ніколи не закінчується ні при якій початковій конфігурації обчислення по алгоритму:
I1
S(1)
I2
J(1, 1, 1)
У випадку, якщо обчислювальний процес не закінчується одержанням результату, говорять, що алгоритм неможливо застосувати до початкової конфігурації.