Що таке алгоритм?

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

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

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

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

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

Визначення і ознаки алгоритму

Єдиного «істинного» визначення поняття «алгоритм» немає (див. перелік визначень).

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

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

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

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

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

Чудовий сам термін «алгоритм». У самому справі, чи багато існує математичних термінів, в яких входить географічна назва? Подібну назву не відразу розгледиш в слові «алгоритм», однак воно там є … »» »Див. Звідки взялося слово алгоритм?

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

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

Близько 1250 року англійський астроном і математик Іоанн Сакробоско написав працю з арифметики «Algorismus vulgaris», на сторіччя став основним підручником з обчисленням у десятковій позиційній системі числення в багатьох європейських університетах. У вступі Сакробоско назвав автором науки про рахунок мудреця на ім'я Алгус (Algus). А в популярній середньовічної поеми «Роман про троянду» (1275-1280) Жана де Мена «грецький філософ Алгус» ставиться в один ряд з Платоном, Аристотелем, Евклідом і Птолемеєм! Зустрічався також варіант написання імені Аргус (Argus). І хоча, згідно з давньогрецькою міфологією, корабель «Арго» був побудований Ясоном, саме цьому Арго приписувалося будівництво корабля.

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

Однак з часом такі пояснення все менше займали математиків, і слово 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»). Розуміння Ейлером алгоритму як синоніма способу вирішення завдання вже дуже близько до сучасного.

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

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

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


Category: Медицина і здоров'я

Comments (Прокоментуй!)

There are no comments yet. Why not be the first to speak your mind.

Leave a Reply