Алгоритм (Від латинської форми імені середньоазіатського математика аль-Хорезмі) - правило дій, послідовність проведення обчислювальних операцій, спосіб знаходження шуканого результату.
У традиційному трактуванні алгоритм - це точний набір інструкцій, що описують послідовність дій виконавця для досягнення результату рішення задачі за кінцевий час. У міру розвитку паралельності в роботі комп'ютерів слово «послідовність» стали замінювати більш загальним словом «порядок». Це пов'язано з тим, що якісь дії алгоритму повинні бути виконані тільки один за одним, але якісь можуть бути і незалежними. Раніше часто писали «алгорифм», зараз таке написання використовується рідко.
Часто в якості виконавця виступає деякий механізм (комп'ютер, токарний верстат, швейна машина), але поняття алгоритму необов'язково відноситься до комп'ютерних програм, так, наприклад, чітко описаний рецепт приготування страви також є алгоритмом - в такому випадку виконавцем є людина.
Поняття алгоритму - одне з основних у програмуванні та інформатики. Запис алгоритму на формальному мові називається програмою. Іноді саме поняття алгоритму ототожнюється з його записом, так що слова «алгоритм» і «програма» - майже синоніми.
Визначення і ознаки алгоритму
Єдиного «істинного» визначення поняття «алгоритм» немає, (див. ).
Сучасне формальне визначення алгоритму було розроблено в 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 в. для математиків слово «алгоритм» вже означало будь арифметичний або алгебраїчний процес, що виконується за суворо визначеними правилами, і це пояснення також дається в БСЕ.
Алгоритми ставали предметом все більш пильної уваги вчених, і поступово це поняття посіло одне з центральних місць у сучасній математиці. Що ж стосується людей, від математики далеких, то до початку сорокових років це слово вони могли почути хіба що під час навчання в школі, в поєднанні «алгоритм Евкліда». Незважаючи на це, алгоритм все ще сприймався як термін суто спеціальний, що підтверджується відсутністю відповідних статей в менш об'ємних виданнях. Зокрема, його немає навіть у десятитомной Малої Радянської Енциклопедії (1957), не кажучи вже про однотомних енциклопедичних словниках. Але зате через десять років, в третьому виданні Великої радянської енциклопедії (1969) алгоритм вже характеризується як одна з основних категорій математики, «що не володіють формальним визначенням у термінах більш простих понять, і абстрагіруемие безпосередньо з досвіду». Відмінність навіть від трактування першим виданням Вікіпедія разюча! За сорок років алгоритм перетворився на одне з ключових понять математики, і визнанням цього стало включення слова вже не в енциклопедії, а в словники. Наприклад, воно присутнє в академічному «Словнику російської мови» (1981) саме як термін з області математики.
Одночасно з розвитком поняття алгоритму поступово відбувалася і його експансія з чистої математики в інші сфери. І початок їй поклало поява комп'ютерів, завдяки якому слово «алгоритм» увійшло в 1985 р під асі шкільні підручники інформатики та знайшло нове життя. Взагалі можна сказати, що його сьогоднішня популярність напряму пов'язана зі ступенем поширення комп'ютерів. Наприклад, у третьому томі «Дитячої енциклопедії» (1959) про обчислювальних машинах йдеться чимало, але вони ще не стали чимось звичним і сприймаються скоріше як якийсь атрибут світлого, але досить далекого майбутнього. Відповідно і алгоритми жодного разу не згадуються на її сторінках. Але вже на початку 70-х рр. минулого сторіччя, коли комп'ютери перестали бути екзотичної дивиною, слово «алгоритм» стрімко входить в ужиток. Це чуйно фіксують енциклопедичні видання. В «Енциклопедії кібернетики» (1974) у статті «Алгоритм» він уже зв'язується з реалізацією на обчислювальних машинах, а в «Радянської військової енциклопедії» (1976) навіть з'являється окрема стаття «Алгоритм рішення задачі на ЕОМ».
За останні півтора-два десятиліття комп'ютер став невід'ємним атрибутом нашого життя, комп'ютерна лексика стає все більш звичною. Слово «алгоритм» в наші дні відомо, ймовірно, кожному. Воно впевнено зробило крок навіть в розмовну мову, і сьогодні ми нерідко зустрічаємо в газетах і чуємо у виступах політиків вислови на кшталт «алгоритм поведінки», «алгоритм успіху» або навіть «алгоритм зради». Академік М.М. Моісеєв назвав свою книгу «Алгоритми розвитку», а відомий лікар - «Алгоритм здоров'я» та «Алгоритми розуму». Слово збагачувалося все новими значеннями і смисловими відтінками.
Види алгоритмів
Особливу роль виконують прикладні алгоритми, призначені для вирішення певних прикладних задач. Алгоритм вважається правильним, якщо він відповідає вимогам завдання (наприклад, дає фізично правдоподібний результат). Алгоритм (програма) містить помилки, якщо для деяких вихідних даних він дає неправильні результати, збої, відмови або не дає жодних результатів взагалі. Остання теза використовується в олімпіадах з алгоритмічного програмування, щоб оцінити складені учасниками програми.
Важливу роль відіграють рекурсивні алгоритми (алгоритми, що викликають самі себе до тих пір, поки не буде досягнуто деяке умова повернення). Починаючи з кінця XX - початку XXI століття активно розробляються паралельні алгоритми, призначені для обчислювальних машин, здатних виконувати кілька операцій одночасно.
Наявність вихідних даних і деякого результату
Алгоритм - це точно певна інструкція, послідовно застосовуючи яку до вихідних даних, можна отримати рішення задачі. Для кожного алгоритму є деяке безліч об'єктів, допустимих в якості вихідних даних. Наприклад, в алгоритмі ділення дійсних чисел ділене може бути будь-яким, а дільник не може бути рівний нулю.
Алгоритм служить, як правило, для вирішення не однієї конкретної задачі, а деякого класу задач. Так, алгоритм складання застосуємо до будь-якій парі натуральних чисел. У цьому виражається його властивість масовості, тобто можливості застосовувати багаторазово один і той же алгоритм для будь-якої задачі одного класу.
Для розробки алгоритмів і програм використовується алгоритмизация - процес систематичного складання алгоритмів для вирішення поставлених прикладних завдань. Алгоритмізація вважається обов'язковим етапом у процесі розробки програм і вирішенні завдань на ЕОМ. Саме для прикладних алгоритмів і програм принципово важливі детермінованість, результативність і масовість, а також правильність результатів вирішення поставлених завдань.
Форма алгоритмів
Алгоритм може бути записаний словами і зображений схематично. Зазвичай спочатку (на рівні ідеї) алгоритм описується словами, але в міру наближення до реалізації він знаходить все більш формальні обриси і формулювання мовою, зрозумілою виконавцю (наприклад, машинний код). Наприклад, для опису алгоритму застосовуються блок-схеми. Іншим варіантом опису, не залежною від мови програмування, є псевдокод.
Ефективність алгоритмів
Хоча у визначенні алгоритму потрібно лише кінцівку числа кроків, необхідних для досягнення результату, на практиці виконання навіть хоча б мільярда кроків є занадто повільним. Також зазвичай є інші обмеження (на розмір програми, на допустимі дії). У зв'язку з цим вводять такі поняття, як складність алгоритму (временнaacute-я, за розміром програми, обчислювальна та ін.). Для кожного завдання може існувати безліч алгоритмів, що призводять до мети. Збільшення ефективності алгоритмів становить одну із завдань сучасної інформатики.
Джерела:
Додатково:
Звідки взялося слово алгоритм?