Конструирование изображений клеточными автоматами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова»

На правах рукописи

Титова Елена Евгеньевна

Конструирование изображений

клеточными автоматами

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

17 д ег т

005561447

Москва — 2015

005561447

Работа выполнена на кафедре математической теории интеллектуальных систем Механико-математического факультета ФГБОУ ВО «Московский государственный университет имени М.В. Ломоносова». Научный руководитель: Гасанов Эльяр Эльдарович,

доктор физико-математических наук, профессор

Официальные оппоненты:

Ведущая организация:

Чечкин Александр Витальевич

доктор физико-математических наук, профессор кафедры "Математика-1"(ФГБОУ ВО "Финансовый университет при Правительстве Российской Федерации")

Снегова Елена Александровна

кандидат физико-математических наук консультант (ООО "Техкомпания Хуавэй")

ФГБОУ ВО "Московский государственный университет информационных технологий, радиотехники и электроники"

Защита диссертации состоится 9 октября 2015 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84, на базе ФГБОУ ВО МГУ имени М.В. Ломоносова, по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, ФГБОУ ВО МГУ имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08. С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВО МГУ имени М.В. Ломоносова, по адресу: Москва, Ломоносовский проспект, д. 27, сектор А, http://mech.math.msu.Su/~ snark/index.cgi, http://istina.msu.ru/dissertations/9607159/. Автореферат разослан 9 сентября 2015 г.

Ученый секретарь диссертационного совета Д.501.001.84, на базе

ФГБОУ ВО МГУ имени М.В. Ломоносова, доктор физико-математических наук, профессор Иванов Александр Олегович

Общая характеристика работы

Актуальность темы и степень ее разработанности

Клеточный автомат — это математический объект с дискретными пространством и временем. Каждое положение в пространстве представлено отдельной клеткой, а каждый момент времени — дискретным временным шагом или поколением. Состояние каждой пространственной клетки определяется очень простыми правилами взаимодействия. Эти правила предписывают изменения состояния каждой клетки в следующем такте времени в ответ на текущее состояние соседних клеток. При этом для разных клеток правила изменения состояний могут быть разными.

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

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

Впервые идея клеточных автоматов отмечена в работах Дж. фон Неймана в 1940-х годах. Вплоть до конца 60-х идея клеточных автоматов была забыта и лишь в 1970 году Джон Конвей, математик Кембриджского университета, попытался упростить идеи предложенные Нейманом, и в конце концов описал ныне широко известный двумерный клеточный автомат, названный игра ">Kn3iib"("Life"). Описанный выше вариант однородной структуры использовался А. Берксом, Э. Муром1, Майхиллом и другими2. На механико-математическом факультете МГУ имени М. В. Ломоносова исследованием свойств однородных структур занимались В. Б. Кудрявцев3,

^.Ф. Мур, Математические модели самовоспроизведения, Математические проблемы в биологии,

1 !)(j(i, 3U -42

2Дж. фон Нейман, Теория самовоспроизводящихся автоматов, 1971, 384

■'В.Б. Кудрявцев, C.B. Алешин. A.C. Подколзип, Введение в теорию автоматов, 1985, 320

А. С. Подколзин4, А. А. Болотов5; результатом их работы также стала монография 6.

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

Цель работы

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

Методы исследования

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

Научная новизна

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

4А.С. П0ДК0ЛЗШ1, Об универсальных однородных структурах, Проблемы кибернетики, 1975, 199-255

5 A.A. Болотов, О задачах сводимости и выразимости для однородных структур со входами и выходами, ДАН СССР Т.254., N1, 1980, 14-16

6В.Б. Кудрявцев, A.C. Подколзин, A.A. Болотов Основы теории однородных структур, 1990, 296

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

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

Также получены оценки сложности управляющего автомата для построенных алгоритмов.

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

Практическая ценность

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

Наличие большого числа выходов и малого числа входов экрана является типичной для чипов. Поэтому все упомянутые алгоритмы построения изображений могут применяться в перепрограммировании программируемых чипов (ПЛИС или РРСА).

Апробация работы

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

(1) Семинар "Теория автоматов"нод руководством академика, профессора, д.ф-м.н. В.Б. Кудрявцева (2011 - 2014 г.г.)

(2) Семинар "Вопросы сложности алгоритмов поиска"под руководством проф., д.ф-м.н. Э.Э.Гасанова (2007-2014 гг.).

(3) Международная конференция "Современные проблемы математики, механики и их приложений", посвященная 70-летию академика В.А. Садовничего (30 марта - 2 апреля 2009, Москва, МГУ).

(4) Международная конференция студентов, аспирантов и молодых ученых "Ломоносов"(13-18 апреля 2009, 11-15 апреля 2011, 9-13 апреля 2012, 8-13 апреля 2013, 7-11 апреля 2014, Москва, МГУ).

(5) I Международная научно-практическая конференция "Интеллектуальные машины"(9-10 апреля 2009, Москва, МГТУ "МАМИ").

(6) X Международный семинар "Дискретная математика и ее приложения"(1-6 февраля 2010, Москва, МГУ).

(7) X Международная конференция "Интеллектуальные системы и компьютерные науки"(21-26 ноября 2011, Москва, МГУ).

(8) XI Международный семинар "Дискретная математика и ее приложения", посвященный 80-летию со дня рождения академика О.Б. Лупа-нова (18-23 июня 2012, Москва, МГУ).

Публикации

Результаты автора по теме диссертации опубликованы в четырех работах, список которых приводится в конце автореферата [1-4].

Структура и объем работы

Диссертация состоит из введения, трех глав и заключения. Объем диссертации 92 страницы. Список литературы содержит 24 наименования.

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

Во введении к диссертации кратко изложена история вопроса, показана актуальность темы и сформулированы основные результаты. Также описаны структура и краткое содержание диссертации.

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

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

Для ? £ N будем обозначать Ед = {0,1,..., д — 1}.

Конечный инициальный автомат — это шестерка А = (А, С}, В,<р, ф, до), где А — входной алфавит, <3 — множество состояний, которое является конечным подмножеством некоторого фиксированного счётного множества, В — выходной алфавит, ¡р : С} х А С} — функция переходов, ф : <5 х А —» В — функция выходов, д0 — начальное состояние.

Элементарным автоматом будем называть конечный инициальный автомат А с четырьмя входами и одним выходом, такой что: А = Е В = = Ед для некоторого € N \ {1}, -ф = <р = 1р(д,1,г,и,(1), причем имеет место свойство </?(0,0,0,0,0) = 0.

(п,т)-экраном 5 будем называть следующую конструкцию. Пусть имеется прямоугольник размера п х т, т, п € N. В каждую клетку прямоугольника поместим по одному экземпляру одного и того же элементарного автомата А. К входам этого автомата присоединим выходы автоматов, стоящих в четырех соседних с ним клетках, то есть у автомата имеется левый вход I, правый вход г, верхний вход и и нижний вход ¡1 соответственно и д

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

— это тройка 5 =< А,п,т >, где А — элементарный автомат, п, т 6 N — соответственно количество строк и столбцов прямоугольника.

Состояния 0 и 1 элементарного автомата будем называть метками. Черно-белой конфигурацией будем называть такую конфигурацию состояний элементарных автоматов экрана, при которой каждый элементарный автомат экрана находится в нулевом или единичном состоянии.

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

Кодом К изображения назовем матрицу п х т,п,т € 14, состоящую из нулей и единиц. Множество всех кодов изображений размера п х т, п,т £ N будем обозначать через /С(п, т). Изображение Эд- на (п,т)-

экране соответствует данному коду К, если положение нулей и единиц в изображении и в коде совпадают.

Внешний или управляющий автомат для экрана < А,п,т > — это автономный инициальный автомат Ле с множеством состояний С} = Е^ для некоторого </ € М, <70 = О, В = Е£+т. Это автомат, который генерирует последовательности входных символов из множества Ед для свободных входов экрана. Выход внешнего автомата — это слово а1...апЬ\...Ьт, где <2;,^- 6 Еч,1 = 1, = 1, ...,?п, причем первые п букв будут подавать-

ся на свободные входы по левой границе экрана, остальные т букв будут подаваться на свободные входы по верхней границе экрана.

Обозначим Э(п, т) — множество изображений размера (п х т), соответствующих всем возможным кодам размера п х т,п,т е N.

Генератором С назовем пару С? =< Ле.З >, где 5 — экран, Ле — внешний автомат для экрана 5.

Пусть на экране 5 находится некоторая черно-белая конфигурация. Скажем, что генератор < Де^ > формирует изображение с кодом К, если при подаче выходов Ле на свободные входы экрана через некоторое время на экране появляется изображение, соответствующее коду К.

Если п, 771 е М, то экран 5 =< А,п,т > — универсальный, если для любого кода К существует внешний автомат , такой что генератор й =< А1*.в > формирует изображение соответствующее коду К.

Множество всех универсальных (п, тгс)-экранов обозначим через Ы{п,тп). Если 5 =< А,п,т > — экран, то через (¿(Б) обозначим число состояний элементарного автомата А■ Обозначим С}(п, т) = тш5й(М СЦБ).

Теорема 1. Если п, т € М, то при тт(п,т) = 1 имеем (3(п,т) = 2, а при п, т > 2 имеем СЦп, т) = 3.

Элементарный автомат А называется универсальным, если для любых п. т Е N экран 5 =< А,п,т > является универсальным.

Теорема 2. Не существует универсального элелкнтарного автомата с двумя состояниями, и существует универсальный элементарный автомат с тремя состояниями.

Для генератора < Ае,3 > через Т(Ае,3) обозначим момент времени, после которого конфигурация экрана не изменяется. Считаем, что Т(«4е,5) = схэ, если стабилизация не наступает.

Если генератор < 5" > формирует изображение соответствующее коду К, то Т(Ле, S) — время формирования изображения ö/f.

Если S — универсальный экран, 3 — изображение, то через Q(S, ö) обозначим множество генераторов < Ае, S >, формирующих изображение Ö. Обозначим

T(S,90= min T(Ae,S), T(S,n,m) — max T(5,3f),

ЭеЭ(п,т)

T(n,m) = min T(S,n,m),

S£U(n,m)

T(n,m,q) = min T(S,n,m).

SeU{n,m),Q{S)<q

Теорема 3. Если n,m € N, mo T(n,m) = min(n,m) + 1.

Теорема 4. Для любых n,m G N выполнено

T(n, m, 3) < n + m + min(n, m) + 1, T(n, m,4) <2 min(n, m) + 1.

Получены оценки времени построения изображений при растущем числе состояний элементарного автомата.

Теорема 5. Если п, m, s € N, т, п > 2, 1 < s < п — 2, то

Т(п, т, 4 + 2s) < 2 min(n, т) — s + 2,

T(n, т, 2 min(n, т) + 2) = min(n, m) 4- 1.

(n, тп)-экран, на все свободные входы которого, кроме левого входа элементарного автомата, стоящего в первой строке и первом столбце, все время подается значение 0, будем называть (п,т)-экраном с одним свободным входом. То есть свободным входом данного экрана является только левый вход первого автомата самой верхней строки.

Обозначим через Tl(n,m,q) минимальное время построения изображения на универсальном экране с одним свободным входом.

Для экрана с одним свободным входом получена оценка времени построения изображения.

Теорема 6. Для любых n, m € N, то Т1{п, тп, 8) < 2тп + 5.

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

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

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

Примером предобработки является работа следующей конфигурации элементов. На вход перестановки я" поступает код К изображения. 7Г формирует из него некоторое слово, которое поступает на вход компоновщику Я^. К^ объединяет буквы входного слова в подслова по букв и подает эти подслова на вход разреживателю который между подсловами вставляет по элементов <ц. Полученное слово поступает на вход предо-бработчика который в начало слова добавляет к букв а2. Полученная таким образом последовательность поступает на вход автомата Ае, который генерирует последовательности входных слов для свободных входов экрана.

Ниже даны строгие определения перечисленных устройств.

Перестановкой -к для п, т е N будем называть функцию

7г; !С(п,т) —> Щ,

где г € N — некоторое натуральное число.

Компоновщиком с коэффициентом й € N для некоторого множества Уак, к Е N будем называть функцию

Я* ■ Улк -> {Уа)к,

такую что если у = г/х... € Уёк, то

Rd(v) = ("1 • • • щ) ■ ■ ■ {Vd(k-i)+i • ■ • Щк)> то есть исходное слово v разбивается на подслова длины d.

Разреживатпелем с коэффициентом d G N н параметром а £ V для некоторого множества (Vl)k, 1,к 6 N будем называть функцию

Rd . _ yi х 1 xVl x...xVlx {a}d_1 x V\ (возможно a G V), такую что если v = v\... vt G (Vl)k, где гG V1, то R%{v) = Via... av2a... a... Vk-\a... avk,

где между каждыми l буквами слова v вставлено по (d — 1)-й букве а.

Прсдобработчиком Gk,k 6 N U {0} для некоторого множества Vs (возможно a G V), s G N будем называть функцию

Gk : Vs {a}* х У5,

такую что ссли v = i>x... vs € Vs, то Gk{v) = а ... av\ ... vs, то есть буква а вставлена в начало исходного вектора к раз.

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

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

В третьей главе изучаются движения изображений на экране. Рассмотрим экран, представляющий нз себя конечную последовательность из т одинаковых элементарных автоматов А с двумя входами. Входы автомата А называются левым и правым и ими соответственно являются состояния левого и правого соседа. Правый вход последнего m-го автомата доопределяется как тождественный ноль, а левый вход первого автомата называется свободным и подключен к выходу управляющего автомата Ае. При этом функцию переходов состояний автомата А обозначим через ip{l,q,r), где q — текущее состояние автомата, 1,г — состояния его левого н правого соседей соответственно. Положим для любого экрана выполнено свойство

</з(0,0,0) = 0. Через 3(А,т) будем обозначать экран длины т. £ N с элементарным автоматом А■ Через (?(5) будем обозначать мощность множества состояний элементарного автомата экрана 5. Тройку в = (Ае,А,т) будем называть генератором. Среди состояний элементарного автомата выделим непустое подмножество Ь, не содержащее элемент 0, и элементы этого множества будем называть метками.

Изображением будем называть слово в алфавите {0,1}, начинающееся и заканчивающееся единицей. Длиной слова А будем называть количество букв в слове А и обозначать |Л|. Если изображение имеет длину 1, то будем называть его точкой н обозначать через I1, то есть I1 — слово, состоящее из одной буквы 1. Для произвольного изображения I ненулевые буквы изображения будем называть точками. Также точками будем называть метки на экране.

Законом дви'жения Е для экрана 3(А, т) будем называть слово в алфавите {0,1}, которое заканчивается единицей и содержит ровно т единиц. Множество всех законов движения для экрана 3(А, т) будем обозначать через Тт.

Будем говорить, что на экране 3(А, т) реализуется движение изобра-э/сения Iх по закону Е из Тт, если выполняются следующие условия:

1) в некоторый момент времени в самой левой ячейке экрана появляется метка (до этого на экране нет меток), этот момент будем называть моментом начала движения или началом двиэ/сения;

2) изменение позиции метки на экране в г-й момент от начала движения (1 < г < |/7'|) соответствует г-й букве в слове Е, а именно, если .Р(г) = 0, то в (г + 1)-й момент метка остается в той же ячейке, где была в текущий момент, если Е({) = 1, то в (г + 1)-й момент метка сдвинется на одну ячейку вправо, по сравнению со своим текущим положением;

3) в каждый момент времени после начала движения и до |^|-го такта от начала движения (этот момент называем моментом окончания движения) на экране есть ровно одна метка.

Понятно, что поскольку в законе движения Е ровно т единиц и F за-

канчивается на единицу, то после окончания движения на экране не будет ни одной метки.

Экран 3(А,т) будем называть универсальным для изобраэ/сения Iх

и множества законов движения Т, если для любого закона движения Е из Т существует такой управляющий автомат Ае, что генератор

(7 = {Ае, Л,т) формирует на экране изображение I1, движущееся закону .Р. Множество всех таких экранов 63'дем обозначать через Ы{11.Т, т).

Экран 5(А,т) будем называть универсальным для изображения I1, если он является универсальным для изображения I1 и множества Тт всех законов движения для экрана 5 и изображения /1.

Если Т С Тт, то обозначим (¿(^^.т) = тн^^л угт) <5(5), Я{1\т) = С>{1\Гт,т).

Через ТТ'й обозначим множество таких законов движения Е, в которых начиная с момента й + 1 не встречается более чем г единиц подряд, г, с? € Ми {0}. То есть, для любого отрезка единиц с длиной больше г, правая граница этого отрезка имеет координату меньше (1 + 1.

Законы движения из будем назвать законами движения с ограниченной скоростью с параметром г, г 6 N.

— множество законов движения, в которых не встречается более чем г единиц подряд.

Теорема 10. Если m>2,meN, то С\ Тт,т) = 4.

Теорема 11. Если т Е N и тп > 2, то 4 < <3(11,т) < 7.

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

Через Б (А) будем обозначать бесконечный в одну сторону (вправо) экран.

Законом движения для бесконечного экрана будем называть сверхслово

^ е {о,1}°°.

Переформулируем определение движения для случая бесконечного экрана. Будем говорить, что на экране Б (А) реализуется движение изображения 11 по закону Е, если выполняются следующие условия:

1) в некоторый момент времени в самой левой ячейке экрана появляется метка (до этого на экране нет меток), этот момент будем называть моментом иа'чала движения или на'чалом двио/ссния;

2) изменение позиции метки па экране в г-й момент от начала движения соответствует г-й букве в сверхслове .Р, а именно, если Е({) = 0, то в (г + 1)-й момент метка остается в той же ячейке, где была в текущий момент, если Р(г) = 1, то в (г + 1)-й момент метка сдвинется на одну ячейку вправо, по сравнению со своим текущим положением;

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

Экран 5"(Д) будем называть универсальным для изобрао/сения Iх и множества законов движения Т, если для любого Е из Т существует такой управляющий автомат Ле, что генератор б = {Ле,Л,оо) формирует на экране изображение 11, движущееся закону Е . Множество всех таких экранов будем обозначать через 1А{Т).

Если Т С {0,1}°°, то обозначим — т\п3еи(?)

Теорема 12. Для любого бесконечного экрана 5(-4) существует такой закон двио/ссния Е € {0,1}°°, что на экране 5(Л) невозмоэ/сно реализовать движение изображения 11 по закону Е.

Теорема 13. Существует закон двиэ/сения F е {0,1}°°, движение по которому невозможно реализовать ни на каком экране .

Как и ранее через ТГ>Л обозначим множество таких законов движения Е (но теперь уже сверхслов), в которых начиная с момента 1 не встречается более чем г единиц подряд, г, д е N и {0}.

Теорема 14. Если в, й € М, то имеют место следующие оценки

3 < < 2з + 2;

3 < <25 + 9.

Движение изображения на экране будем называть автономным, если начиная с некоторого момента £ € N. £ < оо на свободный вход экрана поступают только нулевые значения.

Обозначим — количество единиц в префиксе длины Ь закона движения Е.

Если для закона движения Е существует предел Нт(^оо Т0 будем называть его скоростью движения точки по закону F и обозначать через у(Е).

Теорема 15. Для любого рационального числа а, 0 < а < 1, существует непериодг1ческий закон Еа, такой что у(Еа) = а иЦ({Еа}) ф 0.

Скажем, что в законе движения Е реализуется скорость у 6 К, если существует такая бесконечная возрастающая последовательность {£,■},

и € N. что Шп^оо ^ =

Теорема 16. Существует бесконечный экран £(«4), на котором реализуется такой закон движения Р изображения I1, что в Р реализуются все скорости V из отрезка [0,1].

Следствие 1. Существует автономный бесконечный экран, реализующий для изображения 11 закон движения с растущим числом идущих подряд нулей и растущим числом идущих подряд единиц.

Заключение

В диссертации получены следующие основные результаты.

Показано, что число состояний элементарного автомата минимального универсального экрана равно 3.

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

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

Найденные способы построения изображений расширены для случая многомерного экрана, и получены оценки времени построения изображений па многомерном экране в зависимости от числа состояний элементарного автомата.

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

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

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

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

Для любого натурального к существует такой элементарный автомат Л с 7к состояниями, что для любого натурального т экран Б(Л, т) является универсальным для любого изображения I, состоящего из не более чем к точек.

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

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

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

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

Построен бесконечный экран, на котором реализуется такой закон движения одной точки, что в этом законе реализуются все скорости нз отрезка [0,1].

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

Благодарность

Автор выражает искреннюю благодарность научному руководителю д.ф.-м.н., профессору Э. Э. Гасанову за постановку задачи и внимание к работе. Также хочется высказать признательность заведующему кафедрой математической теории интеллектуальных систем академику, профессору В. Б. Кудрявцеву и всему коллективу кафедры за опыт и знания, полученные во время обучения, за доброжелательную и творческую атмосферу.

Публикации автора по теме диссертации

[1] Е.Е. Титова, Конструирование изображений клеточными автоматами, Интеллектуальные системы, 12, 2008,105-121

[2] Е.Е. Титова, Линейгюе по времени конструирование изображений клеточными автоматами, Интеллектуальные системы, 16, 2012, 215-234

[3] Е.Е. Титова, Сложность конструирования изобаражений клеточными автоматами, Интеллектуальные системы, 17, 2013, 191-195

[4] Е.Е. Титова, Конструирование движущихся изображений клеточными автоматами, Интеллектуальные системы, 18, 2014, 153-180

Подписано в печать: 19.06.2015 Тираж: 100 экз. Заказ № 418 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, д. 39 (495) 363-78-90; www.reglet.ru