Теория алгоритмов: различия между версиями

Перейти к навигации Перейти к поиску
(Новая страница: « '''Теория алгоритмов''', раздел математики, изучающий общие свойства алгоритмов. Содержат…»)
 
Строка 8: Строка 8:
1) "вычисляет функцию ''f''", коль скоро его область применимости совпадает с областью определения ''f'' и ''Á'' перерабатывает всякий ''x'' из своей области применимости в ''f(x)'',  
1) "вычисляет функцию ''f''", коль скоро его область применимости совпадает с областью определения ''f'' и ''Á'' перерабатывает всякий ''x'' из своей области применимости в ''f(x)'',  


2) "разрешает множество ''А'' относительно множества ''X''", коль скоро он применим ко всякому ''х'' из ''Х'' и перерабатывает всякий ''х'' из Х Ç A в слово "да", а всякий ''х'' из ''Х\A'' в слово "нет"; 3) "перечисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. Функция называется вычислимой, если существует вычисляющий её алгоритм. Множество называется разрешимым относительно X, если существует разрешающий его относительно Х алгоритм (см. Разрешимое множество). Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм (см. Перечислимое множество).
2) "разрешает множество ''А'' относительно множества ''X''", коль скоро он применим ко всякому ''х'' из ''Х'' и перерабатывает всякий ''х'' из Х Ç A в слово "да", а всякий ''х'' из ''Х\A'' в слово "нет";  


Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее — областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида <x, f(x)>. (IV) Подмножество А перечислимого множества Х тогда и только тогда разрешимо относительно X, когда А и Х \А перечислимы. (V) Если А и В перечислимы, то A' ÈB и А ÇВ также перечислимы. (VI) В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно X]. (VII) Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма Á с неразрешимой областью применимости.
3) "перечисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В.  


Функция называется [[вычислимая функция|вычислимой]], если существует вычисляющий её алгоритм. Множество называется [[Разрешимое множество|разрешимым]] относительно ''X'', если существует разрешающий его относительно ''Х'' алгоритм. Множество называется [[Перечислимое множество|перечислимым]], если либо оно пусто, либо существует перечисляющий его алгоритм.
Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее — областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида <x, f(x)>. (IV) Подмножество А перечислимого множества Х тогда и только тогда разрешимо относительно X, когда А и Х \А перечислимы. (V) Если А и В перечислимы, то A' ÈB и А ÇВ также перечислимы. (VI) В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно X]. (VII) Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают пример алгоритма алгоритма с неразрешимой областью применимости.


== Алгоритмические проблемы ==
== Алгоритмические проблемы ==

Навигация