Д.Кнут, Мистецтво програмування. Книга 1. Основні алгоритми. Розділ 1.1. Алгоритми. Фрагмент 2 - виконання алгоритму

Д. Кнут, Мистецтво програмування
Книга 1. Основні алгоритми

1.1. АЛГОРИТМИ

Попередня публікація
...

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

Отже, давайте як приклад розберемо алгоритм E. Припустимо, що m = 119 і n = 544; почнемо з кроку El. (Зараз можете просто стежити за викладом, оскільки ми розберемо алгоритм і детально все випишемо.) Ділення m на n в цьому випадку виконується просто, навіть дуже просто, оскільки частка дорівнює нулю, а залишок - 119. Таким чином, r ← 119. Переходимо до кроку Е2. Оскільки r != 0, на цьому кроці ніякі дії не виконуються. На кроці ЕЗ присвоюємо m ← 544, n ← 119. Вочевидь, якщо спочатку m < n, то частка на кроці El завжди виявляється рівною нулю і в ході виконання алгоритму завжди відбувається взаємний обмін значень змінних m і n, хоч і таким громіздким способом. Тому можна зробити додатковий крок.

E0. [Гарантувати, що m >= n.] Якщо m < n, то виконати взаємний обмін m ↔ n.

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

Повернемося до кроку El. Знаходимо, що 544/119 = 4 168/19, тому r ← 68. В результаті на кроці Е2 знову не виконуються ніякі дії, а на кроці ЕЗ присвоюємо m ← 119, n ← 68. У наступних циклах спочатку отримуємо r ← 51 і m ← 68, n ← 51, а потім - r ← 17 і m ← 51, n ← 17. Нарешті, в результаті ділення 51 на 17 отримуємо r ← 0.Таким чином, на кроці Е2 виконання алгоритму припиняється. Найбільший спільний дільник 119 і 544 дорівнює 17.

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

1) Кінцевість. Алгоритм завжди повинен закінчуватися після виконання скінченного числа кроків. Алгоритм Е задовольняє цій умові, тому що після кроку
Е1 значення r менше, ніж n. Тому якщо р != 0, то в наступному циклі на кроці Е1
значення n зменшується.Спадна послідовність позитивних цілих
чисел має кінцеве число членів, тому крок Е1 може виконуватися тільки
кінцеве число раз для будь-якого спочатку заданого значення n. Але майте
на увазі, що кількість кроків може бути скільки завгодно великою; вибір занадто
великих значень m та n призведе до того, що крок Е1 буде виконуватися більше
мільйона разів.
Процедура, що володіє всіма характеристиками алгоритму, за винятком, можливо, кінцевості, називається методом обчислень. Евклід (Euclid) запропонував не тільки алгоритм знаходження найбільшого спільного дільника, а й аналогічну йому геометричну побудову "найбільшої загальної міри" довжин двох відрізків прямої; це вже метод обчислень, виконання якого не закінчується, якщо задані довжини виявляються не співмірними.

2) Визначеність. Кожен крок алгоритму має бути точно визначений. Дії, які потрібно виконати, повинні бути строго і недвозначно визначени для кожного можливого випадку. Я сподіваюся, що алгоритми, наведені в даній книзі, задовольняють цьому критерію. Але справа в тому, що вони описуються звичайною мовою, і тому існує можливість неточного розуміння читачем думки автора. Щоб подолати це ускладнення, для опису алгоритмів були розроблені формально певні мови програмування, або машинні мови, в яких кожен оператор має строго певне значення.Багато алгоритми в цій книзі даються як на звичайній мові, так і на мові програмування. Метод обчислень, виражений на мові програмування, називається програмою.
Розглянемо як приклад алгоритм E. Стосовно до кроку Е1 критерій визначеності означає, що читач зобов'язаний точно розуміти, що означає розділити m на n і що таке залишок.Але в дійсності немає ніякої загальноприйнятої угоди з приводу того, що це означає, якщо m та n не є цілими позитивними числами. Яким буде залишок від ділення -8 на -π? Що розуміти під залишком від ділення 59/13 на нуль?Тому в даному випадку критерій визначеності означає наступне: ми повинні бути впевнені, що в кожному разі виконання кроку Е1 значеннями m та n завжди будуть цілі позитивні числа. Якщо спочатку за припущенням це вірно, то після кроку Е1 r - це ціле невід'ємне число;за умови переходу до кроку ЕЗ воно є також ненульовим. Таким чином, поставлену вимогу виконано і m та n - це дійсно цілі позитивні числа.

3) Ввід. Алгоритм має деяке (можливо, рівне нулю) число вхідних даних, тобто величин, які задаються до початку його роботи або визначаються динамічно під час його роботи. Ці вхідні дані беруться з певного набору об'єктів.Наприклад, в алгоритмі Е є два вхідних значення, а саме - m і n, які належать множині цілих позитивних чисел.

4) Вивід. У алгоритму є одне або декілька вихідних даних, тобто величин, котрі мають цілком визначений зв'язок із вхідними даними. У алгоритмі Е присутнє тільки одне вихідне значення, а саме - n, одержуване на кроці Е2. Це найбільший спільний дільник двох вхідних значень.
(Можна легко довести, що це число дійсно є найбільшим загальним дільником. Після кроку Е1 маємо
m = qn + r,
де q - деяке ціле число.

Якщо r = 0, то m кратне до n і, вочевидь, в цьому випадку n - найбільший спільний дільник m та n. Якщо r != 0, то будь-який дільник обох чисел m та n повинен бути також дільником m - qn = r і будь-який дільник n і r - також дільником qn + r = m. Таким чином, множина дільників чисел {m, n} збігається з множиною дільників чисел {n, r}. Отже, пари чисел {m, n} і {n, r} мають один і той же найбільший спільний дільник. Таким чином, крок ЕЗ не змінює відповіді вихідної задачі.

5) Ефективність. Алгоритм зазвичай вважається ефективним, якщо всі його оператори є достатньо простими для того, щоб їх можна було точно виконати протягом кінцевого проміжку часу за допомогою олівця і паперу. В алгоритмі Е використовуються тільки наступні операції: поділ одного цілого позитивного числа на інше, порівняння з нулем і присвоєння одній змінній значення іншої. Ці операції є ефективними, тому що цілі числа можна представити на папері з допомогою кінцевого числа знаків, і оскільки існує не менш як один спосіб ("алгоритм ділення") ділення одного цілого числа на інше. Але ті ж самі операції були б неефективними, якщо б вони виконувалися над дійсними числами, що представляють собою нескінченні десяткові дроби, або над величинами, що виражають довжини відрізків фізичних прямих, які не можна виміряти абсолютно точно. Наведемо ще один приклад неефективного кроку:
"Якщо 4 - це найбільше ціле n, при якому існує рішення рівняння wⁿ + xⁿ + yⁿ = zⁿ для цілих позитивних чисел w, х, у і z, то перейти до кроку Е4".

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

Давайте спробуємо порівняти поняття "алгоритм" з рецептом з кулінарної книги. Передбачається, що рецепт має властивість кінцевості (хоча і говорять, що "хто над чайником стоїть, у того він не кипить"), має вхідні дані (такі, наприклад, як яйця, борошно і т. д.), і вихідні дані (обід "на швидку руку" і т. п.), але добре відомо, що йому не вистачає визначеності. Інструкції з кулінарних рецептів дуже часто бувають невизначеними, наприклад: "Додайте крихту солі"."Крихта" визначається як кількість, "менше 1 % чайної ложки", і що таке сіль, ймовірно, теж відомо всім. Але куди саме потрібно додати сіль - зверху? Збоку? Інструкції "Злегка потрясіть, поки суміш не стане розсипчастою" і "Підігрійте коньяк у маленькій каструльці" будуть цілком зрозумілі досвідченому кухареві, але вони не годяться для алгоритму. Алгоритм повинен бути визначений настільки чітко, щоб його вказівкам міг наслідувати навіть комп'ютер. Тим не менше програміст може багато чому навчитися, прочитавши гарну куховарську книгу. (Чесно кажучи, автор ледь встояв перед спокусою назвати даний том "Поварена книга програміста". Але, може, коли-небудь він спробує написати книгу під назвою "Алгоритми для кухні".

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

Продовження