Объектно-ориентированное программирование

Объектная ориентированность пытается претворить в жизнь общие принципы разработки программного обеспечения и программ с помощью учета конкретных способов разработки и использования вполне определенных средств описания. Исторически объектная ориентированность восходит к языкам программирования Simula-67 и Smalltalk. В настоящее время одним из наиболее употребительных на практике языков этого типа является C++.

Для обычных фаз разработки программ характерны следующие моменты объектной ориентированности:

·         объектно-ориентированный анализ,

·         объектно-ориентированный проект,

·         объектно-ориентированное программирование.

Это образование понятий проистекает из классического разбиения процесса разработки программного обеспечения на отдельные фазы. На фазе анализа выясняется специфика применения с целью охватить требования к разрабатываемой программной системе. На фазе проектирования вырабатывается структура системы (ее архитектура). На фазе реализации программируются части системы, предусмотренные в проекте. В дальнейшем будет рассмотрено прежде всего объектно-ориентированное программирование (00-программирование).

При 00-программировании опираются на следующие концепции:

·         инкапсуляция данных,

·         классы и наследование,

·         объекты и воплощение (динамическое создание новых объектов),

·         вызов методов и обмен сообщениями.

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

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

·         модульность,

·         унификация и систематика,

·         модифицируемость и гибкость,

·         повторная применимость (переносимость).

Принцип модульности преследует цель строить систему из замкнутых частей ("строительных кирпичиков"), для использования которых не нужно знать деталей их реализации, а достаточно знать лишь их действие на точках разреза (т. е. интерфейс). Детали реализации скрываются (англ. information hiding) от пользователя. Благодаря этому пользователь модуля не обременяется ненужными для него деталями и не может их использовать при применении модуля. Тем самым детали реализации модуля могут быть изменены без того, чтобы возникали какие-либо проблемы при его использовании, если только сохраняются требования спецификации на интерфейс. Это снова соответствует уже обсуждавшемуся принципу делать различие между аспектами доступа и реализации.

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



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

Можно различать следующие два основных направления 00-программирования:

(а) объектная ориентированность в традициях программной инженерии (как она выступает, например, у Б. Майера или реализуется в языках Smalltalk, Eiffel, а также в вариантах языка С),

(б) объектная ориентированность в традициях "искусственного интеллекта" (проявляющаяся в 00-расширениях языка LISP или во фреймах, в частности при разработке экспертных систем).



В дальнейшем будет ориентация на направление (а), поскольку там более заметную роль играют важные для нас вопросы проектирования и методики.

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

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

·         последовательное выполнение (как в Simula, C++, Eiffel, Smalltalk),

·         параллельное выполнение (00-SDL, GRAPES).

В 00-языках программирования с последовательной моделью выполнения, как и в классических императивных ЯП, вызовы процедур (которые здесь часто называют вызовом метода) обрабатываются последовательно. При параллельной же модели объекты действуют параллельно и обмениваются сообщениями. Впрочем, языки с параллельной моделью выполнения в настоящее время являются еще предметом исследования. Однако с учетом все возрастающей роли распределенных систем ЭВМ под терминами вычислительные сети, системы клиент/сервер и распределенные информационные системы значение таких языков становится все более важным.

Центральными понятиями для объектной ориентированности являются классы

и объекты. Класс понимается как единица описания (аналог аксиоматической спецификации или модуля), состоящая из объявлений программных переменных, обозначений констант (в 00-программировании говорят об атрибутах класса), а также функций, процедур (здесь говорится о методах)

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

·         типов (типы данных),

·         функций, процедур (или методов),

·         переменных (или атрибутов),

·         каналов коммуникаций,



·         других классов (при определенных обстоятельствах).

Класс имеет обозначение, которое используется (также как тип) для объявления объектов этого класса.

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

Класс есть поименованная единица описания. В процессе выполнения 00-программы с помощью этой единицы генерируются объекты данного класса. Поэтому с этим классом во время выполнения программы можно связать множество генерируемых объектов данного класса.

Под термином объектная ориентированность между тем охватываются хорошо известные принципы software-инженерии. При этом в основе лежит принцип модульности,

который подразумевает известные критерии software-систем:

·         модульную декомпозицию (модульная разложимость системы на под системы),

·         модульную композицию (модульная собираемость системы из подсистем),

·         модульную понимаемость (независимая понимаемость подсистемы),

·         модульную стабильность (модульная модифицируемость, локальность изменений),

·         модульную инкапсуляцию (модульная защита, однозначно установленные права и методы доступа).

Модульность требует особенно тщательной спецификации и описания взаимодействия (интерфейса) между составными частями software-системы. Поэтому формульная спецификация поведения интерфейса представляет особый интерес.

Для образования интерфейса выдвигаются следующие пять принципов, которые сохраняют свою силу и вне объектной ориентации:

·         синтаксически ясная и независимая формулируемость единиц (частей системы),



·         небольшое число точек разреза (интерфейсов) (адекватная гранулированность проекта системы),

·         простота интерфейса ( простота точек разреза, их адекватный выбор),

·         явное описание интерфейса,

·         упрятывание информации о реализации (принцип инкапсуляции).

Честолюбивая цель объектной ориентированности состоит в обеспечении широкого повторного использования программ, проектов, архитектур, спецификаций и концепций с помощью схематизации образа действий. При этом внедряются следующие категории схем:

·        схема объявлений типов,

·        схема родственных вычислительных структур (типы и алгоритмы),

·        схема для вычислительных предписаний.

На переднем плане стоит осознание структурных и поведенческих общностей с целью:

·        независимость представления (упрятывание информации),

·        использование общностей родственных единиц.

Многократное использование поддерживается следующими концепциями:

·        перезафузки (англ. overloading) операторов,

·        наследования,

·        полиморфизма,

·        инкапсулированных, параметризуемых, генерируемых структур.

В объектной ориентированности присутствует как параметрический полиморфизм, так и ad-hoc-полиморфизм (перекрытие).

В параметрическом полиморфизме используются те же самые тела функций и, соответственно, процедур, которые работают с объектами различных типов. В ad-hoc-полиморфизме

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


late binding). При этом получается тесная связь с подтипами, когда рассматриваются частичные отношения между множествами носителей и выбор вычислительного предписания осуществляется динамически при его применении к объектам.

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

Существенными, техническими составными частями объектной ориентированности являются:

·         концепция классов с отношениями наследования и быть частью (иерархия классов, отношение "является частью"),

·         концепция коммуникации и устойчивость программных переменных (см. ниже),

·         динамическое создание (воплощение) и удаление объектов.

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

Отношение наследования "класс А есть один из классов В" выражает, что объект класса А является также и объектом класса В. Это значит, что класс А обладает всеми составными частями и свойствами (всеми атрибутами и методами), которые имеет класс В, и в данном случае еще некоторыми дополнительными. Класс А наследует составные части класса В. При наследовании делается различие между

·         единственным и

·         множественным

наследованием.


При единственном наследовании один класс наследует свойства самое большее от одного из классов. При множественном наследовании один класс наследует свойства от нескольких других классов.

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

Далее даются простые примеры классов и 00-концепций, чтобы разъяснить эти понятия.

Алгебраические спецификации, как спецификация POOL в разд. 5.1.2, описывают вычислительные структуры. Подкласс алгебраической спецификации можно образовать следующим образом:

spec QUEUE =

import POOL,

sort bool, data, queue data,

subsort queue data inherits from set data,

fct deq ==  ( queue data ) queue data,

fct next = ( queue data ) data Axioms:

deq(add(empty, e)) = empty,

next(add(empty, e)) = e,

deq(add(add(q, d), e)) = add(deq(add(q, d)), e),       ~

next(add(add(q, d), e) = next(add(q, d)) end_of_spec spec QUEUE 1 =

sort bool, data, queuel data,

subsort queuel data inherits from queue data Axioms:

any(s) = next(s) end_pf_spec

Переменная v типа var queue data может принимать значения типа queue data или типа queuel data. Тем самым результат вызова any(v) будет зависеть от типа переменной v. Если значение v имеет тип

queuel data, то вызов any(v) соответствует вызову next(v), в противном случае - нет. Тогда говорится о полиморфизме

и о динамическом связывании

(англ. late binding).

Как правило, объекты имеют состояния, которые определяются значениями их атрибутов. Это ведет к понятию устойчивости,

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

Атрибуты в качестве значений могут содержать также ссылки на объекты. Это определяет структуру связей между объектами.

Операционно можно смоделировать устойчивость посредством спецификации большого глобального пространства состояний, в котором состояния отдельных объектов содержатся как частичные состояния.


Каждый метод может изменять соответствующую часть.

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

Модульной формализации устойчивости данных можно достигнуть, например, с помощью следующих математических концепций:

·         автоматов ввода/вывода,

·         потокообрабатывающих функций,

В частности, объект можно понимать как машину состояний с входом и выходом.

Пример (описание классов для объектов с устойчивостью данных). Типичный для 00-программирования пример класса выглядит следующим образом:

class SET_CLASS = based on:            SET Attributes:          s : set data Methods:           put_empty,

              padd      param data,

                    pdelete    param data Selektors:            sisempty:   -> bool,

                    siselem:    data -> bool,

                    sany:      -> data Axioms:             put_empty = [ s := empty ],

padd(x) = [ s := add(s, x) ],

pdelete(x) s [ s := delete(s, x) ],

siselem(x) = iselem(s, x),

sisempty = isempty(s),

sany = any(s) end_of_class

Здесь речь идет о классе 00-языка программирования с последовательной моделью выполнения.

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

Пример (описание класса интерактивного объекта). Типичным для 00-программирования примером является следующее описание класса:

class INTERACTIVE_SET_CLASS = Based on:     SET State:        set data Input Channel Messages:

message, data -> message, data ->• message, message, data -> message, message,

put_empty:

padd:

pdelete:

sisempty:

siselem:

sany:

data bool

Output Channel Messages:

message, message,

data:

bool:

Axioms:

(см. табл.11.1) end_of_class

Поведение объекта класса задано таблицей переходов состояний. Здесь речь идет о примере класса 00-языка программирования с параллельной моделью

выполнения.

 

                       Таблица 11.1. Таблица переходов состояний для класса

Ввод	Состояние ввода	Вывод	Следующее состояние
Putempty	S		Empty
Padd(d)	S		add(s, d)
Pdelcte(d)	S		delete(s, d)
Sisempty	S	bool(isempty(s))	S
Siselem(d)	S	bool(iselem(s))	S
Sany	S	data(any(s))	S

Объекты возникают во время выполнения программы как воплощения классов. Во многих 00-языках программирования существуют универсальные методы специально для создания объектов. Созданные объекты, как правило, идентифицируются ссылками. В более сложных примерах также и ссылки на объекты могут возвращаться в качестве результатов.

Формализация этого обращения с классами и объектами возможна с помощью явного представления ссылок и создания объектов. Это ведет к понятию состояния по аналогии с состоянием памяти

Пример (классы с созданием объектов). Приведем типичный пример класса с созданием объекта:

class QUEUE_CLASS = Based on: QUEUE

Attributes: d : data, b : bool, s : Pointer to QUEUE_CLASS,

Methods:   put_empty,

padd    param data, pdeq

Selectors:   qisempty: -> bool, qnext:    -»data

Axioms:    put_empty = [b := true ],

padd(x) = [if b      then       d := x;

b := false;

create(s);

s.put_empty(s) else       s.padd(x) fi], pdeq =   [if qisempty(s)  then    b :== true

else    d :== qnext(s); s.pdeq(s) fi], qisempty = b, qnext = d

end_of_class

Концепция наследования касается таких составных частей класса, как:



·         атрибуты (компоненты состояния),

·         методы (функции и процедуры)

как имена (ad-hoc-полиморфизм), как предписания (параметрический полиморфизм),

·         свойства поведения.

Дополнительные отношения на классах и объектах, которые часто имеют место в 00-описаниях, это:

·         является (чем-либо),

·         знает, использует, клиент,

·         является частью (чего-либо).

Эти отношения выражают определенные связи между объектами некоторого класса. Для разработки систем и software представляет интерес формализация этих отношений.

00-программирование является, несомненно, одним из наиболее интересных направлений для профессиональной разработки программ. Впрочем, здесь имеются еще нерешенные проблемы:

·         интерфейс часто бывает недостаточно описан;

·         в проектировании software концепция воплощения трудно осваивается и просматривается;

·         нахождение классов часто бывает трудным и требует больших затрат;

·         отсутствуют формальные модели;

·         концепция модульности для программирования по большому счету недостаточна (классы для этого слишком мелки); связь с обычной software-инженерией зачастую описана неясно (E/R-моделирование, переход от последовательной модели выполнения программ к параллельной).

Тем не менее, от объектной ориентированности ожидаются большие выгоды в отношении снижения стоимости, повышения качества и повторной применимости software.

Объявление элемента

Пусть х - любой идентификатор, s - тип, а Е - выражение этого типа; тогда s х: Е называется объявлением элемента или согласованием элемента с идентификатором х. Через объявление элемента идентификатор х связывается со значением выражения Е. С помощью такого объявления принимается соглашение о том, что с этого момента х стоит в качестве этого значения.

Область связанности, порождаемая объявлением ограничивается блоком, в начале которого и помещаются объявления. Пусть G -объявление, а ЕО - выражение. Тогда

[О; EO]

есть блок. Угловые скобки называют скобками блока. Они ограничивают область действия объявления G,

т.е. область связанности идентификатора, порождаемую объявлением G. Это значит, соглашение о том, что объявленный в G идентификатор стоит в качестве соответствующего значения, действительно только внутри скобок блока.

Синтаксис объявления элемента описывается следующим БНФ-правилом:

<объявление_элемента>:: =<тип><идентификатор>=<выражение>

Пусть для объявления элемента справедливы следующие дополнительные условия:

·

тип выражения Е есть s;

·         х не входит свободно в Е.

Второе условие указывает на то, что в модельном языке не допускаются рекурсивные объявления элементов.

Пример (объявление элемента). С помощью объявления

nat х = 3 + 4

принимается соглашение о том, что х имеет значение 7. Это объявление может использоваться в каком-либо блоке. Блок

[nat x =3+4;x*x]

имеет тогда значение 49. Внутри блока х стоит в качестве значения 7.

В ЯП вместо угловых скобок часто записываются также begin и end. Тогда блок будет записываться в виде

begin s х = El; E2 end

Скобки блока begin (соответствующая [) и end (соответствующая ]) ограничивают область действия описания для идентификатора х. Внутри этой области могут приниматься другие, вложенные соглашения, и тогда исходное соглашение на время теряет свою силу (становится "невидимым"). Так, значение блока

[nat х= 1; [nat х =2; х ] + х ] идентично блоку

[nаt х = 1; [nat у = 2; у ] + х ].

Систематическое переименование идентификаторов в локальных объявлениях в блоке (аналог -редукции) не меняет значения блока.

В программном выражении какой- либо идентификатор может объявляться повторно - тем самым принимаются различные соглашения относительно его связывания, и тогда один и тот же идентификатор в разных местах выражения будет иметь различные значения. Впрочем, все эти области связанности должны быть вложенными. Поэтому при наличии объявлений необходимо делать различие между областью действия объявления и длительностью жизни связывания идентификатора. В разделе

[s x=- El; E2]

соглашение о связывании идентификатора х со значением Е1 имеет силу во всей области, находящейся между угловыми скобками, в частности и в E2, причем действие этого соглашения прерывается с помощью соглашений, принимаемых (через соответствующие объявления) в E2. Это проясняет различие между длительностью жизни и областью видимости связывания. Длительность жизни, т.е. область связанности, охватывает всю область между угловыми скобками (т.е., в частности, и полностью E2). А область видимости соответствует длительности жизни за вычетом внутренних блоков с новыми связываниями для х.

С помощью объявления элемента устанавливаются конкретизации для соответствующего идентификатора. Область действия такой конкретизации ограничивается угловыми скобками. Внутри угловых скобок х стоит в качестве значения выражения Е1. Семантически это означает, что E2 интерпретируется с соответствующим изменением конкретизации для х. Значение I[G] объявления G можно понимать как "точечное" (локальное) изменение подстановки и тем самым как отображение между конкретизациями.

Caмo объявление не обладает никаким простым элементом данных в качестве значения, поэтому оно не вычисляется непосредственно с помощью правил подстановки термов. В дальнейшем будет даваться исключительно правило для вычисления значения выражения, в котором встречается объявление.

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

Объявления функций

Идентификаторы используются не только как держатели мест и имена для элементов данных, но и как обозначения функций. Аналогично объявлению элемента, идeнтификаторы для функций объявляются ("принимаются соглашения") с помощью записи вида

fct f= (s1x1, ..snxn) s: E и говорят об объявлении функции

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

Синтаксис объявления функций очень схож с объявлениями элементов. Правда, требуется, чтобы правая часть всегда была абстракцией функции. Точная функциональность в левой части объявления не требует задания, поскольку она непосредственно может быть установлена из правой части. Достаточно в левой части задать лишь ключевое слово fct. <объявление_функции>::== fct <идентификатор>=<абстракция функции>.

В отличие от упомянутого ранее ограничения на объявления элементов допускается рекурсивное объявление функции. Объявление функции называется рекурсивным,

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

чтобы подчеркнуть алгоритмический характер объявления функции.

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

Операционально (нерекурсивное) объявление функции в каком-либо блоке может быть разъяснено с помощью подстановки (развертывание, англ. unfold): [fct f=F;E]

E[F/f].

Это правило не может применяться для рекурсивных объявлений функций, в которых идентификатор f встречается в теле F.
В случае рекурсии в возникающем после подстановки выражении могли бы существовать дальнейшие вызовы f, причем идентификатор f больше не был бы связан данным объявлением.

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

[nat х = 1; [fсt f = (nat у) nat: х + у; [nat х = 2; f(3)] ] ]

возникает вопрос: дает вызов f(3) значение 4 или 5? Это зависит от упорядочения вхождения идентификатора х в тело f по отношению к одному из обоих объявлений х.

По вышеприведенному определению f(3) имеет значение 4, так как х в теле функции f связывается через первое объявление со значением 1. Говорят о статическом связывании (англ. static scoping): идентификаторы х, которые входят свободно в вычислительное предписание, связываются ("статически") с помощью ближайшего внешнего объявления х, содержащегося в записи, которая охватывает место описания вычислительного предписания. Это выражается также в приведенном выше правиле вычисления благодаря требованию переименования локальных идентификаторов при конфликте имен.

В противоположность статическому связыванию, динамическое связывание (англ. dynamic scoping) в этом примере f(3) даст значение 5. Свободные идентификаторы х в теле вычислительного предписания при динамическом связывании связываются с ближайшим внешним объявлением х, которое охватывает место вызова функции в вычислительном предписании. Имеются ЯП, которые - в противовес введенному нами языку -используют динамическое связывание идентификаторов. Однако это приводит к сложным правилам анализа программ и, вообще говоря, рассматривается как неблагоприятное обстоятельство.

Общие программные переменные

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

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

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

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

Пусть Е - булевское выражение, a S - оператор или последовательность операторов. Если S может содержать чреватые конфликтами действия, то следует писать охраняемую критического область в виде await Е then S endwait, чтобы выразить, что оператор S должен выполняться только при условии Е и при взаимном исключении других охраняемых критических областей.
Условие Е называется стражем, а оператор S - критической областью.

Упомянутая охраняемая критическая область выполняется следующим образом. Осуществляется ожидание до тех пор, пока не будет достигнуто состояние, в котором выражение Е дает значение true

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

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

Пример (недетерминизм в параллельных программах с критическими областями). Программа

await true then z := I endwait || await true then z := 2 endwait ||

допускает выполнение

await true then z := I endwait; await true then z := 2 endwait

с конечным состоянием z = 2, а также выполнение

await true then z :== 2 endwait; await true then z := I endwait

с конечным состоянием z = 1.

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

Буферизованные посылки/приемы сообщений можно понимать как использование особой вычислительной структуры (а именно структуры очереди) в форме общих переменных.



Особые общие переменные являются семафорами

- они служат исключительно для синхронизации процессов. Различают булевские и целочисленные семафоры. Целочисленный семафор s вводится в потребление с помощью объявления sema nat х: == n.

Это равносильно объявлению программной переменной типа nat, с точностью до следующих ограничений на использование. Семафор s разрешается использовать только с помощью вызовов процедур P(s) и V(s), а не какими-либо присваиваниями или опросами. Процедуры Р и V определяются следующим образом:

proc Р = (sema nat

х) : await х > 0 then х : = х - I endwait,

proc V = (sema nat х): await true then x : = x + I endwait.

Семафоры, в частности, используются для того, чтобы обеспечить взаимное исключение.

При критических областях взаимные исключения дополнительно проверяются с помощью простого синтаксического условия (общие переменные встречаются только в охраняемых критических областях). В противоположность этому при недисциплинированном использовании семафоров проверка взаимных исключений для доступа к общим переменным представляет собой трудный семантический вопрос, так как обеспечение взаимного исключения может зависеть от сложных логических отношений программы. Булевские семафоры вводятся с помощью объявления sema bool s := b и изменяются с помощью следующих процедур:

proc Р = ( sema bool s ) : await s then s := false endwait,

proc V = ( sema bool s ) : await true then s := true endwait.

При использовании семафоров в незавершающихся программах ставится вопрос о справедливости выполнения операций над семафорами. При V - операциях можно без ограничений требовать, чтобы каждый вызов завершался успешно, однако это не имеет места для Р - операций. Вызовы Р - операций могут приводить к ситуациям ожидания, если значение семафора есть 0, или false. Если одновременно ожидают многие Р - вызовы семафора, то после выполнения V - вызова продолжается один Р - вызов. Выбор подлежащего продолжению вызова происходит недетерминированно. При этом без предположения справедливости может случиться, что определенный Р - вызов никогда не будет продолжаться, хотя постоянно выполняются V - вызовы, поскольку всегда будут выбираться для продолжения другие ожидающие Р - вызовы.


В этом случае говорят о старвации

(«морении голодом», бесконечном ожидании; англ. starvation) вызова и соответствующей программы. Старвация имеет место, когда вызов (и соответственно, программа) должен ждать бесконечно долго, хотя все снова и снова возникают возможности продолжить выполнение программы. Если в (бесконечном) ходе работы старвации не возникает, то ход работы называется справедливым. В случае семафоров справедливые ходы работы могут быть реализованы путем введения очередей ожидания. К этому мы вернемся в следующей главе.

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

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

Пример (задача производитель/потребитель с помощью монитора). Приводимый ниже монитор регулирует доступ к программной переменной q с помощью доступных извне процедур send и receive:

monitor EV

var queue m q; signal nonempty;

proc send == (m x) : q := stock(q, x); nonempty.signal;

proc receive = (var m y):

if isempty(q) then nonempty.wait fi;

q,y:==rest(q),first(q)

q := emptyqueue;

var m x, z := xq, zq;

while b(x) do EV.receive(x);

сonsume (x)

od

while b(z) do produce_next(z);

EV.send(z)

od

Сигнал nonempty при этом соответствует булевской переменной, причем nonempty.signal соответствует nonempty:=true; nonempty.wait соответствует nonempty:=false; await nonempty then пор endwait.

Взаимные исключения доступа к переменным монитора обеспечиваются концепцией монитора.А именно: при мониторах предполагается, что каждая из процедур при взаимных исключениях выполняется до тех пор, пока процедура успешно завершится или же по сигналу наступит ситуация ожидания.

Описание значений выражений

Как уже упоминалось, существенный интерес представляют два дополняющих описания значения ("семантики") ЯП:

(1) операционная, ориентированная на вычисление значения по форме описания, которая дает алгоритм для вычисления значения выражения;

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

(3)   Форма (1) соответствует операционной семантике, а форма (2) - функциональной. Соответственно этому для выражения в аппликативном языке обе семантики определяются следующим образом:

(1)    семантика подстановки термов, которая представляется через алгоритм подстановок термов, приводящий выражение (при известных дополнительных условиях) в нормальную (примитивную) форму;

(2)    функция интерпретации I, которая отображает выражение ЯП на математические элементы.

При этом предполагается, что заданы "примитивная" вычислительная структура А с сигнатурой ? = (S, F), так что каждый носитель sА типа s в А содержит элемент 1, и система подстановки термов R над ?. В дальнейшем предполагается заданным множество ID идентификаторов. Оно соответствует формальному языку, который связан с синтаксической единицей <id>. Определяются множества D, FCT и Н.

D =def {а

sA:sS}

FCT =def {(f:sA1

x...xsAn> sAn+1): n

 N ^ f строгая ^ (i, 1<= i <=n + 1: siS)}.

D представляет множество элементов данных, FCT - множество функций, а

Н =-def D ^ FCT

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

Для задания операционной семантики будет применяться семантика подстановки термов. К томy же предполагаются заданными правила подстановки термов для термов над сигнатурой примитивных вычислительных структур. Пусть для терма из wЕ определена система R, которая полностью корректна и каждый терм t (с подходящим образом определенной интерпретацией, т.е.
I[t]

 ) переводит в однозначную нормальную форму. Далее предполагается, что терм t с I[t] =  не обладает никаким терминальным вычислением.
Для СПТ устанавливалось, что правила подстановок термов в АПТ могут применяться на любом месте. В противоположность этому для описания операционной семантики ЯП мы применяем такую концепцию подстановки термов, при которой выбор места применения определяется индивидуально. В последующем в выражениях ЯП должно быть целенаправленно установлено, на каком месте выражения ЯП должно быть возможно применение правила. Общая концепция применения ППТ на любом месте была бы неэффективной, так как при известных обстоятельствах благодаря этому упрощались бы термы, значение которых для вычисления результата на самом деле не используется. Однако существенно, что свободное применение правил на любом месте для определенных элементов ЯП приводило бы к незавершающимся вычислениям, тогда как целенаправленное управление применением может гарантировать завершение вычислений. В ЯП обычно встречаются выражения, чье вычисление завершается успешно, т.е. которые имеют значение , хотя они содержат подвыражения, для которых существуют незавершающиеся вычисления, т.е. значение которых =. Общая концепция безусловного применения неизбежно ведет для таких выражений к существованию незавершающихся вычислений.
Поэтому мы нуждаемся в ограниченном понятии применения ППТ. Эти правила должны применяться не в любом месте терма, а только при определенных условиях на подтерм. Для этой цели мы будем применять условные ППТ. Благодаря этому достигается более тонкое управление вычислением значения, т.е. выбор места применения правил в аппликативном выражении ЯП. Говорят также об управляемом потоке.
Пример (управляемое вычисление для нестрогих функций). Мы рассматриваем нестрогую функцию соr (условную or), которая соответствует последовательной дизъюнкции с функциональностью
fеt соr = (bool, bool) bool и таблицей значений:
соr       L           О       
L          L           L         L


О         L           О       
                        
Применяем следующие правила раскрытия:
хz ==> cor(x, y) cor(z, у),
 соr (true, y)  true,
 соr (false, у)  у.
Заметим, что в этом случае раскрытие терма cor(tl, t2) завершается даже тогда, когда завершается только вычисление t1, и дает значение true.
В дальнейшем для каждого элемента языка определяются условные ППТ, которые во взаимодействии с имеющимися для данной вычислительной структуры правилами обеспечивают, что для каждого замкнутого программного выражения t1 (т.е. для каждого программного выражения, которое не зависит от значения конкретизации) с интерпретацией а, система подстановки термов отображает вход t1 в выход t2, причем t2 есть однозначная нормальная форма t1 в соответствии с R. Впрочем, для определенного терма t с интерпретацией  вычисление не будет терминированным. Уместное обращение с такими термами - также дальнейшее основание для введения условных (управляемых) СПТ.

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

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

Пример (стохастический источник сообщений). Стохастический источник сообщений для заданного алфавита А поддается, например, следующим образом. Возьмем любое количество шаров и каждый шар пометим знаком из алфавита А (при этом один и тот же знак может встретиться на нескольких шарах). Положим помеченные шары в коробку и перемешаем их. Затем из коробки случайным образом возьмем шар, запишем содержащийся на нем знак, бросим шар обратно в коробу и перемешаем шары. После этого опять случайным образом возьмем шар из коробки и т.д.

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

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

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

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

Можно разрешающую информацию или информационное содержание знака примерно отождествить с обратной величиной частоты появления знака. Это наглядно соответствует нашему представлению об информационном содержании сообщений:

·

сообщение о фактическом наступлении почти всегда наступающего события имеет небольшое информационное содержание;

·         сообщения о фактическом наступлении редкого события, напротив, имеют высокое информационное содержание. Другими словами, чем реже поступает сообщение, тем выше его информационное содержание.

Основные аспекты операционных систем

Под вычислительной машиной (ЭВМ) понимается совокупность технологических устройств (аппаратура, «жесткое оборудование», “hardware”), таких как процессоры, память, шина и периферийные устройства, т. е. техническая система для переработки информации. Программирование на языке машины утомительно и чревато ошибками. Поэтому ЭВМ без специальной системы программ, которая поддерживает функционирование машины, для пользователя практически бесполезна. Программирование на чисто машинном уровне, без использования вспомогательных, весьма дорогостоящих программ, для пользователя было бы почти невозможно. Только наличие специальной поддерживающей программной системы, которая дает возможность пользователю проще организовать и реализовать свои индивидуальные применения, делает вычислительную машину работоспособным, непосредственно применимым инструментом. Семейство упомянутых системных программ называется операционной системой (ОС). Вычислительная машина, снабженная операционной системой, называется вычислительной системой (ВС). Конечно, даже для одной и той же ЭВМ можно создать и предоставить в распоряжение пользователей различные ОС. ОС (в широком смысле) понимается комплекс программ, функции которых определяют ВС с точки зрения пользователя. Работая на машине с ОС, пользователь не обращается непосредственно к машинным операциям. Скорее он дает запросы (задания) программам ОС, которые затем уже используют машинные операции. ОС, как правило, содержу себе большое семейство программ. Объем ядра достаточно простой ОС составляет примерно 100-500 Кбайт программного кода. Новейшие ОС могут иметь значительно больший объем.

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

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

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

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

Без ОС вычислительная машина была бы для пользователя практически неприменима. Только ОС обеспечивает интерфейс для удобного общения пользователя с ЭВМ и доступа к ее функциям.


Поэтому ОС должна в зависимости от спектра применений ЭВМ справляться с решением различных задач.

Функции операционной системы

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

Эта задача охватывает комплекс управления и распределения ресурсов системы для:

·

длительного хранения данных и управления ими (внешняя память);

·         выполнения программ пользователей (процессор и оперативная память);

·         использования устройств ввода/вывода, включая устройства для дальней передачи данных (устройства ввода/вывода).

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

·         допустимых пользователях и их правах (управление пользователями)

·         выполняемых в данное время программах (управление процессами)

так и информацию о фактическом внутреннем распределении ресурсов системы такую как:

·         состояние процессора (управление процессором);

·         распределение оперативной памяти (управление оперативной памятью) и внешней памяти (управление внешней памятью),

·         конкретизация устройств ввода/вывода (управление устройствами).

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


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

Режим обработки пользовательских программ, поступающих в ВС. Различают пакетный режим, режим диалога и режим реального времени (управление реальными процессами).

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

На эксплуатационную ситуацию ВС существенно влияют вид желаемого использования ВС и число ее пользователей. В однопользовательском режиме ВС используется только одним пользователем. В этом случае достаточно однопрограммного режима работы ВС. Однако если и здесь желательно определенные запросы пользователя выполнять параллельно, т. е. наряду друг с дротом (типичный пример - печать результатов как фоновый процесс), то однопрограммного режима работы системы уже недостаточно даже в случае одного пользователя. В многопользовательском режиме многие пользователи одновременно применяют ВС. Если к тому же пользователи ведут диалог с ВС, то говорят о системе разделения времени (англ.


time sharing); в этом случае требуется мультипрограммный режим работы ВС. При этом программы пользователей (которые считаются упорядоченными и замкнутыми в кольцо) поочередно получают определенный квант процессорного времени. Функционирование системы разделения времени требует учета готовых к выполнению программ, и благодаря этому ОС осуществляет управление выполнением программ.

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

ОС для систем разделения времени, естественно, являются более сложными, чем однопрограммные ОС. Здесь возникают и совершенно новые требования, как, например, желание иметь системную поддержку для общения пользователей между собой. Часто многие ВС - как с одним, так и с несколькими рабочими местами - объединяют в сеть, так что система разделения времени возникает в форме вычислительной сети. При этом объединение в сеть производится так, что на каждой включаемой в сеть ВС  устанавливается своя собственная ОС, а затем эти ОС обмениваются сообщениями.

Наряду с режимами обработки (пакетный, диалоговый, реального времени) и числом пользователей (одно- или многопользовательская работа), на структуру ОС оказывает влияние и состав имеющейся в распоряжении аппаратуры. Если ЭВМ имеет только один процессор, то говорят об однопроцессорной системе, в противном случае - о много- или мультипроцессорной системе. В приводимом ниже примере рассматривается типичная однопроцессорная система, которая используется со схематичной ОС разделения времени. Если в ЭВМ имеется несколько процессоров, работающих одновременно, то это требует в ОС дополнительных мер для их управления и синхронизации.

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


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

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

В ОС при каждом запросе пользователя на ресурсы должно приниматься решение о том, может ли запрос удовлетворяться немедленно, или он должен быть отложен до тех пор, когда система придет в такое состояние, при котором запрос можно удовлетворить без опасности прийти в тупиковое состояние.

Наряду с целью избежания тупиков одна из важнейших целей ОС состоит в возможно большем удовлетворении запросов пользователей в единицу времени. Число запросов, обрабатываемых в единицу времени, называют пропускной способностью ВС. Распределение ресурсов в ОС охватывает следующие комплексы задач:

·         выделение процессорного времени при оптимальной пропускной способности (с целью достижения возможно более высокого темпа обработки запросов);

·         умелое перемещение программ, частей программ и данных между оперативной и внешней памятью;

·         управление устройствами ввода/вывода.

Одна из важнейших внутренних задач ОС - максимизация пропускной способности. Конечно, она ограничена производительностью ЭВМ, но внутри этих рамок ОС должна обеспечить оптимальность обработки.


Принципиально мы можем определить задачу ОС как проблему оптимизации.

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

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

 

Режимы обработки

По роду взаимодействия между пользователем и ВС различают следующие режимы:

·         пакетная обработка,

·         диалоговый режим,

·         управление процессами  (режим реального времени).

Часто эти режимы в какой-либо ВС присутствуют наряду с другими при мультипрограммной работе машины.

a)                  Пакетный режим

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

b)                  Диалоговый режим



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

Диалоговый режим требует особых свойств интерфейса между пользователем и системой. В идеальном случае пользователь должен иметь возможность легко вести диалог, лучше всего без использования дополнительных письменных инструкций. Это требует предоставления ему дополнительной информации (объяснение системных фикций и состояния системы в данный момент), а также помощи при выдаче сообщений об ошибках (диагностика ошибок и пути их устранения). Особое значение имеет простота и наглядность представления требуемой информации о текущем состоянии системы. Далее, все системные фикции должны возможно больше соответствовать ожиданиям и интуиции пользователя (англ. principle of least surprise). Это приводит в область эргономики программного оборудования, которая имеет своей целью по возможности простое и понятное оформление пользовательского интерфейса.

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



c)                  Управление процессами (режим реального времени - РРВ)

Если с помощью ЭВМ осуществляется управление каким-либо процессом или наблюдение за ним (управление дорожным движением пли наблюдение за ним, управление роботом и т. д.), то это предъявляет особые требования к ОС. В управлении процессами или наблюдением за ними особое значение приобретает время реакции системы. Чтобы обеспечить работу в реальном времени, соответствующие программы и, соответственно, языки программирования должны содержать зависящие от времени конструкты.

При управлении процессами ввода данных наряду с обычными средствами ввода используются сенсоры (акустические, оптические, осязательные и т. д.) с аналого-цифровыми преобразователями. Вывод наряду с обычными средствами производится с помощью управляющих устройств.

Не все ВС приспособлены для одновременного обслуживания многих пользователей в режиме диалога. Если ВС в каждый момент времени может обслуживать только одного пользователя, то говорят о ВС с одним рабочим местом или персональном компьютере (англ. PC - personal I computer), а также о рабочей станции (англ. workstation). При этом в простейшем случае в процессе выполнения находится единственная программа (однопрограммный режим).

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

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


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

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

Простая ОС для пакетного режима

Чтобы точнее представить себе проблемы, возникающие при проектировании ОС, рассмотрим простую ЭВМ и обсудим требования к ОС. Обратим внимание, что в ВС:

·         также должны вводиться и программы самой ОС (начальный запуск системы);

·         должны выполняться и программы пользователей, и части ОС;

·         определенные программы ОС без внешнего воздействия никогда не завершаются.



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

Удобнее ввести в рассмотрение специализированный достаточно простой процессор в виде канала ввода/вывода, который по заказу (центрального) процессора осуществляет передачу между памятью и периферийными устройствами. Наличие канала ввода/вывода разгружает процессор, так как ему теперь не нужно управлять передачей каждого знака или слова по отдельности. В этом представлении канал, предъявленный программой, является активной компонентой, которая подает заказы от процессора и самостоятельно их выполняет. Действия процессора и канала протекают параллельно. В то время как канал обрабатывает заказ, процессор мог бы обратиться к другим задачам. Для этого для канала должна быть предусмотрена соответствующая аппаратура.

Теперь мы обратимся к упрощенному рассмотрению вопросов эффективности. Процессор в случае необходимости ждет окончания выполнения заказа на чтение или запись. Тем самым одновременные запись и чтение исключены. Если процессор выполняет программу пользователя, находящуюся в области памяти, то периферийные устройства не заняты. Никакая из трех компонент ЭВМ - процессор, принтер и ввод - не загружены оптимально. Возникающий отсюда недостаток становится все более заметным с возрастающей разницей в быстродействии между отдельными устройствами ЭВМ.

Этот пример, при всем его упрощении, делает ясным сложность структуры ОС. Если мы хотим иметь эффективные версии, то мы должны смириться с тем, что структура ОС становится еще сложнее.



Простая ОС для мультипрограммной системы

Чтобы лучше использовать все устройства ВС» мы должны в системе одновременно хранить и выполнять многие пользовательские программы. Тогда в эффективной версии ОС ввод, вычисление и печать могут осуществляться так, что всегда в обработке находятся три пользовательские программы:

·         программа  печатает,

·         программа  вычисляет,

·         программа  вводит.

Разумеется, по меньшей мере, три программы должны одновременно находиться в системе и потому храниться в памяти. Для этого память мы делим на три подобласти 0, 1 и 2. Мы также используем по одному каналу для обработки заказов на ввод и вывод. Фазы чтения, вычисления и печати представляются различными программами, распадаются на отдельные шаги и выполняются одна наряду с другой (т. е. параллельно). Конечно, и в этой версии ОС загрузка отдельных устройств остается еще очень плохой, т. е. не достигает оптимального их использования. Если выполняются пользовательские программы с сильно различающимися временами для осуществления ввода, счета и вывода, то другие устройства будут простаивать, хотя позднее следующая программа может интенсивно использовать как раз эти устройства.

Поэтому рассмотрим другую простую ОС, которая обеспечивает более полную загрузку устройств. Она допускает большее число заказов в системе, чтобы иметь запас заказов для каждого из устройств. Для этого ОС работает стремя очередями заказов: очередь свободных областей памяти; очередь областей памяти с программами, готовыми к счету;    очередь областей памяти с программами, готовыми к печати. К подобной ОС, необходимо сделать следующие замечания:

1.      Если операции упорядочения заменить другими операциями упорядочения в очереди ожидания, то получится другой порядок выполнения. Можно также ввести приоритеты, чтобы установить последовательность процессов в очереди ожидания.



2.      От выбора величины  времени  для счета зависит, как долго должен ожидать канал, пока он сможет получить новый заказ.

3.      Программы не получают определенных областей памяти постоянной длины.

4.      С помощью вмешательства человека оператор ЭВМ может манипулировать очередью ожидания (например, определенные области памяти, содержащие пользовательские программы, исключить из очереди программ, желающих печатать или считать, и добавить эти области в очередь свободных областей памяти).

Чтобы достичь оптимальной загрузки устройств, в современных ОС единственный процессор предоставляется по очереди многим программам, так что выполнение одной программы разбивается на последовательность ее активных фаз. Для выбора программы, которой предоставляется процессор, и для определения выделяемого интервала времени существуют различные способы действий. Мы говорим о стратегии расписания»

Для мультипрограммных ЭВМ в стратегии расписания должно быть установлено:

·         когда должно быть прервано выполнение программы,

·         по какой стратегии должна выбираться для выполнения одна из ожидающих программ.

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

В реальных ОС не всегда выполняется только одна программа, а по некоторому правоту каждой из программ, имеющихся в системе, по очереди выделяется определенный короткий интервал (квант) времени процессора для ее выполнения. Это особенно удобно при интерактивном использовании ВС многими пользователями.



Выбор готовой к выполнению программы может производиться в соответствии с определенными приоритетами, при учете состояния системы. При этом могут использоваться статические приоритеты, которые не изменяются в течение всего времени выполнения программ, или же динамические приоритеты, которые в процессе выполнения программ изменяются по тем или иным соображениям. ОС работают с приоритетами по определенной стратегии, причем эти приоритеты могут изменяться даже благодаря действиям оператора ЭВМ.

Если в системе находится много пользовательских программ, то некоторая часть ОС, управляющая ходом процесса и называемая диспетчером  (англ. Scheduler, dispatcher), решает, какая из программ в первую очередь должна быть выбрана для исполнения. Простейшая стратегия заключается в том, что программы для исполнения выбираются в порядке их поступления в систему, и каждая программа выполняется до тех пор, пока не возникнет прерывание (например» вследствие заказа из этой программы на ввод/вывод), и программа продолжает выполняться, как только это становится возможным. Конечно, такой способ действий не всегда отвечает ожиданиям пользователей. Часто скорее ожидается, что программа с коротким временем ее выполнения, которая может быть распознана ОС по заданному при программе требуемом времени на ее выполнение, будет снабжена более высоким приоритетом.

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

В течение времени пребывания какого-либо задания в системе, с одной стороны, производится выполнение некоторых из находящихся в системе заданий, если они еще не завершены, а с другой стороны, в систему поступают новые задания и добавляются к имеющимся в ней заданиям.

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

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

Относящиеся к пользователю аспекты ОС

Для пользователя ОС ряд деталей ее воплощения, как, например, внутренняя структура ОС, не относится к делу (по крайней мере так должно быть), если это не оказывает влияния на общение пользователя с ОС.

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

Обычно ОС через имеющиеся в распоряжении пользователя операций (команды, адресованные ОС) делает возможным доступ к соответствующим службам ОС, которые охватывают следующие виды работ:

·         вычислительную работу для выполнения пользовательских и системных программ;

·         хранение данных и доступ к банкам данных;

·         передачу сообщений другим пользователям и - через сеть - другим ВС;

·         доступ к специальным терминальным (конечным) устройствам (в частности, к устройствам вывода).

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

Командный язык

Для спецификации запросов к ОС в распоряжении пользователя имеются определенные операции. Эти операции вызываются путем задания указаний для ОС, которые будем называть командами.

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

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

В пакетном режиме обработки заданий используются пакеты заданий пользователей. Задание состоит из группы команд, которые обрабатываются последовательно ОС и преобразуются в соответствующие операции.

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

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

Новейшие командные языки в большей степени ориентируются на языки программирования высокого уровня. Они разрешают также задавать “командные процедуры” и гибкую поддержку диалога. Команды пользователя обрабатываются интерпретатором команд.


Интерпретатор команд имеет в своем распоряжении список имен команд, которые содержатся  в определенном файле, и ссылки на операторы, реализующие эти команды.

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

У пользователя в режиме диалога обычно возникают следущие вопросы:

·         каков модус системы в настоящее время?

·         какие операции и какие команды являются при этом доступными для использования?

·         какой последовательностью команд я создал это состояние?

·         каких состояний системы и с помощью, каких последовательностей команд я могу достигнуть?

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

Управление пользователями

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



Данная часть ОС устанавливает каждому пользователю рамки использования ресурсов системы, что предполагает ограничения:

·         на потребность процессорного времени,

·         текущие потребности памяти,

·         потребности для тигельного хранения данных,

·         приоритет,

·         специальные правовые отношения.

В рамках управления пользователями ОС регистрирует также фактическое расходование ресурсов системы отдельными пользователями и тем самым создает основу для расчетов оплаты за работу в ВС.

Организация данных и управление ими

В ВС существуют большие объемы данных, к которым по ходу обработки осуществляется доступ и которые передаются между различными видами памяти.

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

В файлах мы делаем различие между их внутренней структурой и их структурой доступа. ОС должна  как создавать внутреннюю структуру файла и управлять им, так и реализовать структуру доступа к ним.

Доступ к внешним наборам данных во внешней памяти должен поддерживаться ОС. Это включает:

·         локализацию единиц информации на запоминающих средах,

·         передачу информации между различными видами памяти.

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


Обеспечение защиты от неправомерного доступа является одной из центральных задач ОС.

Системы файлов обычно имеют иерархическую структуру. Часто они имеют древовидную структуру - тогда говорят о файловом дереве. Доступ к какому-либо файлу осуществляется по трассе доступа. Она состоит из последовательности имен, которая исходя из корня дерева, соответственно - из корня позиции пользователя в дереве, по отдельным шагам выбора ведет к нужному файлу. В файловой системе имеется два типа файлов: файлы, которые содержат простые наборы данных (листья файлового дерева) и управляющие файлы, называемые директориями (англ. directories), которые служат для управления наборами данных (внутренние узлы дерева). В принципе оба типа файлов могут быть построены одинаково - различно лишь их использование (см. ОС UNIX и DCL).

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

В новейших ОС ряд названных команд можно не задавать в явном виде - они неявно вводятся самой ОС и затем выполняются при обработке определенных команд пользователя.

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

Аспекты надежности и защиты

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


В-третьих, если ЭВМ используется для управления процессами, сбои в работе ОС могут повлечь за собой большой материальный ущерб.

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

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

Однако даже самые изощренные и остроумные способы защиты не являются полностью надежными против вторжения («взлома») извне со стороны специалистов и против злоупотреблений неясных системных программистов. Эта проблематика должна быть обдумана при эксплуатации ВС и разработке ОС. Классическими методами защиты данных среди других являются:

·         механизмы запрета,

·         пароли,

·         блокировка данных (криптографические методы, см. BAUER, 1992).

Впрочем, аспект защиты касается не только наборов данных - его слезет понимать шире: должно быть обеспечено, чтобы пользователь не только не мог полнить доступ к ресурсам, которые находятся вне его компетенции, но и не мог недозволенным образом помешать функционированию ОС или изменить ее. Проблема защиты данных обостряется из-за того, что через сети ЭВМ технически возможен доступ к большому числу ЭВМ.

Полиномиальная и недетерминированная полиномиальная временная сложность

Множество задач, которые могут быть решены за полиномиально-ограниченное время на детерминированных машинах, обозначим через Р:   

Р == È DTIME (n^)           [^=i].

I ³ l

Задачи из Р называют эффективно решаемыми.

Ряд важных задач могут быть достаточно просто решены на недетерминированных полиномиально-ограниченных по времени Т-машинах. Класс этих задач обозначим через NP:

NP = È NTIME (n^).

        i ³1         

Пример (задача из NP). Следующая задача входит в класс NP. Для заданного графа с k вершинами определить, имеется ли циклически замкнутая трасса, на которой лежат все вершины графа. Такая трасса называется  направленным обходом Гамильтона.

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

pspace = È DSPACE(n^),

               i³l

Постановка вопроса

Информация для целей ее машинного хранения и обработки всегда должна быть представлена в строго определенной форме. На нашем уровне культурного развития наиболее распространенной формой представления информации являются тексты. С точки зрения информатики текст является последовательностью знаков (литер), или, точнее говоря, конечной последовательностью знаков. Существует много различных систем представления, базирующихся на последовательностях знаков. Наряду с этим способом имеется много и других возможностей представления информации. В этой главе будет рассматриваться представление  информации в виде последовательностей знаков из некоторого конечного их набора. Различные системы представления информации по-разному удобны для целей ее машинной обработки.

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

При выборе способа кодировки и его обсуждения в первую очередь учитываются две цели: экономичность представления и обработки, а также мера надежности от ошибок. Прежде всего - из естественных соображений эффективности -  интересны по возможности короткие кодовые слова, с тем чтобы представление информации в виде кодов было по возможности компактным, наглядным и более дешевым. Кроме того,и обработка информации в выбранной системе представления должна быть простой и экономичной. С другой стороны, если в процессе передачи или обработки информации в кодовых словах появляются случайные незначительные ошибки, то , естественно, хотелось бы быть в состоянии такие «испорченные» кодовые слова по меньшей мере выявлять и даже - несмотря на это - соответствующим образом их декодировать. Если  установить заданную среднюю частоту (вероятность) появления кодируемой информации и тем самым среднюю частоту появления отдельных знаков в представлении кодируемой информации, то кажется естественным так умело выбрать кодировку, чтобы средняя длина кода была по возможности меньше. Отсюда весьма уместно - при задании вероятности помех - так выбрать кодировку, чтобы вероятность невыявления помех была достаточно малой.

С помощью этого перевода вместо абстрактного отображения между натуральными числами

f: N” -> N

рассматривается конкретное отображение между последовательностями знаков

f : (Т*)» -> Т*

со следующим свойством (для всех xj,..., Хn Î N):

f(xi, ..., Хn) = abs(f(rep(xi), ..., rep(Xn))).

Это равенств говорит, что , вместо того чтобы вычислять значение функции f для аргументов х1, ..., хn, можно определить представления гер(x1), ..., гер(xn) аргументов и для них вычислить значение f . С помощью функции abs можно из результата применения f к rep(x1), ..., rep(xn) получить значение функции для аргументов (Xi), ..., (Хn). Из приведенного выше равенства получается коммутирующая диаграмма, показанная на рис.9.1.

f

N”             N

Rep ­          abs¯

(Т*)»         T*

f

Рис. 9.1. Коммутирующая диаграмма

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

Употребительными формами представления чисел являются представление соответствующим количеством штрихов, двоичное или десятичное представления и разложением на простые числа. Существует зависимость между сложностью вычислений и выбором конкретного представления. Для определения понятия вычислимости дополнительно требуется, чтобы функции гер и abs сами были вычислимы в интуитивном смысле.

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

Нужно, чтобы конкретные представления были также реалистически приемлемы для обращения. Поэтому  предполагается, что Т есть конечное множество.

Потоки ввода/вывода

Рассмотрим функциональное представление интерактивных систем. Взаимодействующие (интерактивные) программы могут также пониматься как функции на потоках входных значений, которые в качестве результата порождают потоки выходных значений. Это делает возможным функциональное моделирование распределенных, взаимодействующих систем. Такое толкование подходит как для моделирования программ, которые в интерактивном режиме обмениваются данными с человеком-пользователем, так и для коммуникации между программами.

Поток данных над заданным множеством данных D есть конечная или бесконечная последовательность элементов из D.

С помощью основных функций на потоках могут быть определены функции, которые берут конечные или бесконечные потоки в качестве входа и вырабатывают конечные или бесконечные потоки в качестве выхода, В нотации языков программирования пишут stream m в качестве обозначения типа потока с множеством данных M, где М обозначает множество данных типа m.

Бесконечный поток всех натуральных чисел >= n можно сгенерировать с помощью вызова функции enum(n), где enum определена следующим образом:

fct enum = (nat n)

stream nat: n&enum(n + 1).

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

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

Пустой поток представляет наименьший элемент в префиксном порядке и соответствует неопределенному потоку. Так как функция относительно этого наименьшего элемента префиксного порядка является нестрогой, мы можем задать также нетривиальные рекурсивные объявления для потоков.

Предикаты над процессами

Наряду с сетями и термами агентов множества процессов могут быть охарактеризованы через задание свойств с помощью выражений логики предикатов. Мы будем обсуждать лишь очень простые предикаты. Пусть задан процесс р = (Е0, ?0, ?),  с помощью терма #(а, р) обозначим число событий в р, помеченных действием а. Точно #(а, р) определяется следующей формулой:

#(а,р) = | {е c Ео: ? (е) = а}|.

Для бесконечных процессов значение #(а, р) может быть бесконечным. С помощью этой формулы можно образовывать предикаты и тем самым описывать множества процессов.

Пример (множества процессов через предикаты). Рассмотрим следующее множество А действий:

А = {а, b, с, d}.

Множество конечных процессов p = (Е0, ?0, ?),  можно охарактеризовать через предикат Q(p). Пусть Q(p) задан с помощью следующих формул:

(1)   0 ? # (а, р) - #(с, р) ? 1 ^

(2)   0 ? #(b, р) - #(d, р) ? 1 ^

(3)  

 е, е' c Eo: ? (е) - с ^ ? (е') = d => (е ?0 е' v е' ?0 е).

Процесс р выполняет предикат Q,

если:

(1)               число событий, помеченных через а, либо на единицу больше числа событий, помеченных через с, либо равно ему;

(2)               число событий, помеченных через  b либо на единицу больше числа событий, помеченных через d, либо равно ему;

(3)               события, помеченные через c и d не протекают параллельно.

Студентам МИРЭА практически всех специальностей

Студентам МИРЭА практически всех специальностей начиная с первого курса, предстоит изучать объемный курс “Информатика”, а студентам специальности 071900 “Информационные системы (в образовании)” два тесно связанных между собой курса: «Информатика» и «Теория информации». Студенты и школьники, занимающиеся в секторах НИТ и ИВТ МГДТДиЮ, а также самостоятельно повышающие свой уровень знаний в сфере НИТ, неизбежно сталкиваются с потребностью углубления своих знаний и навыков по курсу информатики, являющимся фундаментальной образовательной дисциплиной направления.
В курсе лекций по дисциплине “Введение в специальность” уже упоминалось, что эти учебные дисциплины выстраивают фундамент знаний и умений будущего специалиста по специальности 071900. Строго говоря, по многим специальностям высшей школы курс информатики - один из важнейших. Он призван не только отражать предметную область информатики как науки о сущности и протекании информационных процессов, но и с точки зрения информационного представления показать в системном, модельном виде сущность будущей специальности студента. В этом, а не только в инструментальных возможностях, роль информатики как одной из ведущих дисциплин, формирующих специальность и специализацию обучения в высшей школе. Именно поэтому в практике МИРЭА наметилась линия на то, что курс «Информатика» читают выпускающие кафедры по своим специальностям. В данном случае, то есть по специальности 071900 «Информационные системы (в образовании)» курс ставит и ведет выпускающая кафедра Технических и информационных средств систем управления (ТИССУ) факультета Кибернетики. Информатика как предмет изучения в учебном плане по специальности озвучена дважды: «Информатика» и «Теория информации». Эти курсы самым теснейшим образом связаны между собой и дополняют друг друга.
Теоретической информатикой называют науку о структурах, основывающихся на математике и логике. С другой стороны, практическая информатика является инженерной дисциплиной, изучающей в числе других вопросов инженерного обеспечения сети и системы.
Информатика исследует информационные процессы и связанные с ними явления в технике, природе и обществе. В круг этих вопросов входят базы данных, базы знаний и информационно-поисковые системы, гиперсреда. Важное значение в информатике имеют вопросы языков, компьютерного перевода.
Информатика является новой научной областью, опирающейся на традиционные и самые современные и новые науки. К ним в первую очередь относятся:
·         теория информации - математическое описание методов передачи данных и обработки данных, а также классификация информации;
·         искусственный интеллект - способность устройства решать задачи, ассоциируемые с разумными действиями человека;
·         электроника, обеспечивающая техническую базу информатики;
·         семиотика - комплекс направлений, изучающих знаковые системы.
Именно наукоемким мировоззренческим построением и связью со специальностью высшего профессионального образования вузовский курс информатики отличается от одноименного школьного курса. В школе даются общие представления об алгоритмических языках программирования, более или менее осваивается один из них (обычно Бейсик), формируются представления об аппаратном и программном обеспечении компьютерно-сетевых комплексов (в основном в увязке к персональному компьютеру - ПК), осваиваются основные приложения и приемы работы на ПК. Иными словами, у выпускника средней общеобразовательной школы формируется компьютерная грамотность, позволяющая перейти непосредственно к изучению вузовского курса информатики и использовать полученные знания и навыки для компьютеризации своей учебной и, возможно, производственной деятельности.
В вузе вопрос ставится глубже, фундаментальнее, на наукоемкой основе. В курсы «Информатика» и «Теория информации» включены для изучения следующие вопросы: количественные оценки информации и ее виды, структуры и закономерности протекания информационных процессов, сбора, передачи и накопления информации, средства реализации и модели решений функциональных и вычислительных задач, формы представления и преобразования информации, математические основы информатики, информационные подходы и решения к оценке качества функционирования информационных систем и другие вопросы.


Особое место уделяется проблематике, связанной с увеличением роли и значения информационных ресурсов в современном обществе, информатизацией общества и перспективами перехода от постиндустриального к информационному обществу. Таким образом, дается старт, и закладываются основы, изучаемой на старших курсах дисциплине «Информационно-социальные технологии в образовании».
Российский образовательный стандарт по специальности 071900 «Информационные системы (в образовании)» обозначает требования к знаниям и умениям в области информатики и математики (связывая воедино эти две фундаментальные общеобразовательные дисциплины):
«Инженер должен иметь представления ... о математическом моделировании систем, об информации, методах ее хранения, обработки и передачи. Инженер должен знать и уметь использовать... математические, в том числе вероятностные модели информационных систем..., базовые понятия вычислительной техники (ВТ), предмет и основные методы информатики, закономерности протекания информационных процессов в искусственных системах, принципы работы технических и программных средств в информационных системах, основные положения теории информации... Инженер должен иметь опыт
исследования моделей с учетом их иерархической структуры и оценкой пределов применимости полученных результатов, ... программирования и использования возможностей вычислительной техники и программного обеспечения (ПО) и методов проектирования информационных систем...».
Таким образом, основы перечисленных выше знаний и навыков закладываются в вузовском курсе информатики (обычно трехсеместровом) и развиваются потом в последующих дисциплинах в течение всего времени обучения в университете.
Настоящий конспект установочных лекций по курсу “Информатики” для студентов специальности 071900 разработан на кафедре ТИССУ МИРЭА с целью дополнить имеющиеся на книжных полках многочисленные учебники по практической информатике наукоемкой постановочной фундаментальной частью, отражающей системообразующие компоненты дисциплины в трактовке высшего учебного заведения.Поэтому настоящее учебное пособие охватывает не весь курс, а только те отдельные разделы и темы лекций, которые недостаточно раскрыты в учебниках в системообразующем отношении. В основу установочного курса лекций кафедры положен огромный научный труд – четырехтомник Манфреда Бройя “Информатика” (изданный в МИФИ в 1998 году), а также труды видных отечественных ученых Международной Академии Информатизации: академиков Евреинова Э.В., Евтихиева Н.Н., Иванникова А.Д., Лохина В.М., Нечаева В.В., Юзвишина И.И., Якубайтиса Э.А. и других.
Конспект установочных лекций сопровождается массивами развивающей информации в гипертексте на сервере МИРЭА и МГДТДиЮ и поддержкой КЕЙС-технологий на CD-ROM.
Ректор МИРЭА,
Действительный член Международной Академии Информатизации
проф. А.С. Сигов
 
 

Предметная область

·

Предметная область – это та часть реального мира, которая является сферой проблемной ориентации автоматизированной системы.

·         Машины могут оперировать только определённой формой описания предметной области, при этом всегда предполагается соотнесение описания на формальном языке с её описанием на естественном.

·         Введение формального языка приводит к необходимости однозначного перевода описания на одном языке (естественном и формальном) в описание на другом и необходимости эквивалентной интерпритации.

·         При определении предметной области объект должен иметь относительно целостный характер и обладать некоторым конечным набором свойств.

·         При этом свойства объекта могут быть индивидуальными и общими, присущими и единичному экземпляру, и целому классу.

·         Технические средства коммуникации в современном общесве играют большую роль. Обмен знаниями посредством передачи, кодирования смысла и сигналов привёл к необходимости разработки общих принципов обработки, хранения, передачи информации.

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

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

·         Информация-это всеобщее свойство материи, проявляющееся в коммуникативных процессах, которые содержат в себе субъектно-объектные отношения.

·         Информационные единицы бывают элементарными и составными. Элементарными единицами информации выступают реквезиты-логически неделиные элементы, соотносимые с определённым свойством отображаемого объекта или процесса. Различают числовые и текстовые реквизиты.

·         Числовые реквизиты характеризуют количественные свойства явлений, полученные в результате подсчёта натуральных единиц, взвешиванием, измерением.

·         Текстовые реквезиты отражают качественные свойства явлений. Дают характеристику тем обстоятельствам при которых протекало то или иное экономическое явление или процесс и были получены те или иные числовые значения.

 

Представление данных

Структура данных

·         Структура данных связана с присутствием различных компонент, различными отношениями между ними, порядком следования компонент, установленных отношением.

·         Структуру данных можно определить как множество компонент и отношений между ними, задающих порядок подчинённости и связи компонент.

·         Если множество компонент полностью определено и конечно, то структура называется абсолютной или финитной.

·         Все структуры данных могут быть разделены на иерархические, неиерархические и смешанные.

·         В иерархических структурах каждая компонента является либо главной, определяющей, либо зависимой, подчинённой. Любая зависимая компонента связана только с одной операцией.

·         Иерархическую структуру, у которой хотя бы одна компонента является одновременно и главной и зависимой по отношению к некоторым другим компонентам, называют многоуровневой.

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

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

·         Смешанные структуры являются комбинацией иерархических и неиерархических структур.

Иерархические структуры

·         Иерархические структуры данных и связи между ними отображаются в виде схем, называющихся деревьями.

·         Дерево представляет собой иерархию элементов, называемых узлами.

·         На самом верхнем ее уровне имеется только один главный узел — корень дерева.

·         Любой узел, кроме корня, связан с одним узлом на более высоком уровне. Этот узел называется исходным.

·         Ни один узел не имеет более одного исходного. Любой рассмотренный узел может быть связан с одним или несколькими элементами на более низком уровне. Эти элементы называются порожденными.

 

Представление деревьев массивами

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

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

Представление знаний

Классификационные системы

·

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

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

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

 

Иерархические системы

·         Иерархическая система классификации—такая система, в которой между классификационными группировками установлено отношение подчинений, как правило, родо-видовое .

·         Классификационное множество объектов делится по некоторому выбранному признаку (основание деления) на крупные группировки.Затем любая группировка в соответствии с выбранным основанием деления разбивается на ряд последующих группировок, которые в свою очередь распадаются на более мелкие, постепенно конкретизируя объект классификации, причем однозначности должны быть учтены отношения синонимии, омонимии и полисемии, свойственные словам естественного языка .

·         Основными преимуществами иерархической системы являются большая информационная емкость и простота поиска группировки; недостатки заключаются в малой гибкости структуры и невозможности агрегировать объекты по любому сочетанию признаков.

 

Алфавитно-предметная классификация

·        Алфавитно-предметной классификацией называется система классов, расположенных в алфавитном порядке их имен.

 

Применение функции

Пусть F - обозначение (идентификатор, или абстракция, для) функции с функциональностью (s1, ..., sn) s и пусть E1, ..., En - любые выражения типов s1, ..., sn; тогда F (E1, ..., En) есть выражение типа s, называемое применением функции или вызовом (указателем) функции. Значение указателя функции есть f(a1, ..., an), где f - функция, обозначенная через F, а a1, ..., an - значения выражений E1, ..., En. E1, ..., En

- фактические параметры-выражения

(или аргументы), a a1, ..., an - фактические параметры-значения.

В БНФ-нотации синтаксис указателя функции выглядит следующим образом:

<указатель_функции>::=<функция>{(<выражение>{,<выражение>}*)}

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

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

Для вычисления значения указателя функции используются следующие ППТ (пусть 1 <= i <= n):

E

 E' => F(E1, ..., Ei-1, E, Ei+1, .... En) F(E1, ..., Ei-1, E’, Ei+1, .... En)

По этому правилу значение указателя функции вычисляется следующим образом: сначала (в произвольном порядке) вычисляются выражения-аргументы ("вызов параметра значением", "call-by-value").

Следует заметить, что имеются и другие стратегии вычисления указателя функции. Так, можно было бы сразу начинать с вычисления результата функции ("call-by-name") - до того, как будут вычислены значения аргументов. В этом случае вычисление параметров-выражений могло бы производиться по мере надобности при вычислении значения функции. Это в определенных ситуациях ведет к различению подслучаев по отношению к терминированности и в итоге позволяет также вычислять некоторые нестрогие функции.

Пример нестрогой функции дает условное выражение: конструкцию if-then-else-fi можно трактовать как нестрогую трехместную функцию. В нашем примере языка, однако, все функции, встречающиеся в указателях функций, предполагаются строгими. Поэтому языковой элемент if-then-else-fi вводится не как функция, а как элемент выражения (конструкт образования выражения).

в качестве результата выдает любое

fct f == ( nat n ) nat:
 if n == 0    then 0
else f(n—l)
fi
является недетерминированным и при его вызове
f(m) для m Î N в качестве результата выдает любое число i Î N, такое, что 0£ i £ m.
Обратим внимание, что от недетерминированного выбора может также зависеть и завершаемость вычислений.
Пример (недетерминированный алгоритм с неопределенным завершением).
Предписание
fct f =( nat n ) nat:
n?f(n+1)
При вызове f(m) либо вычисляет такое число i Î N, что m £ i, либо вычисление выражения не завершается.
В дальнейшем мы хотим - в свете полиномиально-ограниченных Т-машин - сконцентрироваться на недетерминированных алгоритмах, при которых завершение вычислений всегда обеспечено. В таком случае завершаемость не зависит от недетерминированного выбора.
Пример (недетерминированное порождение перестановки). Алгоритм f,  заданный описанием
fct f = ( nat n ) seq nat:
      if n = 0    then
else nperm(f(n—l), n)
      fi
fct nperm == ( seq nat s, nat n ) seqnat:
      if s == e then append(n, s)
else
append(n, s) ?
append(first(s), nperm(rest(s), n))
      fi
При вызове f(n) для заданного числа n порождает недетерминированным образом некоторую перестановку чисел {1, 2, ..., n} и всегда завершается. Докажем это по индукции.
(0) Для n > 0 утверждение тривиально.
(1) Предположение индукции: утверждение справедливо для заданного n Î N. Вызов f(n) дает перестановку s из {1, 2, ..., n}. Функция nperm(s, n+l) вставляет (n+l) в какую-нибудь позицию в s. Так можно породить любую перестановку.
Рассмотрение недетерминированных выражений приводит к ряду трудностей, поскольку классические правила преобразований логики не обязательно имеют место. Так, высказывание f(x)==f(x) для недетерминированного алгоритма f можно интерпретировать двояко:
·         вычисления правой и левой частей приводят к одинаковому значению (если значений не больше одного);
·         множества недетерминированно-возможных значений левой и правой частей совпадают.


Эти тонкие различия затрудняют обращение с недетерминированными выражениями.
Для организации завершения вычислений при недетерминированном выборе введем специальное выражение failure  («неуспешная попытка»), которое в некотором (недетерминированном) вычислении обозначает выражение, не доставляющее никакого «желаемого» значения (неуспех). Благодаря этому может быть промоделирована концепция вычислений, встречающаяся в недетерминированных Т-машинах.
Введением failure
определяется так называемый «бэктрекинг-недетерминизм» (недетерминированный поиск с возвратом). Недетерминированные ветви вычисления, которые ведут к failure, отсекаются, т. e. не принимаются в качестве результата. Неуспех фиксируется только в том случае, когда все ветви приводят к failure.
Использование failure (выбор по-прежнему является недетерминированным) позволяет организовать поиск в недетерминированно-выбранном дереве вычислений.
Пример (алгоритмы с недетерминированным поиском).
Сортировка недетерминированным выбором. Рассмотрим систему вычислительных предписаний
fct ndsort == ( seq nat s, seq nat r ) scq nat:
    if s = e   then  r
                  else nat x == any(s);
                          if x > first®    then failure
                                                 else ndsort(drop(s, x), <x> * r)
                          fi                 
        fi
    fct any = (seq nat
s) nat:
   if s=e   then failure
       else   first(s)  any(rest(s))
        fi
fct drop = (seq nat s, nat x) seq nat:
   if   s == є       then  failure
   elif   first(s) = x  then   rest(s)
                              else append(first(s), drop(rest(s), x))
   fi
fct sort = ( seq nat s)
seq nat:
   if s = є        then s
                      else nat x = any(s);
                             ndsort(drop(s,x),<x>?є
При вызове sort(s) порождается отсортированная по неубыванию версия s.
Обратим внимание: если затраты времени простого (т.e. недетерминированного) выбора составляют z, то затраты бэктрекинг-недетерминизма в самом неблагоприятном случае имеют порядок 2^z.


Эти затраты определяются как глубиной «почти сразу» успешного поиска, так и происходящей широтой поиска.
Можно представить себе два возможных способа действий (т. e. возможные способы реализации) при вычислении недетерминированного выражения с failure-подвыражениями.
·         Параллельное вычисление, которое соответствует одновременному развитию событий, как при Т-недетерминизме. Вычисление завершается успешно, если найдется одна из ветвей успешного вычисления.
·         Поиск с возвратом (бэктрекинг-недетерминизм). Если текущая ветвь вычислений приводит к failure , то она обрезается и для вычисления выбирается другая ветвь. Лишь в том случае, когда все ветви вычислений приводят к
failure, вычисление в целом считается неуспешным.  Таким образом, бэктрекинг-недетерминизм требует поиска в недетерминированно-выбранном дереве вычисления.
Обратим внимание: каждая задача в NP с помощью подходящих функций gi, которые соответствуют недетерминированным альтернативам Т-машины, а также предикатов vollstandig и korrekt, которые проверяют, является ли потенциальное решение полным и корректным, может быть представлена следующей схемой программы с бэктрекинг-недетерминизмом:
fct f = (m x) m:
        if vollstandig(x)    then if korrekt(x)   then x
                        else failure
 fi
                              else   f(gi(x))a...a f(gk(x)(x))
fi
При этом глубина рекурсии предписания f должна быть полиномиально-ограниченна.
Бэктрекинг-недетерминизм может быть обобщенна выбор из конечных множеств. Выбор элемента х типа m с определенным свойством q(x) назовем также недетерминированным выбором.
Для этого мы пишем
some m х: q(x).
С помощью этого оператора выбора для некоторых задач можно достаточно просто формулировать алгоритмы.
Пример (недетерминированное порождение обхода Гамильтона). Пусть тип node
является множеством {0, 1, ..., п-1} вершин ориентированного графа, ребра которого заданы через fct g = (node, node) bool.


Гамильтонов обход через подмножество S узлов - это замкнутый путь без повторений, все узлы которого содержатся в S.
Предписание
fct hk == (set node s,
seq node q) seq node:
      if s = Æ
then if g(last(q), first(q))   then q
                                                              else failure
                           fi
                        else  node x == some node z: z e s;
                                if g(last(q), x)            then hk(s\{x}, q 0 <x>)
                                                     else failure
                fi
 fi
порождает недетерминированно-направленный Гамильтонов обход (если он существует) через узлы из конечного множества S в качестве результата вызова hk(s\{x}, <x> о є ), при любом х Î S.
Недетерминированный выбор и концепцию бэктрекинг-недетерминизма можно ввести аналогичным образом в императивные программы. Тогда справедливо: S1 ? S2 для оператора, выполнение которого происходит путем недетерминированного выбора для исполнения одного из операторов S1
и S2
.Снова может быть использовано ключевое слово
failure для обозначения неуспешной ветви (тупика).

Принципы Фон Неймана

В своем историческом докладе 1945 года Джон фон Нейман описал, как должен быть устроен компьютер для того, чтобы он был универсальным и эффективным устройством для обработки информации.

УСТРОЙСТВА КОМПЬЮТЕРА.

Прежде всего, компьютер должен иметь:

·

-арифметическо-логическое устройство, выполняющие арифметические и логические операции (устройство должно уметь складывать, вычитать, умножать и делить).

·         -устройство управления, которое организует процесс выполнения программ;

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

·         внешние устройство для ввода-вывода информации (с помощью этого устройства должна осуществляться связь между оператором и машиной).

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

ПРИНЦИПЫ РАБОТЫ КОМПЬЮТЕРА. В общих чертах работу компьютера можно описать так. Вначале с помощью какого либо внешнего устройства в память компьютера вводиться программа. Устройство управления считывает содержимое ячейки памяти, где находиться первая инструкция (команда) программы, и организует ее выполнение. Эта команда может задавать выполнение арифметических или логических операций, чтение из памяти данных для выполнения арифметических или логических операций или запись их результатов в память, ввод данных из внешнего устройства в память или вывод данных из памяти на внешние устройство.

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

(перехода). Эти команды указывают устройству управления, что ему следует продолжить выполнение программы, начиная с команды, содержащейся в некоторой другой ячейке памяти. Такой «скачок », или переход, в программе может выполняться не всегда, а только при выполнении некоторых условий, например, если некоторые числа равны, если в результате предыдущей арифметической операции получился нуль и т.д. Это позволяет использовать одни и те же  последовательности команд в программе много раз (т.е. организовывать циклы), выполнять различные последовательности команд в зависимости от выполнения определенных условий и т.д., т.е. создавать сложные программы. Таким образом, выполняющие устройство выполняет инструкции программы автоматически, т.е. без вмешательства человека. Оно может обмениваться информацией с оперативной памятью, и внешними устройствами компьютера. Поскольку внешние устройства, как правило, работают значительно медленнее, чем остальные части компьютера, управляющие устройство может приостановить выполнение программы до завершения операции ввода-вывода с внешним устройством. Все результаты выполненной программы должны быть ею выведены на внешние устройства компьютера, после чего компьютер переходит к ожиданию каких-либо сигналов внешних устройств.

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

 

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

Булевское выражение логики высказываний образуется из идентификаторов, скобок, одноместного оператора и двухместных операторов n и v. Так что такое выражение является элементом формального языка, который через нетерминал <bе> описывается следующим БНФ-правилом:

<bе> ::= <id> ï Ø <bе> ô (<bе> Ù <bе>) ï (<bе> Ú <bе>)

Представим идентификаторы числами в их двоичном изображении. Тогда выражение длины n (с n символами) может быть представлено с помощью O(n log2n) знаков из некоторого конечного множества. Меру n для величины задачи положим равной длине булевского выражения. Точнее говоря, мы используем число знаков, необходимое для записи' выражения.

Проблема выполнимости lsat cостоит в выдаче ответа на следующий вопрос для заданного булевского выражения t: имеется ли такая конкретизация идентификаторов в t, при которой t может быть сведено к значению true?

Теорема. Проблема выполнимости lsat для булевского выражения является NP-полной.

Доказательство.

1.

lsat принадлежит классу NP: мы «угадываем» значения параметров для выполнимости и вычисляем значение формулы. Вычисление значения формулы полиномиально от n по времени, а угадывание полиномиально от n по памяти.

2.      Дадим доказательство того, что каждый недетерминированный полиномиально-ограниченный алгоритм может быть сведен за полиномиальное время к проблеме выполнимости lsat  исключительно для общей проблемы распознавания слова. Чтобы показать, что для каждого формального языка, чья проблема распознавания слова входит в NP, каждый алгоритм распознавания может быть сведен к lsat, для заданной  Т-машины М построим Т-машину М. Эта машина М реализует полиномиально-ограниченный алгоритм, получающий на входе слово х и порождающий булевское выражение Еx, которое точно тогда выполнимо, когда М принимает слово х. При этом М является р(n)-ограниченной по времени, а р(n) есть полином.

Теперь покажем, что каждая проблема из NP может быть за полиномиальное время сведена к lsat- B качестве недетерминированной Т-машины возьмем одноленточную правостороннюю машину (на ленте есть левый маркер).
Пусть {bi}0£ i £р(n) - последовательность конфигураций Т- машины М, которая соответствует последовательности вычислений машины М, причем пусть каждое из n состоит в точности из р(n)+1 символов (р(n) символов ленты, и один символ - состояние машины). Если вычисление заканчивается раньше, чем будут выполнены р(n) шагов, то повторим конфигурацию конечного состояния нужное число раз, так что имеется ровно р(n)+1 конфигураций. Основные идеи аргументации по сводимости таковы.

·         Каждое вычисление машины М состоит из последовательности самое большее р(n)+1 конфигураций. Эта последовательность может быть представлена (р(n)+1)^2 знаками, если мы также и состояния закодируем знаками. Обратим внимание: за р(n) шагов машина М может рассмотреть самое большее р(n) ячеек ленты.

·         Для каждого знака z в представлении последовательности конфигураций введем булевскую переменную Ci,z (1£ i £ (р(n)+1)^2), которая принимает значение true точно тогда, когда i-й знак есть z.

·         Образуется булевское выражение, дающее значение true точно тогда, когда соответствующая последовательность соответствует принимающему вычислению.

·         Формула может быть порождена из входного слова для М с затратой времени О(р(n)^2).

Свяжем состояние, знак под головкой и номер возможного для применения правила с одним новым знаком. Пусть теперь

# bо # b1— # bр(n)

есть последовательность вычислений, где #

b0 # -

это последовательность знаков с их номерами 0, 1, ..., р(n), р(n)+1 и т.д., а самый последний знак имеет номер (р(n)+1)^ причем этот последний знак есть # либо вновь введенный знак.

Для каждого знака z из алфавита Т-машины М, который может встретиться в таком вычислении, и для каждого числа i, 0£ i < (p(n)+l)^2 породим булевскую переменную Ci,z, которая задает, является ли i-й знак в последовательности конфигураций знаком z.


Образованное нами булевское выражение Еx точно тогда выполнимо, когда переменные Ci,z с присвоенными им значениями true

передают корректное вычисление.

В частности, Еx, естественно, должно быть таким, чтобы были справедливы следующие высказывания:

(1)"

i, l £ i < (p(n)+l)^2: $ x:Ci,x;

(2)        bо есть начальная конфигурация Т-машины М с входом х;

(3)        bр(n) есть принимающая конечная конфигурация;

(4)        bi ® bi+1 справедливо по заданному правилу.

Ex соответствует конъюнкции этих четырех высказываний. Точнее говоря, справедливо:

" i: ($ х: Ci,x) Ù Ø$ х, у,  у ¹ х: Ci,x Ù Ci,у.

(1)        Это записывается посредством формулы логики высказываний вида

Ф1Ù...ÙФ(р(n)+1)^2,

где

Фr =  ( Cr,a1 Ú Cr,a2 Ú…Ú Cr,ak) Ù (i,j(i¹j)(ØCr,i Ú ØCr,j))

(2)        Пусть х == <a1 ... аn> есть вход для Т-машины М. Приведенное выше высказывание (2) соответствует конъюнкции следующих высказываний:

(2i) cq,# Ù Cp(n)+i,# ,

(2ii) ci,yi Ú...Úc1,yk^,

 причем yi„ ..., у^ соответствуют знакам, которые кодируют знак а^ состояние qo и номер правила из k возможных, которое исходит из начального состояния qo и знака ai под головкой;

 (2iii)  " i Π {2, ..., п}: Ci,ai.

Остальные знаки а^, ..., an являются корректными.

 (2iv)  " i Π {n+1,..., р(n)}: Ci,#.

Выражение (3) говорит о том, что bр(n) является конечным состоянием. Как описание формулы логики высказываний получаем:

$ i, р(n)*р(n)+1) < i £ (р(n)+1)^2: ($ x Π F: Ci,x),

причем F обозначает множество новых (введенных нами) знаков, которые представляют конечное состояние.

(4)        То, что bi+1 вытекает из bi с помощью законного шага вычислений, проверяется высказыванием

"j, Р(n) < j < (р(n)+1)^2: $ w, х, у, w, x, y, :

Cj-l - (p(n)+l),w Ù Cj - (p(n)+l),x  Ù  Cj+l-(p(n)+l),y Þ Cj-l,w Ù Cj,x Ù Cj+l,y),



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

х ® x', или ху ® хy, или wx ® wx.

Порожденная таким образом формула Еx выполнима точно тогда, когда закодированная в конкретизации последовательность вычислений

# bo #…# bp(n) представляет собой корректно принимающее вычисление.

Можно показать, что формула Еx имеет длину О(р^2(n)). Она может быть порождена логарифмически ленточно-ограниченной Т-машиной

М из входа х. Действительно, Т-машине требуется лишь достаточно памяти, чтобы смочь считать до (р(n)+1)^2.

Поскольку log(p(n)+l)^2 = k*log n, достаточно 0(logn) памяти. Тем самым каждую проблему распознавания в NP можно свести к lsat  затратами памяти logspACE- Таким образом, lsat является NP-полной.

Пока не доказано ни Р = NP, ни Р ¹ NP, доказательство NP-полноты для какой-либо проблемы равносильно высказыванию, что для этой проблемы неизвестен какой-либо полиномиальный алгоритм. Если же удается задать полиномиальный алгоритм для NP-полной проблемы, то тем самым будет также доказано, что Р = NP.

Распределение ресурсов ВС

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

Выделение процессора

Принципиально выделяют следующие стратегии выделения процессора:

·

LIFO: программа с высшим приоритетом, прерванная последней, продолжается первой;

·         FIFO: программа дольше всех ожидающая продолжения выполнения первой продолжает выполняться;

·         смешанные формы FIFO-и LIFO-стратегий.

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

Длительность активной фазы программы может определяться одним из следующих способов:

·         неограниченное выполнение,

·         выделение времени программам по кругу,

·         концепция прерывания.

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

Управление оперативной памятью

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

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

2.      защита отдельных отрезков памяти от неправомерного доступа к ним из других программ пользователей.

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

1.      области памяти, необходимые для разных контекстов процессов, имеют различные размеры, которые к тому же могут изменятся по ходу выполнения программ;

2.      часто объем оперативной памяти оказывается недостаточным для размещения всех данных в пользовательских программах,

3.      наборы данных, содержательно связанные друг с другом должны быть объединены и организационно.

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

·         сегментация,

·         страничный обмен.

При сегментации оперативная память разбивается на много частичных отрезков.


Контекст процесса также может охватывать многие сегменты. Сегменты управляются с помощью дескрипторов.

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

Выделение устройств ввода/вывода

В противоположность центральному процессору, устройства ввода/вывода в основном не воспринимают активно относящиеся к ним указания, хранимые в памяти. Эти устройства активизируются процессором ввода/вывода с помощью регистров команд. Если последовательность команд запомнена в регистрах устройства, то взводится особый регистр (флаг); этим действием активизируется устройство ввода/вывода, которое автономно выполняет запомненную последовательность команд. После этого (путем установки соответствующего регистра) выдается сигнал об окончании выполнения заказа и устройство снова становится пассивным.

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

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

Распределение ресурсов в мультипрограммном режиме

Ресурсы машины в ОС не могут распределяться независимо друг от друга, поскольку отдельные запрашиваемые ресурсы обычно находятся в многообразных отношениях друг к другу.



Обратим внимание, что пользовательские программы предъявляют к ВС самые различные требования:

·         программы с интенсивным счетом требуют, прежде всего, процессорного времени;

·         программы с большими объемами используемых данных требуют, прежде всего, оперативной и внешней памяти;

·         программы с интенсивным вводом/выводом, прежде всего, запрашивают устройства ввода/вывода;

·         всякого рода управляющие программы, прежде всего, нуждаются в слябах системы и тем самым, соответственно, в каналах, памяти и процессоре.

При мультипрограммном режиме перед ОС возникают дополнительные проблемы:

·         замещение при выполнении отдельных программ для разрешения конфликтов при запросах на ресурсы;

·         справедливое распределение ресурсов;

·         минимизация организационных затрат;

·         минимизация времени переключения с задачи на задачу при прерываниях;

·         регулирование прав доступа к наборам данных. В таких случаях могут возникнуть и технические проблемы:

·         если в системе будет обрабатываться одновременно слишком много программ пользователей, то взаимное вытеснение программ из памяти может привести почти к застою в работе системы;

·         если в системе одновременно обрабатывается слишком мало программ, то определенные устройства иногда будут недостаточно загружены.

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

Выделение ресурсов в режиме диалога



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

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

·         полудуплексном: попеременно осуществляется то ввод, то вывод;

·         полностью дуплексном: одновременно может идти и ввод, и вывод.

В квазимногопрограммном режиме с простыми дисплеями каждый введенный или выведенный знак или слово вызывает прерывание, что ведет к значительной загрузке процессора (на обработку прерываний). Если использовать более мощные дисплеи и каналы, то процессор может быть существенно разгружен.

В диалоговом режиме ОС дополнительно к ее классическим функциям решает и следующие задачи:

·         объединяет введенные знаки в последовательности знаков и соединяет их в команды;

·         предписывает ввод/вывод отдельным программам пользователей и дисплеям;

·         выдает информацию на экран как эхо ввода и как истинный вывод;

·         управляет данными пользователей

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

Расширение аппликативных языков: объявления

Объявления обозначений элементов данных и функций служат улучшению читаемости выражении ЯП. Объявление позволяет ввести в употребление идентификатор и одновременно связать его с определенным элементом или определенным отображением, которое задается с помощью выражения. Говорят о "связывании" идентификатора с элементом или функцией. С помощью объявления принимается соглашение, что идентификатор в некоторой ограниченной области будет стоять в качестве сокращения (обозначения) значения выражения. Объявления находятся в секциях

(англ. section) (в некоторых ЯП вместо термина "секция" употребляется "блок".- перев.). Секция служит для установления границ области связанности идентификатора, порождаемого его объявлением.

Рассматриваются объявления для элементов данных и функций со следующим синтаксисом:

<сeкция> ::= [<inner>]|

if <inner> then <inner> {elif <mner> then <inner>}*

else <inner> fi

<inner> ::=

<объявлсние_типа>;<ехр>|

<объявление_элемента>;<eхр>|

{<объявление_функции>;}*<ехр>|

<procedural_inner>

Синтаксическая единица <procedural_inner> служит привязывайте элементов императивного ЯП к аппликативному стилю, а синтаксическая единица <объявлениe_типа> служит для привязывания объявлений типа к аппликативному стилю.

Разрешимость

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

Невычислимые функции

Все формализмы для представления алгоритмов позволяют представлять алгоритмы через конечные термы («программы»). Пусть PRG есть множество всех таких термов, которые представляют одноместные функции, например в нотации m-рекурсии. На самом деле PRG есть формальный язык. Для р Î

PRG обозначим через fp частичное отображение, вычисляемое программой р.

Все элементы р Î PRG есть слова над конечным множеством знаков и могут быть однозначно представлены («закодированы») с помощью натуральных чисел. Соответственно, существует инъективное отображение, гёделизация для PRG:

code: PRG -> N.

Существование такого кодирования получается тотчас из существования вычислимого, инъективного отображения, которое отображает конечные последовательности над “N в N. Например, мы можем

seqcode:N*àN

специфицировать через

seqcode(<n... nk>) = рn11 ,... ,рnkk

,

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

Теорема. Существует тотальная функция

g: -N->N,

которая не является вычислимой.

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

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

Разрешимые предикаты

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

Предикат р называется разрешимым,

если существует алгоритм, который для каждого предложения от аргументов х1, ..., xn вычисляет булевское

значение р (х1, ..., xn). Предикат р называется позитивно полуразрешимым, если имеется алгоритм, который для любого предложения от аргументов х1, ..., xn, при которых р (x1, ..., xn) справедлив, завершается и вычисляет значение true, а в противном случае (если р (x1, ..., xn) несправедлив) вычисляет значение false или же не завершается. Другими словами, положительный ответ выдается корректным образом и в конечное время, а отрицательный ответ следует либо корректно, либо не выдается. Предикат р называется отрицательно полуразрешимым, если -p является положительно полуразрешимым.

Примеры (разрешимость).

1.      Следующие проблемы разрешимы:

·         равенство двух натуральных чисел в их двоичном представлении;

·         определение простоты натурального числа;

·         принадлежность заданного слова языку, определяемому заданной грамматикой типа 3 по Хомскому;

·         существование нулевого места полинома над натуральными числами.

2.      Следующие проблемы являются положительно полуразрешимыми:

·         завершаемость работы машины Тьюринга для определенного входного слов;

·         принадлежность заданного слова языку, определяемому грамматикой типа 0 по Хомскому.



3.      Следующая проблема отрицательно полуразрешима:

·         равенство двух функций, заданных с помощью примитивной рекурсии.

4.      Следующая проблема неразрешима и тем самым не является ни положительно полуразрешимой, ни отрицательно полуразрешимой:

·         завершаемость функции, описанной с помощью ц-рекурсии, для любых значений ее параметров.

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

Важно делать различие между «неразрешим» («невычислима») и «не доказано». Так, для вычислимой функции f вообще неразрешимо, всегда ли ее вычисление завершается.

Рекурсивные и рекурсивно-перечислимые множества

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

Пусть М - заданное множество. Подмножество S с М называется рекурсивным, если характеристический предикат множества S является разрешимым.

Теорема. Каждый контекстно-зависимый язык (язык типа 1 по Хомскому) является рекурсивным.

Доказательство. Для каждого слова (на основании монотонности длин слов) множество слов, к которым оно сводимо, конечно; это множество может быть вычислено с помощью алгоритма. Отсюда получается существование способа разрешения.

Для подмножества S Í М тотальное отображение

е: N à М

называется перечислением (перенумерацией), если

S = {е(n): n Î N}.

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

если существует вычислимое («рекурсивное») перечисление для множества S.


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

Пример (рекурсивная перечислимость).

1.      Множество примитивно-рекурсивных функций является рекурсивно-   перечислимым, но не рекурсивным.

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

Если множество рекурсивно-перечислимо, то его характеристический предикат положительно полуразрешим.

Теорема. Любой язык Хомского рекурсивно-перечислим.

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

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

Доказательство. Если бы множество было перечислимым, то была бы разрешима проблема завершаемости для частично рекурсивных функций.

Теорема. Язык S над множеством знаков Т точно тогда является рекурсивным, когда и множество S, и множество T*\S являются рекурсивно-перечислимыми.

Доказательство.

1.      Если S и T*\S перечислимы, то тотчас получается способ разрешения для характеристического предиката для S:  параллельно перечисляются множества S и T*\S. Как только при этом встречается заданное слово, вопрос решен.

2.      Если S рекурсивно, то можно (очевидным образом существующий) способ перечисления для Т* уточнить к способу перечисления для множества S и соответственно для T*\S.

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

Теорема. Подмножество рекурсивно-перечислимого множества точно тогда рекурсивно-перечислимо, когда его характеристический предикат является положительно полуразрешимым.

Важное применение теории рекурсивных и рекурсивно-перечислимых множеств лежит в математической логике: множества булевских выражений (формул) можно также рассматривать с точки зрения рекурсивных и рекурсивно-перечислимых множеств.Рекурсивная система доказательств есть система доказательств с рекурсивным множеством аксиом и выводов, которые соответствуют рекурсивным отношениям над формулами. Тогда множество доказуемых формул является рекурсивно-перечислимым. Этот способ рассмотрения дает важный результат неполноты по Гёделю: соответственно этому для достаточно сложных структур, куда попадают и натуральные числа, не существует рекурсивных систем доказательств и потому есть только неполные аксиоматизации. Неполные системы доказательств содержат формулы, которые, хотя они и представляют элементарные высказывания, являются недоказуемыми и отрицание которых также недоказуемо.

Рекурсивные функции

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

Примитивно-рекурсивные функции

Примитивно-рекурсивные функции - это n-местные, тотальные функции

f: N” -> N,

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

В качестве базовых функций для определения примитивно-рекурсивных функций используются следующие отображения:

succ: N -> N                                 (функция следующего числа),

zero(0):à N                (константная нуль-функция),

zero(1):Nà N              (одноместная нуль-функция),

Справедливы следующие равенства, однозначно характеризующие базовые функции:

succ(n) = n+1,

zero(0)(n) = 0,

zero(l)(n) = 0,

Из заданных примитивно-рекурсивных функций путем композиции могут быть получены дальнейшие функции. Пусть функции

g: NӈN,

hi: N» -> N, 1£ i£ n,

примитивно-рекурсивны.

Тогда функция f: Nmà N,

специфицированная равенством    f=g.[h1,..., hn],

примитивно рекурсивна. Эта схема композиции функций введена в разделе, посвященном машинам Тьюринга.

С помощью схемы примитивной рекурсии,

как и с помощью композиции, из заданных функций можно получить дальнейшие функции. Пусть

g: NkàN,

h: Nk+1àN заданные функции. Тогда схема

f(x1,...,xk,0)=g(x1,...,xk), (*)

f(x1, ..., xk, n+1) = h(x1, ..., хk, n, f(x1, ..., xk, n)),

индуктивно специфицирует однозначно функцию

f: Nk+1 ->N.

При этом (*) называется схемой примитивной рекурсии. Однозначность функции f доказывается просто полной индукцией. Поэтому также об индуктивном определении функции f.

Примитивная рекурсия соответствует функциональному представлению статической ограниченной итерации или повторению (ср. с “for-повторением»), при которых параметр глубины рекурсии определяется статически (к началу итерации с помощью явно заданного числа). Отсюда получается, что при примитивной рекурсии рекурсивные вызовы всегда завершаются. Для приведенной выше схемы примитивной рекурсии путем развертывания получается следующее равенство:

f(x1, ..., xk, n) =h(x1, ..., xk, n-

h(x1,..., xk, n-2,

                           …

h(x1, ..., xk, 0, g(x1, ..., xk)) ... )).

Функцию f, специфицированную с помощью примитивной рекурсии над g и h,  обозначается также через pr(g, h). При этом рг можно трактовать как функционал следующего вида:

рг: ((Nk -> N) х (Nk+2àN))à (Nk+1® N).

Функционал pr примитивной рекурсии соответствует схеме определения. Пишется

f= pr(g, h)

в качестве сокращения для приведенной выше схемы (*).

Равенство вида

g(x1, ..., Хm) = E

для определения функции g с произвольным выражением Е, которое образовано из символов функций f1, ..., fn и идентификаторов x1, ..., xn,  может быть через применение композиции и проекции записано также в  форме равенства между функциями:

g=F,

причем выражение F построено из композиций функций f1, ..., fn и проекций. Такая нотация ведет к стилю «функционального программирования», при котором вместо применения функций используются только  композиции функций.

Схема примитивной рекурсии ведет, обращаясь к Т-вычислимым функциям, снова к Т-вычислимым функциям. Выражаясь точнее, справедливо следующее высказывание: если

g:Nk->N,

h:Nk+2àN

есть Т-вычислимые функции, то pr(g, h) тоже Т-вычислима. Формально J

это можно показать путем построения из двух Т-машин для вычисления g g и h новой Т-машины, которая вычисляет pr(g, h).

Определение множества PR примитивно рекурсивных функции как наименьшее подмножество множества {f: N” -> N : n Î N} n-местных (тотальных) функций над натуральными числами N со следующими свойствами этих подмножеств:



(1) Все базисные функции входят в PR.

(2) Если g, h1 ,.., hn Î PR (пусть g есть n-местная, a h1, ..., hm - m-местные функции), то справедливо

g . [h1,..., hn] ÎPR.

(3) Если g (k-местная) и h ((k+2)-местная) принадлежат PR, то pr(g, h) также принадлежит PR.

Однако это - неявное определение. Поэтому существуют примеры примитивно-рекурсивных и непримитивно-рекурсивных функций. Функция

sign: N -> N,

где

sign(n)=0, если n = 0, sign(n)= 1, если  n > 0,

является примитивно-рекурсивной:

справедливо sign(0) = 0, sign(n+l) = 1.

Отсюда получается следующее применение схемы примитивной рекурсии для определения функции sign:

sign = pr(zero(0), succ . [zero(1) о [ п21

]]).

Функция case

case: N3 ->

N,

специфицируемая равенством

case(x,y,z)=   [ y,  если х =0; z, если x>0 ]

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

case(x, у, z) = у* (l-sign(x))+z * sign(x).

Это соответствует выражению :

case(x, у, z) = add(mult(y, sub(l, sign(x)))), mult(z, sign(x))).

Подставляя примитивно-рекурсивные функции add, mult, sub и sign, получается выражение, которое построено только средствами примитивно рекурсии.

Из схемы определения для примитивно-рекурсивных функций получаются следующие высказывания:

(1) Все функции в PR тотальны.

(2) Все функции в PR Т-вычислимы.

(3) Существуют Т-вычислимые функции, которые не являются прими тивнo-рекурсивными.

Высказывания (1) и (2) следуют из того факта, что по схеме определени из тотальных, Т-вычислимых функций возникают тотальные, Т-вычислимые функции.

Высказывание (3) получается тривиально из того обстоятельства, чтo существуют частичные функции, которые являются Т-вычислимым Однако это высказывание может быть также подтверждено на примере тотальной функции. Рассмотрим для этого функцию Аккермана

ack: N2->N,

специфицированную следующей (непримитивно-рекурсивной) схемой:

ack(n,m)=[m+1,если n=0; ack(n-1,1),если n>0,m=0; ack(n-1,ack(n,m-1)),

если n>0,m>0]

Функция ack с помощью этого различения случаев определяется индуктивно.


Тем самым она определяется однозначно, что просто показывается через индукцию. Конечно, функция Аккермана интуитивно вычислима. Ее Т-вычислимость можно показать путем задания машины Тьюринга, которая вычисляет эту функцию. Этого можно достигнуть путем  моделирования магазина на Т-машине

Функция ack не является примитивно-рекурсивной. Фнкция ack состоит и множества примитивно-рекурсивных функций.

Теорема. Для любого числа n Î N функция Вn: N -> N,

специфицированная через

Теорема. Функция ack не является примитивно-рекурсивной.

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

m-рекурсивные функции

Примитивно-рекурсивные функции, соответственно определению, всегда являются тотальными. Как показывает пример функции Аккермана, существуют также тотальные функции, которые интуитивно являются вычислимыми и также

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

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

Пример (частично вычислимая функция). Для одноместной функции, заданной примитивно-рекурсивным определением (выражением), вычисляется ее наименьшее нулевое место - наименьшее натуральное число, для которого функция имеет значение 0 (т. е. min {х Î N: f (х) = 0}). Известно, что существует универсальная функция F (i, х), представляющая множество  всех  одноместных  частично  рекурсивных  функций (выражений).


Функция g, реализующая для универсальной функции указанное выше вычисление min по схеме m (см. ниже):

g(i) = min{x Î N: F(i, х) = 0},

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

g=[ g(i), если нулевое место существует; 1 в противном случае],

не является вычислимой (см. десятую проблему Гильберта).

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

Пример (недоказанная завершаемость). Пусть отображение ulam специфицировано через

Ulam(n)=[1,n<1;ulam(g(n)) в противном случае]

причем функция g специфицирована следующим образом:

g(n)=[n/2,n- четно;$*n+1  иначе]

Обратим внимание, что функция g примитивно-рекурсивна. Это можно показать следующим образом. Отображение

Even(n)=[1,n-четно; 0  иначе]

является примитивно-рекурсивным. Функция g специфицирована через различение двух примитивно-рекурсивных функций и тем самым сама является таковой.

В зависимости от вопроса, завершается ли вычислительное предписание ulam для всех аргументов, справедливы следующие высказывания:

(1)                Если предписание ulam завершается всегда, то для всех n Î N справедливо

ulam(n) = 1.  При этом предположении функция ulam примитивно-рекурсивна.

(2) Если для определенных входных значений ulam не завершается, то ulam есть частичная функция и потому определенно непримитивно-рекурсивна, так как примитивно-рекурсивная функция всегда тотальна. Форма описания функции ulam не позволяет сделать заключение, что эта функция является примитивно-рекурсивной.

До сих пор не удалось показать завершаемость функции ulam.

Очевидно, что формализм примитивной рекурсии не достаточно мощен.


Поэтому нужно расширить его так, чтобы также могли быть описаны и частичные функции.

Пусть задана частичная функция

f: Nk+1 -> “N (k Î N).

Специфицируем частичную функцию

m(f): Nkà N

через

m(f)(x1, ..., xk) = min {у Î N : f(x1, ..., xk y) = 0},

если существует такое число у ÎN, что

f(x1, ..., xk, у) =0

и для всех z < у значение функции f (х1, ..., хk, z) определено. Если такого числа у не существует, то значение применения функции m(f) к аргументу (x1, ..., хn) не определено.

Здесь говорится о принципе минимизациию

Функционал

m: (Nл+1

-> N) -> (NkàN),

который в описанной выше форме каждую (k+1)-местную функцию отображает

на k-местную функцию, называется также m-оператором.

Функция m(f) очевидно вычислима, если функция f вычислима. Это можно обосновать следующим образом. Можно тривиальным образом вычислять последовательно значения f(x1, ..., xn, 0), f(x1, ..., xn, 1),... до тех пор, пока не получится значение 0 как результат. Тогда можно закончить вычисления с соответствующим значением у в качестве результата. Если не существует нулевого места или же один из исследуемых вызовов не завершается до того, как будет найдено нулевое место, то такой способ не завершается. В этом случае применение функции m (f) не определено. Функции, которые могут быть определены на основании примитивно-рекурсивных функций с дополнительным применением m-оператора, называются m-рекурсивными.

Пример (m-рекурсивные функции). Следующие функции являются m-рекурсивными:

(1) Частично определенное вычитание

а-Ь= [a-b,  если а>Ь; не определено иначе.]

Определяется

а - b = m(hо)(а, b), где

ho:N3

-> N

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

ho(a, b, у) = sub(b+y, a)+sub(a, b+y).

Здесь sub обозначает тотальное вычитание на натуральных числах

Sub(а,b)=[a-b, если а>b; sub(a,b)= 0 иначе]

m (ho) на самом деле есть искомая функция.

1.                   Случай а >.



b. Для у = а-b получается:

ho(a, Ь, а-Ь) = sub(b+(a-b), a)+sub(a, b+(a-b)) = 0.

Для у < а—b (т. е. для b+у< а)

справедливо: ho(a, b, у) = sub(b+y, a)+sub(a, b+y) = sub(a, b+y) > 0.

Таким образом, в этом случае имеет место ). m(ho)(a, b) = а—b.

2.         Случай а < b. Для всех чисел у получается:

ho(a, b, у) = sub(b+y, a)+sub(a, b+y) =

sub(b+y, а) > 0.

Таким образом, в этом случае m(Ьо) (а, b) не определено.

(2)                Деление. Частично определенное деление

a./.b=[a/b,a mod b=0; 0, a=b=0; не определено иначе]

специфицируется через m-рекурсию

m(h1),

где

h1(a, b, z) = а - (b * z).

Это снова можно показать путем различения случаев.

1.         Случай a mod b = 0 или а =Ь= 0;

Если имеет место b > 0, то число у однозначно определено и для z < у определено

a-b*z.. Если b = 0, то у = 0 удовлетворяет уравнению.

2.         Случай a mod b не равно 0 или b = 0 , а> 0; если b > 0, то справедливо а •/•b не определено.

Не существует такого числа z, что a-b*z= 0, так что выражение а - b * z или не определено, или оно > 0. Если а > 0 и b = 0, то

а - b*y > 0

для всех у; тогда m (h1) (а,b) не определено.

(3) ulam. Функция ulam специфицируется через

ulam(n) = succ(zero(l)(m( h )(n))), причем пусть функция g специфицирована так же, как и при введениифункции ulam в начале данного раздела, а функции h и h специфицированы следующим образом:

h(n, 0) = п,

h(n, m+l) = g(h(n, m)),

h(n, m) = sub(h(n, m)-1) == pred(h(n, m)).

Снова можно доказать, что для всех n Î N значение ulam (n) совпадает

со значением succ (zero(1))(m(h )(n))). Имеет место: ulam (n) = 1 или ulam (n) не определено.

(1)  h(n, m) = gm(n),     где go(n) =n,

(2)  h(n, m) = 0à h(n, m) < 1à g”’(n) < 1.

Поэтому m( h )(n) определена точно тогда, когда справедливо

Э m:gm(n) < 1,

и дает наименьшее число m, для которого это свойство имеет место.

Определяется множество MR m-рекурсивных функций как наименьшее подмножество пространства функций



{f: N” -> N: n Î N}

m- местных частичных отображений, для которого имеет место:

1.      MR содержит примитивно-рекурсивные функции PR,

2.      MR содержит все функции, которые можно получить путем композиции функций из MR,

3.      MR вместе с f содержит также m(f).

Множество MR охватывает все в общем смысле рекурсивно определимые функции над натуральными числами. Мы говорим о MR также как о множестве частично рекурсивных функций.

Общие объявления рекурсивных функций

m-рекурсия является частным случаем общего объявления рекурсии. На ряду с

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

(1) Общая структурная рекурсия. Функции с функциональностью

f : N” -> N описываются через систему уравнений вида

f(ti1,...,tin)=Ri,

где терм Ri содержит только рекурсивные вызовы функций, включая f, базисные функции (как succ, zero и pred) и встречающиеся в левой части

уравнения идентификаторы хi, причем для термов tij. пусть справедливо

tij= xi+l или tij = 0.

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

Пример (функция Аккермана через структурную рекурсию). Функция Аккермана однозначно определяется уравнениями:

ack(0,0) = 1,

ack(0, m+l) = ack(0, m)+l,

ack(n+l, 0) = ack(n, 1),

ack(n+l, m+l) = ack(n, ack(n+l, m)).

Уравнениям структурной рекурсии могут удовлетворять различные частичные функции. Аналогично принципу минимизации  выбирается, в смысле определяемости наименьшая функция (наименьшая неподвижная точка), которая удовлетворяет уравнениям.

Определение рекурсивности может быть обобщено от функций над натуральными числами на любые перечислимые множества М путем введения отображений

rep: М -> N («функция представления»),

abs: N -> М («функция абстракции»),

которые «интуитивно» являются вычислимыми и для которых равенство

abs(rep(m)) = m

справедливо для всех m Î М. Тогда функцию f: МàМ

назовем вычислимой точно тогда, когда существует вычислимая функция

g:N->N, такая, что

f (m) = abs(g(rep(m))).

Можно также, аналогично m-рекурсии, для примитивных рекурсий  или структурной рекурсии над натуральными числами ввести понятие вычислимости прямо над общими вычислительными структурам. Особенно просто можно понятие вычислимости распространить на предикаты над натуральными числами благодаря тому, что мы, например, значения false и true представим соответственно в виде 0 и 1.

Рекурсивные объявления функций

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

Объявление функции fct f = (m x) n: E называется рекурсивным,

если в абстракцию в правой части объявления (вернее, в тело E) снова свободно входит объявляемый идентификатор f. Рекурсивные объявления функций в общем случае ведут к вычислительным предписаниям с неограниченной длительностью вычислений и тем самым представляют собой мощный инструмент программирования. Соответственно этому понимание семантической интерпретации рекурсивных объявлений является особенно важным, но в то же время более трудным, чем при нерекурсивных объявлениях

В рекурсивном объявлении fct f = (m x) n: E символ функции f снова входит в Е в правой части. Поэтому абстракцию (m x) n: E

нельзя понимать как определение. Если попытаться абстракцию наивно представить как определение для f, то это приводит к "цикличности" определения. Так что сначала полностью не ясно, какая функция должна быть связана с идентификатором f.

Соответственно для рекурсивного объявления нельзя, как для нерекурсивного вычислительного предписания, вывести значение просто с помощью установления I[fct f = (m x) n:E](

) =  [f1/f], где f1 = I[(m x) n: E](), так как в Е снова встречается символ f и тем самым функция f1 не может быть определена без того, чтобы в  было задано значение для f. Это определение во всяком случае является циклическим: значение для f может быть установлено, если имеется налицо значение f. Поэтому из рекурсивного объявления можно сначала вывести лишь предписание, которое каждой заданной функции f ставит в соответствие функцию f1.

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

·

индуктивное толкование;

·         толкование через равенство фиксированной (неподвижной) точки.

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

До того как последует точное описание смысла рекурсивного объявления, сначала необходимо дать краткое разъяснение способа того, как можно обращаться операционально с рекурсивным объявлением

Подстановку правой части объявления функции вместо функции называют расширением

или развертыванием (англ. unfold) вызова рекурсивной функции. Через повторное применение правила расширения можно при известных обстоятельствах редуцировать рекурсивный вызов к значению. Идея вычисления через расширение является ведущей линией для операционального смысла рекурсивных объявлений функций.

При толковании с помощью функционала мы соединяем с рекурсивным объявлением функцию, которую связываем с объявляемым идентификатором.

Рекурсивные объявления функций в системах подстановки термов

Пусть снова дано рекурсивное объявление функции let

f == (m х) n: Е.

Для выражения, которое использует f, применяется следующее правило замены термов: f(El)-^((mx)n:E)(El), т. е. для вычисления идентификатор f заменяется на правую часть рекурсивно описанной функции. Тем самых! рекурсивное объявление функции соответствует дальнейшему правилу подстановки термов, которое присоединяется к наличным правилам.

Пример (редукция для рекурсивно описанных функций). Для рекурсивного определения fct fac = (nat x) nat:

if x=0 then 1

else x * fac(x - 1) fi

возникает вычисление (пусть 2 стоит вместо succ(succ(zero))):

fас(2)

((nat x) nat: if... fi) (2)

if 2 = 0 then 1 else 2 * fac(2 - 1) fi

 ...

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

Дерево вычислений

Далее ki à(i) К2,

если конфигурация К^ исходя из ki, может быть достигнута не более чем за 2^ (При ^= i ) шагов. Для i ³ 1

K1®^K2

можно вычислить тем, что мы k1®(Ù-1)k и К®(Ù-1)К2 перепробуем для всех К. Справедливо высказывание:

если вывод Ki ®^ К2 происходит в точности за 2^ шагов, то вывод может быть реализован с затратами памяти, необходимыми для хранения i конфигураций между k1 и К2.

Доказательство этого утверждения можно провести по индукции. При i == 0 справедливость утверждения очевидна. Для (i + 1) вначале реализуется вывод k1 ®^ К с затратами памяти для (i - 1) + 1 = i конфигураций. Затем реализуется вывод К ®^ К^ с теми же затратами на той же памяти.

Таким образом, общие затраты памяти равны 1+(i-1) == i, что и требовалось доказать.

Итак, для доказательства теоремы следует построить Т-машину, которая выполняет приведенную выше стратегию затрат памяти, т. е. надо промоделировать выполнение алгоритма со следующей спецификацией для каждой заключительной конфигурации Kf:

ifTEST(Ko, Kf, [log2(c^)] then принять fi (при ^=S(n))

где

TEST(Ki, К2, i) ==    if i = 0   then

(k1=k2) v (k1 ® К2)

else

$ K: TEST(K1, K, i-l) Ù test(k, K2, i-l),

где К - конфигурация из с^ возможных конфигураций fi

Для задания параметров TEST достаточно памяти O(S(n)). Действительно, для третьего параметра, числа [S(n)*log2(c)]+1 достаточно объема памяти 0(log2S(n)). Для конфигураций (их две) - поскольку входная лента не учитывается, т. е. в конфигурацию вносится только положение головки на входной ленте, - достаточно памяти

m*(S(n)+l) + Log(n) £ (m+1)S(n)+m, где m - число рабочих лент. Глубина стека равна [log2(c^]+2,=[S(n)log2(c)]+2, а поскольку каждый заносимый в стек элемент (параметр для TEST) занимает объем памяти O(S(n)), то общая потребность в памяти имеет порядок 0(S(n)^2).

Семантическая модель реальности и идеальности

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

Сформируем тезисно концептуальные положения по этому заключительному разделу, относящемуся к понятию семантики:

·

Семантика есть интерпритация связи содержания с формой.

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

·         Семантическая сущность информации, циркулирующей в человеко-машинных системах, как в любых искуственных системах, созданных человеком, проявляется через человека. В машинах нет плана-содержания, того, что существует в любых естественных системах. В искуственно созданные человеком информационные системы информация привнесена человеком. В машинах отсутствует интелект. Машинная технологическая информация имеет формальный, синтаксический характер, семантическая же сущность сообщений остаётся человеком.

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

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

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

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

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

·         В социальных системах физическая среда и каналы связи строятся человеком, а в качестве системы кодирования выступает естественный язык-важнейшее средство человеческого общения и орудие мысли. В работе ЭВМ участвуют искуственные языки, в основе которых лежит двоичная система исчесления. Формальная интерпретация сообщений на этих языках на стадии разработки осуществляется программистами, что создаёт семантический барьер между пользователем и машиной на стадии эксплуатации.

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

 

Сети Петри

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

Сеть Петри, или сеть условий/событий, есть направленный граф, состоящий из узлов двух типов - так называемых вентилей

(еще используются термины: переходы, барьеры) и ячеек (места, площадки). Ребра по мере надобности ведут от вентилей к ячейкам или от ячеек к вентилям. Ячейки загружаются логическими значениями или натуральными числами. Содержимое ячеек определяет состояние сети. В каком-либо заданном состоянии определенные вентили (множество вентилей) готовы к передаче (они могут «открываться» - путем открытия такого множества вентилей изменяется загрузка сети, т.е. содержимое ее ячеек).

Пусть дано множество T вентилей и множество Р ячеек (с Р ? Т = Ø ). Сеть Петри есть тройка (Т0, Р0, R), такая, что справедливо

Т0

Т                                                                         вентили,

Р0

 Р                                                                        ячейки,

R 

 (Т0

х Р0) U (Р0 х Т0)                                           отношения потока.

Множества Т0

и  Р0  конечны. В таком случае сеть Петри есть бичастичный направленный граф. Граф называется бичастичным, если множество его узлов разбито на два класса и ребра могут соединять только узлы из различных классов.

Для сети Петри (Т0, Р0, R) каждое отображение

b: Р0

> N, которое ячейкам предписывает числа, означает целочисленную конкретизацию (занесение в ячейки конкретных чисел). Сети с целочисленными конкретизациями называются также сетями ячейки-вентили. Часто для некоторых ячеек устанавливаются дополнительно определенные наибольшие значения («мощность ячейки»), которые могут иметь заносимые в эти ячейки значения.

В некоторых случаях можно ограничиться сетями Петри с конкретизациями, использующими только значения 0 и 1, или соответственно false

и true. При этом рассматриваются только конкретизации вида b: Р0 > В.

В таких случаях говорят о булевских сетях Петри или сетях условия-события.

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

Для целочисленной конкретизации b  сети Петри (Т0, р0, R) непустое подмножество К Т0 называется готовым к передаче, если для каждой ячейки р  р0, справедливо:

| {k  K: (р, k)  R}| ? b(p).

Множество К вентилей по этому определению для некоторой конкретизации готово к передаче, если в каждой ячейке р находится достаточно меток, чтобы все вентили k  K, для которых стрелка от ячейки р ведет к вентилю k, при переключении были снабжены метками. Если для каких-то ячеек предусмотрены ограничения на помещаемые туда метки, то имеет место ограничение мощности. Множество К только тогда готово к передаче, когда проходящие через вентили метки не превосходят соответствующие максимально допустимые значения. В случае булевских сетей Петри для каждой ячейки р Р0

и каждого вентиля k  K требуется выполнение следующего условия для готовности к передаче множества вентилей К Т:

(р, k)  R => b(p) ^ | { k  K: (р, k)  R}| ? 1

и дополнительно следующего условия бесконфликтности: для каждой ячейки р Р0

и каждого вентиля k  K должно иметь место

(k, р)  R => ¬b(p) ^ | { k  K: (k, р)  R}| ? 1.

Это условие говорит о том, что вентиль k может открыться только тогда, когда все ячейки, к которым ведут ребра из k, помечены через false. Аналогично булевские сети Петри соответствуют целочисленным сетям Петри, в которых каждая ячейка имеет мощность 1.

В булевских сетях Петри дополнительно требуется выполнения следующего условия «отсутствия петель»: никакой вентиль не имеет права использовать одну и ту же ячейку как в качестве входной, так и в качестве выходной ячейки.


Т. е. должно выполняться следующее условие:

 t  Т0, p  P0: ¬ ((t, p)  R ^ (p, t)  R).

Если бы для какого-либо вентиля t это условие не выполнялось, то такой вентиль (при учете правила переключения для сети условие-событие) никогда не был бы готов к передаче.

Лемма. Пусть заданы сеть Петри и множество К вентилей со следующим дизъюнктивным разложением:

К = К1  К2,                               К1

 К2 = Ø.

Тогда имеет место: если множество К готово к передаче для конкретизации b0 с последующей конкретизацией b, то имеется такая конкретизация b1, что справедливо: К1 готово к передаче с последующей конкретизацией b1, и К2 готово к передаче для b1 с последующей конкретизацией b.

Доказательство.

Определение готовности к передаче К влечет за собой готовность к передаче любого его подмножества К1. Для последующей конкретизации b1

при К1 для b0 подмножество К2 готово к передаче, так как К = К1  К2 было готово к передаче для b0. Поскольку К1  К2 = Ø, то сумма эффектов от К1 и К2 есть эффект К.

Сеть Петри обладает, как правило, большим числом процессов как ходов работы. Исходя из начальной конкретизации сеть Петри порождает ход работ (процесс пробегает по сети Петри) благодаря тому, что активизируются готовые к передаче множества вентилей и выполняются соответствующие им действия, в результате чего и осуществляется переход к последующим конкретизациям.

Для сети N = (Т0, Р0, R) рассмотрим процесс р = (Е0, ?0, ?) с маркировкой события через действия:

?: Е0 > Т0.

Для исходной конкретизации b0 и сети Петри N0 = (Т0, Р0, R) конечная структура действий р = (Е0, ?0, ?) называется ходом работы сети Петри с конечной конкретизацией b1, если р соответствует поведению сети с исходной конкретизацией b0:

b0 b1.

Это отношение между конкретизацией и процессами для заданной сети определяется следующим образом:

(1)        Пустой процесс всегда есть ход работы и не меняет конкретизации. Т.о. для пустого процесса р и любой конкретизации b справедливо следующее соотношение:



b b.

(2)        Пусть р = (Е0, ?0, ?) - процесс с тривиальным причинным порядком, в котором различные события являются причинно независимыми.

Для процесса р справедливо следующее:

e, d  Е0: e ?0 d e = d.

Тогда  для конкретизации b0 и b1

отношение

b0 b1

справедливо только тогда, когда все события в р помечены по-разному и потому справедлива следующая формула:

e, d  Е0: e ? d  ?(e) ? ?(d),

и множество К = { ?(e): e  Е0 } для конкретизации b0

готово к передаче и ведет к последующей конкретизации b1.

(3)        Для каждого процесса р = (Е0, ?0, ?), который не удовлетворяет условиям (1) или (2), отношение

b0 b2

справедливо только тогда, когда для каждого непустого префикс-процесса

р1 = (Е1, ?1, ?1) со свойством

р1  р ^ p1 ? p

существует такая конкретизация b1, что для процесса р2 = р | E0\E1

справедливо следующее высказывание:

b0 b1

^ b1 b2

Это определение принимает во внимание в пункте (2) то обстоятельство, что вентили в сети Петри рассматриваются только как последовательные единицы. Параллельные события всегда маркируются различными вентилями.

ас

be

Для каждого конечного процесса р и каждой конкретизации b0 через

b0 b1

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

Лемма. Если для процесса р = (Е0, ?0, ?) и конкретизации b0 и b1 справедливо высказывание

b0 b1,

то для каждого префикса р1

процесса р с множеством событий Е1 справедливо следующее высказывание: для каждого множества событий Е2, которое является минимальным относительно ?0 в Е0\Е1, справедливо, что множество { ?(e): e  Е2} является готовым к передаче.

Доказательство. Подпроцесс в р, который состоит только из событий из Е2, для конкретизации b1 является ходом работы.

Лемма.

Если процесс р есть ход работы сети N с исходной конкретизацией b0, то каждый префикс-процесс р1  р есть ход работы сети N с исходной конкретизацией b0.

Доказательство.


Согласно определению понятия хода работы для сети Петри процесс р есть ход работы, если любой префикс р есть ход работы.

Структура действий р = (Е0, ?0, ?) называется совершенным ходом работы сети Петри N с конкретизацией b0, если справедливо одно из следующих условий:

(1)               Множество событий E0 бесконечно, и любой конечный префикс р есть ход работы сети N с исходной конкретизацией b0.

(2)               Множество событий Е0 конечно, и р есть ход работы сети N для начальной конкретизации b0 с конечной конкретизацией b1, и для b1

не существует непустого готового к передаче множества.

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

Две сети с исходными конкретизациями называются эквивалентными

(с точки зрения их работы), если они имеют одинаковые множества совершенных ходов работы.

Лемма (линеаризация процессов). Если р есть ход работы сети Петри N с исходной конкретизацией b, то каждая линеаризация р также есть ход работы N с исходной конкретизацией b.

Доказательство.

Каждая линеаризация, по лемме линеаризации для готовых к передаче множеств, может через может через линеаризацию достичь определенных готовых к переходу множеств.

Обратное утверждение леммы не справедливо. Из множества последовательных ходов работы сети Петри нельзя сделать вывод о множестве не последовательных ходов работы.

Бесконечный ход работы р = (Е0, ?0, ?) сети Петри N с исходной конкретизацией b называется несправедливым по отношению вентиля а, если  одновременно выполняются следующие условия:

(1)        Множество {e  Е0: ?(e) = a} событий, помеченных действием а, конечно.

(2)        Множество конечных префиксных процессов р1 р, причем р1 = (Е1, ?1, ?1) с

{e  Е0: ?(e) = a} = {e  Е1: ?1(e) = a}

и

b0 b1,

причем вентиль а в b1



готов к передаче, является бесконечным.

В несправедливом по отношению действия а бесконечном ходе работы сети Петри вентиль а встречается лишь конечное число раз, хотя он бесконечно часто готов к передаче. Ход работы называется справедливым, если он не является несправедливым относительно никаких вентилей.

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

Термы для описания процессов

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

Для представления систем используются языковые термы, называемые агентами. Рассмотрим следующий БНФ-синтаксис языка агентов:

<agent>::= skip

<action>

<agent>; <agent>

<agent> or <agent>

<agent> || <agent>

<agent> id

<agent id>:: <agent>

В данном случае <action> обозначает некоторый наперед заданный принятый язык для описания отдельных действий, а <agent id> - наперед заданное множество идентификаторов для агентов. С помощью этого языка агентов, как и с помощью сетей Петри, могут описываться множества процессов. Эти множества снова означают ходы работ агентов. Агент skip может выполнить только пустой процесс. Агент t1; t2 соответствует последовательной композиции процессов, описанных агентами t1 и t2.  Агент t1 or t2.в качестве множества процессов обладает объединением множеств процессов, описанных агентами t1 и t2.  Агент t1 || t2. описывает множество процессов, которое содержит параллельную композицию некоординируемых процессов, описываемых агентами t1 и t2 . Пусть t есть терм агента, в который свободно входит идентификатор агента х. Агент соответствует агенту (вызову агента) х, который характеризуется рекурсивным объявлением х == t. С помощью рекурсивно определенных агентов могут быть специфицированы бесконечные процессы.



При известных обстоятельствах необходимо использовать непоименованные вспомогательные вентили, чтобы выразить поведение агента сетью Петри.

Для каждого терма t синтаксической единицы <agent> и каждой структуры действий р = (Е0, ?0, ?) можно аналогично конкретизациям сетей Петри установить, представляет ли структура действий р возможный ход работы агента t. Это можно сделать формально с помощью определения отношения (аналогично отношениям переходов между состояниями сети Петри) t1 t2., которое свидетельствует о том, что агент t1 может выполнить процесс р и после этого ведет себя как агент t2.

Это отношение, которое устанавливает, какие ходы работы возможны для агентов и к каким агентам они ведут, определяется рекурсивно следующим образом:

(1)        Каждый агент может выполнить пустой процесс. Для пустого процесса р0 и любого агента t определим соответственно:

t t.

(2)        Агент а, состоящий из единственного действия а, может выполнить процесс, который содержит единственное событие, помеченное действием а.

a  skip,

(3)        Пусть р, р0, p1 и р2 - любые процессы. Агент t1 ог t2 показывает неде-терминированно поведение агента t1 или агента t3.

t1 t2 => t1 or t2   t3,

t2   t3

=> t1 or t2  t3.

Агент t1; t2 ведет себя как агент t1 и, если t1 этим поведением переводится в skip, в заключение ведет себя как агент t2 . Соответственно определяются следующие два правила для последовательной композиции агентов:

t1   t3 => t1 ; t2   t3

; t2,

t1  skip

^ t2   t3 ^ isseq(p, p1, p2) => t1 ; t2   t3.

Поведение агента t1 || t2 складывается параллельно из поведения t1 и t2. Если поведение обоих агентов приводит к skip, то и поведение t1 || t2 тоже приводит к skip. Агент t1 || t2

завершается, если завершается как t1, так и t2 . Соответственно определяем:

t1  r1 ^  t2   r2

^ ispar(p, p1, p2, Ø) => t1 || t2   r1 || r2,

t1  skip

^ t2  skip ^ ispar(p, p1, p2, Ø) => t1 || t2   skip.

(4)        Для любого процесса р определим ходы работ для рекурсивных агентов с помощью следующего правила:



t[ x::t/x ]   t0 => x::t  t0.

Теперь через определенное выше отношение каждому агенту можно предписать множество процессов. Процесс р называется (несовершенным) ходом работы агента t0, если существует агент t1.

t0  t1.

Множество ходов работ является замкнутым относительно образования префиксов.

Лемма (закон разложения). Если для агентов t0, t2 и конечного процесса р справедливо высказывание

t0t2,

то для каждого префикса р1 р существует агент t1 такой, что

t0 t1, t1  t2,

Доказательство - индукцией по числу событий в p1.

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

Предложение (связывание процессов). Если для агентов t1, t2, t3

и процессов р0, p1  справедливо высказывание

t1 t2 ^ t2   t3,

то существует процесс р2 такой, что t1 t3.

Доказательство, индукцией по структурам агентов.

Агент t0 называется терминальным, если для любого агента t1

высказывание

t0 t1

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

Процесс р называется совершенным ходом работы агента t0, если для терминального агента t1 справедливо:

t0 t1

или же процесс р является бесконечным и каждый его префикс р1 р является ходом работы.

Два агента называются эквивалентными,

если они обладают одинаковыми множествами совершенных ходов работы.

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

Для агента t0 агент t1 называется достижимым, если существует процесс р такой, что t0 t1



Для агента, который моделирует распределенную систему или определенный ее аспект, можно выделить следующие вопросы:

1.      Какими свойствами обладает множество достижимых агентов? Является ли это множество конечным?

2.      Исключается ли для определенных действий, что будет порожден процесс, в котором оба эти действия имеют место одновременно (взаимное исключение)?

3.      Может бы быть с помощью процесса достигнут агент (отличный от skip), для которого возможны только тривиальные переходы (тупики)?

4.      Может ли быть достигнут агент (отличный от skip), исходя из которого больше не достижим никакой агент, в котором имеют место определенные действия (локальный тупик, отсутствующая живучесть)?

5.      Существуют ли бесконечные процессы, в которых одно из действий никогда не встречается (справедливость)?.

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

Координация особенно необходима, чтобы при параллельно протекающих процессах можно было исключить конфликты.

Пусть S - подмножество множества действий А. Процесс р0 = (Е0, ?0, ?0) может быть сложен из процессов р1 и р2 тем, что события, помеченные действиями из S, установлены в качестве общих событий. Тогда справедливо: ispar(p0, p1, р2, S).

Рассмотрим частный случай для установления общих событий. Множество действий А разлагается на два дизъюнктивных подмножества U и S:

·         действия множества U являются асинхронно выполняемыми действиями,



·         действия множества S являются только синхронно выполняемыми действиями.

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

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

Наряду с несинхронизируемой параллельной композицией агентов важно рассмотреть и  синхронизируемую параллельную композицию агентов. Это может происходить посредством синхронной параллельной композиции ||s, где S обозначает множество действий, которые при параллельно протекающих процессах должны выполняться синхронно.

Точное значение синхронной параллельной композиции по отношению к ходу течения процесса задается следующими правилами:

t1  r1 ^  t2   r2

^ ispar(p, p1, p2, Ø) => t1 ||s t2   r1 || r2,

t1  skip

^ t2  skip ^ ispar(p, p1, p2, Ø) => t1 ||s t2   skip.

Эти правила являются обобщением уже рассматривавшихся правил для несинхронизируемой параллельной композиции. Здесь имеет место то, что какой-либо процесс есть ход работы агента t1 ||s t2, если он возникает через параллельную композицию ходов работы t1  и t2, причем в параллельной композиции этих процессов события, помеченные действиями из S, являются общими событиями. По этому определению существуют агенты, которые отличны от skip, но тем не менее являются терминальными и тем самым не могут выполнять какого-либо процесса, кроме пустого (такие агенты находятся в тупике).

Пример (тупик). Агент а ; b ||(a, b)  b ; a находится в тупике, поскольку он не может выполнять ни действия а, ни действия b.

Наряду с синхронизацией процессов относительно определенных действий над общими событиями имеет место координация параллельно выполняющихся агентов о «взаимных исключениях».


Определенные последовательности действий одного агента должны выполняться без того, чтобы параллельно происходили определенные действия другого агента, например, для избежания конфликтов между действиями. С помощью синхронной параллельной композиции t1 ||s t2, порождается процесс, который (при отсутствии возникновения тупиков) содержит определенные линеаризации ходов работы t1  и t2,  как частичных процессов. Возникают дальнейшие причинные отношения между событиями в обоих частичных процессах - это следует ввести для обеспечения взаимных исключений.

Пример (взаимное исключение через пару синхронизируемых действий). Пусть даны следующие три агента:

t1 = х1 :: а1 ; p; b1; v; х1

t2 = х2 :: а2 ; р; b2; v; х2

k = y :: p; v; y.

Предположим, что действия b1 и b2 могут конфликтовать между собой и поэтов не должны выполняться параллельно. Для агента t1 || t2 возможен ход работы, заданный с помощью следующего графа действий:

а1 -> р -> b1

-> v -> а1 -> р -> b1 -> v -> ...

а2 -> р -> b2

-> v -> а2 -> р -> b2 -> v -> ...

Этот процесс содержит пару параллельных событий, которые помечены конфликтующими действиями b1 и b2. В агенте

(t1 || t2) || {v; p}k такой ход работы исключается. Каждое выполнение действий р и v агента k совпадает с одними из действий р и v или агента t1, или агента t2, но что р и v - действия в процессах t1 и t2 не помечают каких-либо общих событий.

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

и t2. В агентах t1 и t2 заменим действие а на терм агентов Р ; a; v, причем пусть р и v - до сих пор не встречавшиеся действия в t1 и t2 . Агент с :: р; v; с  в каждом ходе работы агента по мере надобности вынуждает один из обоих агентов ti' или ti ждать с выполнением р; а; v-до тех пор, пока агент с::р; v; с снова будет готов для события, помеченного действием р.


События с действием а в t1'  или t2'  в ходах работы, описанных с помощью агента

(t1' || t2' ) || (p; v)    с :: р; v; с, полностью линейно упорядочены. При таком способе действий для обеспечения взаимных исключений возникают агенты, которые обнаруживают дополнительные возможные тупики - в случае, когда в агенте t1 или t2 в параллельных композициях действие а должно выполняться синхронно.

Лемма (взаимное исключение). Для любого агента t, в котором действие а всегда встречается в виде р; а; v и иначе действия р и v не встречаются, справедливо, что каждый из процессов, порождаемых агентом не содержит никакой пары параллельных событий, помеченных действием а.

Доказательство. Пусть р' - процесс, порождаемый агентом t'. События, которые помечены действиями р или v, образуют последовательный подпроцесс, в котором р и v чередуются. Каждому событию е, помеченному через а, может быть однозначным образом предписано натуральное число событий, которые являются причиной для е и которые помечены через v, соответственно через р. Каждому событию е, помеченное через а, можно однозначно предписать помеченное через р событие еrp(е), которое является причиной для е, а также помеченное через v событие еry(е), для которого е является причиной.

Схема для рекурсивного объявления функции

Рекурсивному объявлению fct f = (m1x1, …, mkxk) n: E соответствует схема (формуляр) вычислений, что можно разъяснить на примере.

Пример (формуляр для рекурсивно объявленной функции факториала).

fct fас = (nat x) nat:

else if x=0 then 1

x * fac(x - 1) fi

В вычислениях с помощью формуляров для каждого рекурсивного вызова (каждого развертывания рекурсии) прикладывается новый аналогичный формуляр. Управление с помощью формуляра может происходить по принципу штабеля: как только должен вычисляться рекурсивный вызов функции, на вершину штабеля кладется новый элемент формуляра, по которомy и продолжаются вычисления. Начальные, но еще не полностью выполненные, формуляры при этом оказываются в штабеле ниже. Как только формуляр, который соответствует рекурсивному вызову, будет полностью выполнен (т.е. искомое значение функции будет зарегистрировано) вычисление вызова переносится в предыдущий формуляр, а данный формуляр убирается со штабеля. Тогда можно продолжить вычисление по формуляру, который находится на верху штабеля. Так вычисления продолжаются до тех пор, пока не будут выполнены все формуляры.

Управление выполнением формуляров по принципу штабеля является типичным для обработки на машине рекурсивно объявленных функций. Этот способ обработки в связи с машинной реализацией рекурсий связывается с термином "стек" (аналог штабеля).

Синтаксис выражений и примитивных вычислительных структур

Теперь вводится формальный и язык выражений (англ. expression)

в программах. Язык выражения it БНФ-нотации описывается следующим образом:

<выражение> ::= <id>||<указатель_функции>|

<условное_выражение>| (<выражение>)|

<одноместная_операция><выражение>|

<выражение><двуместная_операция><выражение>|

<секция>

<одноместная_операция>::= -|

<двуместная_операиция>::=+| -| *| /|<| <=| = | >|>= | ^| v| ==>| <==|<==>|

Таким образом, выражение - это идентификатор (id), указатель функции. условное выражение или выражение в инфиксной или префиксной форме записи. Синтаксическая единица <секция> служит для введения локальных объявлений.

БНФ-правила описывают синтаксическую структуру выражений. Помимо этого требуется, еще ряд дальнейших синтаксических условий (контекстных условий). В дальнейшем, кроме всего прочего, будет предполагаться, что каждому выражению рассматриваемого ЯП предписывается точно один тип значений (в общем случае в зависимости от типов, предписанных используемым идентификаторам). Эти типы характеризуют множество элементов, рассматриваемых в качестве значений выражений. ЯП с этим свойством называются также сильно типизированными языками. Благодаря сильной типизации может быть механически обнаружен ряд ошибок программиста, приводящих к выражениям, которым невозможно приписать какой-либо определенный тип значений. Кроме того, типизация поддерживает более сильную структурированность программ. Условия типизации являются примерами контекстных условий.

 

Сложение чисел линейно (длине входного слова), ленточно-ограниченно

Примем следующее упрощающее предположение: для функции ленточной сложности S(n) всегда имеет место

(n)?log(n),где log(n)={[log2(n)]+1  при n?1

                                       { 1                 при n=0

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

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

Мы говорим, что функция g, характеризующая сложность задачи, имеет порядок роста O(f(n)), если справедливо высказывание

$ с, d Î N/{0}, nо Î N: " n Î N, n ³ no: d * f(n) £ g(n) £ с * f(n).

Тогда функция g с точностью до постоянного множителя имеет асимптотически тот же рост, что и функция f. В частности, говорят о логарифмически-, линейно-, квадратично-, полиномиально- и экспоненциально-, ограниченном росте g, если функция g асимптотически растет соответствующим образом.

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

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

Концепцию временной и ленточной ограниченности можно обобщить и на недетерминированные Т-машины. Так, недетерминированная Т-машина называется недетерминированной Т неограниченной по времени, если эта оценка имеет место для каждого слова w при его недетерминированной обработке (т. е. для каждого слова w, Ц = n, существует допускающая его ветвь вычисления, по времени не превосходящего Т(n)). Аналогично определяется и недетерминированная S(n) ленточная ограниченность.

Состояние Левое слово Знак Правое слово

 Конфигурация TM:                 si             w1                  a                 w2

Регистры машины М имеют следующее содержимое:

1.      Регистр: <а> о w как зеркально отраженное двоичное число. (½= L,¾  = 0)

2.      Регистр: W1 как двоичное число.

3.      Регистр: i для состояния si.

Последующие регистры могут использоваться для запоминания переходов состояний. Это требует кодирования входных знаков и состояний числами.

Программа R-машины имеет следующую структуру, причем без oгpaничения общности считается, что sw есть единственное заключительное состояние Т-машины:

While3 (вычислим новое состояние и изменения ленты).

При выбранном представлении конфигураций Т-машины через  содержимое   регистров чтение знака под головкой Т-машины соответствует выяснению четности или нечетности содержимого первого регистра, а запись соответствует операции целочисленного деления на два с дальнейшим действием +1, если должен записываться знак L, +0 - в противном случае.

Сдвигу головки вправо соответствуют следующие операции:

·         содержимое второго регистра умножить на два; записать знак L путем прибавления единицы ко второму регистру, если содержимое первого регистра нечетно;

·         содержимое первого регистра разделить на два.

Сдвигу головки влево соответствуют следующие операции:

·         содержимое первого регистра умножить на два; записать знак L путем прибавления единицы к первому регистру, если содержимое второго регистра нечетно;

·         содержимое второго регистра разделить на два.

Теорема. Любая частично рекурсивная функция RM-вычислима.

Идея доказательства. Принципы, по которым строятся частично рекурсивные функции, могут быть смоделированы на R-машинах.

Теорема. Любая RM-вычислимая функция частично рекурсивна.

Идея доказательства. Отношение следования на регистровых машинах оказывается примитивной рекурсией.

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

Тезис Чёрча

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

Уже в 1936 г. А. Чёрч сформулировал это обстоятельство в своем знаменитом тезисе Чёрча:

«Любая интуитивно вычислимая функция является частично рекурсивной».

Обратим внимание, что тезис Чёрча математически недоказуем,ноего можно опровергнуть. Поскольку определение «интуитивно вычислимая» в тезисе Чёрча используется неформально, невозможно провести никакого формального доказательства. До сих пор не опровергнутый и общепринятый тезис гласит:

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

Было предложено несколько  определений понятия алгоритма:

(а) m-рекурсивность (частичные рекурсивные функции, Чёрч, 1936 г.),

(Ь) общерекурсивные функции (исчисление равенств

Гёделя - Хербранда - Клини, 1936; Клини, 1952; Мендельсон, 1964),

(с) -исчисление (Чёрч, 1936),

(d) машины Тьюринга (Тьюринг, 1936),

(е) система подстановок Поста (Пост, 1943),

(f)        алгоритмы Маркова (Марков, 1951),

(g)        регистровые машины (Шепердсон - Штургис, 1963).

Все эти формализации понятия алгоритма ведут к тому же самому понятию вычислимости.

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

Структуры ОС

Этот раздел дает краткий заключительный обзор структурирования ОС.

Структурирование ОС

ОС - это большие и сложные программные структуры, и рекомендуются тщательно структурированное их построение. Для этого обычно ОС разделяется на слои. Самые нижние два слоя часто обозначаются как ядро ОС, которое охватывается одной программой. Имеется много разных ОС. Это многообразие обусловлено различными областями применений, режимами работ и вычислительными машинами. Отсюда запросы потребителей и коммерческие аспекты определяют выбор используемых на практике ОС.

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

Процессно-ориентированные структуры ОС

Кажется, проще всего программировать выдачу запросов к ОС в виде вызовов процедур. Однако это означает, что заказчик непосредственно ждет окончания выполнения запроса. Если же заказчик не должен ждать, а в это время мог бы выполнять какие-либо другие работы, то вызов процедуры должен быть разбит на два акта коммуникации:

1.

выдачу запроса (включая передачу параметров),

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

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

Такой процессно-ориентированный взгляд на ОС полезен также при моделировании консоли оператора.
Эта консоль служит в качестве устройства ввода/вывода и с точки зрения системного программирования может трактоваться как самостоятельный процесс. Однако ввод с консоли, конечно, имеет совсем особое значение. Эти вводы в процессе работы системы воспринимаются как управляющие воздействия и решающим образом влияют на поведение системы. Такими воздействиями оператора являются:

·         нажатие кнопки стоп,

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

·         досрочное прекращение определенной части запроса,

·         замена запоминающих сред (диски, ленты),

·         управление пользователями,

·         изменение состояния системы,

·         изменение системных данных (например, приоритетов).

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

В заключение суммируем: ОС служит следующим целям эксплуатации, которые отчасти противоречат друг другу:

·         удобство для пользователей (простая, ясная структура системы), приспособляемость к требованиям использования;

·         эффективность, высокая пропускная способность, краткость времен ожидания и пребывания в системе, хорошая загрузка устройств;

·         защита данных и их сохранность;

·         надежность;

·         переносимость.

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

Связывание (свободных) идентификаторов: абстракция функций

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

Пример (описание функций с помощью выражений с идентификаторами). Под выражением  х * (х + 1) в математике часто понимается такая функция, которая заданное натуральное число отображает в то натуральное число, которое соответствует значению выражения при замене х на заданное число. При этом нет никакой разницы между интерпретациями термов х * (х + 1) и у * (у + 1). Но если х и у являются различными свободными идентификаторами, то интерпретация обоих выражений при заданной подстановке будет, вообще говоря, различна и тем самым выражения не будут семантически эквивалентными. Если выражения должны использоваться для представления функции, которая натуральному числу n

 N ставит в соответствие число п * (п + I), то использование идентификаторов n, х или у не должно иметь каких-либо различий.

Чтобы устранить нежелательную разницу между выражениями из-за "случайного" выбора конкретных идентификаторов, используемых в качестве держателей мест, и чтобы достичь абстрактного вида, в математике часто предпринимается введение обозначения функций; так, функцию (1) f: N

 N можно определить через (2) f(x) = х * (х + 1) для всех х  N, что,

конечно, полностью равнозначно (3) f(y) = у * (у + 1) для всех у  N.

Это может быть выражено через явное задание квантора всеобщности:

, (4) nat х: f(x) = х * (х + 1).

Тем самым описание функции делается независимым от выбора конкретного идентификатора х пли у, правда, ценой введения идентификатора f для описываемой функции.

В ЯП используется более последовательная нотация вида fet f= (nat x) nat: х * (х + 1), которая объединяет в себе и задание области (1), и определяющее функцию равенство (4). Кроме того, благодаря этому делается ясным, что идентификатор х используется исключительно в качестве держателя мес­та для свободно выбираемого фактического аргумента. При таком способе записи можно полностью проигнорировать введение обозначения f для функции благодаря использованию (в ЯП) записи (nat х) nat: х * (х + 1) как нотационного представления соответствующего отображения. При этом х в функциональном выражении называют уже не свободным,

а связанным, так как х синтаксически (через nat х) выделяется' как держатель места (формальный параметр). Поэтому х в подстановке теперь уже нс может заменяться на заданное выражение Е. В частности, связанные идентификаторы могут систематически заменяться на любые другие идентификаторы без изменения интерпретации (значения) функционального выражения, пока не возникает конфликта .со свободным вхождением встречающихся обозначений в рассматриваемое выражение. Это переименование связанных обозначений называется -конверсией.

Пусть Е - выражение типа s. Запись

(s1x1,…, snxn) s: Е

называется абстракцией функции, причем x1,…, xn называются формальными параметрами.

Последовательность символов (s1x1,…, snxn)s называется заголовком абстракции функции; она, в частности, задает тип абстракции функции. Тем самым специфицируется, что указанная выше абстракция функции представляет собой функцию вида

М1 * ... * МnМ,

причем Мi обозначают носители типа si,. Выражение Е называется телом (англ. body) абстракции функции.

Для каждой заданной конкретизации  вышеприведенная абстракция функции определяет функцию



f: Mi * ... * Мn М,

где М, - структуры данных типа si.

В БНФ- нотации получается следующий синтаксис для функций:

<функция>::=<id>| (<абстракция_функции>)

<абстракция_функции>::= (<тип><id> {,<тип><id>} * )<тип>: <выражение>

В классической математической нотации абстракция функции иногда используется в связи с применением функции:

((s1x1, ..., snxn) s: Е) (e1, .... Еn)

где Еi - выражения типа si.

Интерпретация выражения синтаксической единицы <функция> всегда дает отображение. Если f - идентификатор, то отображение, соответствующее идентификатору, определяется конкретизацией, т.е. справедливо

I [f] =  (f).

Абстракции функций представляют отображения, а не какие-либо простые математические элементы. Вообще не существует никакой СПТ, которая переводилa бы абстракцию функции в однозначную нормальную форму, т. е. чтобы семантически эквивалентные функциональные выражения имели ту же самую нормальную форму. Однако можно указать правила замены термов для вычисления абстракции функции в связи с вызовом функции. Так как при этом вычисляется не само функциональное выражение, а только вызов функции, указываются только правила вычисления для применения функции с вычисленными значениями параметров (вызов значением, "call-by-value").

Если все аргументы еi терминированы, то применение функции в связи с абстракцией функции может быть вычислено по следующим правилам замены термов:

((s1x1, ..., snxn) s: Е) (e1, ..., Еn) E[E1/x1, .... Еn/xn]

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

f(a1, ...,an) =I1[E],



где 1 пусть определено, как выше. Конечно, при этом  может быть внесено в конкретизацию. Функции могут быть нестрогими.

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

Абстракция функции представляет собой предписание для вычислений (блок-схему): для каждого набора параметров с помощью абстракции функции предписывается определенная схема вычислений. Если типы параметров и результата функции не должны определяться очень жестко или они устанавливаются по-разному, то для абстракции функции часто пишут без задания типа х: Е и тогда говорят о -абстракции.

В связи с абстракциями функции появляются некоторые (вопросы, такие, как связывание и подстановки

идентификаторов. Как уже неоднократно отмечалось, конкретный выбор идентификатора х в абстракции вида х: Е пли ((m x) n: Е несуществен. Можно х заменить на любой другой идентификатор у, в предположении, что у сам не входит свободно в Е ("нe имеется конфликтов в обозначениях"). Тогда (m y) n: Е[y/x] семантически эквивалентно с вышеприведенным выражением. Систематическое переименование формальных параметров в -исчислении называют также -редукцией.

Чтобы гарантировать такую равнозначность абстракции функции, возникающей при переименовании, с исходной, х и Е в абстракции функции (m х) n: Е не должен свободно заменяться на любые выражения. В противном случае его замещение выражением, которое должно бы быть семантически эквивалентным ио правилу -редукции, приводило бы к различным результатам.


В частности, х не должен быть заменяемым в (m x) n: Е. Такое вхождение идентификатора х называется (аналог ситуации с кванторами) связанным вхождением.

Для большей ясности определим более точно, когда идентификатор х в выражение Е входит свободно: идентификатор х наверняка является свободным it выражении Е, ecли имеет место следующее:

·

Е состоит точно из идентификатора х;

·         Е состоит из одною указателя функции f(e1, .... Eт) и х входит свободно по крайней мере в одно из выражений e1, .... Eт

или в функциональное выражение для F;

·         Е есть абстракция функции вида(s1x1, ..snxn) sn+1: Е' и х входит свободно в Е'

и отличается от идентификаторов х; для 1 <=

i <= n;

·         Е имеет вид

if С then E else E'fi

и х входит свободно в С, Е или Е'.

Если х отлично от у и х не является свободным в ЕО, то справедливо

((m х) n:

Е)[ЕО/у] = (m х) n: (Е[ЕО/у]).

Справедливость условия "х не является свободным в ЕО" всегда может быть обеспечена посредством -редукции, т.е. через переименование формальных параметров. Аналогично обстоит дело для многоместных функций.

В абстракции функции (s1x1, ..snxn) sn+1: Е создаются связывания для формальных параметров относительно их вхождения в тело Е. Связывание для идентификатора относится всегда к области связанности или, точнее, к каждому свободному вхождению соответствующего идентификатора в область связанности. Для приведенной выше абстракции функции областью связанности для идентификатора х; является выражение Е.

Связывания существуют для всего выражения Е. Тем самым Е соответствует так называемая длительность жизни связывания. Однако при некоторых обстоятельствах связывание имеет место не для всей длительности жизни, т.е. не для всего выражения Е. Связывание может быть вложенным посредством обновленного связывания в Е.

Пример (вложенное связывание). В выражении

(*) (nat х) nat: (((nat х) nat: х * х) (х + 1))

связывание х во внутренней абстракции функции вложено. Выражение (*) равносильно выражению (после переименования х во внутренней области связанности)

(nat х) nat: (((nat у) nat: у * у) (х + 1)).

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

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

(nat х, nat у) nat: if х < у then у else х fi

описывает функцию выбора наибольшего из двух натуральных чисел.

Вычисление полинома (по схеме Горнера) при заданных коэффициентах а0, ..., an

описывается через

(nat х) nat: (...(an * х + an-1) * х + ... + a1) * х + а0.

Формальные параметры являются держателями мест для исходных данных, которые необходимы для выполнения вычислений.

Толкование через наименьшую неподвижную точку

Наряду с индуктивным толкованием рекурсивное объявление функции

fct f = (m x) n: E

можно истолковывать через решение функционального уравнения

(*)   f=

[f],

где

 было определено выше, т.е. ищут отображение

f: М

 N

с тем свойством, что для всех х

 М справедливо

f(x) =

[f](х).

Тогда f называют неподвижной точкой

, а (*) - функциональным уравнением,

относящимся к рекурсивному объявлению f. То, что функциональное уравнение всегда обладает решением, будет показано ниже. Для этого понадобятся некоторые теоретические понятия упорядоченности. Функция

f: М

 N

называется монотонной,

если для всех х1, х2

 М имеет место

xl

 x2 => f(xl)  f(х2).

Множество монотонных отображений обозначают через

[М

 N].

Для произвольного функционала

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

f

 g =>[f] [g].

Для монотонного функционала

 на вполне упорядоченном множестве с наименьшим элементом гарантируется существование неподвижной точки, т.е. решения приведенного выше уравнения (*). Отсюда всегда имеется однозначно определенная наименьшая неподвижная точка

.

Теорема (Knaster-Tarski). Если

- монотонное отображение на вполне упорядоченном множестве А с наименьшим элементом, то уравнение x =

 [х] разрешимо и существует однозначно определенная наименьшая неподвижная точка для .

Лемма Zorn'a. Пусть М - частично упорядоченное множество, которое для каждой цепи В

 А содержит также sup В; тогда М обладает максимальным элементом.

Теорема Knaster-Tarski справедлива не только для рекурсивно определенных вычислительных предписаний, но также и для многих других областей информатики и математики.

Теорема (по Клини). Если

 непрерывно, то наименьшая неподвижная точка

f для |

[f] совпадает с супремумом цепочки отображений (fi)iN

f = suр{fi: i

 N},

где

f0(х) =

, fi+1 = [fi], т е. справедливо

fix

 = suр{i[f0]: i N},

причем

i обозначает i-кратную функциональную композицию функционала  с самим собой.

Упорядоченные ориентированные и отсориентированные деревья

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

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

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

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

sort ordtree = ordtree(m root, seq ordtree subtrees).

Число непосредственных поддеревьев соответствует длине последовательности в дереве в приведенном выше представлении типа. Это число называется степенью ветвимости дерева. Считается, что z—максимальная степень ветвимости какого-либо дерева, если оно само и все его поддеревья имеют степень ветвимости не превосходящую z.

Двоичное дерево является частным случаем упорядоченного дерева. Двоичные деревья имеют максимальную степень ветвимости 2. В дальнейшем, если речь идет об ориентированных деревьях, будет употреблено просто «деревья».

Максимальное число вершин в путях по дереву называется высотой дерева. Высота пустого дерева, таким образом, равна нулю, а высота одноэлементного дерева есть 1. Высота hi(b) дерева b  определяется самым длинным путем в дереве. Дерево называется полным, если все его поддеревья имеют одинаковую степень ветвимости и все пути доступа от корня к его листьям имеют одинаковые длины.

Пусть #b есть число вершин в дереве, а m—максимальная степень ветвимости. Для непустого, полного дерева справедливо

hi(b)-1£logmb.

В соответствии с этим в полном дереве число его вершин растет экспоненциально с высотой дерева.

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

Условные выражения

Пусть В - булевское выражение (выражение типа bool) и пусть Е, Е' -любые выражения одного и того же типа s; тогда

if В then E else Е' fi есть условное выражение типа s. Условное выражение по своему смыслу соответствует различению случаев в математике. Если булевское выражение В имеет значение "истина", то значение условного выражения равно значению выражения Е, а если выражение В имеет значение "ложь", то значение условного выражения равно значению выражения Е'. Если В не имеет какого-либо определенного значения, то значение условного выражения нe определено.

Используется следующий синтаксис для условного выражения:

<условное_выражение>::==if <выражение> then <выражение>

{elif <выражение> then <выражение>}* else <выражение> fi

Возможность записывать с помощью elif последовательность условных выражений ("каскад разветвлений") вводится лишь из соображений сокращения записи. Значение и дополнительные условия описываются словесно.

Для условного выражения предполагаются следующие дополнительные условия:

·

условие В есть выражение типа bool,

·         Е и Е' имеют одинаковые типы,

·         идентификаторы, встречающиеся в В, Е и Е', используются с одними и теми же типами.

Выражения Е, Е' называют также ветвями условного выражения.

Условные выражения, в частности, могут быть вложенными - в этом случае говорят о каскаде разветвлении. Обозначение

... elif В then Е else Е' fi используется как сокращение для записи (является в смысле математической и операционной семантики эквивалентным) . else if В then Е else Е' fi fi и допускает более удобный способ записи для каскада разветвлений.

Пример (условные выражения).

if I <= 2 then 1 else 2 fi

if a then true else b fi

if a <= b then a else b fi

if a = b then a elif a < b then b - a else a - b fi

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

В

 В' => if В then Е else Е' fi  if В' then Е else Е' fi

if true then Е else Е' fi  Е

if false then Е else Е' fi  Е'

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

Заметим, что условное выражение в определенной степени соответствует нестрогому

отображению: даже в том случае, когда выражение в одной из ветвей интерпретируется к , значение условного выражения может быть отлично от.

Семантика условных выражений описывается также достаточно точно с помощью следующих равенств:

if true then E else E' fi = E

if false then E else E' fi = E'

if В then E else E' fi = if B then E' else E fi

if  then E else E' fi =

Временная и ленточная сложность задач

Задача допустимости слова языка называется детерминированно-Т(n)-ограниченной (соответственно, недетерминированно-) по времени (S(n)-ленточно-ограниченной), если существует детерминированная (соответственно, недетерминированная) Т-машина, которая решает эту задачу и является соответствующей Т(n)-ограниченной по времени (S(n)-ленточно-ограниченной) машиной.

Рассмотрим следующие классы задач в зависимости от определенных свойств их сложности.

DSPACE (S(n)): детерминированные 8(n)-ленточно-ограниченные задачи,

NSPACE(S(n)): недетерминированные 8(n)-ленточно-ограниченные

задачи,

DTIME(T(n)): детерминированные Т(n)-ограниченные по времени задачи,

NTI^E(T(n)): недетерминированные Т(n)-ограниченные по времени задачи.

Обратимся к некоторым теоремам, которые показывают, что выбранные меры сложности содержательны (информативны), так как они, в частности, нечувствительны к умножению на константу.

Теорема (сжатие лент). Если задача S(n)-ленточно-ограниченна, то для каждой константы с Î R, где с > 0, эта задача с*S(n)-ленточно-ограниченна. Идея доказательства. Для S(n)-ленточно-ограниченной Т-машины ТМо построить Т-машину TM1, которая по мере необходимости представляет r следующих друг за другом знаков на лентах ТМо (слов длины r) одним знаком на лентах TM1.

Следствие. Для всех вещественных чисел с ÎR, с > 0, справедливо

NSPACE(S(n)) = NSPACE(c*S(n)), так же как и

DSPACE(S(n)) - DSPACE(c*S(n)).

Теорема (редукция числа лент). Если задача может быть решена на S(n)-ленточно-ограниченной Т-машине с k лентами, то она может быть решена и на S(n)-ленточно-ограниченной Т-машине с одной лентой.

Идея доказательства. Пусть М есть S(n)-ленточно-ограниченная Т-машина с k лентами. Можно построить Т-машину, которая k лент машины М моделирует на одной ленте. При этом нужный объем памяти не больше чем k*S(n).

Теорема (линейное увеличение скорости). Если задача, решаемая на Т-машине с k лентами M1, является Т(n)-ограниченной по времени, то эта задача для любого вещественного числа с > 0 также решается на с*Т(n)-ограниченной по времени Т-машине с k лентами М2, если k > 1 и

lim T(n)/n=+?

n®? n

Идея доказательства. Покажем, что для любого числа m Î N можно построить Т-машину М2, которая в случае надобности m знаков в M1 сводит к одному знаку и по меньшей мере m шагов вычислений на M1 заменяет постоянным числом шагов вычислений.

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

Сначала М2 анализирует ячейки слева и справа от головки. М2 объединяет в один переход все шаги машины M1, которые могут иметь место, пока не остановится M1 или головка машины M1 пройдет область длины 3*m. Эта область представляется тремя знаками в М2, которые находятся слева, справа от головки и под нею. Благодаря этому объединяются, по крайней мере, m шагов m1. Тем самым М2 моделирует самое большее за 8 шагов вычислений (4 для чтения и 4 для записи) по меньшей мере m шагов M1. Для заданного числа с выберем число m, такое, что с*m > 24.

Каждые Т(n) шагов M1 моделируются с помощью 8*[Т(n)/m] шагов М2; кроме того, М2 должна читать свое входное слово и кодировать его. Это даёт n+[n/m] шагов, так что всего получается меньше чем  n+[n/m]+[8T(n)/m]+9 шагов вычислений (поскольку [х]1 < х+1). Так как справедливо limT(n)/n=? n®?, получаем

" d: $ nd Î N: "n³  2: nd: T(n)/n³d (это значит n £, T(n)/d).

Таким образом, для n³2 и n³nd  всегда справедливо n+[n/m]+[8T(n)/m]+9=T(n)[n/T(n)+n/T(n)m+8/m+9/T(n)]£T(n)[1/d+1/md+8/m+9/nd]£ T(n)[8/m+8/d+1/md]

Число d может быть выбрано произвольно. Если мы возьмем d=m+1/8,то имеет место

8/m+8/d+1/md£c.

Это получается из следующего вспомогательного вычисления:

8/m+8/(m+1/8)+1/(mÙ2+1m/8)£24/m£c

Итак, число шагов М^ ограничено числом с*Т(п).

Следствие.

Если LimT(n)/n=?  ,  n>? и c> 0, то справедливо:

DTIME(T(n)) = DTIME(cT(n)) и



NTIME(T(n)) === NTIME(cT(n)).

Предыдущая теорема показывает, что для вопроса о сложности прежде всего интересен порядок функции Т(n).

Важным вопросом является взаимосвязь между DTIME и NTIME, а также между DSPACE и NSPACE. Для ленточной сложности ответ дает теорема Савича (Sawitch). Для формулирования этой теоремы понадобится следующее определение. Функция

S: N > N называется вполне ленточно-конструируемой (конструируемой по памяти), если существует S(n)-ленточно-ограниченная Т-машина, для которой справедливо: для всех чисел nÎ N существует входное слово длины n, для которого Т-машине действительно требуется S(n) ячеек памяти. Аналогично определяется и вполне временно конструируемая функция (конструируемая по времени).

Теорема (по Савичу). Каждая проблема распознавания из NSPACE (S(n)) принадлежит также DSPACE (S(n)2), если S является вполне ленточно-конструируемой и "n Î N: S(n)³ Log(n).

Доказательство. Пусть М1 есть S(n)-лeнтoчнo-oгpaничeннaя Т-машина. Существует константа с Î N, такая, что для всех чисел n Î N справедливо высказывание: Т-машина останавливается самое большее через с^ (при ^=S(n)) шагов, так что существует самое большее с^) конфигураций для входного слова длины n.

Вычисление недетерминированной Т-машины есть трасса (ветвь) в дереве, приведенном на рис. 10.1. При этом для допускаемого слова существует ветвь, на которой нет повторяющихся узлов.

                                            K0

                          å     æ

                                  k1     ….      Kn1

                                        å..æ       å..æ

Временная сложность

Чтобы получить реалистичные и стабильные рассмотрения сложности, рассмотрим Т-машину с k лентами. Для каждой из k лент имеется своя головка чтения/записи. Конфигурация состоит из внутреннего состояния Т-машины и для каждой из ее лент из слова слева от головки, знака под ней и слова справа от головки. На каждом шаге вычислений - в зависимости от внутреннего состояния и знаков под каждой из головок - определенные знаки заносятся в ячейки под головками, определенные головки сдвигаются влево или вправо, а также меняется внутреннее состояние. Рассмотрим Т-машину М с k лентами (каждая из них бесконечна в обе стороны), одна из которых содержит входное слово. Для каждого входного слова w длины n машина делает, если она завершает свою работу, b(w) шагов вычислений. Число b(w) тем самым обозначает длину соответствующей последовательности шагов вычислений. Если для функции Т: N®N для всех слов w длины n = /w/ справедливо b(w) Î Т(n), то машина М называется Т(п)-ограниченной по времени Т- машиной.

Это означает, что вычисление для входа w (а в недетерминированном случае - существует ветвь вычислений, которая) требует самое большее T(/w/) шагов вычислений.

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

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

В задачах анализа формальных языков  L Í V* будем считать, что при представлении слова (последовательности букв входного алфавита) каждая буква хранится в одной ячейке ленты. Для языка L Í V* определим: L имеет сложность Т(п), если задача принятия (допустимости) слова из L имеет сложность Т(п), где n есть длина входного слова.

Пример (сложность языков).

(1) Язык L == {а^ с b^ : Ù Î N}

имеет (n+1)-ограниченную сложность, поскольку существует Т-машина ТМ, которая любое слово w из L с /W/ == n принимает за n + 1 шаг. ТМ хранит принимаемое слово на первой из своих лент, и головка в начале работы указывает на первый (самый левый) знак. Как только под головкой оказывается знак а, машина записывает его на вторую ленту и на обеих лентах сдвигает головки вправо. Появление знака с под головкой первой ленты влечет за собой сдвиг головки по первой ленте вправо, а по второй - влево. Далее эти сдвиги повторяются, пока на первой ленте прочитывается знак b, а на второй - знак а. Если события «на первой ленте не прочитывается знак b» и «на второй ленте не прочитывается знак а» происходят одновременно, то слово принимается.

(2) Сложение двух чисел а, b > 1 (в двоичном представлении) в предположении, что а и Ь заданы на входной ленте с соответствующим разделительным знаком, требует

[ log2(b+a)]+ l+2*([log2(b)]+1)+2

Запись [log2(b)] для вещественного числа г обозначает наименьшее целое число n, такое, что r < n) шагов вычислений, если мы предположим, что к началу работы головка стоит на позиции единиц числа b. Действительно, сначала нужно [log2(b)]+l шагов для копирования числа b на вторую ленту; затем мы проходим шаг за шагом по числам и производим поразрядные сложения, обеспечивая переносы через состояния. Таким образом, временная сложность операции сложения линейна относительно длин складываемых чисел в их двоичном представлении.

Часто принимается следующее упрощающее предположение: для функций временной сложности всегда имеет место Т(n) ³ n+1.

Этo говорит о том, что мы будем рассматривать только такие машины, вторые всегда просматривают все входное слово до того, как они останавливаются.

---

---