Теорія алгоритмів

Коротко

• Виникла в 1930-х роках, коли Алонзо Черч, Курт Гедель, Стівен Кліні, Алан Тюрінг і Еміль Пост запропонували точні моделі обчислюваності.
• Теза Черча — Тюрінга стверджує, що будь-який алгоритм в інтуїтивному розумінні можна виконати на машині Тюрінга.
• Доведено існування задач, для яких загального алгоритму не існує, — наприклад, проблеми зупинки.
• Сучасна частина теорії — аналіз складності алгоритмів, зокрема відкрите питання про рівність класів P і NP.

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

Як формалізували поняття алгоритму

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

Рік	Модель	Автор
1932	λ-означувані функції	Алонзо Черч
1934	загальнорекурсивні функції	Курт Гедель
1936	частково рекурсивні функції	Стівен Кліні
1936	абстрактна обчислювальна машина	Алан Тюрінг, Еміль Пост
1952–1954	нормальні алгоритми	А. А. Марков
1963	регістрові машини	Дж. Шепердсон, Г. Стерджіс

1936 року Черч і Кліні довели, що перші два класи функцій збігаються, а 1937-го Тюрінг показав, що й його машини обчислюють ті самі функції. Різні підходи дали один результат — це стало сильним аргументом на користь того, що інтуїтивне поняття алгоритму схоплено правильно.

Теза Черча — Тюрінга

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

Найвідоміша з них — проблема зупинки: загального способу визначити, чи зупиниться довільна машина на довільних даних, не існує. 1936 року Черч встановив нерозв’язність проблеми розв’язності для числення предикатів. Спершу здавалося, що нерозв’язні задачі трапляються лише в самій логіці. 1947 року А. А. Марков та Еміль Пост, працюючи окремо, довели нерозв’язність проблеми рівності слів для напівгруп, тобто класичного алгебраїчного питання, а 1952 року П. С. Новіков — аналогічний результат для груп.

Складність обчислень

Сучасна теорія алгоритмів значною мірою займається не тим, чи можна щось обчислити, а тим, скільки часу й пам’яті для цього треба. Розрізняють:

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

Такі дослідження дали швидші, ніж традиційні, методи множення многочленів і матриць та розв’язування систем лінійних рівнянь.

Застосування

Теорія алгоритмів — теоретична основа програмування й інформатики. Через неї можна отримати теорему Геделя про неповноту формальних систем. 1965 року Андрій Колмогоров запропонував спирати на неї теорію інформації. Її методами користуються також кібернетика, обчислювальна математика, лінгвістика й економіка.

Запитання

Що таке проблема зупинки?

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

Чим теорія алгоритмів відрізняється від програмування?

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

Що означає питання «P = NP?»

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

Див. також

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

Джерела

1. Теорія алгоритмів — Вікіпедія (українська)
2. Wikidata: Q844718

Статтю написано редакцією словника за наведеними джерелами; дати й факти звірено між ними. Якщо джерела розходяться, це сказано в тексті.