Модели вычислений


с. 1



МОДЕЛИ ВЫЧИСЛЕНИЙ


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

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

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

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

Ниже рассматриваются 2 модели вычислений в узком смысле:


  • ассоциативные исчисления;

  • рекурсивные функции,

а также 2 модели дискретной переработки информации – автоматы и машины Тьюринга.

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

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

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

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

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



Алфавит — любая конечная совокупность различных символов, называемых буквами. Любая конечная совокупность n букв некоторого алфавита является словом длины n в этом алфавите.

Если, слово L является частью слова М, то говорят, что слово L входит в слово М. Например, в слове abcbcbad имеются два варианта вхождения слова bcb и одно вхождение слова bа.

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

Например, пусть имеется алфавит А = {а, b, с}. Рассмотрим слово abcbcbab; к этому слову можно применить подстановку ab - bcb четырьмя способами. Заменяя вхождение ab дважды, получим: bcbcbcbbcb. В то же время к слову bacb эта подстановка не применима.

Рассмотрим особую подстановку B. Она означает, что из преобразуемого слова удаляется вхождение слова Р (оно заменяется пустым символом), а также, что между двумя какими-либо буквами преобразуемого слова, впереди него либо за ним, вставляется слово Р. Например, заданы слово dbcd и подстановка abc - #. В результате подстановки получаем: dabcbcd

Итак, ассоциативное исчисление (АИ) — это множество всех слов в некотором алфавите вместе с конечной системой допустимых подстановок.



Эквивалентность слов. Два слова называют эквивалентными, если, одно из них можно получить из другого последовательным применением допустимых подстановок.

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

Эквивалентность слов (обозначается L ~ M) обладает всеми свойствами отношения эквивалентности — рефлексивностью, симметричностью и транзитивностью.

Если L ~ М, то при наличии в каком-либо слове R вхождения L в результате подстановки L - М получается слово R', эквивалентное R.

Например, используя эквивалентность acd ~ cad, из слова R = bacdc получаем эквивалентное ему слово R' = bcadc.

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

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

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

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

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

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

2.2. Вычислимые и рекурсивные функции
Арифметическая функция y=(x1, х2, ...,хn) - это целочисленная функция, зависящая от целочисленных значений аргументов, т.е. это функция, построенная на множестве {0, 1, 2, ...}. Под  понимается суперпозиция операций сложения, вычитания, умножения и деления, операций определения абсолютного значения результата при вычитании и целой части - при делении, а также некоторых специальных операций, например

.

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

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


2.3. Модели дискретной обработки информации
2.3.1 Конечные автоматы
Автомат — это математическая абстракция, которая предназначена для описания и анализа поведения разнообразных устройств дискретного действия или протекания процессов дискретной обработки информации, для моделирования и построения устройств и процессов. Такая модель успешно используется как в технике, при проектирование вычислительных машин, систем управления, связи, так и в других областях – теории и практике административного управления, лингвистике (анализ синтаксиса формального языка, расшифровка древних рукописей) и т.д.

Автомат описывается шестёркой элементов A=(Q, X, Y, , , q1),

где Q = {q1, q2,..., qr} - множество состояний (алфавит состояний);

X={x1, x2,..., хn} - множество входных символов (входной алфавит):

Y={y1, y2,…, ym} - множество выходных символов (выходной алфавит);

- функция переходов, реализующая отображение множества D, D  QX, на множество Q (qp = (qj, Xj), qpQ);

 - функция выходов, реализующая отображение множества D, D  QX, на множество Y (yd = (qj, Xj), ydY);

q1 - начальное состояние автомата.

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

Автомат называется конечным, если конечны множества Q, X и Y. Автомат называется полностью определённым, если D=D=QX; у частичного автомата функции  и  определены не для всех пар (qj, xj)QY.

Символами хj и уk, обозначают события в процессе или сигналы в устройствах. Иногда используют понятие "буква" вместо понятия "символ", и, соответственно, словом называют последовательность букв.

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

Дискретным временем t будем называть время, которое принимает лишь эти целочисленные значения. Моменты времени, обозначенные числами 0,1,2,..., называют тактами.

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

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

Понятие "состояние автомата" определяет некоторую предысторию его поведения как реакцию на символы, которые поступали ранее на его входы, т.е. состояние соответствует некоторой памяти о прошлом.

Важным при определении конечных автоматов является то, что во-первых, значение выходной переменной у(р) на р-м такте (p-present-настоящее) однозначно определяется текущим состоянием q(p) и значением входной переменной х(р) на том же такте, т.е. у(р)=(q(р), х(р)). Во-вторых, состояние в следующем, (р+1)-м такте, т.е. q(p+1), однозначно определяется состоянием q(p) и входной переменной х(р) в текущем, р-м такте - q(p+1)=(q(p), х(р)).

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

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

Следует отметить, что в начальный момент t=0 автомат всегда находится в начальном состоянии q(0)=q1. В последующие моменты р, КА в зависимости от входного символа х(р)Х выдает на выходе соответствующий выходной сигнал y(p)=(q(p), x(p)), переходя в состояние q(p+1)=(q(p), х(р)); q(p)Q, y(p)Y.

Автомат без памяти называется тривиальным автоматом, или комбинационной схемой. В таких автоматах значения выходных переменных определяются только комбинацией входных переменных в данный момент; для комбинационных схем функция переходов не имеет смысла, а функция выходов вырождается к виду у(р)=(х(р)).

На практике наибольшее распространение получили автоматы Мили и Мура, приведенные на рис. 2.1,в и г; здесь: F1 и F2 – комбинационные схемы; D – задержка на один такт (память), q' - новое (следующее) состояние в момент t = р.

Закон функционирования автомата Мили задается уравнениями:

q(t+1) = (q(t), x(t)); y(t) = (q(t), x(t)), t = 0, 1, 2, ..., (2.11)

а автомата Мура -

q(t+1) = (q(t), x(t)); y(t) = (q(t)), t = 0, 1, 2, ..., (2.12)

Рис. 2.1. Конечный автомат: а - автоматное время;

б - структура; в - автомат Мили; г - автомат Мура
Особенностями функционирования автоматов Мили и Мура являются:

1) оба автомата одинаково формируют новое состояние (q, x)q', которое затем задерживается на один такт, q(p+1) = q'(p);

2) выходной символ в автомате Мура определяется только состоянием в текущий момент (qу), т.е. y(p)=(q(p)), где q(p)=(q(p-1), x(p-1))), в то время как в автомате Мили — и входным символом и состоянием в текущий момент t=p: y(р) = (q(р), x(р))

3) автомат Мили содержит меньшее число состояний, чем эквивалентный ему автомат Мура .

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

Автомат может быть представлен двумя таблицами для каждой из функций  и  либо совмещённой таблицей, несколько отличающейся для автоматов Мили и Мура.

При табличном представлении строки именуются символами состояний, а столбцы - символами входа; в клетках таблиц проставляются символы состояний, причём состояния записываются рядом через разделитель “/” с соответствующими выходными символами: для автомата Мили – в клетках, а для автомата Мура – в именующем столбце.

Для примера табл. 2.1 описывает поведение автомата Мили, а табл. 2.2 – автомата Мура.

Таблица 2.1 Таблица 2.2


A1

x1

x2

q1

q2/y1

q3/y2

q2

q3/y3



q3

q1/y3

q2/y1




A2

x1

x2

q1/y1

q2

q3

q2/y1

q3

q1

q3/y2

q3

q1



Граф автомата – ориентированный связный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Две вершины графа автомата qi и qj соединяются направленной дугой от qi — исходного состояния к qj — состояние перехода. В случае автомата Мили дуге графа приписывается входной символ xk и выходной символ yg=(qi, хk). При описании автомата Мура в виде графа выходной символ yg=(qi) записывается рядом с вершиной qj (или внутри неё).

На рис. 2.2 и 2.3 приведены заданные ранее табл. 2.1 и 2.2 графы автоматов А1 (частичный автомат Мили) и А2 (автомат Мура; здесь переход q3q3 является петлёй).


Рис. 2.2. Пример графа частичного автомата Мили

Рис. 2.3. Пример графа автомата Мура


2.3.2. Машина Тьюринга, её свойства и особенности
Ранее были отмечены интуитивные требования к алгоритмам: (дискретность, элементарность шагов) детерминированность, массовость и результативность. При этом не важно, как алгоритм реализуется: человеком или машиной. Из отличительных свойств алгоритмов вытекают общие требования к машине, выполняющей алгоритм:

• машина должна быть полностью детерминированной и действовать в соответствии с заданной системой правил;

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

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

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

Машина содержит бесконечную одномерную ленту, которая разделена на ячейки. Считается, что лента бесконечна лишь в одном направлении (вправо), так что существует ячейка, про которую можно сказать, что она нулевая (самая левая). В каждой ячейке может быть записан лишь один символ хi из конечного алфавита Х={x0, x1,..., хn}; символ x0 выделяется специально: если в некоторой ячейке записан символ х0, то эта ячейка "пустая". В дальнейшем будем считать, что непустых символов на ленте каждый раз имеется конечное (но сколь угодно большое) число, остальные ячейки – пустые. Символом # отмечается левый конец ленты.

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

Головка может также по команде uU = {R, L, S} перемещаться на одну позицию вправо (R-Right) или влево (L-Left), если она не находится в самой левой ячейке, либо не перемещаться (S-Stop). Команды на головку подаются от управляющего устройства, которое в свою очередь получает от головки сигнал о наличии того или иного символа в ячейке ленты, расположенной под головкой.

Управляющее устройство (УУ) машины Тьюринга – это конечный автомат, который имеет конечное число состояний (m+1) из множества Q={q0, q1,..., qm) и работает в дискретном времени t = 0,1,2... . Структурная схема УУ как автомата приведена на рис 2.4,б; здесь F1, F2, F3 – комбинационные схемы (преобразователи дискретной информации без памяти); D1, D2 - элементы задержки символа (сигнала) на один такт.

Рис. 2.4. Машина Тьюринга: а - конструкция; б - структура


Нетрудно видеть, что блоки F1, D1, F2 образуют автомат Мили (рис. 2.1,б), который формирует новый символ х, хХ, для записи на ленте, а дополнительные к ним блоки F3, D2 формируют команду uU на перемещение головки.

Рассмотрим функционирование машины Тьюринга.



Входным данным для УУ является символ хi, считываемый головкой с текущей ячейки с номером l.

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

Пусть в момент t головка находилась напротив второй ячейки l, в которой был записан символ хi, а управляющее устройство находилось в состоянии qj. УУ в зависимости от пары символов (qj, xi) выдаёт символ хk, (т.е. головка стирает старый символ хi и записывает новый символ xk), a затем – один из символов перемещения головки R, L, S. После этого УУ переходит в новое состояние qr (также однозначно определяемое парой символов (qj, хi,)). Тем самым в момент t+1 в ячейке l будет записан символ xk, УУ будет находиться в состоянии qr, а головка может находиться справа или слева ячейки l, либо над ней.

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

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

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

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

Далее будем считать, что символ q0 состояния УУ означает состояние покоя МТ, т.е. строка q0 ФС обладает следующими свойствами:

•первым символом в каждой клетке этой строки всегда является q0;

•вторым символом в клетке столбца хi, этой строки является символ хj;

•третьим символом в каждой клетке строки является символ S.

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

В дальнейшем для простоты будем предполагать, что алфавит символов X состоит из двух символов: "пустого" - 0 и "не пусто" -1.



Рассмотрим несколько примеров МТ. Начальным состоянием машины здесь и далее будем считать состояние q1; рассмотренные в этих примерах машины имеют по одному состоянию (не считая состояния покоя).
Таблица 2.4 Таблица 2.5 Таблица 2.6 Таблица 2.7

A

0

1

q1

q01S

q11R




B

0

1

q1

q10L

q00L




C

0

1

q1

q00L

q11L




D

0

1

q1

q’00S

q”01S





Пример 2.4. Машина А (табл. 2.4). Если в начальный момент машина воспринимает заполненную ячейку, то она "отыскивает" на ленте первую пустую (т.е. заполненную символом 0 ячейку) справа от той, под которой находится головка, вписывает туда символ 1 и останавливается. Если вначале головка находится напротив пустой ячейки, то машина её "заполняет" и останавливается, не передвигая головку.

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

Пример 2.6. Машина С (табл. 2.6), отправляясь от заполненной ячейки, идёт влево и останавливается левее группы единиц на две ячейки.

Пример 2.7. Машина D (табл. 2.7), имея два состояния покоя, распознает, напротив какой ячейки находится, - пустой либо заполненной; в зависимости от этого переходит в первое либо второе состояние покоя.

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



Иногда МТ может иметь несколько состояний покоя: q0, q’’0, q’’’0 ....
с. 1

скачать файл

Смотрите также: