Сборник ответов к экзамену «Теория вычислительных процессов»

• Версия от 12.01.2015 15:25

• Вопросы 1 – 46 из 56

• Отсутствует доказательство свойств редукции к вопросу 11. Поэтому у кого оно есть - неплохо было бы дополнить

Раздел 1. Асинхронные процессы (ап)

1. Понятие дискретной динамической системы.

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

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

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

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

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

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

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

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

2. Дискретное время. Дискретная информация.

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

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

меняться.

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

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

длительного переходного процесса.

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

Пусть t=0, 1, 2, … – начальные моменты времени тактов (единицы измерения для времени не существенны). Ноль соответствует началу работы. Далее при рассмотрении АП будем считать, что процесс, относящийся к такту t – подача входного воздействия, изменение состояния, выдача выходного воздействия –происходит мгновенно в момент времени t.

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

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

алфавита называется словом.

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

Наиболее часто используются дискретные устройства, осуществляющие переработку слов над алфавитом {0, 1}.

3. Понятие асинхронного процесса. Траектория АП. Максимальная траектория.

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

• начальные (инициаторы), они характеризуются тем, что предшествовать инициатору может только инициатор;

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

Формально асинхронный процесс это четверка <S, F, I, R>, где S ={si} (i=, n) - непустое множество ситуаций;

Как правило, I≠ и R ≠ . Если I=R= , то АП называется автономным.

Содержательно инициаторы это ситуации, активизирующие

процесс. Назначение инициаторов делается на основе семантики

процесса. Аналогично результанты это финальные ситуации. Их

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

Отношение F можно изобразить орграфом, вершины которого соответствуют ситуациям асинхронного процесса. Дуга исходит из s_i и входит в s_k, тогда и только тогда, когда s_j F s_k.

Определение. Поведение системы описывается последовательностью ситуаций системы (s1, s2, …, sk) такой, что si F si+1 (i=,k). Такая последовательность называется траекторией.

Любую подпоследовательность траектории, не совпадающую с самой траекторией, будем называть отрезком траектории.

Траектории, которые не являются отрезками никаких других траекторий, называются максимальными.

4. Отношение F. Отношение М.

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

Это отношение транзитивное, поскольку если si M sj и sj M sk, то si M sk.

Отношение sj M sk означает возможность перехода из sj в sk.

В АП возможны случаи sj M sk и sj M sl, k не равно l.

Заметим, что если для некоторого sj существует единственная ситуация, для которой sj M sk, то обязательно sj F sk.

Отношение непосредственного следования F не восстанавливается однозначно по отношению M.

5. Отношение эквивалентности. Классы эквивалентности. Свойства классов эквивалентности.

На множестве S введем бинарное отношение Е следующим образом:

а) если sj M sk и sk M sj, то sj E sk;

б) sj S sj E sj.

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

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

Если множество ситуаций АП разбить на классы эквивалентности e(1), e(2),..., e(р), то между ними естественным образом возникает отношение непосредственного следования F.

Запись e(i) F e(j) означает, что из некоторой ситуации класса e(i) можно попасть непосредственно (т.е. применением отношения F) в какую-либо ситуацию класса e(j).

Определение. Рассмотрим последовательности классов эквивалентности вида: П=(e(1), e(2),..., e(р)).

Последовательность называется допустимой, если e(i) F e(i+1) при i=,p. Допустимая последовательность называется максимальной, если она не является отрезком никакой допустимой последовательности.

6. Эффективный асинхронный процесс.

Определение. Эффективным называется асинхронный процесс <S, F, I, R>, удовлетворяющий следующим условиям:

1) I≠ , R≠ ;

2) каждая ситуация принадлежит некоторой максимальной

траектории;

3) множества ситуаций I и S\(I R) не содержат циклов.

Отсюда следует, что максимальная траектория либо завершается результантом, либо содержит цикл из результантов.

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

содержит циклов, не входящих в множество R.

7. Управляемый асинхронный процесс.

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

В управляемом АП, таким образом, вводится ограничение на степень недетерминизма.