S-задача (задачный конструктивный объект)

©  А.В. Ильин, В.Д. Ильин, 1989, 2007, 2009

□ S-задача (задачный конструктивный объект) [англ. s-problem (problem constructive object)] –

это триада {Formul, Alg, Prog}, где Formul – постановка задачи, Alg – множество алгоритмов, поставленных в соответствие постановке задачи, Prog – объединение множеств программ, каждое из которых поставлено в соответствие алгоритму из Alg.

Постановка задачи Formul – это пара {Mem, rul}, где Mem – s-представление множества понятий задачи, на котором задано разбиение Mem = Inp U Out (Inp ^ Out = 0), а rul – правило, задающее на Mem бинарное отношение Rel [rul (Mem)] < Inp * Out [1]. Назовем множество Mem памятью задачи, а Inp и Out – входом и выходом задачи, значения которых предполагается соответственно задавать и искать □.

См. TSM – комплекс средств формализации гипермедийных описаний s-моделей.

Исходим из того, что одной формулировке могут соответствовать несколько алгоритмов, а каждому алгоритму – несколько программ. Различия между алгоритмами из множества Alg определяются задаваемым описанием применения (ограничениями на предельный размер задачи, точность полученного результата и др.), а различия между программами – выбранными языками программирования и операционными системами.

◊ Каждая программа сопровождается обязательной ссылкой на набор тестовых примеров, что необходимо для проверки ее работоспособности [2]. ◊.

В общем случае множества Prog и Alg могут быть пустыми (число элементов этих множеств зависит от степени изученности задачи). Если ни один из алгоритмов множества Alg не запрограммирован, Prog = Ø. Если в соответствие постановке задачи не поставлен ни один алгоритм, Alg = Ø и Prog = Ø.

□Спецификация spec s-задачи – это пара (Formul, as), где as – описание применения.□

☼ Формулировка задачи линейного программирования. Вход задачи Inp = {матрица a [i = 1…m, j = 1…n] коэффициентов ограничений, вектор b [i = 1…m] правых частей ограничений, вектор c [j = 1…n] коэффициентов целевой функции}. Выход Out = {искомый вектор x [max; j = 1…n]}. Правило rul максимизации по x [j = 1…n] целевой функции c [j = 1…n] * x [j = 1…n] при ограничениях a [i = 1…m, j = 1…n] * x [j = 1…n] ≤ b [i = 1…m] и x [j = 1…n] ≥ 0 имеет следующий вид:

max [x [j = 1…n]: a [i = 1…m, j = 1…n] * x [j = 1…n] ≤ b [i = 1…m], x [j = 1…n] ≥ 0] (c [j = 1…n] * x [j = 1…n]) [2]. ☼

/ Связи по памяти между s-задачами

Связи по памяти между s-задачами определяются тремя типами функций, каждая из ко­торых является функцией двух аргументов и позволяет по­ставить в соответствие паре s-задач некоторую третью s-задачу, образованную из этой пары.
□ S-задача a связана с s-задачей b по памяти, если существует хотя бы одна пара элементов {elem Mem[a], elem Mem[b]}, принадлежащих памяти Mem[a] s-задачи a и памяти Mem[b] s-задачи b, от­носительно которой определено общее означивание (эле­менты имеют одно и то же множество значений). Пусть S и H – множества s-задач и D ≤ S * S. Если каждой паре (s[i], s[j]) элементов из D ста­вится в соответствие определенный элемент из H, то будем говорить, что задана функция связи по памяти h = conn (s[i], s[j]). При этом D будем называть областью определения функции conn и обозначать D [conn]. Множество R = {h: elem H; h = conn (s[i], s[j]); s[i]: elem D[conn], s[j]: elem D[conn]} будем называть областью значений функции conn. 
Тип связи зависит от содержимого пересечения по памяти: составлена ли связь из элементов выхода одной и входа дру­гой задачи; из элементов выходов задач или из элементов их входов; или же связь получена путем комбинации предыду­щих способов. Будем обозначать функцию связи по памяти типа вход-вход через conn[x], выход-вход – через conn[yx] и выход-выход – через conn[y].

/ Родовые связи между s-задачами

□ S-задача может быть прообразом некоторого непус­того множества s-задач или образом некоторого прооб­раза; или быть одновре­менно и образом какой-то одной s-задачи, и про­образом некоторого множества других s-задач.

Предусмотрены следующие типы родовых связей между s-задачами:

s‑(специализация задачи) — указание на s-задачу, частную по отношению к исходной;

s‑(обобщение задачи) — указание на s-задачу, которая служит обобщением исход­ной. □

/ Конструирование s-задачи

□ S‑(конструирование задачи) реализуется посредст­вом связи по памяти между задачами. Элементарная задачная конструкция — это задачная пара. Из задачных пар можно построить более сложную задачную конструкцию, если рассматривать их как задачные элементы. Любая задачная конст­рукция, в свою очередь, может быть использована как со­ставляющая еще более сложной задачной конструкции. □

/ Конкретизация s-задачи

□ S‑(конкретизация задачи) — это переход формулировка → алгоритм → программа).

Для s-задач, имеющих пустое множество программ (Prog = Ø), конкретизация сводится к выбору или разработке алгоритма. Если и Alg = Ø, s-задача может быть использована в s‑(конструированиии задач), но не может быть конкретизирована. □

/ Атомарная s-задача

□ S-задача называется атомарной, если её формулировка не представлена в виде структуры, заданной на некотором множестве формулировок других s-задач. Будем также говорить об атомарной s-задаче как о простой s-задаче. □ Простая задача (с точки зрения построи­теля задачных конструкций) не наделена внутренней струк­турой и потому не подлежит декомпозиции. Простые задачи используются для создания конструкций. Каждая созданная задачная конструкция может быть объявлена некоторой новой задачей. В свою очередь, эти новые задачи вместе с атомар­ными могут быть применены при конструировании задач.

/ Литература

1. В.Д. Ильин, Система порождения программ, М.: Наука, 1989, 264 с.

2. А.В. Ильин, Конструирование разрешающих структур на задачных графах системы знаний о программируемых задачах, Информационные технологии и вычислительные системы, №3, 2007, с.30-36

PDF-файл статьи

Эта статья — в сети ResearchGate.net

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s