Loading AI tools
послідовність інструкцій для виконання завдання З Вікіпедії, вільної енциклопедії
Алгори́тм (латинізов. Algorithmi за араб. ім'ям перського математика аль-Хорезмі) — набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій. Для візуалізації алгоритмів часто використовують блок-схеми.
Для комп'ютерних програм алгоритм є списком деталізованих інструкцій, що реалізують процес обчислення, який, починаючи з початкового стану, відбувається через послідовність логічних станів, яка завершується кінцевим станом. Перехід з попереднього до наступного стану не обов'язково детермінований — деякі алгоритми можуть містити елементи випадковості.
Поняття алгоритму належить до основ математики. Обчислювальні процеси алгоритмічного характеру (як-то арифметичні дії над цілими числами, знаходження НСД двох чисел тощо) відомі людству з глибокої давнини. Проте чітке поняття алгоритму сформувалося лише на початку XX століття.
Часткова формалізація поняття алгоритму розпочалася зі спроб розв'язати задачу розв'язності (нім. Entscheidungsproblem), яку сформулював Давид Гільберт 1928 року. Наступні формалізації були необхідні для визначення ефективної обчислювальності[1] або «ефективного методу»[2]; до цих формалізацій належать рекурсивні функції Геделя—Ербрана—Кліні 1930, 1934 та 1935 років, λ-числення Алонзо Черча 1936 р., «Формулювання 1» Еміля Поста 1936 року та машина Тюрінга, яку розробив Алан Тюрінг протягом 1936, 1937 та 1939 років.
В методології алгоритм є базисним поняттям і складає основу опису методів. З методології виходить якісно нове поняття алгоритму як оптимальність з наближенням до прогнозованого абсолюту. Зробивши все в послідовності алгоритму за граничних умов задачі, маємо ідеальне рішення нагальних проблем науково-практичного характеру. В сучасному світі алгоритм будь-якої діяльності у формалізованому вигляді складає основу навчання на прикладах за подібністю. На основі подібності алгоритмів різних сфер діяльності була сформована концепція (теорія) експертних систем.
Слово «алгоритм» походить від імені перського математика й астронома Аль-Хорезмі. Приблизно 825 року він написав трактат, в якому описав придуману в Індії позиційну десяткову систему числення.
У першій половині XII ст. твір Аль-Хорезмі потрапив до Європи в перекладі латиною під назвою «Algoritmi de numero Indorum» («Алгоритми про індійську лічбу»). Вважається, що Algoritmi відповідає невдалій латинізації імені Аль-Хорезмі, проте через неправильне тлумачення його як іменника в множині ним стали називати метод обчислення.
У 1843 р. Ада Лавлейс описала алгоритм обчислення чисел Бернуллі на аналітичній машині Беббіджа. Цей алгоритм визнано першою програмою, спеціально реалізованою для виконання на ЕОМ, і через це його розробницю вважають першим програмістом, дарма що машина Беббіджа не була сконструйована за життя Ади[3].
З 1930-х рр. починається бурхливий розвиток дослідження алгоритмів і становлення інформатики в її сучасному вигляді. 1935 року Стівен Кліні розробив перше формулювання теорії обчислюваності та показав еквівалентність розробленої системи частково рекурсивним функціям. 1936 року незалежно були опубліковані роботи Алана Тюрінга та Еміля Поста, в яких подано подібні системи для визначення поняття алгоритму. А вже 1937 року було доведено еквівалентність різних визначень[4].
Машина Тюрінга пропонувала конструкцію, придатну для автоматичної інтерпретації. Побудована під впливом Алана Тюрінга у Великій Британії обчислювальна система ACE (завершена 1950 року) та системи, побудовані за архітектурою фон Неймана в США та в інших країнах (в СРСР — МЕОМ, яку розробила 1950 року в Інституті електротехніки АН УРСР група вчених під керівництвом Сергія Лебедєва), були першими універсальними обчислювальними пристроями, які повністю задовольняли вимоги обчислюваності[4].
Протягом 1935-1960 років було висловлено численні ідеї та розроблено технології, які лягли в основу сучасної інформатики.
Формальні засоби для представлення алгоритмів мали не лише теоретичну значущість. Розробка алгоритмічних мов для програмування обчислювальних пристроїв розпочалась 1951 року з публікації німецького інженера Ганса Рутісхаузера[en] (нім. Heinz Rutishauser). Спочатку важливою здавалася проблема нотації, її досліджував Олексій Ляпунов, але поступово вона відійшла на другий план[5].
Першу мову програмування, Планкалкюль (нім. Plankalkül), розробив Конрадом Цузе 1946 року, але через відсутність компіляторів виконання написаних цією мовою програм було неможливим. Опис мови був надрукований у 1972 році, а 2000 року був створений компілятор для підмножини мови.[6]
В середині 1950-х було розроблено мову програмування Фортран Джоном Бекусом з IBM. Наприкінці 1950-х розроблено ALGOL та COBOL; для навчальних цілей BASIC (1963) та Pascal (початок 1970-х). Для системного програмування в Bell Laboratories було розроблено мову C[7].
Лямбда-числення дало поштовх до створення наприкінці 1950-х функційної мови програмування Lisp. На основі ідей Lisp було створено Scheme. Мову ML розробив Робін Мілнер наприкінці 1970-х. Наприкінці 1980-х було створено мову Haskell[8].
Під впливом досліджень в галузі штучного інтелекту розроблено парадигму логічного програмування. На відміну від імперативної та функційної парадигм, логічне програмування не вимагає від розробника описання способу розв'язання поставленої задачі. Planner — першу мову логічного програмування розробили 1969 року. На початку 1970-х розробили Пролог, який згодом став найпоширенішою мовою логічного програмування зі стандартом ISO, затвердженим у 1995 році[9].
Кожен алгоритм передбачає існування початкових (вхідних) даних та в результаті роботи призводить до отримання певного результату. Робота кожного алгоритму відбувається шляхом виконання послідовності деяких елементарних дій. Ці дії називають кроками, а процес їхнього виконання називають алгоритмічним процесом. В такий спосіб відзначають властивість дискретності алгоритму[10].
Важливою властивістю алгоритмів є масовість, або можливість застосування до різних вхідних даних. Тобто, кожен алгоритм покликаний розв'язувати клас однотипних задач.
Необхідною умовою, яка задовольняє алгоритм, є детермінованість, або визначеність. Це означає, що виконання команд алгоритму відбувається у єдиний спосіб та призводить до однакового результату для однакових вхідних даних.
Вхідні дані алгоритму можуть бути обмежені набором припустимих вхідних даних. Застосування алгоритму до неприпустимих вхідних даних може призводити до того, що алгоритм ніколи не зупиниться, або потрапить в тупиковий стан (зависання) з якого не зможе продовжити виконання.
Різноманітні теоретичні проблеми математики та прискорення розвитку фізики та техніки поставили на порядок денний точніше визначення поняття алгоритму.
Перші спроби уточнення поняття алгоритму та його дослідження здійснювали в першій половині XX століття Алан Тюрінг, Еміль Пост, Жак Ербран, Курт Гедель, Андрій Марков, Алонзо Черч. Було розроблено декілька означень поняття алгоритму, але згодом було з'ясовано, що всі вони визначають одне й те саме поняття (див. теза Черча).[11]
Машина Тюрінга — це абстрактна машина (автомат), що працює зі стрічкою окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок, яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ з комірки, на яку вказує голівка, та, на основі зчитаного символу й внутрішнього стану робить наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку, або пересунути голівку на одну комірку ліворуч або праворуч.[12]
На основі дослідження цих машин було висунуто тезу Тюрінга (основна гіпотеза алгоритмів):
Ця теза є аксіомою, постулатом, і не може бути доведена математичними методами, оскільки алгоритм не є точним математичним поняттям.
З кожним алгоритмом можна зіставити функцію, яку він обчислює. Однак постає питання, чи можна довільній функції зіставити машину Тюрінга, а якщо ні, то для яких функцій існує алгоритм? Дослідження цих питань призвело до створення в 1930-х роках теорії рекурсивних функцій[13].
Клас обчислюваних функцій було описано в спосіб, що нагадує побудову деякої аксіоматичної теорії на базі системи аксіом. Спочатку було вибрано найпростіші функції, обчислюваність яких очевидна. Потім було сформульовано правила (оператори) побудови нових функцій на основі вже існуючих. Необхідний клас функцій складається з усіх функцій, які можна отримати з найпростіших застосуванням операторів.
Подібно тезі Тюринга в теорії обчислюваних функцій висунуто гіпотезу, що має назву теза Черча:
Доведення того, що клас обчислюваних функцій збігається з обчислюваними за Тюрінгом відбувається в два кроки: спочатку доводять обчислюваність найпростіших функцій на машині Тюрінга, а потім — обчислюваність функцій, отриманих внаслідок застосування операторів.
Таким чином, неформально алгоритм можна визначити як чітку систему інструкцій, що визначають дискретний детермінований процес, який веде від початкових даних (на вході) до шуканого результату (на виході), якщо він існує, за скінченну кількість кроків; якщо шуканого результату не існує, алгоритм або ніколи не завершує роботу, або заходить у глухий кут.
Нормальні алгоритми Маркова — це система послідовних застосувань підстановок, які реалізують певні процедури отримання нових слів з базових, побудованих із символів деякого алфавіту. Як і машини Тюрінга, нормальні алгоритми не виконують самих обчислень: вони лише виконують перетворення слів шляхом заміни літер за заданими правилами[14].
Нормально обчислюваною називають функцію, яку можна реалізувати нормальним алгоритмом. Тобто, алгоритмом, який кожне слово з множини припустимих даних функції перетворює на її вихідні значення[15].
Творець теорії нормальних алгоритмів А. А. Марков висунув гіпотезу, яка отримала назву принцип нормалізації Маркова:
Подібно до тез Тюрінга та Черча, принцип нормалізації Маркова не може бути доведений математичними засобами.
Однак, наведене вище формальне визначення алгоритму в деяких випадках може бути надто строгим. Інколи виникає потреба у використанні випадкових величин[16]. Алгоритм, робота якого визначається не лише вхідними даними, але й значеннями отриманими з генератора випадкових чисел, називають стохастичним (або рандомізованим, від англ. randomized algorithm)[17]. Формально, такі алгоритми не можна називати алгоритмами оскільки існує імовірність (близька до нуля), що вони не зупиняться. Проте, стохастичні алгоритми часто бувають ефективнішими за детерміновані, а в окремих випадках — єдиним способом розв'язати задачу[16].
На практиці замість генератора випадкових чисел використовують генератор псевдовипадкових чисел.
Однак слід відрізняти стохастичні алгоритми та методи, які дають із високою ймовірністю правильний результат. На відміну від методу, алгоритм дає коректні результати навіть після тривалої роботи.
Деякі дослідники припускають можливість того, що стохастичний алгоритм дасть із певною наперед відомою ймовірністю неправильний результат. Тоді стохастичні алгоритми можна поділити на два типи[18]:
Для деяких задач названі вище формалізми можуть ускладнювати пошук розв'язків та здійснення досліджень. Для подолання перешкод було розроблено як модифікації «класичних» схем, так і створено нові моделі алгоритму. Зокрема, можна назвати:
та інші.
Нумерація алгоритмів відіграє важливу роль в їхньому досліджені та аналізі[19].
Оскільки будь-який алгоритм можна задати у вигляді скінченного слова (представити у вигляді скінченної послідовності символів деякого алфавіту), а множина всіх скінченних слів у скінченному алфавіті зліченна, то множина всіх алгоритмів також зліченна. Це означає існування взаємно однозначного відображення між множиною натуральних чисел та множиною алгоритмів, тобто можливість присвоїти кожному алгоритму номер.
Нумерація алгоритмів є водночас і нумерацією всіх алгоритмічно обчислюваних функцій, при чому, будь-яка функція може мати нескінченну кількість номерів.
Існування нумерації дозволяє працювати з алгоритмами так само, як з числами. Особливо корисна нумерація в дослідженні алгоритмів, що працюють з іншими алгоритмами.
Формалізація поняття алгоритму дозволила дослідити існування задач, для яких не існує алгоритмів пошуку розв'язків. Згодом було доведено неможливість алгоритмічного обчислення розв'язків ряду задач, що унеможливлює їхнє розв'язання на будь-якому обчислювальному пристрої.
Функцію f називають обчислюваною (англ. computable), якщо існує машина Тюрінга, яка обчислює значення f для всіх елементів множини визначення функції. Якщо такої машини не існує, функцію f називають необчислюваною. Функція вважатиметься необчислюваною навіть, якщо існують машини Тюрінга, здатні обчислити значення для підмножини з усієї множини вхідних даних[20].
Випадок, коли результатом обчислення функції f є булеве значення істина або неправда (або множина {0, 1}) називають задачею, яка може бути розв'язною, або нерозв'язною в залежності від обчислюваності функції f[20].
Важливо точно вказувати припустиму множину вхідних даних, оскільки задача може бути розв'язною для однієї множини та нерозв'язною для іншої.
Однією з перших задач, для якої було доведено нерозв'язність є проблема зупинки. Формулюється вона наступним чином:
Доведення нерозв'язності проблеми зупинки важливе тим, що до неї можна звести інші задачі. Наприклад, проблему зупинки на порожній стрічці (визначити для заданої машини Тюрінга чи зупиниться вона, будучи запущена на порожній стрічці) можна звести до простої задачі зупинки, довівши, тим самим, її нерозв'язність[20].
Разом з поширенням інформаційних технологій збільшився ризик програмних збоїв. Одним зі способів уникнення помилок в алгоритмах та їхніх реалізаціях є доведення коректності систем математичними засобами.
Використання математичного апарату для аналізу алгоритмів та їхньої реалізацій називають формальними методами. Формальні методи передбачають застосування формальних специфікацій та, зазвичай, набору інструментів для синтаксичного аналізу та доведення властивостей специфікацій. Абстрагування від деталей реалізації дозволяє встановити властивості системи незалежно від її реалізації. Крім того, точність та однозначність математичних тверджень дозволяє уникнути багатозначності та неточності природних мов[22].
За гіпотезою Річарда Мейса «уникнення помилок краще за усунення помилок»[23]. За гіпотезою Гоара «доведення програм розв'язує проблему коректності, документації та сумісності»[24]. Доведення коректності програм дозволяє виявляти їхні властивості по відношенню до всього діапазону вхідних даних. Для доведення коректності програм, поняття коректності було розширене на два типи:
Під час доведення коректності порівнюють текст програми зі специфікацією бажаного співвідношення вхідних-вихідних даних. Для доведень типу Гоара ця специфікація має вигляд тверджень, які називають перед- та післяумовами. В сукупності з самою програмою, їх ще називають трійками Гоара. Ці твердження записують
де P — це передумова, що має виконуватись перед запуском програми Q, а R — післяумова, правильна після завершення роботи програми.
Формальні методи було успішно застосовано до широкого кола задач, зокрема: розробка електронних схем, штучного інтелекту, систем, чутливих до надійності, безпечності, автоматичних систем на залізниці, верифікації мікропроцесорів, специфікації стандартів та специфікації і верифікації програм[25].
Поширеним критерієм оцінки алгоритмів є час роботи та порядок зростання тривалості роботи в залежності від обсягу вхідних даних.[26]
Кожній конкретній задачі зіставляють деяке число, яке називають її розміром. Наприклад, розміром задачі обчислення добутку матриць може бути найбільший розмір матриць-множників, для задач на графах розміром може бути кількість ребер графу.
Час, який витрачає алгоритм як функція від розміру задачі n, називають часовою складністю цього алгоритму T(n). Асимптотику поведінки цієї функції при збільшенні розміру задачі називають асимптотичною часовою складністю, а для її позначення використовують нотацію Ландау (велике O).
Саме асимптотична складність визначає розмір задач, які алгоритм здатен обробити. Наприклад, якщо алгоритм обробляє вхідні дані розміром n за час cn², де c — деяка стала, то кажуть, що часова складність такого алгоритму O(n²).
Часто, під час розробки алгоритму намагаються зменшити асимптотичну часову складність для найгірших випадків. На практиці ж, трапляються випадки, коли достатнім є алгоритм, який «зазвичай» працює швидко.
Грубо кажучи, аналіз середньої асимптотичної часової складності можна поділити на два типи: аналітичний та статистичний. Аналітичний метод дає точніші результати, але складний у використанні на практиці. Натомість статистичний метод дозволяє швидше здійснювати аналіз складних задач[27].
В наступній таблиці наведено поширені асимптотичні складності з коментарями[28].
| Складність | Коментар | Приклади |
|---|---|---|
| O(1) | Сталий час роботи не залежно від розміру задачі | Очікуваний час пошуку в хеші |
| O(log log n) | Дуже повільне зростання необхідного часу | Очікуваний час роботи інтерполюючого пошуку n елементів |
| O(log n) | Логарифмічне зростання — подвоєння розміру задачі збільшує час роботи на сталу величину | Обчислення xn; двійковий пошук в масиві з n елементів |
| O(n) | Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час | Додавання/віднімання чисел з n цифр; лінійний пошук в масиві з n елементів |
| O(n log n) | Лінеаритмічне зростання — подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі | Сортування злиттям або купою n елементів; нижня границя сортування порівнянням n елементів |
| O(n²) | Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час | Елементарні алгоритми сортування |
| O(n³) | Кубічне зростання — подвоєння розміру задачі збільшує необхідний час увосьмеро | Звичайне множення матриць |
| O(cn) | Експоненціальне зростання — збільшення розміру задачі на 1 призводить до c-кратного збільшення необхідного часу; подвоєння розміру задачі підносить необхідний час у квадрат | Деякі задачі комівояжера, алгоритми пошуку повним перебором |
У процесі розробки алгоритму можуть використовуватись різні способи його опису, які відрізняються за простотою, наочністю, компактністю, мірою формалізації, орієнтації на машинну реалізацію тощо[29].
Форми запису алгоритму:
Алгоритми мають ряд важливих властивостей:[30]
Як приклад можна навести алгоритм Евкліда.
Алгоритм Евкліда — ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, один з найдавніших алгоритмів, що досі використовують[31]. Описаний в Началах Евкліда (приблизно 300 до н. е.), а саме, в книгах VII та X. У сьомій книзі алгоритм описано для цілих чисел, а в десятій — для довжин відрізків.
Існує декілька варіантів алгоритму, нижче записано в псевдокоді рекурсивний варіант:
функція нсд(a, b)
якщо b = 0
поверни a
інакше
поверни нсд(b, a mod b)
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
