683
правки
Теория алгоритмов: различия между версиями
Материал из WikiGrapp
→Основные понятия
KVN (обсуждение | вклад) (Новая страница: « '''Теория алгоритмов''', раздел математики, изучающий общие свойства алгоритмов. Содержат…») |
KVN (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
1) "вычисляет функцию ''f''", коль скоро его область применимости совпадает с областью определения ''f'' и ''Á'' перерабатывает всякий ''x'' из своей области применимости в ''f(x)'', | 1) "вычисляет функцию ''f''", коль скоро его область применимости совпадает с областью определения ''f'' и ''Á'' перерабатывает всякий ''x'' из своей области применимости в ''f(x)'', | ||
2) "разрешает множество ''А'' относительно множества ''X''", коль скоро он применим ко всякому ''х'' из ''Х'' и перерабатывает всякий ''х'' из Х Ç A в слово "да", а всякий ''х'' из ''Х\A'' в слово "нет"; | 2) "разрешает множество ''А'' относительно множества ''X''", коль скоро он применим ко всякому ''х'' из ''Х'' и перерабатывает всякий ''х'' из Х Ç A в слово "да", а всякий ''х'' из ''Х\A'' в слово "нет"; | ||
3) "перечисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. | |||
Функция называется [[вычислимая функция|вычислимой]], если существует вычисляющий её алгоритм. Множество называется [[Разрешимое множество|разрешимым]] относительно ''X'', если существует разрешающий его относительно ''Х'' алгоритм. Множество называется [[Перечислимое множество|перечислимым]], если либо оно пусто, либо существует перечисляющий его алгоритм. | |||
Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее — областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида <x, f(x)>. (IV) Подмножество А перечислимого множества Х тогда и только тогда разрешимо относительно X, когда А и Х \А перечислимы. (V) Если А и В перечислимы, то A' ÈB и А ÇВ также перечислимы. (VI) В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно X]. (VII) Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают пример алгоритма алгоритма с неразрешимой областью применимости. | |||
== Алгоритмические проблемы == | == Алгоритмические проблемы == | ||
