Новиков Фёдор Александрович Методы алгоритмизации предметных областей Специальность 05. 13. 11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей» автореферат

Вид материала

Автореферат

Содержание Содержание работы Первая глава В разделе 1.2 В разделе 1.3 Командные предметно-ориентированные языки Императивные (графические) языки Декларативные проблемно-ориентированные языки Вторая глава В разделе 2.1 В разделе 2.2 В разделе 2.3 Таблично-ориентированный метод алгоритмизации предметных областей Третья глава

Подобный материал:

• Новые эффективные методы энтропийного кодирования медиаданных 05. 13. 11 "Математическое, 217.67kb.
• Принципы и решения по совершенствованию эффективности функционирования операционных, 337.67kb.
• Автореферат диссертации на соискание ученой степени, 460.33kb.
• Методы и программные средства повышения эффективности распознавания групп звезд в автономной, 335.05kb.
• Методы и программные средства поиска решения на основе аналогий в интеллектуальных, 324.29kb.
• Математическое и программное обеспечение систем оперативной оценки характеристик сложных, 247.51kb.
• Технология построения многовариантных объектно-ориентированных структур текстов, 1516.01kb.
• Исследование программных методов реализации операций в конечных алгебраических структурах, 294.17kb.
• Разработка математического и программного обеспечения идентификации объектов в базе, 251.79kb.
• Программа-минимум кандидатского экзамена по специальности, 100.67kb.

Содержание работы

Диссертация состоит из введения, пяти глав и заключения.

Во введении рассматриваются следующие вопросы: проблемы технологии разработки прикладного программного обеспечения, необходимость решения этих проблем для алгоритмизации, эффективность применения ПОЯ и МПО, важность опоры на формальные методы. Помимо этого, во введении вводится специфическая терминология, используемая в диссертации, и система обозначений, основанная на унифицированном языке моделирования UML. В частности, вводится понятие степени алгоритмизации. Степень алгоритмизации M определяется как среднее геометрическое двух показателей: доля решаемых типовых задач T (отношение числа типовых задач, которые можно решить средствами оцениваемой алгоритмизации, к числу всех идентифицированных типовых задач), и относительное снижение трудозатрат S (отношение средних трудозатрат на решение типовых задач после оцениваемой алгоритмизации, к средним трудозатратам на решение той же совокупности задач до алгоритмизации): 

С учетом заявленных целей ставится основная задача диссертации: на основе исследования известных методов определения ПОЯ и МПО разработать новые методы определения ПОЯ и МПО, повышающие степень алгоритмизации предметных областей по сравнению с известными методами.

Первая глава  посвящена проблемам разработки прикладного программного обеспечения и изложению предлагаемого подхода к их решению.

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

Центральное место в разделе занимает предложенная автором концепция циклов повышения продуктивности. Как хорошо известно, два фактора решающим образом влияют на продуктивность прикладного программирования: 1) сокращение объема внеплановых изменений артефактов; 2) увеличение объема повторно использованных артефактов. Предлагается рассмотреть в этом ряду третий фактор — использование подходящего проблемно-ориентированного языка. Основной тезис автора о влиянии языковых средств на продуктивность разработки представлен на рис. 1. На этой диаграмме изображена традиционная итеративная модель процесса разработки с оригинальными добавлениями. С основным циклом последовательного выполнения фаз процесса разработки сопряжены два внешних цикла движения определенных артефактов, которые называются циклами повышения продуктивности. Верхний цикл, в который вовлечены заказчики, отражает выявление несоответствий требованиям и, тем самым, определяет объем внеплановых изменений. Нижний цикл, в который вовлечены разработчики, отражает преобразование разработанных компонентов в готовые к применению образцы проектирования и, тем самым, определяет объем повторного использования.



Рис. 1. Циклы повышения продуктивности

Утверждается, что выигрыш за счет уменьшения ошибок проектирования обусловлен движением артефактов в первом цикле (справа вверху), а выигрыш за счет повторного использования обусловлен движением артефактов во втором цикле (слева внизу). Суть в том, что если все эти артефакты выражены на одном языке (то есть на ПОЯ), то сокращаются потери «на трение» при движении информации, и значит, ускоряется движение и растет продуктивность.

В разделе 1.2 исследуются две концепции: «модель предметной области» и «сильный пользователь» Для алгоритмизации предметной области необходимо решить три задачи: 1) определить представление объектов предметной области, 2) реализовать операции с этими объектами и 3) разработать методы решения типовых задач, как систем правил применения операций к объектам для получения значимого результата. Решение первых двух задач алгоритмизации в настоящее время надежно обеспечено технологиями систем управления базами данных (СУБД) и пакетов прикладных программ (ППП). Нерешенные вопросы связаны с представлением знаний о методах решения типовых задач. Заметим, что, в любом случае, решение типовых задач предметной области опирается на готовые программы и данные, которые в диссертации называются доверительным программным фондом (ДПФ).

С. С. Лавров предложил общую классификацию знаний, представляемых в компьютере: фактографические (базы данных), алгоритмические (пакеты программ) и концептуальные (законы, правила). Применяя эту классификацию к рассматриваемому случаю, заключаем, что модель предметной области — артефакт, представляющий концептуальные знания о методах решения типовых задач предметной области. Доверительный программный фонд представляет алгоритмические и фактографические знания.

Рассмотрим варианты использования МПО (рис. 2).



Рис. 2. Модель использования МПО

Важнейшим вариантом использования МПО является решение типовых задач, в этот вариант использования вовлечено основное действующее лицо — пользователь. Возможность решения типовых задач обеспечивается ДПФ. Но модель предметной области допускает и другие варианты использования: создание ПОЯ, что обеспечивается соответствующими инструментальными средствами, или специальных приложений, например, систем с элементами искусственного интеллекта для автоматического решения задач в данной предметной области (так называемых «планировщиков задач»). В последнем случае не обойтись без явного представления в программе концептуальных знаний о предметной области. Действующее лицо, вовлеченное в такие более сложные варианты использования, уместно назвать сильным пользователем. Сильный пользователь (оракул) может ответить на любые вопросы о предметной области: какие задачи являются типовыми, можно ли доверять имеющемуся программному фонду и т.д. Сильный пользователь является центром алгоритмизации, как показано на диаграмме (рис. 3).



Рис. 3. Сильный пользователь как центр алгоритмизации

В этом случае возникают, по меньшей мере, еще два цикла повышения продуктивности. Например, оценив разработанный артефакт, сильный пользователь может, не дожидаясь результатов валидации, сразу изменить постановку задачи (заказанный артефакт) и начать следующий виток основного цикла разработки, «проскочив» полцикла. Или же, анализируя неудовлетворительные результаты валидации, сильный пользователь может изменить спецификацию разработанного артефакта, указав, в каких случаях его не следует использовать повторно (на ошибках учатся). Таким образом, достигается выигрыш в продуктивности и тем самым повышается степень алгоритмизации.

В разделе 1.3 приводится рекомендуемая автором последовательность шагов алгоритмизации и вводится классификация ПОЯ, классификация МПО и классификация методов алгоритмизации.

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

В предложенной классификации ПОЯ выделяются три категории языков по типу взаимодействия с пользователем.

• Командные предметно-ориентированные языки. Языки этой категории, как правило, опираются на развитый ДПФ. Характерным для этой категории является то, что пользователь последовательно, по одной, дает системе команды на выполнение тех или иных действий, причем состав и порядок действий, которые требуются для решения некоторой задачи, пользователь определяет сам по ходу дела, используя как результаты выполнения предыдущих команд, так и другие трудно формализуемые факторы, и не сообщает системе заранее в виде «программы».
  
• Императивные (графические) языки. Языки этой категории примечательны тем, что (сильный) пользователь описывает решаемую задачу в целом, предъявляя совокупность требуемых шагов не по отдельности, а во взаимосвязи, часто в виде графической схемы или диаграммы. Система осуществляет решение задачи, опираясь на ДПФ. Также как и в языках первой категории, программу решения задачи определяет пользователь, но в этом случае он в явном виде предъявляет «программу» системе.
  
• Декларативные проблемно-ориентированные языки. Языки этой категории появляются в том случае, когда алгоритмизация предметной области достигает уровня, при котором возможно (автоматическое) построение алгоритма решения типовых задач предметной области и внесение этого алгоритма в систему. Пользователь только ставит задачу, а система сама строит программу ее решения, подбирает подходящие шаги и сама выполняет их.
  

Языки первой категории не увеличивают степень алгоритмизации предметной области по сравнению с используемым ДПФ. Языки второй категории повышают степень алгоритмизации за счет наглядности и автоматизации процесса выполнения последовательности модулей. Языки третьей категории дают наибольшую степень алгоритмизации за счет своей выразительной силы.

Предлагается использовать две независимых дихотомии для классификации МПО на верхнем уровне. Первая дихотомия: жесткие и гибкие модели. Жесткие мо­дели встроены в ДПФ. Чтобы изменить жесткую модель, пользователь должен изменить программный код системы. Гибкие модели не встроены в систему «намертво». Чтобы изменить гибкую модель, пользователь не должен изменять программный код системы. Ему предоставляется специальный интерфейс или иная возможность отредактировать представление знаний о предметной области. Жесткие модели эффективнее и проще реализуются. Гибкие модели имеют более широкую область применения. Вторая дихотомия: декларативные и императивные модели. Императивные модели в части задания правил решения типовых задач используют алгоритмы, выполнение которых доставляет значимый для пользователя результат. Декларативные модели избегают явных последовательностей при задании правил решения типовых задач, используя логические утверждения, ограничения, уравнения и т. п., которые неявно задают значимый результат через его свойства. Императивные модели эффективнее и проще реализуются. Декларативные модели потенциально дают более высокую степень алгоритмизации.

Существует множество методов и приемов алгоритмизации, основанных на использовании ПОЯ и МПО. Эти методы предлагается классифицировать в соответствии с основными присущими характеристиками, приведенными в табл. 1.

Таблица 1. Классификация методов алгоритмизации

Характеристика	Предметно-ориентированные	Языково- ориентированные	Модельно- ориентированные
Правила решения типовых задач (представление МПО)	Неявные, встроены в ДПФ, неизменяемые пользователем	Неявные, описываются на ПОЯ, изменяемые пользователем	Явные, задаются в МПО, изменяемые пользователем
Класс предметных областей	Узкий, ограничен алгоритмами, встроенными в ДПФ	Широкий, ограничен выразительной силой ПОЯ	Широкий, ограничен мощностью планировщика задач МПО
Трудоемкость / «сила» пользователя	Высокая / Низкая	Средняя / Средняя	Низкая / Высокая

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

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

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

В разделе 2.1 приводится пример пакета «Ample 3» (см. табл. 2) для решения задач динамики малых тел Солнечной системы. Не касаясь особенностей предметной области, отмечается, что привычный графический интерфейс пользователя, построенный на традиционных элементах управления, является проблемно-ориентированным языком командного типа. Заметим, что при переходе от текстовых языков командного типа к графическому интерфейсу пользователя произошел скачок в количестве, но не в качестве. Предметно-ориентированный язык графического интерфейса остается языком командного типа, скрытым за двумерными формами.

Вторым примером в этом разделе является язык «GUIDL» (см. табл. 2). Данный язык является текстовым языком для описания действий пользователя графического интерфейса. Подчеркнем, что это язык публикаций, программы на этом языке предназначены для чтения и исполнения человеком. Язык «GUIDL» — это командный язык для записи пошаговых процедур, допускающий ветвления и циклы. Более десяти тысяч страниц публикаций, в которых используется данный язык, доказали его полезность.

В разделе 2.2 обсуждаются визуальные ПОЯ. Большая часть современных визуальных языков в качестве нотации использует «графоподобные» диаграммы. Программная реализация таких языков требует специализированной инструментальной поддержки. Таким образом, реализация визуальных языков сама является ярко выраженной предметной областью, заслуживающей собственных проблемно-ориентированных языков, и такие языки предложены. В качестве примера в диссертации рассматривается язык описания диаграмм «DiaDeL» (см. табл. 2), разработанный автором совместно с К.Б. Степаняном. Основным назначением языка «DiaDeL» является описание нотации (графического синтаксиса) диаграмм и описание связи нотации с существующей семантикой.

Нотация диаграммы задается в виде описания графических конструкций и отношений между ними. Семантика задается в виде набора классов (семантической модели), реализующих необходимые структуры и операции в выбранной предметной области. Связывание нотации с семантикой является ключевым моментом в описании диаграммы. Для этого элементам из семантической модели, которые должны быть представлены визуально, сопоставляются графические конструкции. Существенным преимуществом языка «DiaDel», которое выделяет этот язык среди подобных языков (например, «TIGER», «MetaEdit», «Moses»), является то обстоятельство, что семантическая модель задается независимо от графической нотации. Другими словами, для готовой системы классов и отношений, реализующих семантику предметной области, можно придумать графическую нотацию, и описав эту нотацию на языке «DiaDel», автоматически получить реализацию графического предметно-ориентированного языка, настроенного на предметную область.

Вторым примером раздела является графический язык описания бизнес-процессов и документооборота, разработанный автором совместно с В. О. Клебаном. Идея этого языка состоит в следующем. Считается, что описываемый бизнес-процесс полностью документирован — все шаги бизнес-процесса отражаются в документах. В отличие от традиционных схем описания документооборота, в предлагаемом языке принята концепция «живого» документа. При этом состояния и жизненный цикл каждого документа хранятся в нем самом, документ реагирует на события, которые происходят с ним и с другими документами, меняя свое состояние и посылая сигналы другим документам и пользователям. Наиболее естественной формой описания жизненного цикла (детерминированного процесса) является автомат, представленный в виде графа состояний-переходов. Каждый документ в каждый момент находится в определенном состоянии. Если в документе что-то происходит, например, пользователь открыл документ и изменил значение контролируемого поля в документе, то это событие, на которое документ реагирует изменением своего состояния. Кроме изменения состояния, документ может послать сообщение своему бизнес-процессу. Бизнес-процесс, также описанный в виде автомата, реагирует на полученное событие, меняя что-то в этом или другом документе. Это изменение может привести к смене состояния и порождению нового события, и т. д. Выбранная архитектура оказалась очень гибкой и легкой в применении. Действительно, никаких дополнительных требований не накладывается, документы хранятся там же, и так же, как и раньше, требуемое поведение обеспечивается взаимодействием распределенной системы автоматов.

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

Первый пример отражает идею применения специализации как средства повышения уровня предметно-ориентированного языка и степени алгоритмизации. Учитывая особенности ограниченной предметной области, можно построить такие специализированные надстройки над универсальными средствами, которые обеспечивают эффективное достижение очень высоких результатов с малыми затратами. Таковы входной язык и система «СВИТА» (см. табл. 2), разработанные при участии автора. С помощью этой системы выпускаются астрономические ежегодники и альманахи — специализированные издания с высокоточными астрономическими данными. Астрономические ежегодники используются в службах навигации, связи, точного времени и в других жизненно важных областях. Для их издания необходима программная система, которая не просто автоматически верстает очень большие и очень сложные таблицы по заранее насчитанному материалу, но и делает это с гарантированной надежностью и с гарантированным качеством результата. Система «СВИТА» совершенствовалась и развивалась течение 15 лет. В результате все таблицы во всех ежегодниках, выпускаемых Институтом прикладной астрономии РАН, в настоящее время изготавливаются с помощью системы «СВИТА». При этом ежегодные трудозатраты на выпуск сократились в шесть раз. Таким образом, достигнутая в данном случае степень алгоритмизации

Вторым примером в третьем разделе — последним и самым важным — является семейство языков таблично-ориентированного программирования. Предложенный автором таблично-ориентированный метод алгоритмизации предметных областей заключается в следующем. Пусть задана предметная область, и пусть в предметной области зафиксирован набор переменных V = {v₁, …, v_n} — величин предметной области. Совокупность значений A = {a₁, …, a_n} этих переменных образует состояние предметной области. Среди значений могут быть как заданные, так и незаданные, то есть неизвестные, подлежащие определению. Имеется также набор функциональных модулей F = {f₁, …, f_m}, которые называются действиями. Действия могут изменять состояние системы, например, вычисляя значения неизвестных величин по значениям известных, или могут иметь побочный эффект, например, печать значений. Суперпозицию действий, которые переводят систему из начального состояния в целевое состояние, называется решением элементарной вычислительной задачи в данной предметной области. Табличный подход основан на допущении, что решение любой типовой задачи в данной предметной области сводится к последовательному и независимому решению совокупности элементарных вычислительных задач.

Последовательность начальных состояний элементарных вычислительных задач можно и удобно представить в виде таблицы. Столбцы такой таблицы помечены именами переменных предметной области, а строки образуют начальные состояния элементарных вычислительных задач, заданных набором действий. Решение общей задачи сводится к тому, что над каждой строкой исходной таблицы выполняются указанные действия, в результате чего получается результирующая таблица целевых состояний. Здесь мы подошли к важному обстоятельству, определяющему применимость табличного подхода. С одной стороны, таблица — это массив данных, который может быть, например, сохранен во внешней памяти в виде файла, а, с другой стороны, таблица — это программа, определяющая последовательность присваиваний значений переменным — величинам предметной области. Такой двойственный взгляд на природу таблицы позволяет удачно интегрировать в рамках таблично-ориентированного подхода средства работы с СУБД и ППП.

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

Для того чтобы подчеркнуть и проиллюстрировать двойственную природу таблицы в таблично-ориентированном подходе, здесь приводятся определения шести базовых операций алгебры таблиц как операций с программами. Определения этих операций для таблиц как структур данных и эквивалентность определений для таблиц как структур данных и таблиц как итераторов приведены в диссертации. В следующих определениях таблица рассматривается как итератор, перебирающий кортежи таблицы. Пусть T, T1, T2 — итераторы таблиц; E, E1, E2 — наборы переменных в соответствующих таблицах; n — натуральное число; s — список переменных; p — булевское выражение; f — действие (процедура); Default — функция, возвращающая значения по умолчанию своих аргументов. Тогда операции определяются так.

1. Сложение.
   T = T1+T2 = for E1  T1 do yield (E1  Default(E2–E1));
   for E2  T2 do yield (Default(E1–E2)  E2)
   Сложение таблиц — это последовательное выполнение двух циклов.
   
2. Умножение.
   T = T1*T2 = for E1  T1 do for E2  T2 do yield (E1E2)
   Умножение таблиц — это вложенность циклов.
   
3. Итерация (операция не обозначается).
   T = n T1 = for i from 1 to n do T1
   Итерация таблицы — это цикл со счетчиком.
   
4. Проекция.
   T = T1 | s = for E1  T1 do yield (E1  s)
   Проекция таблицы — это локализация переменных.
   
5. Выборка.
   T = T1 [p] = for E1  T1 do if p(E1) then yield (E1)
   Выборка из таблицы — это условный оператор в теле цикла.
   
6. Действие (операция не обозначается).
   T = T1 f = for E1  T1 do yield (f(E1))
   Действие над таблицей — это вызов процедуры в теле цикла.
   

На основе таблично-ориентированного подхода при активном участии автора было разработано три проблемно-ориентированных языка (СЛОН, ТОП, Дельта, см. табл. 2), каждый в нескольких версиях и в нескольких системах программирования. В настоящее время разработанные системы используются для решения разнообразных задач, прежде всего задач эфемеридной астрономии, в том числе важнейших, таких как выпуск высокоточных эфемерид больших планет и Луны. Необходимо подчеркнуть, что несомненный успех этого метода во многом определяется тем, что в разработке участвовал сильный пользователь Г. А. Красинский, который фактически построил исчерпывающую МПО в форме встроенного планировщика, решающего все типовые элементарные задачи эфемеридной астрономии. Однако, то обстоятельство, что МПО является встроенной и неотчуждаемой, требует реализации подобных планировщиков для применения подхода в других областях, что ограничивает область применения реализованных таблично-ориентированных ПОЯ, но не ограничивает область применения таблично-ориентированного метода.

Таблично-ориентированный метод алгоритмизации предметных областей является первым результатом, выносимым на защиту. Разработка таблично-ориентированного метода была выполнена автором в 1987 – 2007 годах в ИПА РАН совместно с Г. А. Красинским и В. И. Скрипниченко.

Третья глава представляет разработанный автором метод определения ПОЯ на основе метамоделей и систем взаимодействующих автоматов.