Главная » 2014 » Июль » 22 » Скачать Синтез эффективных математических моделей дискретной обработки данных на основе алгебраической и понятийной декомпозиции бесплатно
9:38 PM
Скачать Синтез эффективных математических моделей дискретной обработки данных на основе алгебраической и понятийной декомпозиции бесплатно
Синтез эффективных математических моделей дискретной обработки данных на основе алгебраической и понятийной декомпозиции предметной области
Диссертация
Автор: Выхованец, Валерий Святославович
Название: Синтез эффективных математических моделей дискретной обработки данных на основе алгебраической и понятийной декомпозиции предметной области
Справка: Выхованец, Валерий Святославович. Синтез эффективных математических моделей дискретной обработки данных на основе алгебраической и понятийной декомпозиции предметной области : диссертация доктора технических наук : 05.13.11, 05.13.15 / Ин-т проблем упр. им. В.А. Трапезникова РАН - Москва, 2007 - Количество страниц: 475 с. ил. Москва, 2007 475 c. :
Объем: 475 стр.
Информация: Москва, 2007
Содержание:
Глава 1 Дискретная обработка данных
11 Математические модели
12 Декомпозиция дискретных функций
13 Логическая обработка данных
14 Дискретные преобразователи
15 Профаммная инженерия
16 Концептуальный подход
17 Представление и обработка знаний
18 Семантика формальных язьпсов
Выводы к Главе
Глава 2 Понятийный анализ
21 Содержательная постановка задачи
22 Основные определения
23 Абстрагирование понятий
24 Семантическая теория понятий
25 Синтаксическая теория понятий
26 Сравнительный анализ формализма К М Б Л И О Т Ь К А
27 Методика понятийного анализа
28 Заключительные замечания д18181-09
Выводы к Главе
Глава 3 Контекстная технология
31 Содержательная постановка задачи
32 Принципы контекстной обработки
33 Протоязьпс понятийной модели
34 Семантика проблемного языка
35 Заключительные замечания
Выводы к Главе
Глава 4 Система программирования
41 Содержательная постановка задачи
42 Разнесенный грамматический разбор
43 Сравнительный анализ систем
44 Архитектура системы программирования
45 Организация обработки данных
46 Реализация компилятора
47 Заключительные замечания
Выводы к Главе
Глава 5 Алгебраическая декомпозиция
51 Содержательная постановка задачи
52 Основные понятия и определения
53 Образующие алгебры
54 Функциональная полнота
55 Синтез формул —
56 Заключительные замечания Вьшоды к Главе
Глава 6 Алгебраический синтез
61 Содержательная постановка задачи
62 Аналитические конструкции
63 Спектральный синтез формул
64 Алгебраический синтез формул
65 Заключительные замечания Вьшоды к Главе
Введение:
Диссертация содержит изложение основных результатов, полученных автором при исследовании проблемы синтеза эффективных математических моделей дискретной обработки данных на двух уровнях: формально-логическом и концептуально-онтологическом.Дискретная обработка - самый распространенный метод вычислений, лежапщй в основе современных вычислительных средств. На аппаратурном уровне дискретная обработка реализуется устройствами, состоящими из блоков, каждый из которых вьшолняет преобразование входных данных в выходные. Трассировка данных от выходов одних блоков ко входам других осуществляется их соединениями. Каждый такой блок, в свою очередь, может быть представлен как отдельное устройство, состоящее из других, более мелких блоков. В пределе, необходимом для практической реализации устройства, в качестве элементарных блоков используются логические элементы, имеющие физическую природу преобразования входных данных в вькодные.На программно-аппаратном уровне преобразование данных осуществляется в виде смены состояния информационной среды под управлением программы, сама информационная среда рассматривается как совокупность носителей данных, а программа представляется формализованным описанием этого процесса. Элементарными компонентами программ являются команды, вьшолняемые техническими средствами информационной системы. Более сложные компоненты - подпрограммы, являются элементарньв^и единицами вызова (адресации программ) и рассматриваются как именованные совокупности команд.Одна или несколько подпрограмм объединяются в модули, представляюпще собой единицы загрузки и хранения программ. Совокупность модулей образуют следующий уровень иерархии - программные средства, предназначенные для вьшолнения той или иной задачи по обработке данных. И, наконец, программы объединяются в комплексы и служат для регпения целого класса задач.Как в первом, так и во втором случае эффективность обработки данных определяется количеством операций (логических элементов, команд), которые необходимо вьшолнить. Однако, как при высокоуровневом моделировании - в рамках концептуальноонтологического подхода, так и при низкоуровневом моделировании - в рамках формально-логического подхода, не решена проблема, связанная с выбором методологии анализа и технологии декомпозиции предметной области, позволяющих получать формальное описание дискретной обработки данных, обеспечивающее эффективное решение стоящих прикладных задач. Более того, на настояпщй момент не существует единой теории, позво4 ляющей выработать критерии и оценить эффективность произвольной дискретной обработки данных, не прибегая к сравнению с другими ее реализациями.Цель предпринятого исследования - решение важной прикладной задачи преобразования высокозфовневого (первичного) описания предметной области в терминах содержательной постановки задачи в ее эффективное низкоуровневое представление, состояш,ее из последовательности команд (операций) вычислительного средства. Для достижения поставленной цели в диссертации разработана теория и обоснованы методы синтеза математических моделей предметной области, которые предназначены для эффективного решения задач дискретной обработьси данных аппаратурными и программно-аппаратными средствами.Объектом исследования является процесс обработки данных, реализуемый вычислительньпу1и средствами дискретного действия, а предметом исследования — математические модели предметной области, полученные на основе концептуальной, объектной, структурной, функциональной и логической декомпозиции.Обгцей задачей, решаемой в диссертации, является получение эффективных математических моделей дискретной обработки данных на основе формальной спецификации предметной области и решаемых в ней прикладных задач. Частньп^и задачами, вытекаюпщми из общей, являются: - разработка методологии анализа предметной области, позволяющей строить ее эффективные декомпозиционные схемы в виде синтаксически и семантически замкнутых (прозрачных) формальных спецификаций; - создание технологии обработки данных, основанной на отражении декомпозиционных схем предметной области в конструкциях специализированного предметного (проблемного) языка; - разработка методов описания семантики проблемного язьпса, обеспечивающих решение заданных прикладных задач путем дискретной обработки данных; - обоснование методики определения эффективности дискретной обработки данных и получение точных, приближенных и асимптотических оценок сложности синтезируемых математических моделей; - развитие общей теории дискретных функций на основе аппарата формальной декомпозиции и его использования для синтеза эффективных описаний дискретной обработки данных.Методика исследования основана на формально-логическом и концептуальноонтологическом моделировании. Концептуально-онтологическое моделирование осуществляется путем формальной спецификации результатов понятийного анализа предметной области, а формально-логическое - при алгебраической декомпозиции дискретных функций. Как в первом, так и во втором случае ищутся декомпозиционные схемы, позволяющие получать эффективные математические модели дискретной обработки данных..Основной результат диссертационной работы состоит в теоретической разработке и практическом решении задачи синтеза эффективных математических моделей дискретной обработки данных. Научная новизна полученных результатов определяется тем, что: - предложена методология понятийного анализа, позволяющая на основе четырех видов отображений понятий получать синтаксически и семантически замкнутые формальные спецификации предметной области; - разработана технология контекстной обработки данных, предназначенная для сокращения семантического разрьша между содержательными представлениями относительно предметной области и языком моделирования (программирования);; - решена задача описания семантики формальных язьпсов на основе метода математической индукции путем определения семантических категорий в процессе описания языка и описанными ранее средствами; - обоснована методика алгебраического синтеза дискретных функций и найдены точные верхние оценки сложности синтезируемых формул в асимптотической области и при конечной размерности задачи; - обобщена теория алгебраической декомпозиции дискретных функций в широком классе образующих алгебр, различаюшдхся требованиями к алгебраическим операциям.Практическая значимость полученных результатов заключается в разработке контекстной технологии программирования, при использовании которой получаются более эффективные и качественные программы, а также в обосновании методик алгебраического синтеза формул и оценки эффективности математических моделей дискретной обработки данных.Проверка полученных результатов осуществлена путем вьиислительного эксперимента, при котором, в частности: - разработана и исследована система контекстного программирования, позволяющая автоматизировать процесс перехода от высокоуровневой формальной спецификации предметной области к последовательности команд целевой вьгшслительной платформы, реализующей решение стоящих прикладных задач путем дискретной обработки данных; - реализованы алгоритмы спектрального и алгебраического синтеза форм дискретной обработки данных в виде формул, заданных в базисе произвольных бинарных операций; - подсчитана порождающая способность аналитических конструкций формул и оценена максимальная сложность спектральной и алгебраической декомпозиции дискретных функций.По результатам исследований опубликовано 50 работ, причем 8 из них, содержащие основные результаты, опубликованы в рецензируемых журналах из перечня ВАК. Диссертация состоит из введения, 6-ти глав, заключения и 5-ти приложений. Список цитированной литературы содержит 396 источников. Объем диссертации 469 страницы.В Главе 1 приводится критический анализ известных результатов в области математического моделирования и обработки данных. Данные при дискретной обработке представляются в виде конечных последовательностей знаков, а сама обработка осуществляется путем преобразования входных данных в выходные посредством разделения входных данных на части (переменные) и вьшолнения над ними некоторой последовательности операций. В связи с этим возникает задача представления функций большой размерности в виде композиции функций меньшей размерности. Постановка задачи в управлении базируется на автоматных моделях с памятью. Описание автомата осуществляется в виде распределенных во времени элементарных действий, каждое их которых является результатом вычисления дискретной функции. Показано, что главной задачей дискретной обработки данных является дискретная декомпозиция.История декомпозиции связана, в основном, с декомпозицией булевьгх функций.Установлено, что почти все функции в асимптотической области реализуются со сложностью, близкой к максимальной. Нерешенной осталась задача определения максимальной сложности функций при конечной размерности задач и нахождения методик синтеза, удовлетворяюпщх этой оценке.Формально-логическая декомпозиция оказалась практически нереализуемой, ибо приводит к серьезным комбинаторным трудаостям, связанным с предельно общей постановкой задачи. В связи с этим дискретную обработку данных представляют в алгоритмических формах, на основе поиска и формализации частных декомпозиционных схем. Теоретической базой для этого служат функциональная, структурная и объектная методологии анализа предметной области, реализуемые одноименньпми технологиями программирования.Несмотря на развитость и завершенность перечисленных методологий, трудно преодолимым остается семантический разрьш между содержательными представлениями относительно предметной области и теми средствами, которые служат для выражения этих представлений в виде формальных спецификаций. Для сокраш;ения семантического раз7 рыва используют повьппение уровня абстракции язьпсов моделирования. Однако, последнее не затрагивает существенным образом вьфазительность языков программирования, что связано с проблемой описания семантики таких язьпсов.В итоге показано, что описание дискретной обработки данных до сих пор вьшолняется в основном на интуитивном уровне с применением неформальных методов, основанных на искусстве разработчиков, их практическом опыте, экспертных оценках и экспериментальных проверках получаемых результатов.Глава 2 посвящена концептуально-онтологическому подходу к анализу, декомпозиции и описанию предметной области - понятийному анализу. Основная цель понятийного анализа состоит в получении таких декомпозиционных схем предметной области, которые хотя и сформулированы в рамках содержательных представлений, однако обладают формальной строгостью и точностью, достаточной для прямого использования полученного высокоуровневого описания для низкоуровневой реализации дискретной обработки данных.Суть подхода заключается в том, что для формальной спецификации предметной области используются две формальные системы. Первая формальная система - исчисление понятий, применена для вьфажения результатов понятийной декомпозиции предметной области. Вторая формальная система — специализированный предметный язык, или проблемный язьпс, строится для каждого класса решаемых задач и используется для описания решения.Понятия, выявленные в процессе анализа предметной области, условно разделены на две группы: терминальные, или сигнификативные, вьфажаемые последовательностью знаков терминального алфавита проблемного язьпса, и нетерминальные, или денотационные, соответствующие нетерминальным знаками порождающей грамматики этого язьжа.Разделение понятий на денотационные и сигнификативные осуществляется с учетом некоторой фиксированной проблематики, задающей класс решаемых задач.На основе выявления способов абстрагирования денотационных понятий строится понятийная структура предметной области, где под абстракцией понимается одно из четьфех видов отображений одних понятий в другие, которые соответствуют четьфем фундаментальным способам их образования: обобщению, типизации, агрегации и ассоциации.Для каждой такой абстракции дано формальное и семантически прозрачное определение, не требующее предметной интерпретации, как это имеет место в других концептуальных моделях, где используется множество связей между понятиями, несупщми различную семантическую нагрузку.Выявленные в процессе анализа предметной области денотационные понятия включаются в множество понятий проблемного язьжа, а найденные декомпозиционные схемы преобразуются в его язьпсовые конструкции, которые, в свою очередь, рассматриваются как формы выражения денотационньж понятий в тексте и задаются последовательностью денотационных и сигнификативных понятий.Таким образом, исследуемый подход основан на допущении, что уже в процессе изучения предметной области, еще до начала формализации, создается система понятий и декомпозиционные схемы, наиболее приспособленные для решения стоящих прикладных задач.Глава 3 посвящена контекстной технологии обработки данных, основанной на понятийном анализе предметной области, контекстной интерпретации текстов и определения семантики проблемного язьша, создаваемого для решения задачи. Отличительной особенностью контекстной технологии является то, что для формализации знаний о некоторой предметной области, данные, выражающие эти знания, сопровождаются описанием их структуры (синтаксиса) и содержания (семантики).Суть подхода заключается в реализации возможности выражать необходимые для описания предметной области понятия и найденные в процессе анализа декомпозиционные схемы в виде специализированной формальной системы, определять семантику этой системы и, в конечном итоге, вьшолнять содержательное описание предметной области и решение стоящих прикладных задач на созданном для этого проблемном язьпсе.Глава 4 посвящена исследованию системы контекстного программирования, которая является одной из реализаций технологии контекстной обработки данных на основе спецификации предметной области в форме язьпса-письма. Однако, не видится препятствий для построения на тех же принципах системы обработки, например, речевых данных, реализующей другой способ обработки - в форме языка-речи.Суть подхода заключается в использовании в качестве программы понятийной модели предметной области, которая дополнена решением прикладной задачи, выраженном на создаваемом в процессе описания проблемном язьпсе и предваряющем это решение.Отсюда, в частности, следует, что понятийная модель и решение задачи должны быть подвергнуты грамматическому разбору и компиляции таким образом, чтобы откомпилированные ранее предложения могли быть использованы при грамматическом разборе и компиляции следующих.Глава 5 посвящена исследованию формально-логического подхода к синтезу математических моделей дискретной обработки данных. Необходимость использования формально-логического подхода вызвана тем, что существует класс задач, для эффективного решения которых неприменимы известные методологии анализа предметной области и соответствуюш;ие им технологии программирования, в том числе и описанный ранее понятийный подход и основанная на этом подходе контекстная технология.При решении таких задач использование высокозфовневых моделей не представляется возможным по причине отсутствия у них необходимой содержательной интерпретации. Например, такие задачи возникают в цифровой обработке сигналов, проектировании дискретных устройств, первичной обработке измерительных данных, и в других областях, характерной особенностью которых является представление исходных и результируюпщх данных в виде таблиц (векторов, двумерных и многомерных массивов и других однородных структур).Суть подхода заключается в том, что дискретная обработка данных, заданная в табличном виде, представляется как одна или несколько дискретных функций. Для синтеза формального описания дискретная функция декомпозируется и представляется в виде композиции функций меньшей размерности (частичных функций). Особенностью описываемого подхода является использование алгебраической декомпозиции дискретных функций в наиболее общей постановке задачи, когда с целью синтеза эффективных математических моделей дискретной обработки данных переменные и функции принимают значения на произвольных конечных множествах, а выбор алгебраических операций не ограничен каким-либо их подмножеством.Глава 6 посвящена алгебраическому синтезу эффективных математических моделей дискретной обработки, где эффективным назьшается такой синтез, при котором представление функции содержит количество операций, не превосходящее некоторого максимального их числа, достаточного для реализации любой функции той же размерности.Для сравнения различных декомпозиционных схем введены количественные характеристики. Сложность разложения функции определена количеством слагаемых в итоговой формуле . Под сложностью представления понимается количество операций, необходимых для вычисления функции.Алгебраическая декомпозиция близка преобразованию Карунена-Лоэва, где разложение осуществляется по собственным векторам ковариационной матрицы функции и, тем самым, обеспечивается наилучшее (оптимальное) приближение функции в среднеквадратическом смысле, а также достигается наименьшая сложность разложения. В этом случае частичные функции вычисляются с некоторой степенью свободы, а их количество равно числу ненулевых собственных значений ковариационной матрицы. Для достижения не только наименьшей сложности разложения, как это имеет место в разложении по Ка10 рунену-Лоэву, но и наименьшей сложности представления функции, используются оставшиеся степени свободы.В приложениях приведен пример эффективного решения средствами контекстной технологии задачи управления лифтом, описана реализация язьпса исчисления предикатов первого порядка, определена виртуальная машина, использованная для задания первичных семантических категорий исчисления предикатов, дана методика синтеза полиномиальных и неполиномиальных форм частичных функций при алгебраической декомпозиции, рассмотрен алгоритм полиномиальной факторизации частичных функций и его применение для сжатия изображений.