Алгоритм

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Сторінка з «Алгебри» аль-Хорезмі — перського математика, від імені якого походить слово алгоритм.

Алгор́итм (латинізов. Algorithmi, від імені перського математика IX ст. аль-Хорезмі) — послідовність, система, набір систематизованих правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій.[1] При написанні комп'ютерних програм алгоритм описує логічну послідовність операцій. Для візуального зображення алгоритмів часто використовують блок-схеми.

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

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

Часткова формалізація поняття алгоритму почалась зі спроб розв'язання задачі розв'язності (нім. Entscheidungsproblem), яку сформулював Давид Гільберт в 1928 році. Наступні формалізації були необхідні для визначення ефективної обчислювальності[2] або «ефективного методу»[3]; до цих формалізацій належать рекурсивні функції Геделя-Ербрана[en]-Кліні 1930, 1934 та 1935 років, λ-числення Алонзо Черча 1936 р., «Формулювання 1» Еміля Поста 1936 року, та машина Тюринга, розроблена Аланом Тюрингом протягом 1936, 1937 та 1939 років. В методології алгоритм є базисним поняттям і складає основу опису методів. З методології виходить якісно нове поняття алгоритму як оптимальність з наближенням до прогнозованого абсолюту. Зробивши все в послідовності алгоритму за граничних умов задачі маємо ідеальне рішення нагальних проблем науково-практичного характеру. В сучасному світі алгоритм будь-якої діяльності у формалізованому виразі складає основу освіти на прикладах, за подоби. На основі подібності алгоритмів різних сфер діяльності була сформована концепція (теорія) експертних систем.

Історія[ред.ред. код]

Слово алгоритм походить від імені перського вченого, астронома та математика Аль-Хорезмі. Приблизно 825 до н. е. він написав трактат, в якому описав придуману в Індії позиційну десяткову систему числення.

В першій половині XII століття книжка потрапила до Європи в перекладі латинською мовою під назвою Algoritmi de numero Indorum. Вважається, що перше слово в перекладі відповідає невдалій латинізації імені Аль-Хорезмі, а назва перекладу звучить як «Алгоритмі про індійську лічбу».

Через невірне тлумачення слова Algoritmi як іменника в множині ним стали називати метод обчислення.

Баронеса Ада Лавлейс, яку вважають першим програмістом.

Перший алгоритм, призначений для виконання на автоматичному обчислювальному пристрої (комп'ютері), описала Ада Лавлейс в 1843 році. Алгоритм мав обчислювати числа Бернуллі й працювати на аналітичній машині?! Беббіджа. Цей алгоритм вважається першою комп'ютерною програмою, а його розробниця, Ада Лавлейс — першим програмістом[4].

З 1930-тих років починається бурхливий розвиток галузі дослідження алгоритмів та становлення інформатики в її сучасному вигляді. В 1935 році Стівен Кліні розробив перше формулювання теорії рекурсії та показав еквівалентність розробленої системи частково рекурсивним функціям. В 1936 році незалежно були опубліковані роботи Алана Тюринга та Еміля Поста, в яких наведено схожі системи для визначення поняття алгоритму. А вже в 1937 році було доведено еквівалентність різних визначень[5].

Машина Тюринга пропонувала конструкцію, придатну для автоматичної інтерпретації. Побудована під впливом Алана Тюринга у Великобританії обчислювальна система ACE[en] (завершена в 1950 році), та системи, побудовані за архітектурою фон Неймана в США та в інших країнах (в СРСР — МЕСМ, розроблена в 1950 році в Інституті електротехніки АН УРСР групою вчених під керівництвом Сергія Лебедєва), були першими універсальними обчислювальними пристроями, які повністю задовольняли вимоги обчислювальності[5].

Протягом 19351960 років було розроблено численні ідеї та технології, які лягли в основу сучасної інформатики.

Формальні засоби для представлення алгоритмів мали не лише теоретичну значущість. Розробка алгоритмічних мов для програмування обчислювальних пристроїв розпочалась в 1951 році з публікації німецького інженера Ганса Рутісхаузера[en] (нім. Heinz Rutishauser). Спочатку важливою здавалась проблема нотації, її досліджував Олексій Ляпунов, але поступово вона відійшла на другий план[6].

Перша мова програмування, Планкалькуль[en] (нім. Plankalkül) була розроблена Конрадом Цузе в 1946 році, але через відсутність компіляторів виконання написаних цією мовою програм було неможливим. Опис мови був надрукований у 1972 році, а в 2000 році був створений компілятор для підмножини мови.[7]

В середині 1950-тих було розроблено мову програмування Фортран Джоном Бекусом з IBM. В кінці 1950-тих було розроблено Алгол та Кобол; для навчальних цілей Бейсік (1963) та Паскаль (початок 1970-тих). Для системного програмування в Bell Laboratories було розроблено C[8].

λ-Числення дало поштовх до створення в кінці 1950-тих функційної мови програмування Лісп. На основі ідей Ліспу було створено Scheme. Мова ML була розроблена Робіном Мілнером[en] в кінці 1970-тих. В кінці 1980-тих була створена мова Haskell[9].

Під впливом досліджень в галузі штучного інетелекту розроблено парадигму логічного програмування. На відміну від імперативної та функційної парадигм, логічне програмування не вимагає від розробника описувати спосіб розв'язання поставленої задачі. Planner[en] — перша мова логічного програмування, була розроблена в 1969 році. На початку 1970-тих був розроблений Пролог, який згодом став найпоширенішою мовою логічного програмування зі стандартом ISO, затвердженим у 1995 році[10] .

Визначення[ред.ред. код]

Неформальне визначення[ред.ред. код]

Кожен алгоритм передбачає існування початкових (вхідних) даних та в результаті роботи призводить до отримання певного результату. Робота кожного алгоритму відбувається шляхом виконання послідовності деяких елементарних дій. Ці дії називають кроками, а процес їхнього виконання називають алгоритмічним процесом. В такий спосіб відзначають властивість дискретності алгоритму[11].

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

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

Вхідні дані алгоритму можуть бути обмежені набором припустимих вхідних даних. Застосування алгоритму до неприпустимих вхідних даних може призводити до того, що алгоритм ніколи не зупиниться, або потрапить в тупиковий стан (зависання) з якого не зможе продовжити виконання.

Формальне визначення[ред.ред. код]

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

Перші спроби уточнення поняття алгоритму та його дослідження здійснювали в першій половині XX століття Алан Тюринг, Еміль Пост, Жак Ербран[en], Курт Гедель, Андрій Марков, Алонзо Черч. Було розроблено декілька означень поняття алгоритму, але згодом було з'ясовано, що всі вони визначають одне й те саме поняття (див. теза Черча).[12]

Машина Тюринга[ред.ред. код]

Докладніше: Машина Тюринга
Схематична ілюстрація роботи машини Тюринга.

Основна ідея, що лежить в основі машини Тюринга, дуже проста. Машина Тюринга — це абстрактна машина (автомат), що працює зі стрічкою окремих комірок, в яких записано символи. Машина також має голівку для запису та читання символів із комірок, яка може рухатись вздовж стрічки. На кожному кроці машина зчитує символ з комірки, на яку вказує голівка, та, на основі зчитаного символу й внутрішнього стану робить наступний крок. При цьому, машина може змінити свій стан, записати інший символ в комірку, або пересунути голівку на одну комірку ліворуч або праворуч.[13]

На основі дослідження цих машин було висунуто тезу Тюринга (основна гіпотеза алгоритмів):

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

Ця теза є аксіомою, постулатом, і не може бути доведена математичними методами, оскільки алгоритм не є точним математичним поняттям.

Рекурсивні функції[ред.ред. код]

З кожним алгоритмом можна зіставити функцію, яку він обчислює. Однак постає питання, чи можна довільній функції зіставити машину Тюринга, а якщо ні, то для яких функцій існує алгоритм? Досліження цих питань призвело до створення в 1930-их роках теорії рекурсивних функцій[14].

Клас обчислюваних функцій було описано в спосіб, що нагадує побудову деякої аксіоматичної теорії на базі системи аксіом. Спочатку було вибрано найпростіші функції, обчислюваність яких очевидна. Потім було сформульовано правила (оператори) побудови нових функцій на основі вже існуючих. Необхідний клас функцій складається з усіх функцій, які можна отримати з найпростіших застосуванням операторів.

Подібно тезі Тюринга в теорії обчислюваних функцій висунуто гіпотезу, що має назву теза Черча:

Числова функція тоді і лише тоді алгоритмічно обчислювана, коли вона частково рекурсивна.

Доведення того, що клас обчислюваних функцій збігається з обчислюваними за Тюрингом відбувається в два кроки: спочатку доводять обчислюваність найпростіших функцій на машині Тюринга, а потім — обчислюваність функцій, отриманих внаслідок застосування операторів.

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

Нормальні алгорифми Маркова[ред.ред. код]

Нормальні алгоритми Маркова — це система послідовних застосувань підстановок, які реалізують певні процедури отримання нових слів з базових, побудованих із символів деякого алфавіту. Як і машини Тюринга, нормальні алгоритми не виконують самих обчислень: вони лише виконують перетворення слів шляхом заміни літер за заданими правилами[15].

Нормально обчислюваною називають функцію, яку можна реалізувати нормальним алгоритмом. Тобто, алгоритмом, який кожне слово з множини припустимих даних функції перетворює на її вихідні значення[16].

Творець теорії нормальних алгоритмів А. А. Марков висунув гіпотезу, яка отримала назву принцип нормалізації Маркова:

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

Подібно до тез Тюринга та Черча, принцип нормалізації Маркова не може бути доведений математичними засобами.

Стохастичні алгоритми[ред.ред. код]

Однак, наведене вище формальне визначення алгоритму в деяких випадках може бути надто строгим. Інколи виникає потреба у використанні випадкових величин[17]. Алгоритм, робота якого визначається не лише вхідними даними, але й значеннями отриманими з генератора випадкових чисел, називають стохастичним (або рандомізованим, від англ. randomized algorithm)[18]. Формально, такі алгоритми не можна називати алгоритмами оскільки існує ймовірність (близька до нуля), що вони не зупиняться. Проте, стохастичні алгоритми часто бувають ефективнішими за детерміновані, а в окремих випадках — єдиним способом розв'язати задачу[17].

На практиці замість генератора випадкових чисел використовують генератор псевдовипадкових чисел.

Однак слід відрізняти стохастичні алгоритми та методи, які дають із високою ймовірністю правильний результат. На відміну від методу, алгоритм дає коректні результати навіть після тривалої роботи.

Деякі дослідники припускають можливість того, що стохастичний алгоритм дасть із певною наперед відомою ймовірністю неправильний результат. Тоді стохастичні алгоритми можна поділити на два типи[19]:

  • алгоритми типу Лас-Вегас завжди дають коректний результат, але час їхньої роботи невизначений.
  • алгоритми типу Монте-Карло, на відміну від попередніх, можуть давати неправильні результати з відомою ймовірністю (їх часто називають методами Монте-Карло).

Інші формалізації[ред.ред. код]

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

та інші.

Нумерація алгоритмів[ред.ред. код]

Нумерація алгоритмів відіграє важливу роль в їхньому досліджені та аналізі[20].

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

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

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

Алгоритмічно нерозв'язні задачі[ред.ред. код]

Формалізація поняття алгоритму дозволила дослідити існування задач, для яких не існує алгоритмів пошуку розв'язків. Згодом було доведено неможливість алгоритмічного обчислення розв'язків ряду задач, що робить неможливим їхнє розв'язання на будь-якому обчислювальному пристрої.

Функцію f називають обчислюваною (англ. computable), якщо існує машина Тюринга, яка обчислює значення f для всіх елементів множини визначення функції. Якщо такої машини не існує, функцію f називають необчислюваною. Функція вважатиметься необчислюваною навіть, якщо існують машини Тюринга, здатні обчислити значення для підмножини з усієї множини вхідних даних[21].

Випадок, коли результатом обчислення функції f є булеве значення істина або неправда (або множина {0, 1}) називають задачею, яка може бути розв'язною, або нерозв'язною в залежності від обчислюваності функції f[21].

Важливо точно вказувати припустиму множину вхідних даних, оскільки задача може бути розв'язною для однієї множини та нерозв'язною для іншої.

Однією з перших задач, для якої було доведено нерозв'язність є проблема зупинки. Формулюється вона наступним чином:

Маючи опис програми для машини Тюринга, визначити, чи завершить роботу програма за скінченний час, чи працюватиме нескінченно, отримавши будь-які вхідні дані.[22]

Доведення нерозв'язності проблеми зупинки важливе тим, що до неї можна звести інші задачі. Наприклад, проблему зупинки на порожній стрічці (визначити для заданої машини Тюринга чи зупиниться вона, будучи запущена на порожній стрічці) можна звести до простої задачі зупинки, довівши, тим самим, її нерозв'язність[21].

Аналіз алгоритмів[ред.ред. код]

Доведення коректності[ред.ред. код]

Докладніше: Формальні методи

Разом з поширенням інформаційних технологій збільшився ризик програмних збоїв. Одним зі способів уникнення помилок в алгоритмах та їхніх реалізаціях є доведення коректності систем математичними засобами.

Використання математичного апарату для аналізу алгоритмів та їхньої реалізацій називають формальними методами. Формальні методи передбачають застосування формальних специфікацій та, зазвичай, набору інструментів для синтаксичного аналізу та доведення властивостей специфікацій. Абстрагування від деталей реалізації дозволяє встановити властивості системи незалежно від її реалізації. Крім того, точність та однозначність математичних тверджень дозволяє уникнути багатозначності та неточності природних мов[23].

За гіпотезою Річарда Мейса «уникнення помилок краще за усунення помилок»[24]. За гіпотезою Хоара «доведення програм розв'язує проблему коректності, документації та сумісності»[25]. Доведення коректності програм дозволяє виявляти їхні властивості по відношенню до всього діапазону вхідних даних. Для доведення коректності програм, поняття коректності було розширене на два типи:

  • Часткова коректність — програма дає коректний результат для тих випадків, коли вона завершується.
  • Повна коректність — програма завершує роботу та видає коректний результат для всіх елементів з діапазону вхідних даних.

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

P{Q}R

де P — це передумова, що має виконуватись перед запуском програми Q, а R — післяумова, правильна після завершення роботи програми.

Формальні методи було успішно застосовано до широкого кола задач, зокрема: розробка електронних схем, штучного інтелекту, систем, чутливих до надійності, безпечності, автоматичних систем на залізниці, верифікації мікропроцесорів, специфікації стандартів та специфікації і верифікації програм[26].

Час роботи[ред.ред. код]

Графіки функцій наведених в таблиці нижче.

Поширеним критерієм оцінки алгоритмів є час роботи та порядок зростання тривалості роботи в залежності від обсягу вхідних даних.[27]

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

Час, який витрачає алгоритм як функція від розміру задачі n, називають часовою складністю цього алгоритму T(n). Асимптотику поведінки цієї функції при збільшенні розміру задачі називають асимптотичною часовою складністю, а для її позначення використовують нотацію Ландау (велике O).

Саме асимптотична складність визначає розмір задач, які алгоритм здатен обробити. Наприклад, якщо алгоритм обробляє вхідні дані розміром n за час cn², де c — деяка стала, то кажуть, що часова складність такого алгоритму O(n²).

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

Грубо кажучи, аналіз середньої асимптотичної часової складності можна поділити на два типи: аналітичний та статистичний. Аналітичний метод дає точніші результати, але складний у використанні на практиці. Натомість статистичний метод дозволяє швидше здійснювати аналіз складних задач[28].

В наступній таблиці наведено поширені асимптотичні складності з коментарями[29].

Складність Коментар Приклади
O(1) Сталий час роботи не залежно від розміру задачі Очікуваний час пошуку в хеші
O(log log n) Дуже повільне зростання необхідного часу Очікуваний час роботи інтерполюючого пошуку[en] n елементів
O(log n) Логарифмічне зростання — подвоєння розміру задачі збільшує час роботи на сталу величину Обчислення xn; двійковий пошук в масиві з n елементів
O(n) Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час Додавання/віднімання чисел з n цифр; лінійний пошук в масиві з n елементів
O(n log n) Лінеаритмічне зростання — подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі Сортування злиттям або купою n елементів; нижня границя сортування порівнянням n елементів
O(n²) Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час Елементарні алгоритми сортування
O(n³) Кубічне зростання — подвоєння розміру задачі збільшує необхідний час у вісім разів Звичайне множення матриць
O(cn) Експоненціальне зростання — збільшення розміру задачі на 1 призводить до c-кратного збільшення необхідного часу; подвоєння розміру задачі підносить необхідний час у квадрат Деякі задачі комівояжера, алгоритми пошуку повним перебором

Представлення алгоритмів[ред.ред. код]

Блок-схема алгоритму визначення дієвідміни в дієслові.

У процесі розробки алгоритму можуть використовуватись різні способи його опису, які відрізняються за простотою, наочністю, компактністю, мірою формалізації, орієнтації на машинну реалізацію тощо[30].

Форми запису алгоритму:

Властивості алгоритмів[ред.ред. код]

Алгоритми мають ряд важливих властивостей:[31]

Скінченність
алгоритм має завжди завершуватись після виконання скінченної кількості кроків. Процедуру, яка має решту характеристик алгоритму, без, можливо, скінченності, називають методом обчислень.
Дискретність
процес, що визначається алгоритмом, можна розчленувати (розділити) на окремі елементарні етапи (кроки), кожен з яких називається кроком алгоритмічного процесу чи алгоритму.[30]
Визначеність
кожен крок алгоритму має бути точно визначений. Дії, які необхідно здійснити, повинні бути чітко та недвозначно визначені для кожного можливого випадку.
Вхідні дані
алгоритм має деяку кількість (можливо, нульову) вхідних даних, тобто, величин, заданих до початку його роботи або значення яких визначають під час роботи алгоритму.
Вихідні дані
алгоритм має одне або декілька вихідних даних, тобто, величин, що мають досить визначений зв'язок із вхідними даними.
Ефективність
Алгоритм вважають ефективним, якщо всі його оператори досить прості для того, аби їх можна було точно виконати за скінченний проміжок часу з допомогою олівця та аркушу паперу.
Масовість
властивість алгоритму, яка полягає в тому, що алгоритм повинен забезпечувати розв'язання будь-якої задачі з класу однотипних задач за будь-якими вхідними даними, що належать до області застосування алгоритму.

Приклад[ред.ред. код]

В якості прикладу можна навести алгоритм Евкліда.

Алгоритм Евкліда — ефективний метод обчислення найбільшого спільного дільника (НСД). Названий на честь грецького математика Евкліда, один з найдавніших алгоритмів, що досі використовують[32]. Описаний в Началах Евкліда (приблизно 300 до н. е.), а саме, в книгах VII та X. У сьомій книзі алгоритм описано для цілих чисел, а в десятій — для довжин відрізків.

Існує декілька варіантів алгоритму, нижче записано в псевдокоді рекурсивний варіант:

функція нсд(a, b)
    якщо b = 0
       поверни a
    інакше
       поверни нсд(b, a mod b)

Див. також[ред.ред. код]

Джерела та література[ред.ред. код]

  • Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. ISBN 0486432289. 
  • Игошин В. И. (2008). Математическая логика и теория алгоритмов (вид. 2-ге). Москва: Academia. ISBN 978-5-7695-4593-1. 
  • за ред. Mikhail J. Atallah та Marina Blanton Algorithms and theory of computation handbook. General concepts and techniques. — 2-ге. — Chapman & Hall/CRC, 2010. — (applied algorithms and data structures). — ISBN 978-1-58488-822-2.
  • Albert Endres, Dieter Rombach A Handbook of Software and Systems Engineering. — Addison Wesley, 2003. — (The Fraunhofer IESE Series on Software Engineering). — ISBN 0-321-15420-7.
  • Gerard O'Regan 4.5 // A Brief History of Computing. — Springer, 2008. — ISBN 978-1-84800-083-4.
  • Friedrich L. Bauer Origins and Foundations of Computing = Kurze Geschichte der Informatik. — Springer, 2010. — ISBN 978-3-642-02991-2.

Примітки[ред.ред. код]

  1. Українська радянська енциклопедія / ред. М. Бажан; 2-е видання. — К., 1974—1985, том 1, Алгоритм.
  2. Kleene 1943 in Davis 1965:274
  3. Rosser 1939 in Davis 1965:225
  4. Fuegi, J. and Francis, J. «Lovelace & Babbage and the creation of the 1843 'notes'.» Annals of the History of Computing 25 #4 (October-December 2003): Digital Object Identifier
  5. а б (Розділ «Algorithms» в Bauer, 2010)
  6. (Розділ «Algorithmic Languages» в Bauer, 2010)
  7. (Розділ 3.2 в O'Regan, 2008)
  8. (Розділ 3.3 в O'Regan, 2008)
  9. (Розділ 3.5 в O'Regan, 2008)
  10. (Розділ 3.6 в O'Regan, 2008)
  11. (Игошин, с. 314)
  12. (Игошин, с. 317)
  13. «Basics: The Turing Machine (with an interpreter!». Good Math, Bad Math. 2007-02-09. Архів оригіналу за 2012-02-02. 
  14. (Игошин, розділ 33)
  15. Енциклопедія кібернетики, т. 2, c. 90-91.
  16. (Игошин, розділ 34)
  17. а б «Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time.» Henri Cohen (1996). A Course in Computational Algebraic Number Theory. Springer-Verlag. с. 2. ISBN 3-540-55640-0. 
  18. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives't, Clifford Stein (2001). «5.1». Introduction to Algorithms (вид. 2-ге). MIT Press. с. 531. ISBN 0-262-03293-7. 
  19. (Розділ 12, с. 12-22 в Atallah, 2010)
  20. (Игошин, розділ 36)
  21. а б в Peter Linz 12.1 // An Introduction to Formal Languages and Automata. — 3-тє. — Jones and Bartlett Publishers, 2000. — ISBN 0-7637-1422-4.
  22. «computability and complexity». Encyclopedia of computer Science and Technology. Facts On File. 2009. ISBN 978-0-8160-6382-6. «Given any computer program, can you determine whether the program will halt (end) given any input?» 
  23. (O'Regan, розділ 4.5)
  24. (Розділ 5.3.6 в Enders, 2003)
  25. (Розділ 5.3.7 в Enders, 2003)
  26. (O'Regan, с. 119)
  27. А. Ахо, Дж. Хопкрофт, Дж. Ульман (1979). «1». Построение и анализ вычислительных алгоритмов. Москва: «Мир».  Проігноровано невідомий параметр |оригінал= (довідка)
  28. (розділ 11 в Atallah, 2010)
  29. (розділ 1 в Atallah, 2010)
  30. а б Н. М. Васильків, Л. О. Васильків Опорний конспект лекцій з дисципліни «Основи алгоритмізації» спеціальність «Комп'ютерні системи та мережі». — Тернопіль: Економічна думка, 2005. — 32 с.
  31. Кнут, т. 1,
  32. Knuth D (1997). The Art of Computer Programming[en], Volume 2: Seminumerical Algorithms (вид. 3rd). Addison–Wesley. ISBN 0201896842.