Формальні властивості алгоритмів

Алгоритм. від імені учёногоаль-Хорезмі (перс. خوارزمی [al-Khwārazmī]) - точний наборінструкцій. описують порядок дій виконавця для досягнення результатарешенія завдання за кінцеве час. У старій трактуванні замість слова «порядок» використовувалося слово «послідовність», але в міру розвитку паралельності в роботі комп'ютерів слово «послідовність» стали замінювати більш загальним словом «порядок». Це пов'язано з тим, що робота якихось інструкцій алгоритму може бути залежна від інших інструкцій або результатів їх роботи. Таким чином, деякі інструкції повинні виконуватися строго після завершення роботи інструкцій, від яких вони залежать. Незалежні інструкції або інструкції, що стали незалежними через завершення роботи інструкцій, від яких вони залежать, можуть виконуватися в довільному порядку, паралельно або одночасно, якщо це дозволяють використовувані процесор і операційна система.

Раніше часто писали «алгоріф м», зараз таке написання використовується рідко, але, тим не менше, має місце (наприклад, Нормальний алгоріфмМаркова).

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

Різні визначення алгоритму в явній або неявній формі містять наступний ряд загальних вимог:

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

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

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

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

Масовість (універсальність). Алгоритм повинен бути застосовний до різних наборів вихідних даних.

Результативність - завершення алгоритму певними результатами.

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

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

Історія терміна

Сучасне формальне визначення алгоритму було дано в 30-50-х роках XX століття в работахТьюрінга, Посту, Черча (теза Черча - Тьюринга), Н. Вінера, А. А. Маркова.

Саме слово «алгоритм» походить від імені вченого Абу Абдуллах Мухаммеда ібн Муса аль-Хорезмі (алгоритм - аль-Хорезмі). Около825 року він написав твір, в якому вперше дав опис придуманої в Індії позиційної десяткової системи числення. На жаль, арабська оригінал книги не зберігся. Аль-Хорезмі сформулював правила обчислень в новій системі і, ймовірно, вперше іспользовалціфру 0 для позначення пропущеної позиції в записі числа (її індійське назва араби перевели какas-sifr або простоsifr. Звідси такі слова, як «цифра» і «шифр»). Приблизно в цей же час індійські цифри почали застосовувати і інші арабські вчені. У першій половінеXII століття книга аль-Хорезмі в латинському перекладі проникла в Європу. Перекладач, ім'я якого до нас не дійшло, дав їй названіеAlgoritmi de numero Indorum ( «Алгоритми про рахунок індійському»). По-арабськи ж книга іменоваласьКітаб аль-джебр валь-мукабала ( «Книга про складання і віднімання»). З оригінальної назви книги відбувається словоАлгебра (алгебра - аль-джебр).

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

Одні виводили algorism з греческіхalgiros (хворий) іarithmos (число). З такого пояснення не дуже ясно, чому числа саме «хворі». Або ж лінгвістам хворими здавалися люди, які мають нещастя займатися обчисленнями? Своє пояснення пропонував іенціклопедіческій словник Брокгауза і Ефрона. У нёмалгоріфм (до речі, до революції використовувалося напісаніеалгоріѳм. Черезфіту) проводиться «від арабського слова Аль-Горетм, тобто корінь». Зрозуміло, ці пояснення навряд чи можна вважати переконливими.

Згаданий вище переклад твору аль-Хорезмі став першою ластівкою, і протягом декількох наступних століть з'явилося безліч інших праць, присвячених все того ж питання - навчання мистецтву рахунку за допомогою цифр. І всі вони в назві мали слово algoritmi іліalgorismi.

"Алгорізм був придуманий в Греції. Це частьаріфметікі. Придуманий він був майстром на ім'я Алгорізм, який дав йому своє ім'я. І оскільки його звали Алгорізм, Він назвав свою книгу« Алгорізм ».

«Майстер Алгус» (або Аргус) став в середньовічній літературі уособленням рахункового мистецтва. І в уже згадуваній «Романе про троянді», і в відомої італійської поемі «Квітка», написаної Дуранте. є фрагменти, в яких йдеться про те, що навіть «mestre Argus» не зможе підрахувати, скільки разів сваряться і миряться закохані. Англійська поетДжефрі Чосер в поемі «Книга герцогині» (1369 г.) пише, що навіть «славний лічильник Аргус» (noble countour Argu) не зможе порахувати чудовиськ, що з'явилися в кошмарних баченнях герою.

Втім, грецька версія була не єдиною. Міфічний алгоритми (Algor) іменувався то королёмКастіліі (Rex quodam Castelliae), тоіндійскім королем. тоарабскім мудрецем (philosophus Algus nomine Arabicus).

Однак з часом такі пояснення все менше займали математиків, і слово algorism (іліalgorismus), незмінно присутнє в назвах математичних творів, знайшло значення способу виконання арифметичних дій за допомогою арабських цифр, тобто на папері, без іспользованіяабака. Саме в такому значенні воно увійшло у многіеевропейскіе мови. Наприклад, з позначкою «устар.» Воно присутнє в представницькому словнику англійської язикаWebster's New World Dictionary. виданому в1957 р

Алгоритм - це мистецтво рахунку за допомогою цифр, але спочатку слово «цифра» відносилося лише до нуля. Знаменитий французький труверГотье де Куанса (Gautier de Coincy, 1177-1236) в одному з віршів використовував словаalgorismus-cipher (які означали цифру 0) як метафору для характеристики абсолютно нікчемного людини. Очевидно, розуміння такого способу вимагало відповідної підготовки слухачів, а це означає, що нова система числення вже була їм досить добре відома.

Багато століть абак був фактично єдиним засобом для практичних обчислень, їм користувалися і купці, і міняйли, і вчені. Переваги обчислень на лічильної дошці роз'яснював в своїх творах такий видатний мислитель, як Герберт Аврілакского (938-1003), що став в 999 г.папой римським під ім'ям Сильвестра II. Нове з величезними труднощами пробивало собі дорогу, і в історію математики увійшло наполегливе протистояння таборів алгорісміков іабацістов (іноді званих гербекістамі), які пропагували використання для обчислень абака замість арабських цифр. Цікаво, що відомий французький математікНіколя Шюке (Nicolas Chuquet, 1445-1488) в реєстр платників податків городаЛіона був вписаний як алгорісмік (algoriste). Але пройшло не одне століття, перш ніж новий спосіб рахунку остаточно утвердився, стільки часу знадобилося, щоб виробити загальновизнані позначення, вдосконалити і пристосувати до запису на папері методи обчислень. У Західній Європі вчителів математики аж доXVII століття продовжували називати «магістрами абака», як, наприклад, математікаНікколо Тарталья (1500-1557).

Отже, твори з мистецтва рахунку називалися Алгоритмами. З багатьох сотень можна виділити і такі незвичайні, як написаний у віршах трактатCarmen de Algorismo (латінскоеcarmen і означає вірші) Олександра де Вілла Деї (Alexander de Villa Dei, розум. 1240) або підручник віденського астронома і математікаГеорга Пурбаха (Georg Peurbach, 1423-1461 ) Opus algorismi jocundissimi ( «веселий твір за алгоритмом»).

Поступово значення слова розширювалося. Вчені починали застосовувати його не тільки до суто обчислювальним, а й до інших математичних процедур. Наприклад, близько 1360 г. французький філософ Микола Орем (Nicolaus Oresme, 1323 / 25-1382) написав математичний трактатAlgorismus proportionum ( «Обчислення пропорцій»), в якому вперше використав ступеня з дробовими показниками і фактично впритул підійшов до ідеї логарифмів. Коли ж на зміну абаку прийшов так званий рахунок на лініях, численні керівництва по ньому стали називатьAlgorithmus linealis. тобто правила рахунку на лініях.

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

У 1684 годуГотфрід Лейбніц в сочіненііNova Methodvs pro maximis et minimis, itemque tangentibus ... вперше використав слово «алгоритм» (Algorithmo) в ще більш широкому сенсі: як систематичний спосіб вирішення проблем диференціального обчислення.

У XVIII столітті в одному з німецьких математичних словників, Vollstandiges mathematisches Lexicon (виданому вЛейпціге в1747 р), термінalgorithmus все ще пояснюється як поняття про чотирьох арифметичних операціях. Але таке значення не було єдиним, адже термінологія математичної науки в ті часи ще тільки формувалася. Зокрема, вираженіеalgorithmus infinitesimalis застосовувалося до способів виконання дій з нескінченно малими величинами. Користувався словом алгоритм іЛеонард Ейлер. одна з робіт якого так і називається - «Використання нового алгоритму для вирішення проблеми Пелля» (De usu novi algorithmi in problemate Pelliano solvendo). Ми бачимо, що розуміння Ейлером алгоритму як синонім способу вирішення завдання вже дуже близько до сучасного.

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

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

Таким чином, слово «алгоритм» розумілося першими українськими математиками так само, як і в Західній Європі. Однак його не було ні в знаменитому словнику В. І. Даля. ні через сто років в «Тлумачному словнику української мови» за редакцією Д. Н. Ушакова (1935 р). Зате слово «алгорифм» можна знайти і в популярному дореволюціонномЕнціклопедіческом словнику братів Гранат. і в першому ізданііБольшой радянської енциклопедії (Вікіпедія), виданому в 1926 р І там, і там воно трактується однаково: як правило, за яким виконується та чи інша з чотирьох арифметичних дій в десятковій системі числення. Однак до початку XX в. для математиків слово «алгоритм» вже означало будь-арифметичний або алгебраїчний процес, що виконується за строго визначеними правилами, і це пояснення також дається в наступних виданнях Вікіпедія.