Введение к работе
Актуальность работы. Информатизация общества относится к глобальным тенденциям его развития, что определяет потребность^ в создает эффективных лингвистических, алгоритмических, программных и технических средств обработки информации. Особую значимость приобретает проблема создания средств обработки символьной информации, тоскольку она занимает до 90% обьемов циркулирующей информации в ювременных системах обработки данных. Символьная информация имеет Зольшие обьемы и разнообразие (публикации, текстовые документы, затеи программ, архивные данные и т.д.). Следует отметить, что ежеминутно в мировой практике создается до 500 тысяч страниц одних только документов.
Символьная информация в виде текстов составляет основу как для формирования текстов задач, так и алгоритмов их решения. Высокая социальная значимость проблем обработки символьной информации (ОСИ) определила существование дорогостоящих государственных и межгосударственных научно-исследовательских программ, например, таких как SPI (США), ALVEY (Великобритания), TELETEXT, JESSI (страны Европейского союза) и др.
Доминирование символьной информации, быстрый рост ее обьемов и разнообразия требует адекватных алгоритмических, программных и технических средств обработки. Фундаментальным проблемам ОСИ посвятили свои работы отечественные и зарубежные авторы Р. Грисоулд, А.Н. Колмогоров, Дж. Маккартн, А.А. Марков, Т. Мотоохо, Дж. Фон Нейман, Д.А. Поспелов, Э. Пост, В.Ф. Турчин, А. Тьюринг, Д. Уоррен, А. Черч, А. Шенгахе и многие другие известные ученые. В академических изданиях и специальном литературе имеются достаточные основания для решения проблемы по созданию высокоскоростных сие.лі ОСИ. Между тем, существующие системы ОСИ базируются на основе таких методов и средств, которые не обеспечивают требуемой скорости решения прикладных задач, вследствие того, что во всех универсапьных алгоритмических системах ОСИ отсутствуют инструментальные средстве акселерации символьных вычислений, что создаст проблемную ситуацию. Требуемая производительность систем ОСИ должна составлять сотни миллионов лс и-ческнх выводов в секунду (ЛИПС), а достигаемая на сегодняшний день производительность составляет единицы миллионов ЛИПС. Поэтому дальнейшее развитие алгоритмических, программных и технических средств ОСИ связывается специалистами с решением актуальной и перспективной задачи по разработке новых методов оНаботки и соответствующих им принципов структурно-функциональной' организации устройств ОСИ.
*
Научный аспект решаемой задачи заключается в разработке форі представления конструктивных обьектов, способов ОСИ, и обосновани их алгоритмической реализуемости, а также в разработке параллельны устройств ОСИ. Практический аспект решаемой задачи включает в себ структурно-функциональные схемы универсальных символьных пара/ лельных процессоров, работающих на основе алгоритмической проду» ционной парадигмы.
Основная часть диссертационной работы выполнялась в рамка госбюджетной НИР по распоряжению Госкомвуза №10-36-41, ИН/10-2С 03 от 16.03.92 г. с пролонгацией до 1999 г. при непосредственном участи автора.
Цель работы заключается в разработке форм представления конст руктивных обьектов, акселеративных способов ОСИ и в синтезе струї турно-фувдсциональных схем параллельных символьных процессоров, аг паратно поддерживающих продукционные алгоритмические схемы.
Основные задачи диссертационного исследования:
1.Разработка форм представления конструктивных обьектов.
2.Разработка способов и алгоритмов сопоставления и модификаци конструктивньпс обьектов в позиционных форматах представления.
З.Адаптация существующих методов модификации каноническо системы алгорифмов Маркова к разработанным формам представленії конструктивных обьектов.
4.Разра6отка системы операций исполнительного устройства.
5.Струкгурно-функциональный синтез параллельного символьног процессора и исследование его скоростных характеристик.
Методы исследования базируются на аппарате теории алгоритмої математической логики, в том числе конструктивной, теории конечны автоматов и проектирования ЭЦВМ. Верификация корректности алгс ритмов функционирования разработанных устройств и эксперименташ ные исследования производительности устройств проводились с поме щью компьютерного моделирования.
Научная новизна работы заключается в решении научной задачи п созданию высокопроизводительных параллельных продукционных уст ройств ОСИ. В результате проведенных исследований получены следук щие основные научные результаты:
,1. Впервые разработан способ представления текстовых данных памяти ЭВМ (параллельное позиционное представление данных) и алп ритмы операции символьного поиска и подстановки. Проведено доказ; тельство корректности алгоритмов поиска и подстановки.
2. На основе параллельного позиционного способа представлени данных разработан и формализован параллельный позиционный аддитш ный способ представления данных, позволяющий организовать хранены данных в виде списка, что позволило сократить временные затраты i/a р<
энфигурацию слова при выполнении операции подстановки. Разработа-ы и формализованы алгоритмы выполнения операции символьного по-ска и подстановки и проведено доказательство их корректности.
3. Методы модификации канонической снстСлы алгорифмов А.А
Іаркова адаптированы к предложенным параллельным способам пред-гавления данных. Уточнено определение алфавитной переменной в при-сняемом контексте и формализованы алгоритмы операции конкретиза-ии и подстановки алфавитной переменной.
Практическая ценность работы состоит в следующем.
-
На основе проведенных теоретических исследований разработана груктурно-функциональная ор/анизация высокопроизводительных уни-ерсальных параллельных символьных устройств ОСИ со встроенными редствамн акселерации операций сопоставления и подстановки, базн-ующихся на модифицированных алгорифмах А.А.Маркова.
-
Разработанные способы представления текстовых данных и аксе-ерации операций символьного поиска и подстановки могут быть нсполь-оваиы для разработки систем ОСИ различной конфигурации и назначе-[ия и создают основу для постановки НИОКР.
Реализация результатов работы. Результаты диссертационной рабо-ы нашли применение при выполнении госбюджетных НИР Курского го-ударстпепного технического университета, практически реализованы и шсдрсны в СКБ "Авиаавтоматнка" (г. Курск) и учебном процессе Кур-:когч> государственного технического университета.
Апробация работы. Результаты работы докладывались и обсужда-шсь на III международной конференции "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и импольной информации" (Курск, 1997), IV международной конференцій "Актуальные проблемы электронного приборостроения" (Новосибирск, 1998), IV международной конференции "Теория і техника передані, приема и обработки информации" (Туапсе, 199S), I всероссийской научно-технической конференции "Компьютерные технологии в науке, проектировании и производстве" (Нижний Новгород, 1999).
Основные положения, выносимые па защиту;
-
Параллельный позиционный способ представления текстовых данных и алгоритмы выполнения операций сим вольного сопоставленнч и подстановки над данными, представленными в такой форме.
-
Параллельный позиционный аддитивный способ представления текстовых данных и алгоритмы выполнения операций символьного сопоставления и подстановки над данными, представленными в такой форме.
-
Модификации канонической системы алгорифмов' А.А. Маркова, адаптированные к обработке данных, представленных в параллельном позиционном (аддитивном) формате. .'-'
-
Алгоритмы работы и структура продукционного устройства, ре лизующгго модифицированную алгоритмическую систему А.А. Маркої над данными, представленными в параллельной позиционной форме.
-
Алгоритмы работы и структура продукционного параллельно] устройства, реализующего модифицированную алгоритмическую систел/ А.А. Маркова над данными, представленными в списковой параллельно позиционной аддитивной форме.
-
Результаты компьютерного моделирования работы разработаї ных устройств.
Публикации по работе. По материалам диссертации опубликовано печатных работ и 1 рукописная.
Структура и обьем работы. Диссертация состоит из введения, четь рех глав и заключения, изложенных на №3- страницах машинописної текста, содержит 61 рисунок, "34 таблицу, список литературы из Ч\ н; именований и 12> приложений объемом в 114 страниц.
