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

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

имени в г. Ташкенте

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

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

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

ВКР рассмотрена и рекомендована к защите Зав. кафедрой «МаТИС» д. ф.-м. н., профессор _________ «___»____________2012год

Научныйруководитель: м. н.с. ______________ «___»_________2012год

Ташкент-2012

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

Содержание Аннотация Введение. Основные определения Постановка задачи и основные результаты Изложение решений. Заключение Перечень используемой литературы

Аннотация

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

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,