Abstract

Abstract

In paper are presented results of development and analysis of automata models of discrete dynamical systems. Are spend complexity estimations of automata functioning lows on the basis of use of geometrical images of automata mappings and special spectrum of recurrent definition of sequences. Are research complexity estimations of automatons in special classes. Also in paper are constructed automata models by geometrical curves having an applied interpretation with subsequent classification of models by complexity.

Full Text

Введение Среди фундаментальных составляющих математических моделей сложных дискретных динамических систем находятся алгоритмы, реализуемые системой в соответствии с ее целевым предназначением. Для алгоритмически разрешимого класса задач существует бесконечное множество алгоритмов (решающих класс задач), которое может быть упорядочено по сложности. Со сложностью алгоритма в общем случае связана реализация алгоритмов в системе, определяющая ряд важнейших показателей: быстродействие, объем памяти, надежность, энергозатраты и т.п. В связи с этим задачи построения новых методов для оценки сложности законов функционирования систем в целом и конкретных процессов функционирования являются актуальными. Число вариантов понятия сложности продолжает увеличиваться [1]: оценки алгоритмов по их принадлежности к NP и P классам, сложность снизу, сверху, сложность в среднем, битовая сложность, мультипликативная сложность, колмогоровская сложность (сложность Колмогорова-Хайтина), алгебраическая сложность, асимптотические оценки сложности и др. [2]. В данной работе предлагается и иллюстрируется применение нового метода оценки сложности алгоритмов функционирования дискретных динамических систем на основе использования предложенного и разработанного В.А. Твердохлебовым [3] спектра динамических параметров рекуррентного определения последовательностей. По одной из основных гипотез теории алгоритмов (которую в литературе называют тезисом Черча-Тьюринга [4]) в случае, если задача имеет решение (существует алгоритм решения), то существует машина Тьюринга, которая решает эту задачу. По данной гипотезе класс всех алгоритмов равномощен классу машин Тьюринга. В свою очередь, машина Тьюринга является расширением конечного детерминированного автомата, класс преобразований которого ограничен числом состояний, входных и выходных сигналов. При снятии ограничения на конечность числа состояний автомата (что сделано В.А. Твердохлебовым за счет введения геометрических образов законов функционирования автоматов [3, 5]) машина Тьюринга может быть представлена как автомат c бесконечным числом состояний, считывающий и записывающий информацию с ячеек ленты. В работе А.Н. Колмогорова и В.А. Успенского [6] отмечается: «...построение теории алгоритмов по образцу теории вычислительных машин требует во всяком случае некоторой идеализации понятия "машины". <...> Вся идеализация, необходимая для перехода от реальных вычислительных машин к математическим алгоритмам, заключается в допущении неограниченного объема "памяти" машины [6, с. 6]». Ввиду ограничений на объем статьи отметим только основные идеи, позволяющие представить законы функционирования автомата типа Мили (Аs = (S, X, Y, d, l, s) с множествами состояний S, входных сигналов X и выходных сигналов Y, функцией переходов d : S ´ X®S, функцией выходов l: S ´ X®Y и начальным состоянием sÎS) в числовой форме (в форме геометрического образа gs): 1. Линейно упорядочивается автоматное отображение: , где , . 2. Элементы пар (p, y) автоматного отображения заменяются их номерами (r1(p), r2(y)) по вводимым линейным порядкам. 3. Полученное множество пар чисел размещается в главном квадранте прямоугольной декартовой системы координат на плоскости. В работе [3] показано, что при выбранных и зафиксированных в линейном порядке на множестве Х* и величине m = | X | геометрический образ автомата однозначно определяется последовательностью вторых координат его точек. 1. Спектр динамических параметров рекуррентного определения последовательностей Для строгого представления свойств последовательности В.А. Твердохлебовым введен спектр динамических параметров рекуррентного определения последовательности [3], характеризующий последовательность по взаимосвязям (взаиморасположению) элементов в ней. Рассмотрим спектр для произвольных последовательностей. Пусть - конечное множество и x - последовательность элементов из множества U: . Спектр W(x) динамических характеристик последовательности x Î U* имеет иерархическую структуру, состоящую из уровней W(x) = (W0(x), W1(x), W2(x), W3(x), W4(x)). Каждый конкретный вариант реализации (представление значениями параметров) любого уровня Wi(x) определяет разбиение множества U* на подмножества по свойствам совпадения характеристик. Подмножества такого разбиения будем рассматривать как классы эквивалентности последовательностей. Введем следующие обозначения. Для любой последовательности , где U ν - множество всех последовательностей длины n элементов из множества U, наименьший порядок рекуррентной формы, определяющей последовательность , будем обозначать . Для любой последовательности и , где , наибольшую длину начального отрезка последовательности , определяемого рекуррентной формой порядка m, будем обозначать , число смен рекуррентных форм порядка m, требующихся при определении последовательности , будем обозначать , а длину j-го отрезка в определении последовательности будем обозначать . Используя введенные обозначения, определим спектр параметров, характеризующих последовательность, как следующую структуру: - ; - ; - ; - , где и (nj - номер последнего отрезка в определении последовательности как последовательности отрезков, определяемых отдельными рекуррентными формами порядка j). 2. Оценка сложности законов функционирования автоматов, заданных последовательностями Среди различных подходов к оценке сложности процессов, алгоритмов, законов функционирования автоматов и реализаций этих законов для исследования выбран подход, при котором используется геометрическое представление поведения автоматов. Рекуррентное описание последовательностей дает полную и глубокую характеристику взаиморасположения элементов в последовательности: определяет функциональную зависимость элемента последовательности от непосредственно предшествующей ему подпоследовательности элементов. Проведено исследование, в котором спектр используется как средство для оценки сложности законов функционирования автоматов, реализаций алгоритмов, трасс «Формулы-1» по геометрическим свойствам, последовательностей ДНК различных живых существ, функций алгебры логики [5]. Ввиду ограничений на объем статьи приводятся только некоторые результаты из указанных выше. Кроме этого, были классифицированы по сложности взаиморасположения цифр в начальных отрезках последовательностей длины до 1 млн знаков, представляющих приближенно иррациональные числа: π, e, φ (так называемое золотое сечение), , , ln(2), ln(10), , константа Каталана , константа Эйлера γ (постоянная Эйлера-Маскеро́ни) и др. Для оценки сложности взаиморасположения цифр в начальных отрезках последовательностей, представляющих приближения иррациональных чисел π, e, φ, , , ln(2), ln(10), , константы Каталана C, константы Эйлера γ и др., рассмотрим последовательности длины до 1 000 000 знаков (π и e дополнительно построены и проанализированы до 10 млн знаков). Эти структуры сравнены и классифицированы по сложности на основе показателей первых двух уровней спектра, так как числовые структуры, соответствующие третьему и четвертому уровням, имеют практически непредставимую размерность. Отметим, что каждая оценка сложности законов функционирования инициального автомата распространяется на весь класс изоморфных по выходам автоматов (включающий l! автоматов, где l = |Y|). Введем следующие обозначения: H = {e, π, φ, , , ln(2), ln(10), , С, γ}, Hd - множество начальных отрезков длины d последовательностей, определяющих элементы множества H, а , где , - дискретный детерминированный автомат с числом входных сигналов m и β, являющийся последовательностью вторых координат точек геометрического образа автомата. Для проведения исследований были разработаны алгоритмы и программы, позволившие построить указанные спектры для рассмотренных величин. Результаты построения двух первых уровней спектров (показатели Ω1 приведены в явном виде, а показатели Ω0 могут быть получены после тривиального анализа показателей Ω1) динамических параметров для указанных последовательностей приведены в табл. 1. В лемме 1 приведены результаты построения показателей спектров для множества и разбиения по совпадению показателей на классы эквивалентности по сложности. Лемма 1. Законы функционирования автоматов из , где d = 1 000 000: - по сложности, определяемой нулевым уровнем W0 спектра W, образуют два класса эквивалентности по сложности: и - по сложности, определяемой первым уровнем W1 спектра W, образуют одноэлементные классы эквивалентности по сложности. Доказательство [5]. В лемме 1 представлены оценки сложности законов функционирования автоматов для случая их определения последовательностями вторых координат точек их геометрических образов длины d = 1 000 000. Полученные классы сложности не являются инвариантными относительно изменения длины d рассматриваемых последовательностей. Таблица 1 Характеристики первого уровня Ω1 спектра Ω для последовательностей из множества H Порядок рекуррентной формы π e 1 4 5 5 3 5 2 23 10 25 14 5 3 64 10 25 63 52 4 136 10 224 90 183 5 556 500 800 989 612 6 1302 500 872 1211 843 7 4608 2738 3673 3551 2854 8 15 442 23 552 6733 15 320 11 923 9 33 853 29 433 62 895 24 707 73 588 10 240 489 159 939 278 219 111 204 96 694 11 694 410 172 265 389 536 320 819 96 694 12 857 994 947 499 988 084 942 583 846 617 13 1 000 000 1 000 000 1 000 000 1 000 000 1 000 000 3. Оценка сложности автоматных моделей управления движением болидов «Формулы-1» В данном разделе содержатся результаты анализа сложности 69 трасс, на которых проводились все официальные этапы автомобильной гоночной серии «Формула-1» с 1950 по 2011 г. Анализ свойств гоночных трасс проводится на основе исследования свойств геометрических кривых, представляющих собой масштабированные карты реальных трасс. Анализ трасс состоит в построении кодов трасс (исследованы различные степени приближения - от 40 до 400 точек), которые также интерпретируются как соответствующие последовательности вторых координат точек геометрических образов автоматов. Для элементов множества, состоящего из 69 построенных числовых последовательностей кодов, строятся спектры, и на основе совпадения числовых показателей спектра множество разбивается на классы эквивалентных последовательностей. Кроме того, по каждой из 69 кривых осуществлено построение семейства автоматов (при различном числе входных сигналов автомата и разных способах доопределения функции переходов автоматов). Построение числовых последовательностей кодов трасс при анализе сложности управления движением по трассе заданного объекта может быть реализовано различными способами и с разной степенью точности и полноты. В общем случае в коде должны быть представлены: геометрические свойства маршрута, физические свойства маршрута (задымленность, туман, тип покрытия, наличие на покрытии трассы веществ, влияющих на сцепление и др.), свойства объекта движения (например, способность набирать/снижать скорость с заданной интенсивностью), свойства органа управления объектом движения, свойства объектов сигнализации и др. В данной работе при проведении анализа свойств трасс рассматриваются только геометрические свойства маршрутов ввиду того, что за 60 лет происходили существенные изменения в техническом регламенте «Формулы-1», оказывающие принципиальное влияние на свойства объекта движения, свойства органа управления и характеристики средств сигнализации (десятки раз вводились и отменялись разные ограничения на мощность двигателя, диаметр и ширину покрышек (и даже на количество колес, яркий пример чего представляли шестиколесные болиды Tyrrell P34 [7]), геометрию и размеры задних и передних антикрыльев, использование систем помощи при торможении и ускорении болида и др.). Числовые последовательности кодов, в которых представлены геометрические свойства трасс, могут быть построены различными способами. В данной работе выбран способ, который предполагает выбор базиса стандартных участков движения и их кодирования, разбиение всего маршрута на стандартные участки и построение кода всего маршрута как числовой последовательности кодов стандартных участков. При этом используется существующая гоночная классификация стандартных участков движения [8], а направление обхода для каждой кривой совпадает с направлением движения болидов «Формулы-1» по трассе, которой сопоставляется кривая. В качестве примера на рисунке приведены карты двух трасс: a - Brands Hatch (Кент, Великобритания); б - Hockenheimring (Хокенхайм, Германия) и выбранного разбиения трасс на стандартные участки. Показатели на нулевом уровне спектра: последовательность ξ1, кодирующая трассу a Brands Hatch, - W0(ξ1) = m0(ξ1) = 19; последовательность ξ2, кодирующая трассу б Hockenheimring, - W0(ξ2) = m0(ξ2) = 21 (для выбранного варианта кодирования трассы). Значения показателей для ξ1 и ξ2 на уровнях W1 - W3 в явном виде не приводятся ввиду большой размерности. a б Рис. Карты трасс: a - Brands Hatch; б - Hockenheimring Построены числовые последовательности кодов всех 69 трасс, и проведен их анализ с использованием спектра динамических параметров W. Вычислены значения показателей на четырех уровнях W0-W3 спектра W, и на основе полученных значений построены классы эквивалентных по сложности последовательностей и соответствующих им трасс. В качестве примера в табл. 2 приведена классификация трасс на нулевом уровне Ω0 спектра Ω этапов «Формулы-1» сезона 2008 г., в которой самой сложной оказалась трасса Маньи - Кур гран-при Франции. Кроме того, по каждой кривой осуществляется построение класса автоматов при разных значениях мощности входного алфавита и различных способах доопределения функции переходов автомата. Автоматы минимизируются, и на основе числа состояний в минимальном автомате, сопоставленном с трассой, также проводится классификация трасс по сложности. Таблица 2 Классы эквивалентных на нулевом уровне Ω0 спектра Ω этапов «Формулы-1» сезона 2008 г. Класс Этап «Формулы-1» Трасса K1 Гран-при Бахрейна Сахир Гран-при Малайзии Сепанг Гран-при Канады Автодром им. Ж. Вильнева Гран-при Германии Хоккенхаймринг Гран-при Венгрии Хунгароринг Гран-при Турции Курткой Гран-при Бельгии Спа Гран-при Китая Шанхай Интернешнл Гран-при Японии Сузука Интернешнл Гран-при Бразилии Интерлагос K2 Гран-при Австралии Трасса Альберт-Парк Гран-при Сан-Марино Автодром им. Энцо и Дино Феррари Гран-при Европы Трасса Нюрбургринг Гран-при Испании Каталунья Монтмелло Гран-при Италии Аутодроме Национале Гран-при Великобритании Сильверстоун Гран-при США Автодром Индианаполис Мотор Спидвей K3 Гран-при Франции Маньи - Кур Невер В один класс разбиения P1 (по показателям первого уровня Ω1 спектра Ω) попали этапы гран-при Канады (трасса Автодром имени Жиля Вильнева) и гран-при Японии (трасса Сузука Интернешнл). В работе [9] приведены данные о трассах, которые подтверждают, что они имеют близкую сложность. Информация, извлеченная из источника [9], также подтверждает одинаковую сложность данных трасс (для указанных сильнейших пилотов «Формулы-1» число побед на обеих трассах отличается не более чем на 1 или совпадает). Выводы Изложены результаты, показывающие возможность практического использования спектра динамических параметров для определения свойств и оценки сложности законов функционирования дискретных детерминированных динамических систем на основе исследования свойств числовых последовательностей, взаимно-однозначно определяющих законы функционирования. Проведен анализ сложности трасс «Формулы-1» (трассы, на которых были проведены все официальные этапы с 1950 по 2011 г.). Для проведения анализа трасс проведено кодирование трасс (двумя способами), и для получения конкретных оценок и классификации трасс по сложности использован специальный спектр динамических параметров рекуррентного определения последовательностей.