16.Рекурсивно перечислимые множества. Связь между рекурсивной перечислимостью и рекурсивностью.

Множество – это некоторая совокупность элементов. Если множество содержит конечное число элементов, то оно называется конечным. Конечные множества можно задавать непосредственным перечислением содержащихся в них элементов. Бесконечные множества задают, как правило, указанием свойства, которым обладают его элементы. Свойства задают с помощью формул.

Формула, с помощью которого определяется множество, называется характеристической формулой этого множества. Например, множество положительных четных чисел можно задать таким образом

М1={ x | x = 2*N}

Множество составных целых положительных чисел можно задать так

М2 = { x | n≠1m≠1 (x=m*n)}

Здесь символ  означает “существует” и называется квантором существования. Наряду с квантором существования, имеется еще квантор всеобщности - . С помощью квантора всеобщности можно записать характеристическую формулу множества всех простых чисел М3:

М3 = { x | n≠1 m≠1 (x ≠m*n)}

Определим множество

M^co={ x | x  M}.

Множество M^co называется дополнением множества М.

Определение. Множество называется рекурсивным, если его характеристическая функция общерекурсивна.

Особенностью рекурсивного множества является то, что для любого х можно с помощью алгоритма вычисления характеристической функции данного множества проверить, принадлежит ли ему х или нет. Поскольку существуют не рекурсивные множества, постольку не для всякого множества можно построить алгоритм для выяснения принадлежности к нему произвольного элемента. Любопытными примерами нерекурсивных множеств являются следующие.

Определение. Множество A называется рекурсивно перечислимым, если его характеристическая функция f(x) частично рекурсивна, причем

Мы помним, что частичная рекурсивность характеристической функции означает, что значение этой функции для некоторых элементов не известно (машина Тьюринга зацикливается на подобных входах). Однако в случае рекурсивной перечислимости, машина зацикливается тогда и только тогда, когда она пытается распознать элемент не из своего множества.

!!! 1.Доказать, что если множество A и его дополнение A^co рекурсивно перечислимы, то A – рекурсивное множество; 2. Пусть А и В рекурсивно перечислимы. Доказать, что таковым будет и множество A  B, A  B, A \ B.

17.Сложность.Подходы к определению сложности алгоритмов.

Аппарат машин Тьюринга позволяет изучить сложностные свойства алгоритмов. В информатике имеется несколько различных подходов к определению понятия сложности алгоритма. Например, понимают под сложностью число проверяемых логических условий. Каждое логическое условие определяет две различные ветки (пути) развития вычислительного процесса. Пусть число всех различных путей в программе есть N. Пусть p_i - вероятность прохождения программы по i-му пути.

Тогда мерой информационной сложности алгоритма (программы) считают энтропию Э, вычисляемую по формуле:

Информационная сложность характеризует возможность п о н я т ь работу алгоритма. Чем больше величина энтропии, тем больше усилий требуется, чтобы разобраться в логике программы. Однако для практики большее значение имеет не информационная, а алгоритмическая или вычислительная сложность алгоритма. Понятие алгоритмической сложности введено советским математиком А.Н.Колмогоровым. Под алгоритмической сложностью он понимал минимально необходимый размер программы для данного алгоритма. Колмогоров полагал, что чем меньше размер записи программы, тем меньше ее сложность. На этом пути ему и его коллегам удалось получить ряд ценных результатов. Вместе с тем оказывается, что даже небольшие по длине записи программы могут требовать огромного времени счета на ЭВМ и это время катастрофически растет с ростом размера входных данных.

Таким образом, выявляется необходимость ввести иную концепцию сложности – вычислительную сложность задачи и связать вычислительную сложность задачи с числом тактов, затрачиваемых машиной Тьюринга, реализующей алгоритм решения этой задачи за кратчайшее возможное число ходов.