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

Розділ V

Алгоритми

З давніх часів в математиці склалося інтуїтивне уявлення про алгоритм як формальне розпорядження, яке визначає сукупність операцій і порядок їх виконання для розв’язання всіх задач якого-небудь типу. Термін походить від латинізованої вимови імені середньовічного узбецького математика Аль-Хорезмі, який ще в IX столітті формулював правила, що дозволяють складати і вирішувати квадратні рівняння. З алгоритмами, тобто ефективними процедурами, що однозначно приводять до результату, математика мала справу завжди і в своєму розвитку накопичила безліч різних алгоритмів. Отримуючи відповідну інтерпретацію в конкретних додатках, вони становлять значну і найбільш істотну частину математичного апарату, що використовується в техніці. Шкільні методи множення «стовпчиком» і розподіл «кутом», метод виключення незалежних змінних при розв’язанні системи лінійних рівнянь, правило диференціювання складної функції, знаходження найбільшого загального дільника двох позитивних натуральних чисел, витягання квадратного кореня з раціонального числа із заданою мірою точності, обчислення рангу цілочисельної матриці, визначення тотожної істинності формули логіки висловлювання, спосіб побудови трикутника за трьома заданими сторонами - все це алгоритми. Однак поки математика мала справу в основному з числами і обчисленнями, і поняття алгоритму ототожнювалося з поняттям методу обчислення, потреби у вивченні самого цього поняття не виникало. Традиції організації обчислень складалися віками і стали складовою частиною загальної наукової культури в тій же мірі, що й елементарні навички логічного мислення. Все різноманіття обчислень комбінувалося з невеликого числа чітко визначених операцій арифметики, тригонометрії і аналізу. Тому поняття методу обчислення вважалося спочатку ясним і не потребувало спеціальних досліджень.

Досвід парадоксів теорії множин навчив математику надто обережно оперувати з нескінченністю й, по можливості, навіть про нескінченність міркувати за допомогою фінітних[1] методів. З'ясування того, які об'єкти і дії над ними потрібно вважати точно визначеними, якими властивостями і можливостями володіють комбінації елементарних дій, що можна і чого не можна зробити з їх допомогою - все це стало предметом теорії алгоритмів і формальних систем, яка спочатку виникла в рамках метаматематики і стала найважливішою її частиною. Головним внутрішнім математичним додатком теорії алгоритмів з'явилися докази неможливості алгоритмічного (тобто точного і однозначного) розв'язання деяких математичних проблем. Такі докази (як і точні формулювання тверджень, що доводяться) нездійсненні без точного поняття алгоритму.

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

Однак у всякої популярності є свої витрати. У повсякденній практиці слово «алгоритм» вживається дуже широко, втрачаючи часто своє точне значення. Приблизні описи поняття «алгоритм» (на зразок того, яке ми навели на початку параграфа) часто приймаються за точні визначення. У результаті за алгоритм часто видається будь-яка інструкція, розбита на кроки.

Ясне уявлення про те, що таке алгоритм, важливо не тільки для правильного слововикористання. Воно потрібне і при розробці конкретних алгоритмів, особливо коли мається на увазі їх подальше програмування. Однак воно ще важливіше при наведенні порядку в бурхливо зростаючому алгоритмічному господарстві. Щоб орієнтуватися в морі алгоритмів, що захлеснуло технічну кібернетику, необхідно уміти порівнювати різні алгоритми розв’язання одних і тих же задач, причому не тільки за якістю розв’язання, але і за характеристиками самих алгоритмів (числом дій, об'ємом пам'яті і т.д.). Таке порівняння неможливе без введення точної мови для обговорення всіх цих питань; інакше кажучи, самі алгоритми повинні стати такими ж предметами точного дослідження, як і ті об'єкти, для роботи з якими вони призначені.

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

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

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

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

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

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

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

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

3. Природно зажадати від алгоритму результативності, тобто зупинки після кінцевого числа кроків (що залежить від даних) з вказівкою того, що вважати результатом. Зокрема, всякий, хто пред'являє алгоритм розв’язання деякої задачі, наприклад обчислення функції f(х), зобов'язаний показати, що алгоритм зупиняється після кінцевого числа кроків (як кажуть, сходиться) для будь-якого х з області завдання f. Однако перевірити результативність (сходимість) набагато важче, ніж вимоги, викладені раніше. На відміну від них сходимість звичайно не вдається встановити простим переглядом опису алгоритму; загального ж методу перевірки сходимості, придатного для будь-якого алгоритму А і будь-яких даних х, як буде показано далі, взагалі не існує. Цю властивість називають властивістю результативності.

4. Потрібно розрізнювати: а) опис алгоритму (інструкцію або програму); б) механізм реалізації алгоритму (наприклад, ЕОМ), що включає засоби пуску, зупинки, реалізації елементарних кроків, видачі результатів і забезпечення детермінірованості, тобто управління ходом обчислення; в) процес реалізації алгоритму, тобто послідовність кроків, яка буде породжена при застосуванні алгоритму до конкретних даних. Будемо припускати, що опис алгоритму і механізм його реалізації кінцеві. Ця властивість називається властивістю кінцівки.

Приклад 5.1. Розглянемо наступну задачу: дана послідовність Р з n позитивних чисел; потрібно впорядкувати їх в порядку зростання.

Відразу ж приходить в голову наступний простий спосіб її розв’язання:

Крок 1. Шукаємо в Р найменше число.

Крок 2. Знайдене число приписуємо праворуч до R (в початковий момент R пуста) і викреслюємо його з Р.

Крок 3. Якщо в Р немає чисел, то переходимо до кроку 4. В іншому випадку переходимо до кроку 1.

Крок 4. Кінець. Результатом вважати послідовність R, побудовану на даний момент.

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

Приклад 5.2. Типовим прикладом логічних алгоритмів може служити алгоритм пошуку шляху в кінцевому лабіринті. Задача ця розв’язана ще до нашої ери при допомозі відомої Аріадни. Лабіринт зручно зобразити у вигляді графа, де вершини - це майданчики лабіринту, дуги - його коридори. Нехай потрібно з'ясувати, чи досяжний майданчик f з майданчика a, і якщо так, то знайти шлях з а в f, а якщо немає - повернутися в a. Припускається, що зазделегідь нічого не відомо про будову цього лабіринту.

Мал. 5.1

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

1. майданчик f – зупинка (мета досягнута),

2. петля (П) - намотування нитки (від даного майданчика розходяться, принаймні, два жовтих коридори),

3. зелена вулиця (ЗВ) - розмотування нитки (від даного майданчика вийде принаймні один зелений коридор),

4. майданчик а - зупинка (початковий пункт),

5. відсутність всіх попередніх ознак (ПО) - намотування нитки.

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

Таблиця 5.1

Номер ходу	Ознака	Хід	Пройдений коридор	Колір коридора після його проходження
	ЗВ	Р	ab	ж
	ЗВ	Р	bc	ж
	ЗВ	Р	cd	ж
	ЗВ	Р	dg	ж
	ЗВ	Р	gh	ж
	ПО	Н	hg	ч
	ПО	Н	gd	ч
	ЗУ	Р	db	ж
	П	Н	bd	ч
	ЗУ	Р	df	ж

Якщо перерахуємо коридори, які залишилися жовтими (ab, bc, cd, df), отримаємо шлях від а до f.

Блок-схеми алгоритмів. Зв'язки між кроками можна зобразити у вигляді графа. Для наведеного прикладу 5.1 граф зображений на мал. 5.2.

Мал. 5.2

Такий граф, в якому вершинам відповідають кроки, а ребрам переходи між кроками, називається блок-схемою алгоритму. Його вершини можуть бути двох видів: вершини, з яких вийде одне ребро (їх називають операторами), і вершини, з яких вийдуть два ребра (їх називають логічними умовами, або предикатами) Крім того, є єдиний оператор кінця, з якого не вийде жодного ребра, і єдиний оператор початку. Важливою особливістю блок-схеми є те, що зв'язки, які вона описує, не залежать від того, чи є кроки елементарними або являють собою самостійні алгоритми, як кажуть в програмуванні, блоки (по суті крок 1 таким і є). Можливість «розблокувати» алгоритм добре відома в програмуванні і широко там використовується: великий алгоритм розбивається на блоки, які можна роздати для програмування різним особам. Для даного блоку неважливо, як влаштовані інші блоки; для програмування блоку досить знати, де лежить вся початкова інформація, яка форма її поданя, що повинен робити блок і куди записати результат.

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

Мал. 5.3

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

При всій наглядності мови блок-схем не треба, однак, переоцінювати її можливості. Вона досить груба і відображає зв'язки лише по управлінню (що робити в наступний момент, тобто якому блоку передати управління), а не по інформації (де цьому блоку брати початкові дані). Наприклад, мал. 5.3 при зробленій обмовці відносно даних зображає обчислення f₂(f₁(х)), однак він же міг зображати послідовне обчислення двох незалежних функцій f₁(5) і f₂(100), порядок яких неістотний. Блок-схеми не містять відомостей ні про дані, ні про пам'ять, ні про набір елементарних кроків, що використовується. Зокрема, треба мати на увазі, що якщо в блок-схемі немає циклів, це ще не означає, що немає циклів в алгоритмі (вони можуть бути в якому-небудь неелементарному блоці). По суті блок-схеми це не мова, а засіб, хоча дуже зручний для однієї мети - опису детермінізму алгоритму. Корисно ввести одне уточнення:

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

Приклади таких умов: а) х<0, х=, х>0, б) х<5, 5£х<20, х=0, х<20.

Про підходи до уточнення поняття «алгоритм». Раніше були сформульовані основні вимоги до алгоритмів. Однак поняття, використані в цих формулюваннях (такі, як ясність, чіткість, елементарність), самі потребують уточнення. Очевидно, що їх словесні визначення будуть містити нові поняття, які знов зажадають уточнення, і т.д. Тому в теорії алгоритмів приймається інший підхід: вибирається кінцевий набір початкових об'єктів, які оголошуються елементарними, і кінцевий набір способів побудови з них нових об'єктів. Цей підхід був вже використаний при обговоренні питання про дані: уточненням поняття «дані» надалі будемо вважати множини слів в кінцевих алфавітах. Для уточнення детермінізму будуть використовуватися або блок-схеми і еквівалентні ним словесні описи (типу того, який наведений в прикладі 5.1), або опис механізму реалізації алгоритму. Крім того, треба зафіксувати набір елементарних кроків і домовитися про організацію пам'яті. Після того, як це буде зроблено, вийде конкретна алгоритмічна модель.

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

Проте, хоч спільність формалізації в конкретній моделі не втрачається, різний вибір початкових засобів приводить до моделей різного виду. Можна виділити три основних типи універсальних алгоритмічних моделей, що розрізнюються початковими евристичними міркуваннями відносно того, що таке алгоритм. Перший тип заснований на уявленні про алгоритм як про деякий детермінований пристрій, здатний виконувати в кожний окремий момент лише вельми примітивні операції. Таке уявлення не залишає сумнівів в однозначності алгоритму і елементарності його кроків. Крім того, евристика цих моделей близька до ЕОМ і, отже, до інженерної інтуїції. Основною теоретичною моделлю цього типу (створеною в 30-х роках - раніше за ЕОМ!) є машина Тьюрінга. Другий тип зв'язує поняття алгоритму з найбільш традиційними поняттями математики - обчисленнями і числовими функціями. Найбільш розвинена і вивчена модель цього типу - рекурсивні функції - є історично першою формалізацією поняття алгоритму. Нарешті, третій тип алгоритмічних моделей - це перетворення слів в довільних алфавітах, в яких елементарними операціями є підстановки, тобто заміни шматка слова (підслова) іншим словом. Переваги цього типу - в його максимальній абстрактності і можливості застосувати поняття алгоритму до об'єктів довільної (не обов'язково числової) природи. Проте, як буде ясно з подальшого, моделі другого і третього типу досить близькі (їх взаємна сводимість доводиться просто) і відрізняються в основному евристичними акцентами. Приклади моделей цього типу - канонічні системи Поста, які будуть розглянуті в VI розділі, і нормальні алгоритми Маркова.

Машини Тьюрінга