Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Доказательство. Для пустого множества искомый алгоритм – константа F, а для множества X — константа T. чтдЛемма 2. Разрешимое подмножество S перечислимого множества M перечислимо. Доказательство. Пусть S – разрешающий алгоритм для S, а M – перечисляющий алгоритм для M. Построим перечисляющий алгоритм S ¢ для S. Если S =Æ, то S ¢:= F, если же S ¹Æ, то существует элемент s Î S. Тогда S ¢:= for m Î M do if S (m) then yield m else yield s end if end for. чтд Отсюда немедленно следует, что всякое разрешимое подмножество натурального ряда перечислимо. Лемма 3. Подмножество S перечислимого множества M разрешимо тогда и только тогда, когда перечислимо как S, так и его дополнение M \ S. Доказательство. [Þ] Если множество S разрешимо относительно M, то множество M \ S также разрешимо, и остается применить лемму 2. [Ü] Если S или M \ S пусто, то по лемме 1 S разрешимо. Пусть теперь S и M \ S оба не пусты и перечислимы перечисляющими алгоритмами S и S ¢ соответственно, а вычислимые функции F и F ¢: N® M доставляют элементы этих множеств по номерам. Тогда следующий алгоритм разрешает множество S: Proc SS (s: M): bool n:=0; while true do n:= n + 1; x:= F (n); y:= F ¢ (n); if x = s then return T end if; if y = s then return F end if; End while. чтд Лемма 4. Если функция вычислима, то образ перечислимого множества перечислим. Доказательство. Пусть функция F: Dom F ® Im F вычислима, а множество AÍ Dom F перечислимо, тогда множество F(A) Í Im F перечисляется следующим алгоритмом: for xÎA do yield F(x) end for. чтд Лемма 5. Если функция вычислима и определена на перечислимом множестве, то прообраз перечислимого множества перечислим. Доказательство. Пусть функция F: Dom F ® Im F вычислима, а множество B перечислимо вычислимой функцией h, и множество Dom F перечислимо вычислимой функцией g. Если F –1(B)=Æ, то прообраз перечислим, иначе существует элемент sÎ F –1(B). Тогда множество F –1(B) перечисляется следующим алгоритмом: for < a, b >Î N2 do if f (h (a))= g (b) then yield h (a) else yield s end if end forчтд
4.4 ¢ .4. Протокол выполнения алгоритма Программистская практика свидетельствует, что программы иногда удаётся отладить, то есть найти и устранить ошибки, содержащиеся в алгоритмах. Процесс отладки основан на том, что за работой алгоритма возможно наблюдение, в частности, для любого алгоритма и для любого случая выполнения этого алгоритма можно составить протокол выполнения, в котором исчерпывающим образом отражается история выполнения алгоритма (для заданных входных данных). Другими словами, в самих алгоритмах и в их выполнении нет ничего чудесного, ничего такого, чего нельзя записать словами в алфавите U. Следующий факт мы принимаем без доказательства, как априорное свойство интуитивного понятия алгоритма. Аксиома [протокола]. Для каждого алгоритма A существует разрешимое множество H и существуют вычислимые функции a: H ® U * и z: H ® U *, такие что A (x)= y тогда и только тогда, когда существует такое h Î H, что a (h)= x и z (h)= y. Множество H — это множество всех возможных протоколов выполнения алгоритма A, h — это протокол выполнения с входом x и выходом y, а функции a и z — это функции определения входов и выходов, соответственно. Отступление. Если для каждой пары < x, y >, для которой A (x)= y слово h Î H, такое что a (h)= x и z (h)= y не только существует, но и единственно, то алгоритм называется детерминированным. В протоколе детерминированного алгоритма порядок действий строгий линейный (п. 1.8.1). В сформулированной аксиоме протокола единственность не требуется, тем самым допускается, что выполнение алгоритма может быть недетерминированным. В протоколе недетерминированного алгоритма порядок действий нестрогий частичный (п. 1.8.1). В недетерминированности нет ничего страшного, более того, это путь к параллельному программированию и другим современным подходам в информационных технологиях. Поэтому накладывать требование детерминированности без необходимости не следует. Следствие 1. Область применимости и множество результатов любого алгоритма перечислимы.
|