Об автоматной модели преследования тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Волков, Николай Юрьевич

• Волков, Николай Юрьевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Волков, Николай Юрьевич

1. Введение

1.1. История вопроса.

1.2. Краткое содержание работы.

1.2.1. Постановка задачи.

1.2.2. Основные результаты.

1.2.3. Структура диссертации.

2. Основные определения и вспомогательные понятия

2.1. Формальная постановка задачи.

2.1.1. Лабиринты, в которых происходит преследование

2.1.2. Взаимодействие автоматов

2.1.3. Рассматриваемые проблемы.

2.2. Вспомогательные понятия.

2.2.1. Вспомогательные определения.

2.2.2. Композиции автоматов

2.2.3. Построение вспомогательных автоматов.

3. Преследование независимой системой хищников жертв

3.1. Траектории автомата в исследуемых лабиринтах.

3.2. Невозможность поимки жертв независимой системой хищников на плоскости.

4. Преследование коллективом хищников жертв в бесконечных лабиринтах

4.1. Поимка автоматов-жертв с периодическим поведением

4.1.1. Леммы о перемещении автоматов.

4.1.2. Вычисление коллективом автоматов арифметических функций от параметров, заданных расстановкой автоматов

4.1.3. Доказательство возможности поимки жертв с периодическим поведением

4.2. Поимка автоматов-жертв с непериодическим поведением

4.2.1. Леммы о перемещении автоматов в квадранте

4.2.2. Вычисление коллективом автоматов еще ряда арифметических функций от параметров, заданных расстановкой автоматов.

4.2.3. Вычисление параметров жертвы по ее коду

4.2.4. Доказательство возможности поимки непериодических жертв в квадранте.

4.3. Доказательство основной теоремы.

5. Преследование коллективом хищников жертв внутри квадрата

5.1. Поимка данной системы автоматов-жертв.

5.2. Построение автоматов-жертв, убегающих от данного коллектива хищников.

5.3. Доказательство теоремы о преследовании внутри квадрата

Введение диссертации (часть автореферата) на тему «Об автоматной модели преследования»

1.1. История вопроса

Автоматный подход к решению задачи преследования впервые был применен в 1987 г. В. И. Грунской в работе [5]. В этой работе рассматривается взаимодействие двух конечных автоматов W и Z («хищника» и «жертвы») в шахматных лабиринтах, имеющих вид квадрата со стороной I. Две клетки такого лабиринта считаются соседними, если они имеют общую сторону. Каждый из автоматов W и Z способен обозревать клетки, соседние той, в которой он находится (все такие клетки, вместе с клеткой в которой на-ходрттся сам этот автомат, образуют его зону обзора). В зависимости от состояния своей зоны обзора (т.е. от наличия и расположения в зоне обзора клеток границы квадрата и от наличия и расположения в зоне обзора автомата-противника), хищник и жертва могут перемещаться за один такт в одну из соседних клеток, либо стоять на месте. Хищник и жертва делают ходы поочередно. Считается, что хищник поймал жертву, если ohpi оказались в соседних клетках.

При фиксированном произвольном размере I стороны квадрата, в котором происходит преследование, изучаются два вопроса.

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

2. Существует ли универсальный автомат-хищник W, ловящий любую жертву Z в данном лабиринте при при произвольных начальных расположениях W и Z?

На эти вопросы в работе [5] получены следующие ответы. Установлено, что для любых l,n е N существует W с числом состояний 0(п • Z2), который ловит за время 0(п ■ 14) любой автомат-жертву Z с числом состояний не большим п, в квадрате со стороной, не большей при любом начальном расположении W и Z. Установлено, что не существует автомата W, ловящего любой Z в произвольном квадрате с фиксированной длиной стороны 1,1 >8.