Главная страница 1
Лекция №3
ТЕХНОЛОГИЯ КОНЦЕПТУАЛЬНОГО ПРОГРАММИРОВАНИЯ
Технология концептуального программирования (ТКП) – одна из старейших и наиболее развитых в ИИ как в теоретическом, так и в практическом аспектах. Она разработана советскими учеными и сейчас ведущие позиции в ней занимают ученые России и Эстонии.
ТКП предназначена для синтеза программ решения задач по их описанию на ограниченном естественном языке (ОЕЯ) при не­которых ограничениях.
Эти ограничения требуют:

  1. точного указания ПрО, к которой относится решаемая задача;

  2. фиксации класса решаемых задач.

Последние получили название вычислительных или расчетно-логических задач.


В общем случае их описание на ОЕЯ имеет вид:

Зная М, вычислить (у1, ..., уn) по (х1, ..., хт) (1.1)
В выражении (1.1) М идентифицирует ПрО (например, тригонометрию, кинематику и т.д.).
Кортеж (х1,...,хт) содержит идентификаторы переменных с известными значениями, а кортеж (у1,..., уn) – идентификато­ры переменных, значения которых требуется определить.
Существенным ограничением ТКП является предположение, что в компьютере имеется модель ПрО (МПрО), с которой можно манипулировать.

В ТКП для представления МПрО используются семантические сети специального вида, называемые вычислительными моделями (ВМ).


Известны четыре подхода к синтезу программ:

  1. дедуктивный;

  2. индуктивный;

  3. трансформационный;

  4. утилитарный.

В ТКП используются пер­вые два подхода.


Основная идея ТКП состоит в следующем:

Пусть существует постановка задачи в виде (1.1).
Необходимо:

  1. перейти от (1.1) к теореме существования решения данной задачи;

  2. построить доказательство теоремы существования;

  3. извлечь из доказательства программу решения задачи.

При реализации этого метода получаем два важных результата:



  1. программа точно соответствует описанию задачи;

  2. вместо отладки программы выполняется «отладка» описания задачи.


Концептуализацией называется процесс перехода от описания ПрО на ОЕЯ к точной спецификации этого описания на некотором формальном языке, ориентированном на компьютерное представление.
В качестве математического аппарата концептуализации в рамках ТКП разработаны ВМ. Они являются разновидностями семантических сетей. Семантическая сеть S в общем виде определяется следующим образом:
S=(0, R) = ({oi|i= 1,2,...,k}, {ri|j= 1,2,...,l}) (1.2)
где О – множество объектов ПрО (|О|=k); R – множество отношений между объектами ПрО (|R|=l).
ВМ для заданной ПрО определяется как кортеж:
({pi}, { fj}, { uk}) (1.3)
где pi — имя понятия ПрО; fj — функциональное отношение между понятиями; ик — управляющая структура.
Функциональное отношение fj задается тройкой плекс-элементов.
fj = (Xj,Fj,Yj) (1.4)
где Xj = (хj1, ..., xjmj) — набор входных переменных для fj; Fj — ссылка на процедуру, реализующую вычисление Yj = Fj(Xj); Yj= (yj1, ..., yjnj) — набор выходных переменных для fj.

Управляющие структуры uk реализуют отображения Xj и Yj в множество раз­решенных типов данных, а также они позволяют приписывать перемен­ным известные и вычисленные значения.


Графически концептуализация ПрО в рамках ВМ изображается графом G:
G = (V, U) = ({xi}  {уj}  {Fl}, {uk}) (1.5)
Процесс доказательства теоремы существования решения задачи (1.1) отображается на графе как «волновой процесс», начинающийся в верши­нах (х1,...,хт) и заканчивающийся, когда «волна» достигнет всех вершин (у1, ..,уn).
При волновой интерпретации можно детализировать постановку зада­чи (1.1) и выделить четыре класса задач:

1. Задачи на доказательство.

2. Задачи на вычисление значений переменных.

3. Задачи на прогнозирование.

4. Задачи планирования эксперимента.
Рассмотрим теорему существования решения задачи в постановке (1.1). Обозначим Р(х) предикат входных условий, a R(x, у) — предикат выходных условий; х = (х1, ..., хт), у = (у1, ..., уn).
Запишем теорему существо­вания в виде x(P(x)  y R(x,y)) (1.6)
Будем рассматривать только конструктивные логические теории. Н.Н. Непейвода доказал, что различные определения реализуемости эквивалентны. Он же показал, что существует реализуемость, при которой формулам вида y R(y) будет соответствовать либо программа вычисления у, либо само значение у. Тогда любой доказуемой формуле будет соответствовать программа.

Предполагается, что реализации всех аксиом заданы априорно. Для каждого правила вывода



A1, … , Ak A1, … , Ak

П (или просто ) заданы правила построения реализации выводимой

A A

по этому правилу формулы А по реализациям формул A1, … , Ak. Тогда реализация любой выводимой формулы может быть построена прямо по выводу формулы.

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

Для каждого правила вывода в ней записываются программные конструкции, дающие реализации формул, выводимых по этому правилу.



Конструктивные доказательства имеют следующие особенности:

  • на каждом шаге доказательства применяется некоторое правило вывода;

  • в качестве посылок используются только аксиомы или ранее доказанные формулы;

  • в доказательстве отсутствуют циклы;

  • некоторые шаги доказательства могут использовать леммы, для которых строятся вспомогательные доказательства.

Каждый шаг доказательства преобразуется во фрагмент программы отдельно от других шагов. Построенные таким способом программы являются хорошо структурирован­ными.

Существуют два способа извлечения программы из доказательства:

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

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


Инструментарий концептуального программирования
ТКП программно реализована в серии программных решателей ПРИЗ: Микро-Приз, Эксперт-Приз. Общим для них является язык УТОПИСТ (Универсальный Транслятор ОПИСаний Теорий). В решателях накоплена значительная база описаний ПрО (теорий): элементарная математика, физика, электротехника, механика и др.

В Эксперт-Приз ТКП объединена с еще одной эффективной технологи­ей ИИ — экспертными системами. На рисунке представлена укрупнен­ная схема решения задачи в ПРИЗ.



Эксперт-Приз предоставляет средства для формирования набора понятий ПрО, с помощью которых описываются объекты и отношения, фигу­рирующие в прикладной задаче. Таким образом, модель задачи состоит из двух разделов: списка объектов и списка уравнений. Запрос на решение задачи содержит перечень искомых параметров объектов.



Смотрите также:
Лекция №3 технология концептуального программирования (ткп)
63.18kb.
1 стр.
Программа обучения студентов (Syllabus) по дисциплине тр302- технология программирования
375.44kb.
1 стр.
Основы объектного программирования на языке C# оо – технология и обучение программированию
141.07kb.
1 стр.
Современные методологии концептуального моделирования предметной области
88.61kb.
1 стр.
Лекция особенности проектирования аит
201.06kb.
1 стр.
Рабочая программа учебной дисциплины (модуля) Технологии параллельного программирования Наименование магистерской программы
79.5kb.
1 стр.
Программа по курсу основы информатики (Введение в программирование) по направлению
162.67kb.
1 стр.
Сравнительные характеристики языков программирования. Встроенный в приложения Windows язык vba программы, модули, проекты. Отладка и тестирование
98.45kb.
1 стр.
Ii задачи математического программирования
419.21kb.
1 стр.
Курсовая работа: 4 курс, 4 семестр
392.84kb.
1 стр.
Лекция 1 Понятие о процессе и о нитях
164.72kb.
1 стр.
Лекция csos01. 320201. Принципы построения операционных систем (ОС)
50.15kb.
1 стр.