Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

835

18. Помните закон экологической ниши! Не пытайтесь продвигать свое

лучшее решение в области, уже занятой и загаженной фанатиками не-

которой конкретной системы. Ищите обходные пути!

19. Помните, что все люди ошибаются

, и исправлять ошибку — не все-

гда лучшее. Порою надо, осознав ее, попытаться использовать и ее как

достоинство (хотя бы в данных конкретных условиях). Более того, не-

тривиальное решение нетривиальной задачи возможно, лишь если по

пути Вы пройдете через ошибки. Учитесь превращать ошибки в реше-

ния!

20. Еще хуже упорствовать на своей ошибке, и тем более ставить психо-

логическую защиту, не давая себе осознать ее. Если Вы сталкиваетесь

с таким поведением Вашего коллеги или партнера, ситуация практи-

чески безнадежная и нужно лишь думать о том, как с наименьшими

потерями из нее выпутаться.

21. Ищите обходные пути при каждом намеке на концептуальную труд-

ность. Если Вы его найдете, труды окупятся сторицей. Лобовое реше-

ние — худший из возможных паллиативов, и если Вам пришлось вре-

менно его принять, а работа над системой еще будет продолжэаться,

помечайте данный модуль как прототип.

22. Помните, что дурно исполненная своя карма лучше хорошо исполнен-

ной чужой. Лучше быть полноценным русским,чем недоделанным аме-

риканцем. Не стесняйтесь своих особенностей мышления и работы, и

не выставляйте их как принцип. В любом обществе будьте свободным

от него, если у Вас достаточно сил, чтобы это реализовать

, и сохра-

няйте в нем свое лицо, если Вы выбрали интеграцию.

23. Самоограничение чаще всего приводит к красивым решениям и к боль-

шим достижениям. Вседозволенность и примитивно понимаемая сво-

бода губительна. Смотрите, насколько стихи (самоограничение пшу-

щего) лучше и компактнее выражают мысль и чувства, чем проза (яко-

бы свободное выражение).

В том числе и авторы данной книги, и Вы.

Еще раз напоминаем, что негативизм — одна из форм конформизма, соответственно, асо-

циальное поведение не является признаком внутренней свободы.

836

ГЛАВА 16. ПОДВЕДЕНИЕ ИТОГОВ

24. Если Вам не удается сказать что-либо стихами, говорите прозой. Учи-

тесь отказываться от ограничений в нужный момент, но при этом не

забюывайте ставить себе другие!

25. Ничто, кроме души, не является абсолютной ценностью. Любая абсо-

лютизированная ценность превращается в идола. Поклонение идолам

губительно. Поэтому остерегайтесь! Особенно остерегайтесь абсолю-

тизации своих мнений и своих красивых находок!

Успехов Вам!

Приложение A

Математические модели

Здесь мы можем лишь дать обзор основных понятий и основных резуль-

татов в предельно популяризированной форме. На русском языке адекватно-

го учебника по математическим основам информатики просто нет.В качестве

некоторого (отличного по качеству и подбору материала, но, что и следовало

ожидать, выдержанного в других традициях обучения) пособия можно реко-

мендовать [84].

§ A.1. НЕСКОЛЬКО ТЕРМИНОВ

Порядок(частичный порядок) — транзитивное и иррефлексивное отно-

шение. Порядок обычно обозначается значками, подобными ≺. Два элемен-

та несравнимы, если неверно ни a ≺ b, ни b ≺ a. Множество с заданным на

нем порядком называется чум.

Предпорядок — транзитивное и рефлексивное отношение , обозначает-

ся подобно 4. Два элемента с точки зрения предпорядка эквивалентны, или

неразличимы, если a 4 b и b 4 a.

Порядок линейный, если любые два неравных элемента сравнимы. Пред-

порядок строгий, если неразличимые элементы равны.

Порядок полон, (или множество является полной решеткой), если в лю-

бом подмножестве есть верхняя и нижняя грани.

Порядок называется полным

, если любое непустое подмножество имеет

наименьший элемент. Множество с линейным полным порядком называет-

ся вполне упорядоченным. Стандартным вполне упорядоченным множеством

Пустячное отличие в словах, а какое отличие в смысле! Будьте внимательны, читая мате-

матические тексты!

837

838

ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

является множество ординалов.

Начальный отрезок ординалов имеет следующую структуру.

0, 1, . . . , n, . . . ω, ω + 1, . . . , ω + n, . . . 2 ·ω.

2 · ω, 2 · ω + 1, . . . , 2 · ω + n, . . . 3 · ω.

Обобщая по всем натуральным числам, получаем следующий ряд:

0, 1, . . . , k, . . . ω, ω + 1, . . . , ω + k, . . . 2 · ω, . . . n · ω . . . .

Вслед за всеми этими ординалами вида n · ω + k стоит ω

. А за ω

выстраи-

вается ряд, изоморфный предыдущему:

, ω

+ 1, . . . , ω

+ k, . . . ω

+ ω, ω

+ ω + 1, . . . , ω

+ ω + k, . . .

+ 2 · ω, . . . ω

+ n · ω . . . 2 ·ω

За всеми k · ω

+ l · ω + n стоит ω

Опять-таки продолжая по всем натуральным числам, получаем всевоз-

можные ординалы вида

· ω

+ k

n−1

· ω

n−1

+ ··· + k

ω + k

За ними идет ординал, обозначаемый ω

. А за ним опять-таки цепочка его

“сумм” со всеми предыдущими ординалами:

+ k

· ω

+ k

n−1

· ω

n−1

+ ··· + k

ω + k

Аналогично, мы приходим к 2 ·ω

, и далее к n ·ω

. Законы сложения степе-

ней сохраняются, и дальше идет ω

ω+1

. Таким образом приходим к ординалам

вида

· ω

ω+m

+ l

m−1

· ω

ω+(m−1)

+ ··· + l

· ω

+ k

n−1

· ω

n−1

+ ··· + k

· ω + k

А за ними идет ординал, который естественно обозначить ω

2·ω

. Продолжая

данный процесс, мы приходим к ординалам вида

···

n раз.

А за всеми этими башнями стоит ординал, который Г. Кантор назвал ε

определил как наименьшее решение уравнения ω

= α.

A.2. ВЫЧИСЛИТЕЛЬНЫЕ ИНТЕРПРЕТАЦИИ

839

Порядок фундирован, если любое линейно упорядоченное подмножество

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

нее всего следующая особенность полных порядков.

Любая убывающая последовательность через конечное число

шагов стабилизируется.

§ A.2. ВЫЧИСЛИТЕЛЬНЫЕ ИНТЕРПРЕТАЦИИ

Для рассмотрения вычислительных интерпретаций программы абстраги-

руются до схем программ. Схема отличается от программы тем, что все кон-

кретные понятия заменяются на абстрактные, например, вместо операции

сложения x + y пишется двухместная функция f(x, y). Это позволяет сосре-

доточиться на общих аспектах того, что такое исполнение, что такое удача

или неудача исполнения, что необходимо знать для того, чтобы исполнить

программу. Заодно это позволяет исследовать общие свойства программ, не

зависящие от примененных конкретных понятий, и общие их преобразова-

ния, что является самым ценным вкладом любой теории в практику.

Прежде всего, мы видим, что каждая схема содержит некоторый набор

переменных, функций и предикатов, которые в ней встречаются. В соответ-

ствии с этим определим

Определение A.2.1. Словарь (сигнатура) σ — тройка конечных множеств

hX, F, Pi, где X — непустое множество,элементы которого называются пере-

менными, F — множество функций (функциональных символов), P — мно-

жество предикатов (предикатных символов). Каждой функции и каждому

предикату сопоставлено натуральное число n > 0, называемое их арностью.

Если нужно явно указать арность функции, мы записываем f

, аналогично

для предиката.

Термы задаются следующим индуктивным определением.

a) Переменная — терм.

b) Если f

— функция, t

, . . . , t

— термы, то f(t

, . . . , t

) — терм.

Элементарная формула — выражение вида P (t

, . . . , t

), где P

— предикат,

— термы.

Конец определения A.2.1.

Определение A.2.2. Схема программ словаря σ — оснащенный ориентиро-

ванный граф с вершинами пяти типов.

840

ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

1) Входная вершина помечена списком переменных, называемых входными

данными схемы программ. Входная вершина в схеме одна. В нее не входит

дуг.

2) Выходная вершина помечена списком переменных,называемых результа-

тами схемы программ. Выходная вершина в схеме одна. Из нее не выхо-

дит дуг.

3) Функциональные вершины помечены присваиваниями вида

x ← t,

где x — переменная, t — терм.

4) Предикаты (называемые еще проверки, распознаватели или разветвле-

ния

) помечены элементарной формулой. Из предиката выходит две дуги,

помеченные символами + и −.

5) В соединения входит несколько дуг. Соединения ничем не помечены.

6) Если количество входящих или выходящих дуг для вершины некоторого

типа не указано, то оно равно 1.

Конец определения A.2.2.

Пример схемы программ можно посмотреть на рис. 3.3.

Определение A.2.3. Интерпретационная модель сигнатуры σ —тройка M =

hS, F, P i, где

• S — непустое множество, называемое универсом. Мы считаем, что оно

обязательно содержит элемент ⊥, интерпретируемый как ошибка.

• F — отображение, сопоставляющее каждому функциональному сим-

волу f

∈ F настоящую функцию F bfc ∈ (S

→ S); функция должна

удовлетворять условию корректности относительно ошибки: она рав-

на ⊥ тогда и только тогда, когда хотя бы один из ее аргументов равен

⊥.

Последние два термина чаще употребляются в связи с недетерминированными схемами

программ.

A.2. ВЫЧИСЛИТЕЛЬНЫЕ ИНТЕРПРЕТАЦИИ

841

• P — отображение, сопоставляющее каждому предикатному символу

∈ P отображение P bpc ∈ (S

→ {true, false, ⊥}), удовлетворяю-

щее условию корректности относительно ошибки.

Конец определения A.2.3.

Чтобы определить исполнение программы, необходимо помимо интерпрета-

ционной модели задать оценку входных переменных z: функцию, сопоста-

вляющую каждой входной переменной значение из S.

Определение A.2.4. Состоянием памяти схемы программ называется оцен-

ка переменных данной схемы программ. Состояние схемы программ — пара

из вершины и состояния памяти.

Исполнение E схемы программ — последовательность (конечная или бес-

конечная) пар ha

, z

i, где a

— вершины схемы, последовательность a

обра-

зует путь в схеме, и пары удовлетворяют следующим условиям:

1. a

— начальная вершина схемы;

2. Если a

— присваивание x

← t

, то состояние памяти z

i+1

отличается

от z

лишь тем, что значение z

i+1

) равно значению t

в состоянии z

при этом значение t

должно быть отлично от ⊥.

3. Если a

— не присваивание, то z

i+1

= z

4. Если a

—предикат P (t

, . . . , t

),то a

соединена с a

i+1

дугой,помечен-

ной символом +,если P (z

), . . . , z

)) истинна,и −,если P (z

), . . . , z

))

ложна.

Исполнение называется успешным, если его последняя вершина — выходная

вершина.

Исполнение при данной оценке y входных переменных — исполнение,

начальное состояние памяти которого z

определяется условием:

(

(x) = y(x) x входная;

(x) = ⊥ иначе.

Конец определения A.2.4.

842

ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

Преобразование оценок переменных, примененное в п. 2, имеет важное зна-

чение в семантике, называется заменой значения переменной и обозначается

y = z ∗ hx, si или y = z [x | s] .

В нашем случае

i+1

= z

∗ hx

, s

где s

= z

). Часто такое преобразование применяется сразу к конечному

числу переменных и обозначается

y = z ∗ hhx

, . . . x

i, hs

, . . . , s

ii или y = z [x

, . . . x

| s

, . . . , s

] .

Согласно приведенному определению, схема программ в каждой интерпре-

тации задает частичную функцию Θ из оценок входных переменных в оцен-

ки выходных переменных. Θ(z) = y, если существует успешное исполнение

схемы при оценке z, и оценка выходных переменных в последней вершине

есть y.

Рассматривая исполнения программ в различных интерпретациях, можно

установить критерии эквивалентности программ, а, опираясь на эти крите-

рии, можно развить системы эквивалентных преобразований программ.

Определение A.2.5. Две схемы программ называются функционально экви-

валентными, если определяемые ими функции совпадают во всех интерпре-

тациях.

Пусть дано исполнение E схемы программ. Историей исполнения про-

граммы называется последовательность, строящаяся по следующему алго-

ритму.

1. (Инициализация) Начальной вершине сопоставляется в качестве теку-

щей оценки оценка входных переменных ими самими;

repeat

2. Следующая вершина, если она не является присваиванием или преди-

катом, истории не изменяет;

3. Если следующая вершина является присваиванием x ← t, то текущая

оценка

заменяется на t, в которое вместо вместо переменных подста-

влены их текущие оценки; полученная оценка становится очередным

членом истории исполнения;

A.2. ВЫЧИСЛИТЕЛЬНЫЕ ИНТЕРПРЕТАЦИИ

843

4. Если текущая вершина является предикатом, то в его аргументы-термы

подставляются текущие оценки всех переменных, и полученное выра-

жение становится очередным членом истории; текущая оценка не из-

меняется;

until

конечная вершина;

5. (Завершение) Конечной вершине сопоставляется ограничение текущей

оценки на множество выходных переменных.

Две схемы программ называются логико-термально эквивалентными, если

их истории исполнения совпадают в любой интерпретации при любой оцен-

ке входных переменных.

Конец определения A.2.5.

Функциональная эквивалентность схем программ неразрешима, а логико-

термальная разрешима. Имеется полная система преобразований схем про-

грамм, сохраняющих логико-термальную эквивалентность.

Имеются три стандартных блока схем программ, рассматриваемых как

структурные блоки:последовательное соединение, разветвление и цикл Кну-

та (см. рис. A.1).Схема программ, которую можно получить из присваиваний

конечным числом применений стандартных блоков к уже построенным ра-

нее таким образом блокам, и затем добавлением входа и выхода, называется

структурированной схемой программ.

К каждой схеме программ можно добавить конечное число булевых пе-

ременных таким образом, что после этого она функционально эквивалентно

преобразуется в структурированную схему программ (теорема Бема-Джако-

пини). Без добавления дополнительных переменных цикл Бема-Джакопини

(см. рис. 3.4) и многие другие программы в структурную форму не преобра-

зуются.

Более детальное изложение рассмотренных в данном параграфе вопросов

можно найти в книге [44] или [45].

Еще один важный вопрос — можно ли избавиться от дополнительных

переменных, ослабив понятие структурности, введя понятие структурного

завершителя цикла. Очевидно, что цикл Бема-Джакопини структурируется

введением завершителя цикла,но этот завершитель, как показано на рис.A.2,

действует на два уровня структурной иерарахии вверх:мы выходим из услов-

ного предложения, вложенного в цикл, а затем уже из цикла.

844

ПРИЛОЖЕНИЕ A. МАТЕМАТИЧЕСКИЕ МОДЕЛИ

A BP

Рис. A.1. Три структурных блока схем программ

§ A.3. МОДЕЛИ ЯНОВА

Важным частным классом схем программ и соответствующих им вычи-

слительных моделей являются схемы Янова.

Определение A.3.1. Схема Янова — схема программ, в которой есть лишь

одна переменная, все функции и предикаты одноместные, все присваивания

имеют вид x ← f(x), причем функция f для каждого присваивания уникаль-

на.

Модель Янова —вычислительная модель,в которой все предикаты и функ-

ции одноместные, снабженная дополнительным значением s ∈ S, называе-

мым текущим состоянием мира. В модели Янова S называется множеством

(или универсом) полных состояний вычислительной системы (или прибора,

или мира; конкретный содержательный термин берется в зависимости от за-

дачи);