авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |

Алгоритмизациипредметных областей

-- [ Страница 1 ] --

На правах рукописи

Новиков ФёдорАлександрович

Методы алгоритмизациипредметных областей

Специальность 05.13.11–«Математическое и программноеобеспечение
вычислительных машин, комплексов икомпьютерных сетей»

АВТОРЕФЕРАТ

диссертации насоискание ученой степени

доктора техническихнаук

Санкт-Петербург

2011

Работа выполнена накафедре «Технологии программирования»Санкт-Петербургскогогосударственного университета информационных технологий,механики и оптики (СПбГУ ИТМО)

Научныйконсультант

докторфизико-математическихнаук

Новосельцев ВиталийБорисович

Официальные оппоненты

докторфизико-математическихнаук, профессор

БарановСергей Николаевич

доктортехнических наук, профессор

КалайдаВладимир Тимофеевич

доктортехнических наук, профессор

ТропченкоАлександр Ювенальевич

Ведущаяорганизация

Государственныйнаучный центрЦентральныйнаучно-исследовательскийиопытно-конструкторскийинститут робототехники и техническойкибернетики

Защита диссертациисостоится «06»июля 2011 года в 15часов 30 минут на заседании диссертационного советаД 212.227.06 в Санкт-Петербургскомгосударственном университете информационныхтехнологий, механики и оптики по адресу:197101, Санкт-Петербург, Кронверкский пр.49.

С диссертацией можноознакомиться в библиотеке СПбГУИТМО.

Автореферат разослан«__» ______________2011 г.

Ученыйсекретарьдиссертационного совета,

доктортехнических наук, профессор

Л.С. Лисицына

Общая характеристикаработы

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

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

Наряду страдиционными методами, распространениеполучили методы алгоритмизации, основанные на применении проблемно-ориентированныхязыков (ПОЯ) и моделей предметных областей (МПО).

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

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

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

Таким образом,предметом диссертационного исследованияявляются методыалгоритмизации предметных областей. Предлагаемые методы развивалисьпостепенно, сконца 70-х годов, в результате анализа опытавыполнения работ по алгоритмизации конкретныхпредметных областей, сначала подруководством члена-корреспондента АН СССРС. С. Лаврова, а позже подруководством автора. Различные аспекты иэлементы методов испытывались ипостепенно совершенствовались в практических применениях, перечисленных в диссертации. Кнастоящему времени сложилась целостнаяметодология, допускающая распространениена различные классы предметныхобластей.

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

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

Методыисследования. В диссертациииспользуются методы дискретной математики: теориимножеств, теории автоматов, математическойлогики, теории графов,теории формальных грамматик, а такжетерминологический и понятийный аппарат технологиипрограммирования. Вкачестве основного средства формального представления применяется унифицированныйязык моделирования UML.

Научная новизна полученныхрезультатов определяется следующимирезультатами,выносимыми на защиту.

  • Таблично-ориентированныйметод алгоритмизациипредметных областей, интегрирующийсредства работы с базами данных и пакетамиприкладных программ. Методобеспечивает сбалансированную предметнуюориентацию в предметных областях, в которых решениелюбой типовой задачи сводится крегулярному инезависимому решению последовательностиоднородных элементарныхзадач.Реализовано и внедрено семействотаблично-ориентированных языков в областях,связанных с обработкой экспериментальныхданных.
  • Автоматный методреализации проблемно-ориентированныхязыков, в том числе визуальных,позволяющий определить все аспектыязыка —структуру, внешнее представление, контекстныеусловия и операционную семантику.
    Полное определение языкаавтоматным методом являетсяреализациейязыка. Воснову метода положенамодельвзаимодействующих автоматных объектов, обобщающая возможности автоматныхмоделей, предложенных ранее.
  • Язык исполняемыхпрограммных спецификаций,позволяющий описывать модели предметныхобластей, в том числе графически, ставитьна них вычислительные задачи и автоматическисинтезировать программы решения этихзадач. Язык обладаетвыразительной силой, в точностисоответствующей эффективно разрешимой теории структурного синтезапрограмм.

Практическаязначимость.Предлагаемая в диссертацииметодология многократно применялась автором напрактике для определения и реализацииразнообразных ПОЯ и МПО (всего 17случаев) в следующихпредметных областях: 1) инструментальныесредства разработки программногообеспечения; 2) эфемеридные расчеты вастрономии; 3) компьютерная версткатабличных изданий; 4) описаниеграфического интерфейса пользователя;5) автоматизация бизнес-процессов всистемах менеджмента качества. При этомдостигнуты и подтверждены положительныерезультаты алгоритмизации,то есть разработанноепрограммное обеспечение используетсяприкладными специалистами для решениятиповых задач регулярно и в течениепродолжительного времени в разныхорганизациях (табл. 2).

Апробациядиссертации.Различные аспектырезультатов работы докладывались на многихсеминарах и форумах, в том числе, наследующих конференциях: Всесоюзная конференция «Методыматематической логики в проблемахискусственного интеллекта и систематическоепрограммирование», Вильнюс, 1980; III конференция«Применение методов математическойлогики», Таллин, 1983; III Всесоюзная конференция«Автоматизация производства пакетовприкладных программ и трансляторов», Таллин, 1983; IIIВсесоюзная конференция«Автоматизация производства системпрограммирования», Таллин, 1986; IAU Colloquium 109, Gaithersburg, 1988; Всесоюзноесовещание «Эфемеридная астрономия ипозиционные наблюдения», Л., 1991; IX научнаяшкола по ППП «Программное обеспечениематематического моделирования,управления и искусственного интеллекта»,Адлер, 1991; Всероссийское совещание с международным участием «Компьютерные методы небесной механики»,СПб., 1992, 1995, 1997; Международная конференция«Современныепроблемы теоретической астрономии», СПб.,1994; Colloquium«Internationalcooperation in dissemination of the astronomical data», St. Petersburg, 1996; ФестивальMicrosoft вСанкт-Петербурге, 1998; International ComputerScience Symposium in Russia CSR2006, СПб, 2006; Международная научная конференция «Космос,астрономия и программирование»(Лавровские чтения), СПб., 2008;Научно-практическая конференция «Научныеисследования и инновационнаядеятельность», СПбГПУ, 2009; Семинар Институтапрограммных систем РАН, 2009; International conference «Asteroid-Comet Hazard – 2009», St. Petersburg, 2009; СеминарИнститута прикладной астрономии РАН, 2010; СеминарСанкт-Петербургского институтаинформатики и автоматизации РАН, 2011;Семинар компании Jet Brains,2011; Семинаркомпании Scite,2011.

Публикации. По материаламдиссертации опубликовано 55работ, изкоторых 13 — статьи в журналахиз списка ВАК, и 7 —многотиражные монографии, выпущенныеиздательствами «Питер»,«БХВ-Санкт-Петербург» и «Наука иТехника». Основные работы, в которыхсодержатся результаты, выносимые назащиту, перечислены в конце автореферата. В работах,выполненных в соавторстве, личный вкладавтораво всех случаях в равных долях с соавторами.

Структура диссертации.Диссертация изложена на175 страницах.Список литературы содержит 120 наименований.Работа иллюстрирована 45 диаграммами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 Рис. 3. Сильныйпользователь -5

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

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

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

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

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



Pages:   || 2 | 3 | 4 | 5 |
 





 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.