Алгори́тм ( algorithmi за араб. ім'ям перського математика аль-Хорезмі) — набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій. Для візуалізації алгоритмів часто використовують блок-схеми.
Для комп'ютерних програм алгоритм є списком деталізованих інструкцій, що реалізують процес обчислення, який, починаючи з початкового стану, відбувається через послідовність логічних станів, яка завершується кінцевим станом. Перехід з попереднього до наступного стану не обов'язково детермінований — деякі алгоритми можуть містити елементи випадковості.
Поняття алгоритму належить до основ математики. Обчислювальні процеси алгоритмічного характеру (як-то арифметичні дії над цілими числами, знаходження НСД двох чисел тощо) відомі людству з глибокої давнини. Проте чітке поняття алгоритму сформувалося лише на початку XX століття.
Часткова формалізація поняття алгоритму розпочалася зі спроб розв'язати задачу розв'язності (), яку сформулював Давид Гільберт 1928 року. Наступні формалізації були необхідні для визначення ефективної обчислювальностіKleene 1943 in Davis 1965:274 або «ефективного методу»Rosser 1939 in Davis 1965:225; до цих формалізацій належать рекурсивні функції Геделя—Ербрана—Кліні 1930, 1934 та 1935 років, λ-числення Алонзо Черча 1936 р., «Формулювання 1» Еміля Поста 1936 року та машина Тюрінга, яку розробив Алан Тюрінг протягом 1936, 1937 та 1939 років.
В методології алгоритм є базисним поняттям і складає основу опису методів. З методології виходить якісно нове поняття алгоритму як оптимальність з наближенням до прогнозованого абсолюту. Зробивши все в послідовності алгоритму за граничних умов задачі, маємо ідеальне рішення нагальних проблем науково-практичного характеру. В сучасному світі алгоритм будь-якої діяльності у формалізованому вигляді складає основу навчання на прикладах за подібністю. На основі подібності алгоритмів різних сфер діяльності була сформована концепція (теорія) експертних систем.
Історія Слово «алгоритм» походить від імені перського математика й астронома Аль-Хорезмі. Приблизно 825 року він написав трактат, в якому описав придуману в Індії позиційну десяткову систему числення.
У першій половині XII ст. твір Аль-Хорезмі потрапив до Європи в перекладі латиною під назвою «Algoritmi de numero Indorum» («Алгоритми про індійську лічбу»). Вважається, що Algoritmi відповідає невдалій латинізації імені Аль-Хорезмі, проте через неправильне тлумачення його як іменника в множині ним стали називати метод обчислення.
У 1843 р. Ада Лавлейс описала алгоритм обчислення чисел Бернуллі на аналітичній машині Беббіджа. Цей алгоритм визнано першою програмою, спеціально реалізованою для виконання на ЕОМ, і через це його розробницю вважають першим програмістом, дарма що машина Беббіджа не була сконструйована за життя Ади.
З 1930-х рр. починається бурхливий розвиток дослідження алгоритмів і становлення інформатики в її сучасному вигляді. 1935 року Стівен Кліні розробив перше формулювання теорії обчислюваності та показав еквівалентність розробленої системи частково рекурсивним функціям. 1936 року незалежно були опубліковані роботи Алана Тюрінга та Еміля Поста, в яких подано подібні системи для визначення поняття алгоритму. А вже 1937 року було доведено еквівалентність різних визначень(Розділ «Algorithms» в Bauer, 2010).
Машина Тюрінга пропонувала конструкцію, придатну для автоматичної інтерпретації. Побудована під впливом Алана Тюрінга у Великій Британії обчислювальна система ACE (завершена 1950 року) та системи, побудовані за архітектурою фон Неймана в США та в інших країнах (в СРСР — МЕОМ, яку розробила 1950 року в Інституті електротехніки АН УРСР група вчених під керівництвом Сергія Лебедєва), були першими універсальними обчислювальними пристроями, які повністю задовольняли вимоги обчислюваності.
Протягом 1935-1960 років було висловлено численні ідеї та розроблено технології, які лягли в основу сучасної інформатики.
Формальні засоби для представлення алгоритмів мали не лише теоретичну значущість. Розробка алгоритмічних мов для програмування обчислювальних пристроїв розпочалась 1951 року з публікації німецького інженера (). Спочатку важливою здавалася проблема нотації, її досліджував Олексій Ляпунов, але поступово вона відійшла на другий план(Розділ «Algorithmic Languages» в Bauer, 2010).
Першу мову програмування, Планкалкюль (), розроблено Конрадом Цузе 1946 року, але через відсутність компіляторів виконання написаних цією мовою програм було неможливим. Опис мови був надрукований у 1972 році, а 2000 року був створений компілятор для підмножини мови.(Розділ 3.2 в O'Regan, 2008)
В середині 1950-х було розроблено мову програмування Фортран Джоном Бекусом з IBM. Наприкінці 1950-х розроблено ALGOL та COBOL; для навчальних цілей BASIC (1963) та Pascal (початок 1970-х). Для системного програмування в Bell Laboratories було розроблено мову C(Розділ 3.3 в O'Regan, 2008).
Лямбда-числення дало поштовх до створення наприкінці 1950-х функційної мови програмування Lisp. На основі ідей Lisp було створено Scheme. Мову ML розробив Робін Мілнер наприкінці 1970-х. Наприкінці 1980-х було створено мову Haskell(Розділ 3.5 в O'Regan, 2008).
Під впливом досліджень в галузі штучного інтелекту розроблено парадигму логічного програмування. На відміну від імперативної та функційної парадигм, логічне програмування не вимагає від розробника описання способу розв'язання поставленої задачі. Planner — першу мову логічного програмування розробили 1969 року. На початку 1970-х розробили Пролог, який згодом став найпоширенішою мовою логічного програмування зі стандартом ISO, затвердженим у 1995 році(Розділ 3.6 в O'Regan, 2008).
Визначення
Неформальне визначення Кожен алгоритм передбачає існування початкових (вхідних) даних та в результаті роботи призводить до отримання певного результату. Робота кожного алгоритму відбувається шляхом виконання послідовності деяких елементарних дій. Ці дії називають кроками, а процес їх виконання називають алгоритмічним процесом. В такий спосіб відзначають властивість дискретності алгоритму(Игошин, с. 314).
Важливою властивістю алгоритмів є масовість, або можливість застосування до різних вхідних даних. Тобто, кожен алгоритм покликаний розв'язувати клас однотипних задач.
Необхідною умовою, яка задовольняє алгоритм, є детермінованість, або визначеність. Це означає, що виконання команд алгоритму відбувається у єдиний спосіб та призводить до однакового результату для однакових вхідних даних.
Вхідні дані алгоритму можуть бути обмежені набором припустимих вхідних даних. Застосування алгоритму до неприпустимих вхідних даних може призводити до того, що алгоритм ніколи не зупиниться, або потрапить в тупиковий стан (зависання) з якого не зможе продовжити виконання.
Формальне визначення
Різноманітні теоретичні проблеми математики та прискорення розвитку фізики та техніки поставили на порядок денний точніше визначення поняття алгоритму.
Перші спроби уточнення поняття алгоритму та його дослідження здійснювали в першій половині XX століття Алан Тюрінг, Еміль Пост, Жак Ербран, Курт Гедель, Андрій Марков, Алонзо Черч. Було розроблено декілька означень поняття алгоритму, але згодом було з'ясовано, що всі вони визначають одне й те саме поняття (див. теза Черча).(Игошин, с. 317)
Машина Тюрінга
Машина Тюрінга — це абстрактна машина (автомат), що працює зі стрічкою окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок, яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ з комірки, на яку вказує голівка, та, на основі зчитаного символу й внутрішнього стану робить наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку, або пересунути голівку на одну комірку ліворуч або праворуч.
На основі дослідження цих машин було висунуто тезу Тюрінга (основна гіпотеза алгоритмів): Для знаходження значень функції, заданої в деякому алфавіті, тоді і лише тоді існує деякий алгоритм, коли функція обчислювана за Тюрінгом, тобто, коли її можна обчислити на придатній машині Тюрінга.
Ця теза є аксіомою, постулатом, і не може бути доведена математичними методами, оскільки алгоритм не є точним математичним поняттям.
Рекурсивні функції
З кожним алгоритмом можна зіставити функцію, яку він обчислює. Однак постає питання, чи можна довільній функції зіставити машину Тюрінга, а якщо ні, то для яких функцій існує алгоритм? Дослідження цих питань призвело до створення в 1930-х роках теорії рекурсивних функцій(Игошин, розділ 33).
Клас обчислюваних функцій було описано в спосіб, що нагадує побудову деякої аксіоматичної теорії на базі системи аксіом. Спочатку було вибрано найпростіші функції, обчислюваність яких очевидна. Потім було сформульовано правила (оператори) побудови нових функцій на основі вже існуючих. Необхідний клас функцій складається з усіх функцій, які можна отримати з найпростіших застосуванням операторів.
Подібно тезі Тюринга в теорії обчислюваних функцій висунуто гіпотезу, що має назву теза Черча: Числова функція тоді і лише тоді алгоритмічно обчислювана, коли вона частково рекурсивна.
Доведення того, що клас обчислюваних функцій збігається з обчислюваними за Тюрінгом відбувається в два кроки: спочатку доводять обчислюваність найпростіших функцій на машині Тюрінга, а потім — обчислюваність функцій, отриманих внаслідок застосування операторів.
Таким чином, неформально алгоритм можна визначити як чітку систему інструкцій, що визначають дискретний детермінований процес, який веде від початкових даних (на вході) до шуканого результату (на виході), якщо він існує, за скінченну кількість кроків; якщо шуканого результату не існує, алгоритм або ніколи не завершує роботу, або заходить у глухий кут.
Нормальні алгоритми Маркова
Нормальні алгоритми Маркова — це система послідовних застосувань підстановок, які реалізують певні процедури отримання нових слів з базових, побудованих із символів деякого алфавіту. Як і машини Тюрінга, нормальні алгоритми не виконують самих обчислень: вони лише виконують перетворення слів шляхом заміни літер за заданими правиламиЕнциклопедія кібернетики, т. 2, c. 90-91..
Нормально обчислюваною називають функцію, яку можна реалізувати нормальним алгоритмом. Тобто, алгоритмом, який кожне слово з множини припустимих даних функції перетворює на її вихідні значення(Игошин, розділ 34).
Творець теорії нормальних алгоритмів А. А. Марков висунув гіпотезу, яка отримала назву принцип нормалізації Маркова: Для знаходження значень функції, заданої в деякому алфавіті, тоді і лише тоді існує деякий алгоритм, коли функція нормально обчислювана. Подібно до тез Тюрінга та Черча, принцип нормалізації Маркова не може бути доведений математичними засобами.
Стохастичні алгоритми
Однак, наведене вище формальне визначення алгоритму в деяких випадках може бути надто строгим. Інколи виникає потреба у використанні випадкових величин. Алгоритм, робота якого визначається не лише вхідними даними, але й значеннями отриманими з генератора випадкових чисел, називають стохастичним (або рандомізованим, від ). Формально, такі алгоритми не можна називати алгоритмами оскільки існує імовірність (близька до нуля), що вони не зупиняться. Проте, стохастичні алгоритми часто бувають ефективнішими за детерміновані, а в окремих випадках — єдиним способом розв'язати задачу.
На практиці замість генератора випадкових чисел використовують генератор псевдовипадкових чисел.
Однак слід відрізняти стохастичні алгоритми та методи, які дають із високою ймовірністю правильний результат. На відміну від методу, алгоритм дає коректні результати навіть після тривалої роботи.
Деякі дослідники припускають можливість того, що стохастичний алгоритм дасть із певною наперед відомою ймовірністю неправильний результат. Тоді стохастичні алгоритми можна поділити на два типи(Розділ 12, с. 12-22 в Atallah, 2010): алгоритми типу Лас-Вегас завжди дають коректний результат, але час їхньої роботи невизначений.