Дипломная работа на тему «Преследование жертв автоматов-жертв автоматом-хищником с красками» по направлению 010500 - «Прикладная математика и информатика» (стр. 1 )

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

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

Ситаблаев Энвер Диляверович

ДИПЛОМНАЯ РАБОТА

на тему «Преследование жертв автоматов-жертв автоматом-хищником с красками»

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

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

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

Ташкент 2012 Аннотация Изучается процесс преследования автоматами с красками («хищников») независимых друг от друга автоматов («жертв») на плоскости, а так же задача преследования одним автоматом-хищником с краской одного автомата-жертвы, без красок на одномерной ленте. Показано преимущество автоматов с красками над коллективами автоматов. В частности, ряд задач по поимке жертв на плоскости, которые в работах и были решены коллективами из трех автоматов-хищников, в данной работе решаются одним автоматом-хищником с  красками. Показана возможность поимки одним автоматом-хищником с одной краской любой жертвы с несамопересекающейся траекторией, оставляющей след. Доказана лемма о существовании физически реализуемой траектории, которая не может быть реализована автоматам с краской на полосе.

Содержание

Введение Основные понятия и результаты Доказательство вспомогательных лемм Доказательство основных результатов Список использованной литературы

Введение

Рассматривается автоматный аналог ситуации преследования хищниками жертв. Исследуется вопрос преследования одним автоматом хищником с краской независимых систем автоматов-жертв. Будем считать, что жертвы способны “видеть” хищника в некоторой своей окрестности, но “не видят” других жертв. Таким образом, жертвы образуют независимую систему.

в работе [2] показано, что для обхода плоскости нужно три автомата без красок, двое из которых – камни, т. е. не могут двигаться самостоятельно. Так же описаны малые коллективы автоматов без красок, которые обходят лабиринты разного типа. В данной работе построены автоматы с одной краской и одним состоянием, обходящие все рассмотренные в работе [2] лабиринты.

  в работе [3] введен класс автоматов-жертв. Доказано, что поимка на плоскости всех жертв из этого класса может быть осуществлена коллективом из трех автоматов-хищников, но может быть осуществлена меньшим числом хищников без красок. В данной работе построен автомат–хищник с одной краской, ловящий на плоскости всех автоматов-жертв из класса.

  Аналогично, в работе [2] показано, что один автомат-хищник без краски не способен осуществлять поимку заданного автомата-жертвы на плоскости. Для решения этой задачи в [2] используется коллектив из трех автоматов-хищников. В данной работе подобная задача решена при помощи одного хищника с краской, в предположении, что жертва, которую необходимо поймать, оставляет на плоскости след раз в несколько тактов. Построен автомат–хищник с одной краской, ловящий на плоскости фиксированный автомат-жертву, оставляющий такие следы.

  В данной работе также построен автомат-хищник с одной краской, ловящий на плоскости любых автоматов-жертв, оставляющих след, с несамопересекающимися траекториями. 

Основные понятия и результаты.

Будем использовать стандартные обозначения для множеств натуральных и целых чисел N и Z, соответственно. Положим N0 = N U{0}.Множество клеток, на которые плоскость разбивается целочисленной решеткой, обозначим через Z2, сопоставляя каждой клетке координаты ее нижнего левого угла. Назовем r-окрестностью клетки (x0,y0) множество D(x0,y0),r = { (x, y) є Z2 | (|x-x0|+|y-y0| ≤ r)}, где r є N0. Будем считать, что задана определенная нумерация клеток множества D(x0,y0),r.

Определим следующие лабиринты – подмножества Z2. = Z2, = {(x, y) | x є Z, y є N}, (l) = {(x, y) | 0 < y ≤ l, x, y є Z}, (l) = {(x, y) | 0 < y ≤ l, x, y є N}, = {(x, y) | x, y є N}, (l) = {(x, y) | 0 < y ≤ l, 0 < x ≤ l, x, y є N}.Здесь l є N.

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

       Рассмотрим автоматный аналог ситуации преследования хищниками своих жертв. В качестве пространства преследования будем рассматривать лабиринт L, являющийся одним из лабиринтов , , (l), (l), , (l). Хищник и жертвы представляются в виде автоматов, которые находясь в какой-либо клетке лабиринта, умеют обозревать некоторую её окрестность, и, в зависимости от вида (конфигурации) этой окрестности и своего состояния, способны перемещаться в другую клетку лабиринта. Поведение каждого автомата определяется его начальным расположением в лабиринте, его «физическими параметрами» - обзором и скоростью, а также его внутренней логикой. Определим хищников и жертв более формально.

Под автоматом будем понимать инициальный конечный автомат вида ў=(A, Q,B, ц,ш, q0), где A-входной, B-выходной, Q-внутренний алфавиты автомата ў, ц:QxA→ Q и ш:QxA→B – функции переходов и выходов ў, соответственно, q0єQ – его начальное состояние. Алфавит A определяет возможности ў “видеть” происходящее вокруг, а алфавит B -  его возможности перемещаться. Алфавит Q и функции ц и ш задают внутреннюю логику автомата ў.

Под автоматом с краской будем понимать семерку вида ў с =(A, Q,B, С,ц, ш,q0), где A-входной, B-выходной, Q-внутренний алфавиты автомата ў с, С – множество красок, ц:QxA→ Q и ш:QxA→BxC – функции переходов и выходов ў с, соответственно, q0єQ – его начальное состояние.

Выходной алфавит B, автомата ў с есть множество пар вида (, ), где є, єC.

Рассмотрим автомат ў с, перемещающийся по Z2. Выходным алфавитом ў с является множество B = ,  где параметр VєN называется скоростью автомата ў с.

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

Входной алфавит A зависит от параметра RєN (R≥V), называемого обзором автомата ў с и способа взаимодействия ў с с другими автоматами. Возможны два случая такого взаимодействия:

1) ў с является элементом независимой системы автоматов;

2) ў с является элементом коллектива автоматов.

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