Машина с бесконечными (неограниченными) регистрами (МБР)

⇐ ПредыдущаяСтр 2 из 2

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

r₁

r₂

r_k

R₁

R_k

МБР состоит из 2 частей:

1) регистров R₁…R_k с натуральными числами r₁…r_k, число регистров бесконечно;

2) программы – конечной последовательности команд I₁…I_p четырех типов:

1. Обнуление Z(n): R_n=0.

2. Прибавление единицы S(n): R_n=r_n+1.

3. Переадресация T(m,n): R_n=r_m.

4. Условный переход J(m,n,q): если r_n=r_m, то выполняется I_q, иначе следующая команда.

Машина останавливается, если счетчик команд переходит к несуществующей команде с номером, большим p.

Разберем те же задачи.

Пример 1.

R₁

100

R₁

Решение:

1) S(1)

Пример 2.

1	2	3	0	0
R₁	R₂	R₃	R₄	R₅

0	2	3	1	0
R₁	R₂	R₃	R₄	R₅

Решение:

1) закодируем а, b, c цифрами 1, 2, 3;

2) перенесем первый символ в конец;

3) обнулим первый регистр.

1: T(1,4)

2: Z(1)

Закрепление материала.

Дан входной алфавит Q={1,2,3}, последовательность P из Q.

Вставить символ из этого алфавита между первым и вторым символом посл-ти Р.

Решить задачу на МБР и МТ.

Вопросы с экзамену

Понятие алгоритма

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

Логические схемы алгоритмов. Определение. Правила составления.

Логической схемой алгоритма (ЛСА) - будем называть конечную строку, состоящую из символов операторов А1,А2,…,Аn, логических условий со стрелками α1 ¹,α2 ²,… αm^m и концов стрелок ¯ ¹ , ¯²,…¯^m такую, что для каждого начала стрелки c индексом i найдётся один и только один конец стрелки с тем же индексом.

Правила составления:

1. Определить число логических переменных.

2. Определить количество базовых логических операций и их порядок.

3. Изобразить для каждой логической операции соответствующий ей вентиль.

4. Соединить вентили в порядке выполнения логических операций.

Матричные и граф-схемы алгоритмов. Определение. Правила составления.

Матричной схемой алгоритма (МСА) - будем называть квадратную матрицу, в которой строки соответствуют операторам A₀ , A₁ ,..., A _n, столбцы – операторам A₁, A₂ ,..., A_к , а элементы – логические функции связи между операторами алгоритма.

Граф-схема алгоритма (ГСА) - есть конечный связный ориентированный граф G, удовлетворяющий следующим условиям:

В графе G имеется два отмеченных узла – входной, из которого выходит не более одной стрелки, и выходной, не имеющий ни одной выходящей стрелки.
Из каждого узла, отличного от входного и выходного, исходит либо одна стрелка (γ-узел), либо две стрелки (β-узел). Стрелки β-узла помечены – одна плюсом, другая минусом или одна 0, другая 1.
Имеется два конечных множества функциональных элементов – множество преобразователей информации Q= {A₁ , A₂ ,...,An} и множество распознавателей P ={ p₁ , p₂ ,..., p _m}.
Каждому γ-узлу однозначно сопоставлен преобразователь A i Î Q , а каждому β-узлу – распознаватель a ₁ ( p₁, p₂,… )Î P. В зависимости от алгоритма преобразователи и распознаватели могут повторяться в графе G.

5. Объединение операторных схем алгоритмов. Понятие. Цель и принцип минимизации объединенного алгоритма.

Объединённой ЛСАU₀ будем называть такую ЛСА, для которой выполняются следующие условия:

1. Любой оператор A _k , входящий хотя бы в одну ЛСАU_i (i =1, l), входит ровно один раз в ЛСАU₀.

2. Если в ЛСАU₀ ( r_1, r_2, r _s ; p_1….. p _n)подставить значения , ,... R₁ =r_1, r_2,….r _n =1 , то U₀ »U_t

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

Принцип?

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

Процесс объединения ЛСА удобно вести с помощью представления алгоритмов

на языке МСА. Поэтому предлагается следующий порядок действий:

1. Построить МСА, равносильные объединяемым ЛСА

2. Построить объединённую МСА, каждый элемент которой имеет вид

здесь

jq a – логический элемент матрицы МСАUi, где i – номер строки, а

j – номер столбца в Ui;

j b – определяющая функция оператора j A из ЛСАUi;

jq aˆ – недоопределённый элемент объединённой МСА, так как i

j b – недоопределённая логическая функция.

3. Построить недоопределённые формулы перехода, которые составят не-

доопределённую систему Sˆ1. Доопределить формулы перехода в системе

S2, перейти системе S3.

4. Провести преобразования системы S3 в соответствии с правилами тождественных преобразований.

5. Перейти от преобразованной системы S3 к объединённой ЛСАÎU0.

7. Модели универсальных вычислителей. Конечный автомат. Примеры.

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

1) Конечный автомат

2) Машина Тьюринга

3) Машина с бесконечными (неограниченными) регистрами (МБР)

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

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

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

Пример:

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

у0: — брать ремень;

у1: — ругать сына;

у2: — успокаивать сына;

уЗ: — надеяться;

у4: — радоваться;

у5: — ликовать.

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

Модели универсальных вычислителей. Машина Тьюринга. Примеры решения задач.

Из-за ограниченной внутренней памяти и отсутствия внешней КА может реализовать только узкий класс задач.

Если к модели КА добавить неограниченную внешнюю память, то получим автомат, реализующий любой алгоритм. Такой автомат называется Машиной Тьюринга.

МТ состоит из 2 частей: ленты и конечного автомата. Лента неподвижна, а головка движется относительно ленты под управлением автомата (влево, вправо, стоит на месте).

МТ может выполнять следующие команды:

1) записывать в ячейку ленты новый символ;

2) сдвигаться на одну ячейку влево или вправо;

3) переходить в новое внутреннее состояние.

Больше МТ ничего не может.

МТ задается:

1) набором внутренних состояний Q={q₁…q_n};

2) входным алфавитом S={s₁…s_k);

3) командами движения головки {L,R,N}.

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

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

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

МБР состоит из 2 частей:

1) регистров R₁…R_k с натуральными числами r₁…r_k, число регистров бесконечно;

2) программы – конечной последовательности команд I₁…I_p четырех типов:

1. Обнуление Z(n): R_n=0.

2. Прибавление единицы S(n): R_n=r_n+1.

3. Переадресация T(m,n): R_n=r_m.

4. Условный переход J(m,n,q): если r_n=r_m, то выполняется I_q, иначе следующая команда.

Машина останавливается, если счетчик команд переходит к несуществующей команде с номером, большим p.

Дата добавления: 2022-01-22; просмотров: 88; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!