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

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Строка 4: Строка 4:


== Основные понятия ==
== Основные понятия ==
Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм ''Á'' говорят, что он:  
Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм <math>\cal A</math> говорят, что он:  


1) "вычисляет функцию ''f''", коль скоро его область применимости совпадает с областью определения ''f'' и ''Á'' перерабатывает всякий ''x'' из своей области применимости в ''f(x)'',  
1) "вычисляет функцию <math>f</math>", коль скоро его область применимости совпадает с областью определения <math>f</math> и <math>\cal A</math> перерабатывает всякий <math>x</math> из своей области применимости в <math>f(x)</math>,  


2) "разрешает множество ''А'' относительно множества ''X''", коль скоро он применим ко всякому ''х'' из ''Х'' и перерабатывает всякий ''х'' из Х Ç A в слово "да", а всякий ''х'' из ''Х\A'' в слово "нет";  
2) "разрешает множество <math>A</math> относительно множества <math>X</math>", коль скоро он применим ко всякому <math>x</math> из <math>X</math> и перерабатывает всякий <math>x</math> из <math>X\cap A</math> в слово "да", а всякий <math>x</math> из <math>X\setminus A</math> в слово "нет";  


3) "перечисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В.  
3) "перечисляет множество <math>B</math>", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть <math>B</math>.  


Функция называется [[вычислимая функция|вычислимой]], если существует вычисляющий её алгоритм. Множество называется [[Разрешимое множество|разрешимым]] относительно ''X'', если существует разрешающий его относительно ''Х'' алгоритм. Множество называется [[Перечислимое множество|перечислимым]], если либо оно пусто, либо существует перечисляющий его алгоритм.
Функция называется [[вычислимая функция|вычислимой]], если существует вычисляющий её алгоритм. Множество называется [[Разрешимое множество|разрешимым]] относительно <math>X</math>, если существует разрешающий его относительно <math>X</math> алгоритм. Множество называется [[Перечислимое множество|перечислимым]], если либо оно пусто, либо существует перечисляющий его алгоритм.


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


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


== Приложения теории алгоритмов ==
== Приложения теории алгоритмов ==
'''Теорию алгоритмов''' имеет приложения во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают в математической логике и теории моделей; для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех её предложений (теории подразделяются на разрешимые и неразрешимые — в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч установил неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому, А. И. Мальцеву и др. Алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп: первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо А. А. Марковым и Э. Л. Постом, а пример группы с неразрешимой проблемой тождества — в 1952 П. С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 А. А. Марковым); в теории чисел (остающаяся до сих пор открытой проблема разрешимости диофантовых уравнений) и др. разделах математики.
'''Теорию алгоритмов''' имеет приложения во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают в математической логике и теории моделей; для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех её предложений (теории подразделяются на разрешимые и неразрешимые — в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч установил неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому, А. И. Мальцеву и др. Алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп: первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо А. А. Марковым и Э. Л. Постом, а пример группы с неразрешимой проблемой тождества — в 1952 П. С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 А. А. Марковым); в теории чисел (остающаяся до сих пор открытой проблема разрешимости диофантовых уравнений) и других разделах математики.


'''Теорию алгоритмов''' тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики — понятие исчисления и потому, например, теорема К. Гёделя о неполноте формальных систем может быть получена как следствие теорем А. т. Наконец, '''теория алгоритмов''' тесно связана с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности '''теория алгоритмов''' даёт аппарат, необходимый для разработки конструктивного направления в математике; в 1965 А. Н. Колмогоров предложил использовать '''теорию алгоритмов''' для обоснования информации теории. '''Теорию алгоритмов''' образует теоретический фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в т. н. программированном обучении.
'''Теорию алгоритмов''' тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики — понятие исчисления и потому, например, теорема К. Гёделя о неполноте формальных систем может быть получена как следствие теорем теории алгоритмов. Наконец, '''теория алгоритмов''' тесно связана с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности '''теория алгоритмов''' даёт аппарат, необходимый для разработки конструктивного направления в математике; в 1965 А. Н. Колмогоров предложил использовать '''теорию алгоритмов''' для обоснования информации теории. '''Теорию алгоритмов''' образует теоретический фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в так называемом программированном обучении.




Навигация