Головна
Українська Радянська Енциклопедія
Енциклопедичний словник-довідник з туризму
Юридична енциклопедія - Шемшученко Ю.С.
 
Головна arrow Українська Радянська Енциклопедія arrow алгор-алч arrow АЛГОРИТМІВ ТЕОРІЯ
   

АЛГОРИТМІВ ТЕОРІЯ

- розділ математики, в якому вивчаються загальні властивості та застосування алгоритмів. Основним об'єктом А. т. є формалізоване поняття алгоритму, запропоноване в 30-х рр. 20 ст. А. Черчем, Е. Постом, А. Тьюрінгом. Є різні способи точного визначення поняття алгоритму: у вигляді обчислюваної функції, теоретичної обчислювальної машини (Тьюрінга), схеми числення слів (нормальні алгорифми) та інші. Найзагальніше визначення алгоритму запропонував А. М. Колмогоров. Вважають, що будь-який інтуїтивно описаний алгоритм допускає строге визначення в межах А. т. Дослідження в А. т. складаються з класифікації та порівняння алгоритмів; з'ясування звідності й еквівалентності алгоритмів; побудови алгоритмів, що мають певні властивості; оцінки складності алгоритмів; вивчення механізмів обчислювальних процесів певного типу, напр., скінченних автоматів, заг. теорія яких побудована В. М. Глушковим. Важливими проблемами А. т. та її застосувань в ін. розділах математики є проблеми розв'язності, тобто існування алгоритму, що розв'язує даний клас задач. Відомі нерозв'язні класи задач, для яких не існує єдиного алгоритму, напр., побудовані півгрупи (А. А. Марков молодший) і групи (П. С. Новиков) з нерозв'язною проблемою тотожності. А. т., побудована з метою дослідження фундаментальних матем. понять алгоритму, числення та ін., набула практичного значення для програмування, тобто реалізації алгоритмів в електронних обчислювальних машинах, автоматизації керування складними процесами та ін.

Літ.: Марков А. А. Теория алгоритмов. "Труды Математического института им. В. А. Стеклова АН СССР", 1954, т. 42; Глушков В. М. Синтез цифровых автоматов. М-, 1962; Мальцев А. И. Алгоритмы и рекурсивные функции. М., 1965; Клини С. К. Математическая логика. Пер. с англ. М., 1973. В. С. Королюк.

 

Схожі за змістом слова та фрази