Алгоритми навколо нас

Н. А. Криницький

АЛГОРИТМИ НАВКОЛО НАС

Видання друге

ВСТУП

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

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

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

Слово «алгоритм» походить від імені узбецького математика Хорезмі (по-арабски ал-Хорезмі), яку в IX ст. н. е.. розробив правила чотирьох арифметичних дій над числами в десятковій системі числення. Сукупність цих правил у Європі стали називати «ал-горізм». Згодом це слово перетворилося в «алгоритм» і сталось збірною назвою окремих правил певного виду (і не тільки правил арифметичних дій). Протягом тривалого часу його вживали тільки математики, позначаючи правила вирішення різних завдань.

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

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

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

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

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

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

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

На закінчення автор користується нагодою висловити глибоку вдячність Н.М. Нагірному, зробившому при підготовці 2-го видання велику допомогу.

Глава 1

АЛГОРИТМИ У інтуїтивному значенні

§ 1. «Алгоритмічні джунглі»

Серед різноманітних правил, з якими доводиться стикатися щодня і щогодини, особливу роль відіграють правила, що пропонують послідовність дій, що ведуть до досягнення певної необхідного результату. Нерідко їх називають алгоритмами. З наукової точки зору до цього назви потрібно додати слова «в інтуїтивному сенсі».

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

Знання, зодягнені в наукову, зокрема математичну форму, не володіють такою мінливістю, характеризуються великою точністю і служать підставою для наукових висновків. У тих випадках, коли формалізовані знання перестають відповідати інтуїтивним уявленням, наукові формулювання замінюють новими.

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

1) опустіть її в прийомний отвір;

2) зніміть трубку і чекайте звуковий сигнал;

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

4) почувши довгі гудки, чекайте відповіді абонента;

5) "почувши короткі часті гудки, повісьте трубку і отримаєте монету назад: потрібний вам абонент зайнятий».

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

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

Кефір - 5 г, відвар - 45 г, цукровий сироп - 5 м.

Суміш застосовується за призначенням лікаря як догодовування півтора - двомісячної дитини. ^»1

Не думайте, що алгоритми грають роль тільки в житті людей. Ось ще алгоритм.

«Кожного цуценя слід годувати окремо від інших, інакше сильніші і активні будуть з'їдати велику порцію.

Підгодовують 3-4 рази в день після того, як цуценята пососут мати, рівними невеликими порціями, починаючи з півсклянки молока ^»2

В останньому правилі фраза «... інакше сильніші і активні будуть з'їдати велику порцію» до самого правилом не відноситься. Такі фрази називають коментарями. Їх відкидання на сенс правила не впливає.

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

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

Лимонний сік - 8, цукор - 14, желатин - 3, кислота лимонна - 0,1 ». ³

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

«Перед посівом на вирівняною поверхні маркером або кілочком під шнур проводять борозенки глибиною від 0,5 до 1 см на відстані 30-35 см один від одного. У борозенки розподіляють насіння гніздами (по 8-10 зерен у гніздо). Відстань між гніздами 15-20-25 см залежно від культури. Закладають насіння перегноєм, посипаючи його зверху шаром не товще 0,5-1 см ». ⁴

Цікаві приклади алгоритмів представляють широко відомі рецепти, за якими в аптеках готують і видають ліки. Лише дуже досвідчені лікарі складають кожен раз індивідуальний рецепт, в більшості ж випадків його виписують із спеціального довідника:

«Rp. Arpenali 0,05 D. T. D. N 20 in tabul S. По 1 таблетці З рази на день ». ⁵

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

А ось за столом сидить школяр. Чим він зайнятий? За його словами, він готує уроки. Яке до цього мають відношення алгоритми? Виявляється - велике. Він вирішує приклади з арифметики, складає десяткові дробу. Запитайте його, як він це робить, і він вам відповість:

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

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

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

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

Не тільки діти, а й дорослі більшу частину свого часу витрачають на виконання алгоритмів. Багато інструкції та накази, які визначають наші дії на роботі, - це алгоритми. Навіть закінчивши роботу і бажаючи відпочити, ми постійно стикаємося з ними. Уявіть собі, що, знявши аматорський кінофільм, ви збираєтеся його виявити. У вас в руках недавно куплений набір «Хімікати для обертаються кіноплівок». Що ж ви знаходите, розкривши його? Звичайно, хімікати, але крім них інструкцію. Ось один із її пунктів.

«Приготування відбілюючого розчину.

Вміст пакету «Д» розчинити в 500 мл води при температурі 18-20 ° С, потім обережно додати вміст пакету «Е». Об'єм розчину довести до 1000 мл. Розчин профільтрувати »

Це знову алгоритм.

Усюди алгоритми. Вони оточують нас, переплітаються, проникають один в одного; кроку не можна ступити, не наражаючись на них. Але як разюче відрізняються «алгоритмічні джунглі» від справжніх, в яких густі сплутався рослини стискують нас, чіпко тримають в полоні. Дивним чином алгоритми не пов'язують нас, а ведуть найнадійнішими шляхами до вирішення найскладніших проблем.

§ 2. Вихідні дані і результати. Масовість алгоритму

Отже, ми в «джунглях». Але щоб в них орієнтуватися, треба зрозуміти, що таке алгоритм. Наведені вище приклади вже дозволяють здійснити певний аналіз; ще ряд прикладів містить глава 2, в яку можна «підглядати».

Відразу кидається в очі, що кожен алгоритм передбачає наявність деяких вихідних даних і приводить до отримання певного шуканого результату. Наприклад, в § 1 для алгоритму приготування дитячої їжі вихідними даними є порції кефіру (50 г), круп'яного відвару (45 г) і цукрового піску (5 г), а результатом - відповідну кількість дитячої їжі (очевидно, 100 г). Для медичного рецепта (алгоритму) вихідними даними є медикамент арпенал, використовуваний для лікування виразки шлунка, а результатом - коробочка з двадцятьма пігулками і написом «по 1 таблетці 3 рази на день». Для алгоритму складання вихідним даним є пара доданків (чисел), а результатом-сума (знову число).

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

Можна подумати, що кожен алгоритм задає цілком певний процес. На жаль, не зовсім так. Тільки для найпростіших алгоритмів можна говорити про певні алгоритмічних процесах. Для більш складних алгоритмів (ми це побачимо на стор 20) вказати певний процес не можна. Але для тих алгоритмів, про які ми вже говорили, існування такого процесу не викликає сумніву. Тому поки ми говоримо про найбільш простих алгоритмах; будемо вважати, що кожен з них задає цілком певний алгоритмічний процес.

Але повернемося до аналізу тих предметів, які можуть бути вихідними даними і результатами. Очевидно, для кожного алгоритму можна брати різні варіанти вихідних даних. Це видно з того, що, наприклад, для алгоритму приготування дитячої їжі можна слова «грами» при описі вихідних даних розуміти як «вагові частини». Якість одержуваної їжі при цьому не зміниться. Може змінитися тільки її кількість. Для рецепту приготування лимонного желе, очевидно, так і зроблено. Багато алгоритми залишаються в силі для різних варіантів вихідних даних. Алгоритм складання можна застосувати до пар будь-яких позитивних чисел. Алгоритм додаткового годування цуценят годиться не тільки, наприклад, для Рексіка і Бобика, але і для інших щенят.

Помічене нами властивість алгоритмів, наведених у § 1 (їх придатність до великого числа варіантів вихідних даних), називають їх масовістю. Тривалий час вважали, що придатність алгоритмів для багатьох приватних випадків є настільки суттєвою і важливою їхньою рисою, що має увійти в наукове визначення алгоритму . Це виключало ⁶ багато правил з компетенції науки (з-за їх «недостатньою» масовості) і ускладнювало ⁷ як наукові дослідження, так і застосування їх результатів на практиці (а раптом перед нами саме ненауковий випадок?), Що представляє собою серйозні незручності.

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

Розпливчастість терміна «масовість» підтверджується відомим парадоксом Евбулід, який іноді називають парадоксом купи. Сутність його можна передати, задаючи собі ряд запитань і тут-таки, відповідаючи на них. Один камінь - це купа? Ні. А два камені? Теж ні. А три? Врешті-решт ми або прийдемо до висновку, що куп не існує, або змушені будемо визнати, що є таке число каменів, збільшення якого на одиницю призводить до отримання купи. І те й інше суперечить фактам і є наслідком розпливчастості поняття купи. І все ж просто «відмахнутися» від властивості масовості не можна. Потрібно дещо змінити його трактування, з тим щоб усунути зазначені вище незручності.

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

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

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

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

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

Проілюструємо обидва ці випадки. Наведемо приклад нескінченного алгоритмічного процесу. Всім відомий алгоритм розподілу десяткових дробів. Числа 4,2 і 3 є для нього допустимими вихідними даними. При цьому виходить наступний процес:

Шуканий результат дорівнює 1,4. Але зовсім інша картина вийде для чисел 20 і 3, які теж являють собою допустимі вихідні дані. Для них вийде такий процес:

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

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

1. Початкове дане помножити на 2. Перейти до виконання п. 2.

2. До отриманого числа додати одиницю. Визначити залишок у від ділення цієї суми на 3. Перейти до виконання п. 3.

3. Розділити вихідне дане на у. Приватне є шуканим результатом. Кінець.

Нехай цілі невід'ємні числа (так звані натуральні) будуть допустимими вихідними даними для цього алгоритму.

Для числа 6 алгоритмічний процес буде протікати так.

Перший крок: 6-2 = 12; переходимо до п. 2.

Другий крок: 12 +1 = 13; у = 1; переходимо до п. 3.

Третій крок: 6: 1 = 6. Кінець.

Шуканий результат дорівнює 6. Інакше буде протікати алгоритмічний процес для вихідного даного 7.

Перший крок: 7-2 = 14; переходимо до п. 2.

Другий крок: 14 +1 = 15; у = 0; переходимо до п. 3.

Третій крок: 7:0 - поділ неможливо. Процес натрапив на перешкоду і безрезультатно обірвався.

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

§ 3. Зрозумілість алгоритму

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

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

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

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

В подальшому (гл. 9, § 4) читач дізнається, що про деякі машини (ЕОМ) по відношенню до деяких алгоритмів виконання алгоритмів (операційним системам) так і напрошується антропоморфічні вираз «вона 'його знає». І все ж навіть у цих машин механізм розуміння алгоритмів не той, що у людей.

Може здатися, що, роз'яснюючи поняття алгоритму, ми апелювали до цього ж поняття і допустили некоректне міркування, зване порочним колом. У даному випадку це не так (див. § 5).

§ 4. Рекурсивні визначення

Якщо хочуть ввести нове поняття, то, як кажуть математики, йому дають визначення.

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

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

В. І. Даль - укладач першого тлумачного словника російської мови. Візьмемо для прикладу з словника В. І. Даля ⁸ статтю «танцювати». В якості першого ж значення цього слова там наведено: «танцювати». Подивимося тепер статтю «Танцювати» і в якості першого значення слова «танцювати» прочитаємо «танцювати».

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

Визначення. Словом називається або а) порожній рядок літер, або б) слово, до якого приписана буква.

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

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

Тепер повернемося до поняття алгоритму. Його зв'язок з поняттям алгоритму виконання алгоритмів така, що допускає можливість рекурсивного визначення алгоритму, що ми І зробимо надалі (гл. 8, § 7).

§ 5. Визначеність алгоритму

Звернемо увагу ще на одну особливість, притаманну кожному алгоритму. Виконавець алгоритму не тільки не має потреби в якій-небудь фантазії або кмітливості, але, більш того, алгоритм не залишає місця для прояву цих якостей, якщо виконавець ними володіє. Виконуючи алгоритм, діють механічно. Може бути, на думку читача це погано? Може бути, ця риса алгоритму в якійсь мірі пригнічує творчі здібності людей? Ні в якому разі! Люди можуть повною мірою проявляти свої творчі здібності, розробляючи алгоритми. Але після того як вони створені, такий прояв творчих здібностей було б невиправданим витратою психічної енергії. Алгоритми дозволяють її економити. Таким чином, формулювання алгоритму зовсім точний, що повністю визначає всі дії виконавця.

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

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

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

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

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

Властивість визначеності тісно пов'язано з властивістю зрозумілості. Ми говорили вище (в § 4), що зрозумілість полягає в тому, що виконавцю відомий алгоритм виконання адресованих йому алгоритмів. Якщо такий алгоритм виконання володіє визначеністю, то (як наслідок) і виконані відповідно до нього алгоритми виявляться визначеними.

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

§ 6. Висновки

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

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

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

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

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

У чому ж неточність інтуїтивного поняття алгоритму? У неточності тих термінів, в яких ми його висловили. До цих пір йдуть суперечки про те, що таке мова. Також незрозумілий сенс таких слів, як «зрозумілість» і «точність». Науковий сенс неясний. А інтуїтивне значення цих слів ясно.

Глава 2

СТВОРЕННЯ АЛГОРИТМІВ

§ 1. Роль алгоритмів в науці і техніці

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

Особливе значення мають алгоритми, накопичені в математиці, тому що математика пронизує інші науки та її багатство є багатством всіх наук. Вже досить давно вчені та інженери помітили, що якщо вдалося отримати алгоритм вирішення якої-небудь завдання, то можна створити машину, яка вирішувала б це завдання, тобто можна автоматизувати її рішення. Практика вперто підтверджувала цей факт. Наука його пояснила повністю тільки недавно. Читач познайомиться з цим у § 3 гл. 6.

Алгоритми є: 1) формою викладу наукових результатів; 2) керівництвом до дії при вирішенні вже вивчених проблем і, як наслідок: 3) засобом, що дозволяє економити розумову працю; 4) необхідним етапом при автоматизації вирішення завдань; 5) середовищ-ством (інструментом ), використовуваним при дослідженні та вирішенні нових проблем (особливо це стосується математичних алгоритмів); 6) одним із засобів обгрунтування математики (див. гл. 4); 7) одним із засобів опису складних процесів (див. гл. 9, 10).

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

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

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

§ 2. Як виникають алгоритми

Одним з джерел алгоритмів є практика, яка надає нам дві основні можливості: спостереження і експеримент (а також будь-які їх комбінації).

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

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

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

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

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

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

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

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

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

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

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

Перерахуємо найбільш часто застосовуються прийоми.

1) Конструювання алгоритмів. Цей прийом полягає в тому, що новий алгоритм отримують комбінуванням вже відомих алгоритмів як складових частин.

2) Еквівалентні перетворення алгоритмів. Два алгоритму називають еквівалентними, якщо: а) всякий варіант вихідного даного, допустимий для одного з них, допустимо і для іншого, б) застосовність одного алгоритму до якого-небудь вихідного даному гарантує, що й інший алгоритм застосуємо до цього вихідного даним, в) результати, що даються цими алгоритмами для одного і того ж вихідного даного, між собою однакові. Зауважу, що абсолютно неправильно еквівалентні алгоритми називати різними формами одного і того ж алгоритму.

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

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

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

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

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

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

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

Алгоритми, отримані в результаті винахідливості розробника, також вимагають обгрунтування. Зазвичай з ними чинять або як з емпіричними, або (вже після їх отримання) проробляють всі дії, передбачені формальним методом.

§ 3. Завдання на побудову алгоритмів

Можна було б продовжити виклад і обгрунтування різних алгоритмів, накопичених в математиці. Замість цього ми лише перелічимо деякі з них, для того щоб створити в читача правильне враження про їх різноманітність і численності. Алгоритмами є правила для розв'язання систем алгебраїчних лінійних рівнянь (існує велика кількість таких правил), правила диференціювання функцій і правила інтегрування, вивчаються в курсі математичного аналізу, правило Штурма - Ліувілля знаходження наближеного значення кореня довільного рівняння f (х) = 0. Алгоритмами є також і багато інших правила для вирішення різних завдань за допомогою циркуля і лінійки, відомі читачеві з шкільного курсу. Якщо б ми надумали наводити тут усі ці алгоритми та обгрунтовувати їх коректність, то, безумовно, не довели б цю роботу до кінця з-за її великого обсягу.

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

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

У 1742 р. математик X. Гольдбах, петербурзький академік, у листі до Л. Ейлера висунув проблему: довести, що кожне ціле число, яке більше або дорівнює шести, може бути представлено у вигляді суми трьох простих чисел.

Цій проблемі можна надати наступний вигляд. Знайти алгоритм, який дозволив би для будь-якого цілого числа, більшого, ніж 6, знайти хоча б одне розкладання на три простих доданків. У відповідному листі Л. Ейлер зауважив, що для парних чисел ця проблема еквівалентна проблемі розкладання числа на два простих доданків. У 1937 р. І. М. Виноградов довів, що будь-яке досить велике непарне число представляється сумою трьох простих чисел; згодом була вказана і нижня межа, передбачувана в доказі І. М. Виноградова, так що для непарних чисел проблема Гольдбаха вже вирішена, але для парних чисел вона не вирішена і до теперішнього часу.

Зауважимо, що алгоритм її вирішення був би дуже нескладний: якщо задано парне N, потрібно було б (за допомогою алгоритму Ератосфена) знайти все не перевершують його прості числа, далі послідовно віднімати кожне з них від заданого N і дивитися, чи не міститься різниця серед вже отриманих простих чисел. Біда в тому, що до цих пір не вдалося довести коректність цього алгоритму, і тому не можна його вважати алгоритмом розкладання будь-якого парного числа на два простих доданків.

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

Завдання про квадратуру кола полягає в наступному: потрібно знайти метод (алгоритм) побудови за допомогою циркуля і лінійки квадрата, рівновеликого даному колу. Це завдання є масовою, бо вихідним даним для неї може бути будь-коло.

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

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

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

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

Це означає, що за рахунок розширення набору допустимих операцій іноді можна частину проблем, для яких немає алгоритму, зробити можна вирішити. Звичайно, якщо нічим не обмежуватися при визначенні допустимих операцій, то багато проблем стануть розв'язними (але чи всі? Про це див у § 1 гл. 5).

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

§ 4. Антиномії

У той час, коли А. Пуанкаре проголосив, що математика знайшла, нарешті, надійний фундамент, сама арифметика похитнулася через те, що в теорії множин були виявлені протиріччя (парадокси), що увійшли в історію математики під назвою антиномій.

Парадокс Рассела (відкритий в 1902 р.). Якщо парадокс Кантора виникає для безлічі, що містить себе в якості свого елемента, то парадокс Рассела пов'язаний з множинами, що не містять себе в якості своїх елементів. Для зручності будемо безліч, що не містить себе в якості елемента, називати звичайним, а багато, що містить себе в якості елемента, - незвичайним.

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

Але, може бути, воно незвичайне, і справа з кінцем? Перевіримо. Якщо воно незвичайне, то, будучи безліччю тільки звичайних, воно себе в якості елемента не містить, а значить, є звичайним. Знову протиріччя.

Цікаво, що парадокс Рассела може виникнути і для каталогів, якими ми вже користувалися для побудови парадоксу Кантора.

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

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

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

§ 5. Висновки з антиномій

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

Потрібно сказати, що математики реагували на землетрус по-різному. Одні стали у всьому сумніватися. Відомий математик Ю. Дедекінд після опублікування антиномії Рассела на деякий час припинив публікацію своїх робіт. Математик Г. Фреге кінчав у цей час видання свого великої праці, підготовці якого він присвятив десять років життя. У першій же фразі післямови він говорить, що фундамент побудованого ним будівлі похитнута парадоксом Рассела. А. Пуанкаре, про який ми вже говорили, змінив своє ставлення до теорії множин. Були, звичайно, і такі математики, які на відкриття антиномій ніяк не реагували і бездумно продовжували застосовувати теорію множин, правда, в тій її частині, в якій не виявлено антиномій. Цих математиків зазвичай називають послідовниками класицизму. Але багато математиків стали шукати шляхи усунення суперечностей.

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

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

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

Четверті угледіли причину кризи математики в тому, що ряд математичних об'єктів і методів є неконструктивними. Роз'яснимо останню точку зору.

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

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

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

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

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

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

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

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

На цьому автор хотів закінчити розділ, але раптом зрозумів, що допитливий читач, дізнавшись про те, що відбулося в математичному світі на початку XX ст., Безсумнівно захоче дізнатися - а як же справа йде зараз? Розсипалася чи математика, як картковий будиночок, або вона встояла, подолала свою кризу?

Звичайно, поява антиномій потрясло математику. Правильно й те, що криза математики ще і до цих пір повністю не подолано. Три чверті століття - занадто малий для цього термін.

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

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

ВИСНОВОК

§ 1. Чи може машина мислити?

Чи може людина вирішити алгоритмічно

нерозв'язну проблему?

Висновок повинен бути коротким. Тому дуже стисло скажімо про деякі цікаві питання, на перший погляд мають відношення до теорії алгоритмів.

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

Відомо, що мислення - це вища форма руху матерії, що протікає в мозку людини. Деякі «філософи» роблять звідси висновок, що машини не можуть мислити. Хід їх міркувань можна проілюструвати наступною схемою: оселедець - риба; акула - не оселедець; значить, вона не риба.

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

Щоб відповісти на таке складне питання, потрібно перш за все вирішити, за якими ознаками можна розпізнати здатність до мислення. Навіть серед людей є індивідууми, які не можуть мислити.

Але чи завжди можна вирішити, чи є людина мислячим чи ні? Для вирішення таких питань призначають експертні комісії і не завжди отримують ясну відповідь. Ще складніше справа в разі, коли питання ставиться не про конкретну наявної машині, а про машини взагалі, про майбутні машинах. Автор може тільки сказати: жодна з відомих машин не мислить, а чи може взагалі машина мислити? Невідомо. Але чому б і ні?

Супротивники машин в області інтелекту кажуть, що ознакою мислення є здатність вирішувати алгоритмічно нерозв'язні проблеми. Алгоритми, які відповідали б таких проблем, не існують. Значить, немає і програм. Звідси випливає, що машина (через відсутність програми) не може вирішувати алгоритмічно нерозв'язні проблеми. А ось людина - інша справа. Людина - творець. Він навіть алгоритмічно нерозв'язні проблеми може вирішувати! Цієї точки зору дотримуються не тільки прості смертні, а й деякі фахівці в галузі кібернетики. Чи мають вони рацію? Звичайно, ні! Ми пам'ятаємо, що деякі нерозв'язані проблеми полягають у тому, що пропонується побудувати неіснуючий об'єкт. Наприклад, каталог всіх несамоназивающіхся і тільки несамоназивающіхся каталогів, або каталог усіх каталогів, ціна кожного з яких на одиницю більше максимальної з цін зазначених в них книжок. Хотілося б подивитися, як вищеназвані противники машин вирішили б хоч одну з цих проблем. Щоправда, не всі нерозв'язні проблеми настільки безнадійні, як названі. Деякі нерозв'язні проблеми містять в собі розв'язні підпроблеми. Їх може вирішувати людина, але для їх вирішення можливий і алгоритм. Іншими словами, звертаючись до алгоритмічно нерозв'язних проблем, ми не встановимо відмінності між «інтелектуальними» можливостями людей і машин.

§ 2. Детермінованість машин. Самонавчання

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

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

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

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

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

Можливості самонавчання поки що малі, тому що сучасна ЕОМ дуже схожа на сліпого і глухонімого. Вона може навпомацки читати інформацію, нанесену на перфоносители, і наосліп видавати інформацію. Безумовно, оснащення машини різноманітними і численними пристроями введення і пристроями видачі інформації підвищить можливості самонавчання машин. Але ж кожна людина спершу навчається і починає це робити з моменту народження. Лише потім, маючи вже величезні запаси інформації, він починає самонавчатися.

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

§ 3. Свідомість машин. Алгоритмічне моделювання

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

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

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

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

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

Будучи математичної дисципліною, теорія алгоритмів на відміну від деяких дедуктивних, абстрактних розділів математики безпосередньо вивчає певні явища реального світу. Її слід віднести до так званої прикладної математики.

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

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

Це означає, що сучасна теорія алгоритмів охоплює всі практично важливі випадки. Її подальші узагальнення пов'язані з узагальненням поняття конструкції. Сьогоднішні потреби теорії ЕОМ і програмування вона може забезпечити.

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

З широкого формального визначення алгоритму випливає, що алгоритм не тільки може, вирішуючи завдання, переробляти свій запис, але може переробляти і запис свого алгоритму виконання. Для цього потрібно більш чітко пригадати його «тата» (алгоритм виконання), який теж алгоритм і має свого «тата», що припадає нашому алгоритмом «дідусем». Це означає, що, працюючи, алгоритм виконання може переробляти і себе. Позначаючи вихідне дане через s _it j, алгоритм-через _t t, а результат-через _р р _{_},} можемо скласти формулу з якої зазначена можливість і витікає.

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

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

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

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

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

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

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

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

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

Нарешті зрозуміли, що саме математичний опис прототипу можна вважати його моделлю (математичної). Ця проста думка стала результатом тривалих досліджень та роздумів. Зараз її справедливість не викликає сумнівів! Математичну теорію моделей можна знайти в книгах з абстрактної алгебри і в книгах з математичної логіки. Абстрактна алгебра стверджує, що модель - це безліч, на якому задана деяка сукупність відносин. Логіка розглядає моделі систем аксіом - множини, елементи яких такі, що властивості цих елементів задовольняють зазначеним аксіомам і наслідкам з них. Ми бачимо вже три різних визначення математичної моделі. Два останніх є окремими випадками першого. Повторимо його: математичної моделлю прототипу називається деяке його математичний опис. Це математичний опис може бути вироблено різними математичними засобами. Зокрема, опис прототипу може бути алгоритмічним, а якщо воно розраховане на застосування ЕОМ, то - програмним.

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

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

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

На закінчення даної книги скажемо кілька слів про питання, які стосуються галузі світогляду і є по відношенню до аналітичної теорії алгоритмів попередніми. Ці питання вже були дуже коротко порушені в § 5 гл. 3 і в § 3 гл. 5. Там згадувалося, що теорія алгоритмів є основою конструктивного напряму в обгрунтуванні математики. Відразу відзначимо, що конструктивні ідеї в математиці не зводяться до теорії алгоритмів, яка лише найбільш послідовна у цьому відношенні. Обмежимося лише теорією алгоритмів .. У теорії алгоритмів основою для отримання всіляких конструктивних об'єктів є деякі початкові об'єкти. Математичного обгрунтування їх конструктивності немає. З таким же правом їх можна вважати і неконструктивними. Доматематіческое їх обгрунтування полягає в тому, що їх практичне існування або (якщо це операції) практична можливість їх виконання ні в кого не викликають сумніву. У логічних теоріях алгоритмів початковими є букви, слова і деякі операції (наприклад, в теорії нормальних алгоритмів - марковські підстановки); первісної є також здатність перетворювати будь-яку символьну конструкцію в слово. Питання про те, звідки беруться слова-операнди ні явно, ні неявно не зачіпається. В аналітичній теорії алгоритмів початковими є букви, зв'язку, і натуральні операції. Символьні конструкції з букв і зв'язків виходять вже засобами теорії (тому до складу теорії алгоритмів входить розділ про формальні мовами). Поняття актуальної нескінченності ні явно, ні неявно не залучається. Різночитання символьних конструкцій теж немає. Доматематіческім їх обгрунтуванням є визнання існування реального світу, абстрактними образами об'єктів і процесів якого є символьні конструкції і алгоритми. Застосовувані мови тому наділені змістом. Здатність перетворювати будь-яку символьну конструкцію в слово не вважається первинною і забезпечується можливістю обмеженого застосування довільного вибору з кінцевого числа елементів (у процесі довільної нумерації з подальшим отриманням результатів усіх можливих нумерацій і вибору з них одного, лексикографічно не старше всіх інших).

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