Министерство образования и науки Российской Федерации
Федеральное Государственное бюджетное образовательное учреждение высшего профессионального образования “Саратовский государственный университет имени Н.Г.Чернышевского” (СГУ)
УДК 004.942 + 519.713
-
УТВЕРЖДАЮ
|
Ректор Федерального государственного бюджетного образовательного учреждения высшего профессионального образования “Саратовский государственный
университет имени Н.Г.Чернышевского”
_____________________ Л.Ю.Коссович
«_____» _________________2011г.
МП
|
ОТЧЕТ
О НАУЧНО-ИССЛЕДОВАТЕЛЬСКОЙ РАБОТЕ
по Государственному контракту от 7 сентября 2009 года № 07.Р20.11.0029
“Подготовка и переподготовка профильных специалистов на базе центров образования и разработок в сфере информационных технологий в Южном и Северо-Кавказском федеральных округах”
Тема НИР: “ Динамические системы, определяемые геометрическими образами автоматов ”
Научный руководитель Л.Б.Тяпаев
Саратов 2011 г.
Список исполнителей
Научный руководитель НИР, заведующий кафедрой ДМИТ СГУ, к.ф.-м.н., доцент
|
_________________
подпись, дата
|
Л.Б. Тяпаев (введение, реферат, заключение)
|
Исполнители темы
|
|
|
Студент 5 курса факультета КНиИТ СГУ
|
_________________
подпись, дата
|
М.В. Карандашов
(раздел 1,2,3)
|
Студент 5 курса факультета КНиИТ СГУ
|
_________________
подпись, дата
|
М.Б. Куанышев
(раздел 1,2)
|
Студентка 2 курса факультета КНиИТ СГУ
|
_________________
подпись, дата
|
Д.В. Василенко
(раздел 3)
|
Реферат
Отчет 72 с., 12 рис., 4 табл., 24 источника, 2 прил.
конечные автоматы, ГЕОМЕТРИЧЕСКИЕ ОБРАЗЫ АВТОМАТОВ, АФФИННЫЕ КЛАССЫ, ФУНКЦИОНАЛЬНЫЕ графы, конечные динамические системы.
Научно-исследовательская работа по теме «Динамические системы, определяемые геометрическими образами автоматов» выполняется в рамках федеральной целевой программы развития образования на 2011-2015 годы по Государственному контракту от 7 сентября 2011 года №07.Р20.11.0029.
Объектом исследования является дискретная динамическая система. Пространство состояний динамической системы – конечное множество геометрических образов конечных автоматов. Геометрические образы автоматов суть множества точек плоскости с рациональными координатами, прообразами которых являются множества входных слов автомата и его реакций. Фазовое пространство динамической системы формируется посредством ортогональных и аффинных преобразований пространства состояний.
Цель работы — изучение аффинных преобразований на множестве геометрических образов конечных автоматов, построение динамических систем в фазовом пространстве геометрических образов, характеризация произведения динамических систем.
В процессе работы проводились теоретические и экспериментальные исследования динамических систем, определяемых геометрическими образами автоматов, произведений динамических систем заданного типа, аффинных преобразований геометрических образов конечных автоматов.
В результате исследования были определены коэффициенты аффинных преобразований для автономных автоматов с двумя состояниями и фиксированным числом выходных символов. Выяснено, что найденные коэффициенты совпадают с коэффициентами аффинных преобразований для автономных автоматов с произвольным числом состояний и фиксированным числом выходных символов. Установлено, что множество аффинных преобразований для произвольного автомата с фиксированными числом состояний, входных и выходных символов идентично множеству преобразований для автономного автомата с двумя состояниями и фиксированным числом выходных символов. Проведён ряд вычислительных экспериментов, целью которых являлось получение множеств коэффициентов аффинных преобразований и разбиение геометрических образов на классы эквивалентности. Для этого были разработаны соответствующие алгоритмы и получены оценки их временной сложности. Определены произведения динамических систем, порожденных классами аффинной эквивалентности геометрических образов конечных автоматов. Описана геометрическая структура функционального пространства для динамических систем типа «аттрактор-притягиваемая цепь», определены количественные характеристики таких систем (количество циклов-аттракторов и их длины, количество притягиваемых деревьев, число шагов динамики до аттрактора вдоль притягиваемых деревьев); определены расстояния между деревьями, притягиваемые к аттрактору; определены периоды расположения точек ветвления.
Показатели эффективности: полиномиальная сложность алгоритмов, теоретическое обоснование разработанных методов разбиения геометрических образов автоматов на классы аффинной эквивалентности.
Настоящий отчет является заключительным. Работа в рамках проекта завершена в соответствии с календарным планом Государственного контракта от 7 сентября 2011 года №07.Р20.11.0029.
Содержание
Нормативные ссылки
В настоящем отчете использованы ссылки на следующие стандарты.
ГОСТ 15.101–98
|
Система разработки и постановки продукции на производство. Порядок выполнения научно-исследовательских работ
|
ГОСТ 19.001-77
|
ЕСПД. Общие положения.
|
ГОСТ 19.401-78
|
ЕСПД. Текст программы. Требования к содержанию и оформлению
|
ГОСТ 7.1-2003
|
Система стандартов по информации, библиотечному и издательскому делу. Библиографическая запись. Библиографическое описание. Общие требования и правила составления
|
ГОСТ 7.32-2001
|
Система стандартов по информации, библиотечному и издательскому делу. Отчет о научно-исследовательской работе. Структура и правила оформления
|
Определения, обозначения и сокращения
В настоящем отчете о НИР применяются следующие термины с соответствующими определениями, обозначениями и сокращениями.
Научно – исследовательская работа (НИР)
|
Комплекс теоретических и (или) экспериментальных исследований, проводимых с целью получения обоснованных исходных данных, изыскания принципов и путей создания (модернизации) продукции.
|
Автомат
|
Автоматом называется набор  , где
S – множество состояний,
X – входной алфавит,
Y – выходной алфавит,
δ:S×X→S – функция перехода,
λ:S×X→Y – функция выхода.
|
Уравнения динамики
|
Автомат функционирует в абстрактном целочисленном положительном времени, совмещая состояния и сигналы в соответствии с уравнениями динамики:
 ,
 .
|
Конечный автомат
|
Автомат  называется конечным, если  – конечные множества.
|
Инициальный автомат
|
При выделении в автомате так называемого начального состояния  говорят об инициальном автомате  . Тогда к уравнениям динамики добавляется начальное условие
 .
|
Поведение инициального автомата
|
Поведение инициального автомата определяется множеством пар, первыми элементами которых являются входные последовательности, а вторыми – соответствующие выходные:
 .
|
Автономный автомат
|
Автомат называется автономным, если  .
|
Отображение, определяемое автоматом
|
Функции  ,  можно продолжить на множество конечных слов следующими рекуррентными правилами:
где  ,  ,  – произвольные элементы.
Отображение  определяется автоматом , если  для каждого  .
|
Эквивалентность автоматов
|
Два автомата, определяющие одно отображение, называются эквивалентными.
|
Поведение автомата
|
Поведение автомата определяется множеством
 .
|
Функциональная кривая
|
Кривая  называется функциональной кривой, если есть график некоторой непрерывной функции.
|
Аффинная эквивалентность кривых
|
Две кривые называются аффинно эквивалентными, если они могут быть получены одна из другой с помощью аффинного преобразования.
|
Аффинный класс кривой
|
Совокупность всех кривых, аффинно эквивалентных какой-нибудь определенной кривой , называется аффинным классом кривой .
|
|
Класс автономных автоматов, содержащий все автономные автоматы с фиксированным числом  состояний и числом  выходных сигналов.
|
|
Множество геометрических образов всевозможных инициальных автоматов из класса .
|
|
Множество пар коэффициентов преобразований образов из .
|
ДС
|
Динамическая система.
| |
,
,
,
