Введение к работе
Актуальность темы диссертации. В связи с развитием информационных технологий и созданием новых языков программирования актуальными остаются задачи, связанные с разработкой трансляторов, для перевода программ с одного языка на другой.
Для реализации отдельных фаз трансляции программы используют известные модели: формальные грамматики, конечные автоматы, автоматы с магазинной памятью и т.д. Данные модели являются хорошо изученными и применяемыми в области информатики, связанной с теорией обработки формальных языков.
Весомый вклад в развитие теории конечных автоматов внесли Глушков В.М., Бернштейн Л.С., Скляров В.А., Баранов СИ., Трахтенброт Б.А., Бауэр В., Мили Г., Мур Э., Гилл А., Хаффмен Д., Хопкрофт Д., Рабин М., Скотт Д. и др. В исследованиях учёных решены вопросы, связанные с проблемой минимизации, проблемой эквивалентности и эквивалентных преобразований конечных автоматов. В работе В.М. Глушкова разработана теоретическая база для решения задач, возникающих при синтезе цифровых автоматов. Кроме конечного автомата известна модель многоленточного автомата, которая является расширением обычного конечного автомата. В многоленточном автомате в отличие от конечного автомата работа производится на нескольких лентах. Теория многоленточных автоматов развивалась отечественными и зарубежными учёными Подловченко Р.И., Хачатряном В.Е., Летичевским А.А, Бёрдом Р., Гриффитсом Т., Харью Т., Кархумяки Дж., Тамм X. и др.
Для многоленточных автоматов в общем случае решены проблемы эквивалентности и эквивалентных преобразований. Однако, эти методы не всегда применимы для подклассов многоленточных автоматов, которые наиболее часто используются при решении конкретных практических задач. Проблема минимизации многоленточных автоматов остаётся открытой. Существуют решения этой проблемы для отдельных подклассов многоленточных автоматов.
Известны реализации специализированных языков, в которых многоленточный автомат используется, в качестве модели для обработки строк. Запрос, написанный на специализированном декларативном языке, представляет собой пользовательскую функцию для обработки строк базы данных, которая преобразуется в многоленточный автомат. Полученный по функции многоленточный автомат хранится в виде объектного кода и используется при вызове функции. Данный подход позволяет расширять реализованный в СУБД язык, вызывая из него функции, написанные на специализированном декларативном языке. Следовательно, многоленточный автомат даёт возможность использовать его в качестве модели представления программ специализированных языков, работающих со строками. Однако, недостаточная проработка теории многоленточных автоматов, не позволяет
эффективно их применять в качестве моделей для преобразования информационных структур. Например, в качестве моделей запросов специализированного языка к базам данных, в качестве моделей работы многопроцессорной системы.
Диссертационная работа «Фрагментные преобразования структуры многоленточных автоматов», в которой развивается теория многоленточных автоматов для повышения эффективности преобразования информационных структур, является актуальной.
Работа связана с развитием общенаучных направлений РФ и поддержана грантом ФЦП «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы», ГК №16.740.11.0045 от 01.09.2010 г.; грантом РФФИ, проект 09-01-00277, «Обобщенная проблема минимизации многоленточных автоматов при моделировании управляющих систем», 2009-2011 гг.
Целью настоящей работы является развитие теоретических основ минимизации многоленточных автоматов для повышения эффективности преобразования информационных структур.
Для достижения поставленной цели были сформулированы и решены следующие задачи:
разработать систему эквивалентных фрагментных преобразований в подклассе многоленточных автоматов и доказать её полноту;
обобщить трансформационный метод решения проблемы эквивалентности для подклассов многоленточных автоматов;
решить обобщенную проблему минимизации для подкласса многоленточных автоматов;
разработать алгоритмы и программы минимизации многоленточных автоматов;
исследовать временную сложность полученных алгоритмов.
Объектом исследования диссертационной работы являются
трансляторы специализированных языков запросов к базам данных.
В качестве предмета исследования рассматривался многоленточный автомат.
Методы и средства исследований. При решении указанных задач использовались методы исследования из теории автоматов, математической логики, теории алгоритмов, математическое моделирование, интегрированные среды разработки программ.
Положения, выносимые на защиту:
Полная система фрагментных эквивалентных преобразований для подкласса многоленточных автоматов.
Модификация трансформационного метода, позволяющая решить проблему эквивалентности для однородных многоленточных автоматов;
3. Автоматизированная система минимизации для подкласса многоленточных автоматов, включающая процедуру минимизации, алгоритмы и комплекс программ.
Достоверность и обоснованность научных положений и выводов обусловлена корректностью математических выкладок, доказательствами теорем и утверждений, согласованностью основных теоретических решений с их практической реализацией, а также результатами вычислительных экспериментов, подтверждающих непротиворечивость основных теоретических результатов.
Научная новизна состоит в:
разработке новой системы эквивалентных преобразований для подкласса многоленточных автоматов;
формулировке и доказательстве теоремы о полноте предложенной системы эквивалентных преобразований;
модификации трансформационного метода для решения проблемы эквивалентности в подклассах многоленточных автоматов;
разработке алгоритмов минимизации для подкласса многоленточных автоматов.
Практическая полезность работы заключается в следующем:
1)в реализации результатов диссертации при проектировании интерпретатора специализированного языка запросов автоматизированной системы дистанционной передачи радиолокационных измерений с приёмного устройства на спецвычислитель, внедрённой в ООО «Научно-производственное предприятие «Энергетические и информационные технологии» Белгородского государственного университета».
2) разработаны алгоритмы процедуры минимизации для подмножества многоленточных автоматов, использованные при выполнении фундаментальных исследований, выполненных в рамках тематического плана НИР ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), проект «Методы и алгоритмы преобразования структурированного представления модели управления последовательностью процессов, наделенных частично-коммутативными свойствами», 2010-2012 гг.
3)в использовании результатов диссертационной работы в учебном процессе кафедры математического и программного обеспечения информационных систем ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет» (НИУ «БелГУ), при подготовке студентов по специальности 010503 «Математическое обеспечение и администрирование информационных систем», в дисциплине «Теория вычислительных процессов и структур», при обучении студентов по направлению подготовки 010300.68 «Математика. Компьютерные науки», в дисциплине «Теоретическая информатика».
Апробация работы. Основные положения и результаты диссертационного исследования докладывались и обсуждались на Восьмой
международной конференции «Дискретные модели в теории управляющих систем» (Москва, МГУ, 2009), Первой международной научно-технической конференции «Компьютерные науки и технологии» (Белгород, БелГУ, 2009), Десятом международном семинаре «Дискретная математика и ее приложения» (Москва, МГУ, 2010), Десятой международной научно-технической конференции «Проблемы информатики и моделирования» (Харьков, Национальный технический университет «ХПИ», 2010), на международной научно-технической конференции «Информационные системы и технологии» (Орел, ОрелГТУ, 2010), на международной научно-технической интернет-конференции «Информационные системы и технологии» (Орел, ОрелГТУ, 2011), Девятнадцатой международной научно-практической конференции «Информационные технологии: наука, техника, технология, образование, здоровье» (Харьков, Национальный технический университет «ХПИ», 2011).
По результатам исследований опубликовано 16 печатных работ (из них 6 в изданиях из списка ВАК РФ), а так же получены акт о внедрении результатов диссертационной работы, свидетельства об официальной государственной регистрации программ для ЭВМ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа изложена на 125 страницах основного текста, включающего 65 рисунков, список литературных источников из 87 наименований и приложения, содержащего акт о реализации результатов диссертационной работы, свидетельства о государственной регистрации программ для ЭВМ, комплекс программ.
