Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 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, bN2 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. Область применимости и множество результатов любого алгоритма перечислимы.

Date: 2015-07-23; view: 400; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию