«Вычисление коллективом автоматов последовательности целочисленных функций» по направлению 010500 «Прикладная математика и информатика»




Скачать 195.33 Kb.
Дата02.08.2016
Размер195.33 Kb.

Филиал Московского государственного университета


имени М.В. Ломоносова в г.Ташкенте

Сафарян Геворк Ашотович

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

на тему «Вычисление коллективом автоматов последовательности целочисленных функций»



по направлению 010500 - «Прикладная математика и информатика»

ВКР рассмотрена и

рекомендована к защите

Зав. кафедрой «МаТИС»

д.ф.-м.н., профессор

_________Кудрявцев В.Б.

«___»____________2012год



Научныйруководитель:

м.н.с.


______________ ВолковН.Ю.

«___»_________2012год



Ташкент-2012

1. Содержание

  1. Содержание

  2. Аннотация

  3. Введение.

  4. Основные определения

  5. Постановка задачи и основные результаты

  6. Изложение решений.

  7. Заключение

  8. Перечень используемой литературы


Аннотация

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

ft (x)=x+c1+c2t.

3.Введение

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

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

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

Исследование траекторий будем проводить через призму целочисленных функций, которые могут вычислять исследуемые коллективы автоматов. Будем говорить, что коллектив автоматов, находится в а-расстановке (а – целое число), если: последний из них (по номеру) удален от первого автомата наа клеток вправо в случае, если , и на а клеток влево, в случае, если . Будем рассматривать коллективы автоматов, такие, что последний по номеру автомат имеет специальное выделенное состояние qg.Скажем, что коллектив вычисляет последовательность целочисленных функций ft (x) (отображающих каждая Z→Z), если для любого x, стартуя из х-расстановки, коллектив в момент, когда последний автомат в t-й раз окажется в выделенном состоянии qg, будет расположен в ft (x)-расстановке.

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

В данной работе удалось описать класс функций, которые могут вычисляться коллективами из двух автоматов на целочисленной прямой. Это функции вида ft (x)=x+c1+c2*t. Доказано, что такие функции вычислимы коллективами из двух автоматов и никакие другие функции ими не вычислимы.

4. Основные определения

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

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

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

Под автоматом будем понимать инициальный конечный автомат вида , где A— входной, B — выходной, Q— внутренний алфавиты автоматаA, φ: Q × A → Q и ψ: Q × A → B — функции переходов и выходов A, соответственно, Q — его начальное состояние. Алфавит A определяет возможностиA “видеть” происходящее вокруг, а алфавит B — его возможности перемещаться. Алфавит Q и функции φ и ψ задают внутреннюю логику автомата A.

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

Автомат со скоростью V и обзором R будем обозначать как A(R,V). Пусть A(R,V) находится в клетке . Множество называется окрестностью хода A, а множество – зоной обзора A. Рассмотрим коллективавтоматов, где R — обзор, а V— скорость каждого из автоматов коллектива. Положим – размер зоны обзора каждого из автоматов коллектива.

Обозначим внутренний алфавит как , а множество всех пар вида , где – как M. Пусть каждый автомат находится в клетке в состоянии . Для каждого = 1, . . . ,m строку , такую что, , и для любого = 1, . . . ,m,



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

Расположения в автоматов и их состояния однозначно задают все -конфигурации. Множество всех конфигураций при всевозможных расположениях и состояниях автоматов является множеством Aj – входных символов автомата .

В данной работе будет рассматриваться поведение коллектива из двух автоматов (W1, W2) в .Для удобства будем считать, что у рассматриваемых коллективов .

Пусть автомат W1 имеет внутренний алфавит вида . Тогда будем говорить, что коллектив (W1, W2) находится в а-расстановке, если:W2 удален от W1 на а клеток вправо в случае, если , и на а клеток влево, в случае, если .


  1. При , W1 находится в состоянии вида (1,q), а при , W1 находится в состоянии вида (-1,q).

Состоянием покоя автомата A(R,V) назовём то состояние автомата, находясь в котором, при любом входном символе, выходной символ будет .

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



где , ,

где – предпериод, а – период.



5. Постановка задачи и основные результаты

Будем называть целочисленной функцией одноместную функцию f:Z→Z.

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

Будем говорить что коллектив (в данном случае автоматы ).вычисляет последовательность функций если:

1) автомат Wn имеет выделенное состояние qg

2) когда коллектив W1,...Wn стартует из х-расстановки, то последовательность расстояний между Wn и W1 с учетом знака в моменты t1,...tj... есть последовательность f1(x),... fj(x)…, где tj - это момент времени, в который автомат Wnв j-й раз оказался в выделенном состоянии qg.

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

Теорема 1. Существует коллектив из двух автоматов А1(R,V), А2(R,V), который вычисляет последовательность функций вида ft(x)=x+ct,

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

Теорема 3.Коллектив из двух автоматов А1(R,V), А2(R,V) на целочисленной прямой вычисляет последовательность функций только вида ft(x)=x+c1+c2t.
6. Изложение решений

Теорема 1. Существует коллектив из двух автоматов А1(R,V), А2(R,V), который вычисляет последовательность функций вида ft(x)=x+c1+c2t, где c- некоторая задаваемая константа , t - номер функции из задаваемой последовательности функций.

Доказательство.Пусть дана последовательность функций видаf(x)=x+c1+c2t, построим коллектив из двух автоматов вычисляющий последовательность функций данного вида.Множеством состояний автомата будет множество: , где qg-состояние в котором автомат вычисляет функцию, n=c1+c2-1. А множеством состояний автомата будет множество:



Функции переходов и выходов автомата (где — входной, — выходной, — внутренний алфавиты автомата ) не будут зависеть от входного символа , таким образом, имея вид: . Автомат W2 неподвижен.



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

  • – если в зоне обзора нет автомата ,

  • – если находится в клетке левее от ,

  • – если находится в той же клетке, что и ,

  • – если находится в клетке правее от .

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

A

Q1

B

Q2





1







1







1







1



.

.

….

….





1







1







1







1



.

.

.

.





1







1







1







1







1







1







1







1



Табл.1

Легко видеть, что данный автомат все время идет вправо со скоростью 1. При этом видно что автомат проходит с1+с2 клеток в начале и переходит в состояниепосле чего переходит в состояние Период последовательности его внутренних состояний равен c2 (состояния периодически меняются с дои их с2 штук). Таким образом, по данной таблице можно видеть, что автомат зас2тактов передвинулся на с2клеток вправо, следовательно, коллектив перешел из x-расстановки в x+c1+c2-расстановку.

И оказывается, что как можно видеть, этот автомат в t-й раз окажется в состоянии qg в такт tc2, а за каждый шаг смещается ровно на 1 клетку. Т.е. перейдет в (x+ct) расстановку. Таким образом, видим, что построенный коллектив автоматов действительно вычисляет последовательность функций вида ft(x)=x+ct.
Теорема 2.Последовательность выходных сигналов коллектива из двух автоматов на целочисленной прямой, является периодической.

(доказательство данного результата содержится в дипломной работе Улугбека Айтбаева)

Теорема 3. Коллектив из двух автоматов А1(R,V), А2(R,V) на целочисленной прямой вычисляет последовательность функций либо видаft(x)=x+c1+c2t либо вида ft(x)=rj.

Рассмотрим движение автоматовА1(R,V), А2(R,V). По Теореме 2 оно будет периодичным. Обозначим предпериод их движения как Т_0, а период, как Т. Рассмотрим состояния q(T_0+1),...,q(T_0+T), это состояния в которых оказывается автомат за период Т.Возможны два варианта:



  • Если среди них состояние qgне встречается

  • Если среди них состояние qg встречается ровно один раз

  • Если среди них состояние qg встречается несколько раз

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

Разберем случай, когдау автоматаW1 состояние qg встречается ровно один раз.

Пусть qg=q(T0+i), где i - от 1 до T. Обозначим за s1- перемещение, которое проходит автомат W1 за период T и s2- перемещение, которое проходит автомат W2 за период T.

s=s2-s1

,где s– число показывающее, насколько вырастает перемещение за период T.

За х0– обозначим расстояние между автоматами в момент T0-последний момент пред периода.

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



В этом случае в состоянии qg автомат будет оказываться ровно 1 раз за период выходной последовательности. В первый раз - в момент T0+i, затем в T0+T+i, ... в t-й раз он окажется в состоянии qg в момент T0+t*T+i. Следовательно, за каждый период расстояние между автоматами будет меняться на s.

Рассмотрим момент T0. Так как мы определили х0как расстояние между двумя автоматами в момент T0, следовательно автоматы из х-расстановки перешли в х0расстановку.

х0=x+c1. c1- изменение расстояния между автоматами за T0- тактов.

Следовательно,в момент T0в состоянии qgвычислима функция вида f(x)=x+c1 по теореме 1. Автоматы двигаются периодично и за каждый период расстояние меняется на s клеток. Значит автомат W1из x+c1–расстановки в х+с1+s –расстановку за первый период. Логично, что с каждым периодом расстояние между автоматами будет увеличиваться на s клеток.

Следовательно каждый раз когда автомат будет переходить в состояние qgон будет переходить в х+с1+st-расстановку где t- число показывающее какой раз автомат проходит период Т. А по определению «вычисления автоматом функции» следует что автомат вычисляет функцию вида f(x)=x1+st. Таким образом видим, что коллективом автоматов вычислима последовательность функцийft(x)=x1+st=x+c1+c2t.

Разберем случай, когда у автомат W1 состояние qg встречается несколько раз.

Раз у автомата состояние qg встречается несколько раз - это означает, что в этом состоянии за один период автомат оказывается при разных входных символах, т.е. автоматы видятся за период. Допустим что автомат переходит повторно в состояние qgпри одинаковых входных символах. Следовательно его предыдущее состояние будет состоянием что и перед предыдущем переходом в состояние qg, а следовательно существует некоторый период, а так как в периоде не может быть пред периода. =>автомат проходит период второй раз.

А раз они видятся за период, то по теореме 2 о периодичности следует, что s=0т.к. если s>0 или s<0, то автоматы будут все дальше удаляться друг от друга и через много периодов они больше никогда не увидятся. А тут они видятся постоянно, каждый период. Последовательность расстояний между ними в моменты qg - это повторение нескольких одинаковых чисел, т.е. расстояния меняются по циклу.

Раз s=0 отсюда следует, автоматы в начале следующего периода переходят в ту же расстановку что и в начале предыдущего периода, попадая в окрестность,друг друга на разных расстояниях, обозначим эти расстояния как r1,...rk.

Следовательно, автоматы в периоде будут переходить в r1,...rkрасстановки. Так как расстояния между автоматами меняются по циклу следовательно в следующий момент когда автомат перейдет в состояниеqgон переместиться в r1-расстоновку. От сюда следует автомат будет вычислять функции f1(x)=r1, f2(x)=r2,…. fk(x)=rk,… fk+1(x)=r1,…. Следовательно, данным коллективом будет вычислима бесконечная последовательность функций вида ft(x)=rj(константа), гдеr1,...rk это конечный набор константгде, t=jk+i (i - остаток от деления t на k, а j - целое частное)



9. Перечень используемой литературы

  1. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. "Введение в теорию автоматов", Наука, 1985.

  2. Волков Н.Ю. "Об автоматной модели преследования", 2007.


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница