авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Модели и методы анализа, интерполяции и распознавания автоматов

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

Епифанов Антон Сергеевич Модели и методы анализа, интерполяции и распознавания автоматов 01.01.09 –дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Саратов - 2011

Работа выполнена в Институте проблем точной механики и управления РАН (г.Саратов)

Научный консультант: доктор технических наук, профессор Твердохлебов Владимир Александрович

Официальные оппоненты: доктор физико-математических наук, доцент Андрейченко Дмитрий Константинович кандидат физико-математических наук, доцент Богомолов Сергей Анатольевич

Ведущая организация: Институт проблем управления РАН (г.Москва)

Защита диссертации состоится «17» марта 2011 г. в 17 часов 00 мин. на заседании диссертационного совета ДМ 212.243.15 при Саратовском государственном университете им.Н.Г.Чернышевского по адресу: 410012, г.Саратов, ул.Астраханская, 83, СГУ, механико математический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Саратовского государственного университета им.Н.Г.Чернышевского.

Автореферат разослан «_ » февраля 2011 г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент В.В. Корнев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория автоматов как один из разделов математической кибернетики нашла применение в технике (синтез технических систем, техническое диагностирование), в информатике (построение компиляторов, тестирование программ), в медицине и др. Формирование и развитие теория автоматов получила, например, в работах Дж.Неймана [12], В.М.Глушкова [6-7], В.Б.Кудрявцева и др. [10], М.И.Кратко [9], М.А.Айзермана [1] и др. Фундаментальным направлением в теории автоматов явилась теория экспериментов с автоматами (работы Э.Мура [11], А.Гилла [5]). Основа для использования моделей и методов дискретной математики в теории автоматов изложена, например, в работах С.В.Яблонского [14] и сборнике [8].

Исследования по теории автоматов проводились в Саратовско-Донецкой Школе, возглавлявшейся А.М.Богомоловым ([2-4]), в которую входили Д.В.Сперанский, В.Н.Салий, Ю.А.Скобцов, В.Г.Скобелев, А.А.Сытник, И.С.Грунский, В.А.Твердохлебов и др.

Анализ распространения основных положений, моделей и методов теории автоматов на область сложных систем при использовании традиционных средств задания автоматов (таблицами, матрицами, графами, логическими уравнениями, формулами языка регулярных выражений) показал, что требуется добавить новые средства, согласующиеся с возросшей размерностью автоматных моделей и неполнотой их представления, а также для устранения барьера между дискретными символьными и числовыми математическими структурами. Представления числовыми математическими структурами законов функционирования автоматов позволяет, во – первых, в ряде случаев преодолевать барьер размерности данных в моделях, а, во-вторых, принципиально расширить формальный аппарат теории автоматов на основе включения в него развитых числовых структур и методов геометрии. В 1995 1996гг. В.А. Твердохлебовым [13] был предложен новый подход к заданию законов функционирования конечных детерминированных автоматов – задание геометрическими образами, при котором автоматное отображение представляется в формах символьного и числового графиков. Это позволяет использовать для задания законов функционирования автоматов геометрические кривые, с расположенными на них точками автоматных отображений, и произвольные последовательности, интерпретируемые как последовательности вторых координат точек геометрических образов. Задание автоматных отображений числовыми графиками позволило расширить класс автоматов, для которых эффективно решаются задачи распознавания автоматов, применять классические методы интерполяции и разрабатывать новые методы интерполяции для частично заданных автоматных отображений, оценивать сложность законов функционирования автоматов. Разработка методов распознавания, интерполяция и оценка сложности законов функционирования автоматов (при задании этих законов геометрическими образами) являются актуальными. Задачи распознавания, интерполяции и оценки сложности законов функционирования автоматов взаимосвязаны, так как сложные автоматы имеют частично заданные законы функционирования и их распознавание связано с предварительными оценкой сложности и интерполяцией.

Основные результаты диссертации получены с участием автора при выполнении исследований по планам НИР Института проблем точной механики и управления РАН: "Разработка методов и моделей для управления и технического диагностирования мехатронных систем (2007г., № гос.

регистрации – 0120.0 502444)", " Разработка основных положений моделей и методов описания законов функционирования сложных технических систем в форме причинно-следственных комплексов взаимодействий разнородных процессов (2008-2010г.г., № гос. регистрации – 0120. 0 803005)" и по грантам РФФИ " Разработка моделей и методов для технического диагностирования больших систем с использованием автоматных моделей и интерполяции по числовым геометрическим образам законов функционирования объекта диагностирования (2007-2008г.г., №07-07-00088а)" и "Разработка методов технического диагностирования сложных систем с учётом интервалов времени, на которых законы функционирования систем не определены или невозможно применение средств диагностирования (2008-2009г.г., №08-08-00534)".



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

Задача 1. Исследовать возможность методов интерполяции Ньютона, Лагранжа, Гаусса, Бесселя, Стирлинга и др. для законов функционирования автоматов, частично заданных геометрическими образами.

Разработать методы интерполяции частично заданных законов функционирования автоматов с новым выбором узлов интерполяции: узлов, определяемых автономными подавтоматами, и узлов, определяемых горизонтальными сечениями геометрических образов.

Задача 2. Разработать методы распознавания автоматов в семействах автоматов, заданных последовательностями вторых координат точек геометрических образов и геометрическими кривыми линиями, на которых размещены точки автоматных отображений.

Задача 3. Получить оценки сложности законов функционирования автоматов (и их реализаций) с использованием спектра рекуррентных описаний в случаях, когда законы функционирования заданы геометрическими образами, представленными:

- последовательностями вторых координат точек геометрических образов автоматов;

- последовательностями точек на аналитически заданных кривых, интерпретируемых как вершины геометрических образов;

- классом (4,2,2)-автоматов и его подклассами, определенными по свойствам Поста.

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

Научная новизна. Основные результаты диссертации являются новыми и впервые получены автором:

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

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

2. Получены оценки для сравнения по точности интерполяции методами Ньютона, Лагранжа и др. для частично заданных законов функционирования автоматов, последовательности вторых координат вершин геометрических образов которых определены числовыми последовательностями из массива The On-Line Encyclopedia of Integer Sequences™ (OEIS™(США)). Получены оценки для автоматов с частично заданными геометрическими образами, представляющими класс (4,2,2)-автоматов и его подклассы и класс линейных (8,2,2)-автоматов.





3. Разработаны метод и алгоритм распознавания таких автоматов, законы функционирования которых заданы геометрическими образами, расположенными на аналитически заданных геометрических кривых: y=e (x-5.5), x +1 x - 2. x y= + 1.75),,y= и др.

y = 1 + cos( 1.8 4. Разработаны алгоритмы оценки сложности с использованием показателей спектра рекуррентных описаний геометрических образов для автоматов:

- вершины геометрических образов которых расположены на аналитически заданных геометрических кривых, содержащихся в банке ENCYCLOPDIE DES FORMES MATHMATIQUES REMARQUABLES (Франция);

- по последовательностям вторых координат вершин геометрических образов (включая оценку последовательностей длины 1 млн.знаков из массива OEIS™(США)) ;

- для законов функционирования автоматов из класса (4,2,2)-автоматов и его подклассов.

Теоретическая и практическая значимость. Разработанные в диссертации модели, методы и алгоритмы позволяют: доопределять частично заданные законы функционирования автоматов до полностью определенных законов функционирования;

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

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

Апробация работы: Основные результаты работы докладывались и обсуждались на 2-ой школе-семинаре молодых ученых «Управление большими системами», (г.Воронеж, 9-12 июля 2007г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT 2007" (г.Кировоград, Украина, 24-27 апреля 2007г.), Международной научной конференции «Автоматизация проектирования дискретных систем» (г.Минск, Белоруссия, Объединенный Институт проблем информатики НАН Беларуси, - 15 ноября 2007г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2008" (г.Кировоград, Украина, 23- апреля 2008г.), Международной научной конференции "Информационные технологии и системы ИТиС’08" (г.Геленджик, 29 сентября - 3 октября 2008г. ), 5-ой школе-семинаре молодых ученых «Управление большими системами» (г.Липецк, 21-24 октября 2008г.), Второй (1-3 октября 2008г) и Третьей (5- октября 2009г.) Международных научных конференциях "Управление развитием крупномасштабных систем" (г.Москва, Институт проблем управления РАН), Международной научной конференции «Математические методы в технике и технологиях ММТТ-22» (г.Псков, 25 – 30 мая 2008г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2009" (г.Кировоград, Украина, 22-25 апреля 2009г.), Международной научной конференции «Дискретные модели в теории управляющих систем» (г.Москва, МГУ им.М.В.Ломоносова, факультет ВМК, 6—9 апреля, 2009г.), на 7-ой молодежной научной школе по дискретной математике и ее приложениям (г.Москва, Институт прикладной математики им.М.В.Келдыша РАН, 18-23 мая 2009г.), 6-ой школе-семинаре молодых ученых «Управление большими системами» (г.Ижевск, Удмуртский государственный университет, 31 августа – 5 сентября 2009г.), Международной научной конференции «Мехатроника, автоматизация, управление (МАУ-2009)» (п.Дивноморское, 28 сентября – 3 октября 2009г.), на 10-ом Международном семинаре «Дискретная математика и ее приложения», (г.Москва, МГУ, механико-математический факультет, 1-5 февраля 2010г.), Международной научной конференции "Гарантоспособные системы, сервисы и технологии DESSERT-2010" (г.Кировоград, Украина, 11-15 мая 2010г.), на Седьмой Международной научно-практической конференции "Теоретические и прикладные аспекты построения программных систем" (Украина, г.Киев, Киевский Национальный Университет им.Т.Шевченко, факультет кибернетики, 4-8 октября 2010).

Публикации. Основные результаты диссертации опубликованы в печатных работах [A1-A20] (включая монографию [A3]), список которых приведен в конце автореферата. Статьи [A1, A2] опубликованы в изданиях, содержащихся в Перечне ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, списка литературы и приложения. Общий объем диссертации 142 страницы, включая 16 рисунков, список литературы и приложение. Библиография содержит 93 наименования.

ОБЗОР СОДЕРЖАНИЯ ДИССЕРТАЦИИ Во введении определены цели и задачи исследования, обоснована его актуальность, сформулированы основные результаты диссертационного исследования.

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

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

Глава 2 также содержит результаты оценки точности интерполяции методами Ньютона и Лагранжа частично заданных законов функционирования автоматов, представляющих класс (4,2,2)-автоматов и его подклассы, класс линейных (8,2,2)-автоматов. Кроме этого рассмотрена интерполяция частично заданных законов функционирования автоматов, которые определены последовательностями вторых координат точек геометрических образов.

Оценка точности интерполяции проведена для начальных отрезков длины до 1 млн. знаков в приближенных представлениях величин из массива H1 при новом выборе узлов интерполяции, что привело к разработке двух методов интерполяции ( метод 1 и метод 2).

Исследованные инициальные автоматы вида A s 0 =(S, X, Y,,, s 0 ), где S, X и Y - множества состояний, входных и выходных сигналов, и – функции переходов и выходов вида d : S X S, l : S X Y, а s 0 S - начальное состояние, представлены классами автоматов: классами (n, m, l) – автоматов, где n = |S|, m = |X|, l = |Y|, и классами (n, m, l)d начальных отрезков геометрических образов длины d, определяющих автоматы из класса (n, m, l) – автоматов. (Геометрическим образом инициального автомата As0 =(S, X, Y,,, s 0 ) называется автоматное отображение r s0 = U* {(p, l(s 0, p))}, дважды линейно упорядоченное введением линейного p X X* порядка 1 на множестве и линейного порядка 2 на Y.) Геометрический образ автомата представляется точками символьного графика G1, расположенного в системе координат с осью абсцисс (X*, 1) и осью ординат (Y, 2). График G1 преобразуется в график G2 точек с числовыми координатами, в котором каждая пара (p,y) rs0 графика G1 заменена парой y по порядкам 1 и 2 и rs (r1(p), r2(y)), где r1(p) и r2(y) – номера p и r s получено из заменой вторых координат пар последним знаком l(s 0, p). Числовая форма последовательности G2 геометрического образа автомата изоморфно вкладывается в первый квадрант прямоугольной декартовой системы координат на плоскости, что позволяет исследовать методы интерполяции частично заданных геометрических образов классическими методами интерполяции. В диссертации проведен сравнительный анализ точности интерполяции методами Ньютона и Лагранжа, а также модифицированными методами Ньютона и Лагранжа. Модификация методов интерполяции состоит в том, что узлами интерполяции являются точки геометрических образов автономных подавтоматов вида A0=(S, {0}, Y, d0, l0, s0) 1+ 1 2, ln(2), ln(10), 2, Массив H состоит из 10 величин: e,, j = (золотое сечение), (-1 ) n 1 11 z (3 ) =, константы Каталана C =, константы Эйлера g = lim (1 + + +... + - ln( n )).

n=0 (2n + ) x =1 x 23 n n ® и A1=(S, {1}, Y, d1, l1, s0). Введем для сравнения эффективности интерполяции двух методов интерполяции в заданном классе автоматов функцию, числовые показатели которой имеют интерпретацию как показатели эффективности min(n 1, n d ) + n методов интерполяции:, где n1 ( n d ) - число d d F(n 1, n d, n 12 ) = 1 d max(n d, n 2 ) + n d d d d автоматов, для которых методом (методом ) восстановлено больше точек, чем методом (чем методом ), а n12 - число автоматов, для которых d совпадает число правильно восстановленных точек методом и методом, при условии n1 + n d + n12 0. В диссертации исследованы методы интерполяции d d Ньютона (N) и Лагранжа (L), а функция получения оценок эффективности интерполяции имеет вид, где n d + n d + n d 0.

min(n d, n L ) + n d N NL N L NL d N L NL F(n d, n d, n d ) = 1 - N L NL max(n d, n d ) + n d Функция использована для получения оценок F(n d, n L, n d ) N NL d эффективности интерполяции методами Ньютона и Лагранжа в классе (4,2,2) автоматов и его подклассах, выделенных свойствами Поста, а также в классе линейных (8,2,2)-автоматов. В классах автоматов получены оценки, характеризующие эффективность методов интерполяции в зависимости от длины геометрических образов автоматов. Значения функции F= интерпретируются как равная эффективность обоих методов интерполяции. При F=1 только один из методов интерполяции правильно восстанавливает некоторые точки геометрических образов автоматов из рассматриваемого класса автоматов. Значение n, где 0 n 1, функции F интерпретируется как числовой показатель величины эффективности одного из методов.

Следующие теоремы содержат оценки эффективности интерполяции для указанных выше классов автоматов методами Ньютона и Лагранжа.

Теорема 2.1.1. Пусть узлами интерполяции для геометрического образа длины d каждого автомата A=(S, {0,1}, Y,,, s0) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов A0=(S, {0}, Y, 0, 0, s0) и A1=(S, {1}, Y, 1, 1, s0) автомата A. Тогда для методов интерполяции Ньютона и Лагранжа при d=30 в классе инициальных (4,2,2) – автоматов выполняется отношение ndN ndL и функция N L NL F принимает значение F(n 30, n 30, n 30 ) = 0,65 (метод интерполяции Ньютона с оценкой 0,65 точнее метода Лагранжа).

Теорема 2.1.2. Пусть узлами интерполяции для геометрического образа длины d каждого автомата A=(S, {0,1}, Y,,, s0) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов A0=(S, {0}, Y, 0, 0, s0) и A1=(S, {1}, Y, 1, 1, s0) автомата A. Тогда для методов интерполяции Ньютона и Лагранжа при d= в классе инициальных (4,2,2) – автоматов выполняется отношение nd nd N L и функция F принимает значение F(n 62, n L, n 62 ) = 0,44 (метод интерполяции N NL Ньютона с оценкой 0,44 точнее метода Лагранжа).

Теорема 2.1.3. Пусть узлами интерполяции для геометрического образа длины d каждого автомата A=(S, {0,1}, Y,,, s0) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов A0=(S, {0}, Y, 0, 0, s0) и A1=(S, {1}, Y, 1, 1, s0) автомата A. Тогда для методов интерполяции Ньютона и Лагранжа при d=126 в классе инициальных (4,2,2) – автоматов выполняется отношение N L NL nd nd и функция F принимает значение F(n 126, n 126, n 126 ) = 0,14 (метод N L интерполяции Ньютона с оценкой 0,14 точнее метода Лагранжа).

Теорема 2.1.4. Пусть узлами интерполяции для геометрического образа длины d каждого автомата A=(S, {0,1}, Y,,, s0) из класса инициальных (4,2,2)-автоматов являются точки геометрических образов автономных подавтоматов A0=(S, {0}, Y, 0, 0, s0) и A1=(S, {1}, Y, 1, 1, s0) автомата A. Тогда для методов интерполяции Ньютона и Лагранжа при d=126 в классе инициальных (4,2,2) – автоматов выполняется отношение F(n 254, n L, n 254 ) = 0,14 (метод N NL nd nd и функция F принимает значение N L интерполяции Ньютона с оценкой 0,14 точнее метода Лагранжа).

Теорема 2.2.1. Пусть узлами интерполяции для геометрического образа длины d каждого автомата A=(S, {0,1}, Y,,, s0) из класса линейных (8,2,2) автоматов являются точки геометрических образов автономных подавтоматов A0=(S, {0}, Y, 0, 0, s0) и A1=(S, {1}, Y, 1, 1, s0) автомата A. Тогда для методов интерполяции Ньютона и Лагранжа при d=254 в классе инициальных линейных (8,2,2) – автоматов выполняется отношение n d n L и функция F N d принимает значение F(n 254, n L, n 254 ) = 0,012 (метод интерполяции Ньютона с N NL оценкой 0,012 точнее метода Лагранжа).

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

Определение 3.1. Пусть L – геометрическая кривая и – отрезок на оси абсцисс, на котором определена часть кривой L ( или вся кривая L). Эту часть кривой будем обозначать L ().

Теорема 3.1. Пусть a = {A i }iI - семейство инициальных автоматов, где Ai=(Si, X, Y, i, i, s 0 i ), s 0i S i, а b = {g i }iI - семейство их геометрических образов, расположенных соответственно на кривых из семейства L = {L i }iI.

Если существует отрезок оси абсцисс, на котором для любых i, j I, при i j, выполняется система равенств {L i ( )} {L j ( )} = и на отрезке определены некоторые точки геометрических образов из семейства, то отрезок содержит решение простым безусловным экспериментом задачи распознавания автомата относительно семейства.

В четвертой главе разработаны алгоритмы оценки сложности законов функционирования автоматов на основе имеющихся оценок сложности для стандартного набора автоматов. Для этого стандартные автоматы предполагаются заданными геометрическими кривыми для примера выбранными из Международного французского банка математических кривых ENCYCLOPDIE DES FORMES MATHMATIQUES REMARQUABLES (т.е.

представленными последовательностями вторых координат точек, интерпретируемых как последовательности вторых координат точек геометрических образов автоматов) и последовательностями в приближениях величин из массива H (см.стр.9).

Сложность оценивается по показателям спектра рекуррентных описаний последовательностей вторых координат точек геометрических образов законов функционирования автоматов, расположенных на кривых из Международного французского банка математических кривых ENCYCLOPDIE DES FORMES MATHMATIQUES REMARQUABLES. Получены оценки сложности законов функционирования автоматов из класса (4,2,2)-автоматов и его подклассов.

Полученная оценка для каждого инициального автомата A=(S, X, Y,,, s0), где |Y| = l, распространяется на оценку сложности l! изоморфных по выходам автоматов. Введем множество am (Hd ) = {Ad (e), Ad (p), Ad (j), Ad ( 2 ), Ad (3 2 ), Ad (ln(2)), Ad (ln(10)), Am (z(3)), Am (C), Am (g)}, m m m m m m m d d d где m – число входных сигналов автомата, d – длина последовательности, интерпретируемой как последовательность вторых координат точек геометрического образа автомата, b H d, Hd – множество начальных отрезков длины d последовательностей, определяющих элементы из массива H, m - дискретный детерминированный автомат, определяемый величинами Ad (b) m, d и.

Теорема 4.1.1. Множество законов функционирования автоматов из a m (H d ), для d=1000000, по нулевому уровню W0 спектра W разбивается на класса эквивалентности по сложности: {A m (e), A d (p), A d (j), Ad (3 2 ), A m (z(3))} и m m m d d и по первому уровню W1 спектра W A m ( 2 ), A d (ln(2)), A m (ln(10)), A m (C), A d (g)}, m m d d d образуют одноэлементные классы эквивалентности по сложности.

Теорема 4.1.2. Множество законов функционирования автоматов из a m (H d ), для d=1000, по нулевому уровню W0 спектра W разбивается на { Ad (e), A d (3 2 ), A m (z(3)) } и m m класса эквивалентности по сложности: d {A m (p), A m (j), A d ( 2 ), A d (ln(2)), A m (ln(10)), A d (C), A d ( g)} ;

m m m m и по первому d d d уровню W1 спектра W образуют одноэлементные классы эквивалентности по сложности.

Автор выражает глубокую благодарность профессору В.А.Твердохлебову за руководство работой над диссертацией.

Список использованной литературы 1. Айзерман М.А. и др. Логика. Автоматы. Алгоритмы.–М.:Физматгиз,1963.

2. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. –М.: Наука, 1997.

3. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. – Саратов: Изд-во Сарат.ун-та, 1986.

4. Богомолов А. М., Твердохлебов В. А. Диагностика сложных систем. – Киев: Наук. думка, 1974.

5. Гилл А. Введение в теорию конечных автоматов. – М.: Наука,1966.

6. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз,1962.

7. Глушков В.М. Абстрактная теория автоматов // Успехи мат. наук. 1961,Т. 16. Вып.5 (101). С.3-62.

8. Дискретная математика и математические вопросы кибернетики / Под.ред. С.В.Яблонского и О.Б.Лупанова. – М.:Наука,1974.

9. Кратко М. И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов. Докл. АН СССР, 1964, Т.155.

№1, С.35-37.

10. Кудрявцев В.Б., Алёшин С.В., Подколзин А.С. Введение в теорию автоматов. – М.: Наука,1985.

11. Мур Э.Умозрительные эксперименты с последовательными машинами / Автоматы. Сб. статей под ред. К.Шеннона и Д.Маккарти, – М.:ИИЛ, 1956.

С.179-213.

12. Нейман Дж.фон. Теория самовоспроизводящихся автоматов. – М.:

Мир,1971.

13. Твердохлебов В.А. Геометрические образы законов функционирования автоматов.– Саратов: Изд-во «Научная книга», 2008.

14. Яблонский С.В. Введение в дискретную математику. – М.:Наука, 1988.

Список публикаций автора по теме диссертации A1. Епифанов А.С. Автоматная интерпретация целочисленных последовательностей. // Изв. Сарат. ун-та. Новая серия. Сер. Математика, Механика, Информатика. - 2010. - Т. 10,вып.4.С.58-64.

A2. Епифанов А.С. Анализ геометрических образов законов функционирования автоматов. // Управление большими системами. Выпуск 24.

М.: ИПУ РАН, 2009. С.81-98.

A3. Епифанов А.С. Анализ фазовых картин дискретных динамических систем.–Саратов:Изд-во «Научная книга», 2008. ISBN 978-5-9758-0926- A4. Епифанов А.С. Интерпретация спектра характеристик дискретных систем при проектировании./Материалы 6-ой международной конф.

«Автоматизация проектирования дискретных систем». Т.1, Минск.2007.C.73- A5. Епифанов А.С. Интерполяция фазовых картин дискретных детерминированных систем. // «РАДIОЕЛЕКТРОННI I КОМП’ЮТЕРНI СИСТЕМИ», Харкiв, №5,2008. C.128-132.

A6. Епифанов А.С. Анализ эффективности применения методов интерполяции для доопределения законов функционирования сложных систем. / Информационные технологии и системы (ИТиС’08):сборник трудов конференции. – М.: ИППИ РАН, 2008. – 517с. C.104-108.

A7. Епифанов А.С. Классификация законов функционирования дискретных динамических систем на основе спектра параметров. / V Всероссийская школа семинар молодых ученых «Управление большими системами»: Сборник трудов.-Т.1. – Липецк, ЛГТУ,2008.С.17-23.

A8. Епифанов А.С. Построение и анализ классов (H,m,d(H))-автоматов. / V Всероссийская школа-семинар молодых ученых «Управление большими системами»: Сборник трудов.-Т.1. – Липецк, ЛГТУ,2008.С.23-30.

A9. Епифанов А.С. Использование интерполяции и экстраполяции для анализа законов функционирования сложных систем. – Материалы второй международной конференции "Управление развитием крупномасштабных систем MLSD'2008". М.: 2008. – С.232-235.

A10. Епифанов А.С. Анализ фазовых картин дискретных динамических систем с использованием спектра динамических параметров. // «РАДIОЕЛЕКТРОННI I КОМП’ЮТЕРНI СИСТЕМИ», Харкiв,№5,2009. С.111-116.

A11. Епифанов А.С. Анализ дискретных динамических систем, заданных в форме числовых структур.// «РАДIОЕЛЕКТРОННI I КОМП’ЮТЕРНI СИСТЕМИ», Харкiв,№6,2009.C.118-122.

A12. Епифанов А.С. Анализ геометрических образов и свойств автоматов. Восьмая международная конференция «Дискретные модели в теории управляющих систем»: Москва, 6—9 апреля, 2009 г.: Труды / Отв. ред. В. Б.

Алексеев, В.А.Захаров. — М.: Издательский отдел факультета ВМиК МГУ им.

М.В.Ломоносова;

МАКС Пресс, 2009. – 380с. С.87-92.

A13. Епифанов А.С. Классификация дискретных детерминированных автоматов по свойствам геометрических образов. Материалы 7-ой молодежной научной школы по дискретной математике и ее приложениям. ИПМ РАН им.М.В.Келдыша. М. Часть 1. Под ред. А В.Чашкина.2009г. С.34-39.

A14. Епифанов А.С. Метод диагностирования программируемых логических интегральных схем с использованием геометрических образов. / Науково-технічний журнал “ІНФОРМАЦІЙНО - КЕРУЮЧІ СИСТЕМИ НА ЗАЛІЗНИЧНОМУ ТРАНСПОРТІ “, №4(77), Харьков, 2009, С.152-155.

A15. Епифанов А.С. Автоматная интерпретация фрагментов последовательности ДНК. / Информационные технологии и системы (ИТиС’08):сборник трудов конференции.–М.: ИППИ РАН, 2009.C.318-323.

A16. Епифанов А.С. Анализ операций совмещения геометрических образов законов функционирования автоматов. // «РАДIОЕЛЕКТРОННI I КОМП’ЮТЕРНI СИСТЕМИ», Харкiв,№5,2010.C.219-223.

A17. Епифанов А.С. Оценка сложности и классификация маршрутов по сложности на основе спектра параметров.// «РАДIОЕЛЕКТРОННI I КОМП’ЮТЕРНI СИСТЕМИ», Харкiв,№7,2010.C.180-184.

A18. Епифанов А.С. Метод оценки сложности и классификации законов функционирования дискретных детерминированных автоматов. //Материалы Х Международного семинара "Дискретная математика и ее приложения" / Под редакцией О.М.Касим-Заде. - М.: Изд-во механико-математического факультета МГУ, 2010. - 549с. С.358-361.

A19. Епифанов А.С. Метод оценки сложности законов функционирования автоматов на основе дискретных riv-функций. Научно-тех. журнал «Информационно-управляющие системы на железнодорожном транспорте», №4(83), Харьков, 2010, с. 119-122.

A20. Епифанов А.С. Оценка сложности законов функционирования автоматов с использованием дискретных сегментных функций. Материалы седьмой Международной научно-практической конференции "Теоретические и прикладные аспекты построения программных систем". Киев, 2010. С.225-234.

Подписано в печать 07.02.2011. Формат 60x84 1/16. Бумага офсетная.

Гарнитура Times New Roman. Печать RISO.

Объем 1,0 печ.л. Тираж 120 экз. Заказ № Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю.Б. Свидетельство № 410000, г.Саратов, ул.Московская, 152, офис

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.