< table name="demo_Table" what="ID, Name, Status"
source="redefined_table"/>
записями-->
< table name="demo_Table" what="*"/>
< table name="demo_SubTable" what="*" where="LIMIT 0,2"/>
< table name="demo_Table" what="*"/>
Наиболее важной частью всей разработки является модуль, от-
вечающий за автоматическое наполнение интерфейса и контроль це-
лостности данных, а также за автоматический контроль изменений,
сделанных пользователем. Этот модуль называется CDM (client data
manager). Связь между серверной и клиентской частью продукта
осуществляется именно через него. Ключевую роль здесь играют ат-
рибуты datasource и datafield (они есть у всех WIML объектов), так
как в них хранятся указатели на нужные записи из БД. В момент
загрузки страницы создается hash-таблица для увеличения скорости
доступа к элементам пользовательского интерфейса. Когда же в бра-
узере пользователя уже будут инициализированы объекты данных
и самого интерфейса, вызывается метод CDM.populateLayout(). Он
распространяет данные по всем компонентам. В дальнейшем изме-
нение данных, инициированное событиями onchange (для компонент
типа input) и/или внутренними методами интерактивных элементов,
298
будет автоматически учтено объектом CDM. И при вызове метода
сохранения данных CDM.executeRequest() серверу будут отправле-
ны только измененные данные.
Связь между пользовательским интерфейсом и серверной частью
системы реализована с помощью специального модуля, который под-
ключается как расширение к PHP. В этом расширении определены
две функции: fnsendrequest и fngetresponse, работа которых сводит-
ся к установлению соединения с DBML сервером и сериализации
данных в XML-RPC для универсализации работы. Для получения
данных программисту необходимо создать 2 ассоциативных массива:
массив с данными и массив с условиями (последний не обязателен),
после чего требуется вызвать вышеуказанные функции. Например:
$arrData = array(’test_Campaigns’ => array(’Netzwerk’ => 25,
’Subnetzwerk’ => 0, ’Name’ => ’Camp’));
$arrConditions = array(’test_Campaigns’ => array(’Name’ =>
’LIKE’));
$arrData = fngetresponse(fnsendrequest(’192.168.7.60:8000’,
’dbml.select’, $arrData, ’getSimpleList’, $arrConditions));
Для сохранения данных необходимо выполнить следующий код:
$arrData = fngetresponse(fnsendrequest(’192.168.7.60:8000’,
’dbml.update’, $_POST[’CDMRequest’]));
Далее данные автоматически интерпретируются объектом CDM,
выводятся в пользовательский интерфейс, и происходит автомати-
ческий мониторинг изменений.
Данная разработка может быть полезна для программирова-
ния административных интерфейсов Web-сайтов, систем управле-
ния данными в режиме on-line и для корпоративных ethernet-
приложений. Гибкость и простота использования системы обеспе-
чивают необходимый уровень надежности и безопасности, так как
программисту не надо заботиться о конкретных компонентах его
приложения. Строгая модульность системы также дает свои плюсы:
конкретное Web-приложение становится независимым от контекста
задачи, а изменение компонентов будет влиять на всю систему в це-
лом.
299
Виноградов Е.В.
Санкт-Петербургский государственный университет
Методика учета инструментальной и
методической погрешности вычисления
положительного полинома
Рекомендовано к публикации профессором Меньшиковым Г.Г.
Введение. Вычисления на компьютере обычно проводятся с по-
грешностью, обусловленной разными факторами – размерами пере-
менной, в которой сохраняется результат, ограничениями на количе-
ство шагов при вычислении ряда, и т.д. Для того, чтобы уместить
результат в переменную, в большинстве случаев используется то или
иное округление [1]. Для обеспечения доказательности вычислений в
данном случае требуется модифицировать вычислительный процесс
с тем, чтобы получить на выходе интервал, гарантированно содер-
жащий искомый результат. При этом полная замена традиционных
вычислений интервальными не всегда оправдана, так как, например,
с ростом количества операций они дают излишнее расширение ре-
зультирующего интервала. Предлагается использовать комбиниро-
ванный метод – вычислять значение функции в традиционной мане-
ре, а потом проводить учет полной погрешности такого вычисления
в манере интервальной.
1. Анализ погрешности вычисления положительного по-
линома. Рассмотрим на некотором базовом промежутке (БП)
[0, x
δ
] полином с неотрицательными коэффициентами
ϕ(x) = a
0
+ a
1
x + . . . + a
n
x
n
.
Пусть коэффициенты a
i
точно задаются машинными числами и
ϕ(x) вычисляется по схеме Хорнера:
ϕ(x) = (..((a
n
x + a
n−1
)x + a
n−2
x + . . . + a
1
)x + a
0
.
Пусть w – "текущее значение" полинома в процессе вычисления
и запишем алгоритм Хорнера системой соотношений:
w := a
n
,
300
w := wx, w := w + a
n−1
,
. . .
w := wx, w := w + a
0
.
Машинные операции и их результаты символизируем знаком
"тильда", погрешность конкретной операции – θ
i
. Выразим машин-
ные результаты через точные:
w := wxθ
2
,
w := (w + a
n−1
)θ
2
,
. . .
w := wxθ
n
,
w := (w + a
1
)θ
n
,
w := wxθ
n+1
, w := (w + a
0
)θ
n+1
.
Зафиксируем, какой из членов полинома на какие θ умножается:
a
0
θ
n+1
,
a
1
θ
n+1
θ
n+1
θ
n
,
. . .
a
n−1
θ
n+1
θ
n+1
. . . θ
3
θ
3
θ
2
,
a
n
θ
n+1
θ
n+1
. . . θ
2
θ
2
.
Кроме того, для единообразия структуры добавим еще один
неопределенный параметр θ
1
, хотя присвоение w := a
1
не сопровож-
дается округлением.
Так как точное расположение всех θ ∈ Θ неизвестно, ищем гра-
ницы для ϕ, соответствующие вариации θ:
ϕ(x) ∈ a
n
x
n
Θ
2n+1
+ a
n−1
x
n−1
Θ
2n−1
+ . . . + a
1
xΘ
3
+ a
0
Θ
3
+ a
0
Θ.
Далее, будем считать, что вычислительная система соответствует
гипотезам интервального анализа [2].
В соответствии с леммой 111.1 из [2], величина округления не
может превышать единицы младшего разряда переменной для хра-
нения полученного результата. Чтобы предусмотреть все режимы
округления, вводим константу λ, определяемую машинной арифме-
тикой:
|p − p| ≤ λQ(p),
λ ∈ [µ/2, µ],
301
здесь µ – основание внутренней системы счисления. Отсюда легко
получить выражение для представления машинных результатов че-
рез точные:
p = θp,
θ ∈ Θ =
1
1 + β
,
1
1 − β
,
β = λµ
−s
.
Тогда для фиксированного x ≥ 0 будет справедливо следующее
наименьшее и наибольшее значения ϕ по параметрам Θ:
ϕ(x) >
a
n
x
n
(1 + β)
2n+1
+
a
n−1
x
n−1
(1 + β)
2n−1
+ . . . +
a
0
1 + β
,
ϕ(x) <
a
n
x
n
(1 − β)
2n+1
+
a
n−1
x
n−1
(1 − β)
2n−1
+ . . . +
a
0
1 − β
.
Отсюда следует оценка погрешности:
f (x) − f (x) > β
+
n
a
n
x
n
+ . . . + β
+
1
a
1
x + β
+
0
a
0
,
f (x) − f (x) < β
−
n
a
n
x
n
+ . . . + β
−
1
a
1
x + β
−
0
a
0
,
β
k
=
1
(1
β)
2k−1
− 1.
(1)
Преобразуем эту оценку. Обозначив ψ
k
(x) =
1
(1+x)
2k+1
, по форму-
ле конечных приращений получим
ψ
k
(x) − 1 = ψ
k
(x) − ψ
k
(0) = xψ
k
(θ),
где θ расположено между нулем и x. Так как ψ
k
(x) = −
2k+1
(1+x)
2k+2
, то
|ψ
k
(x) − 1| ≤
2k + 1
(1 + x)
2k+2
|x|.
Полагая x = β и x = −β, видим, что в обоих случаях
|β
±
k
| ≤
(2k + 1)
(1 ± β)
2k+2
β.
Ввиду этого из оценки (1) следует
−
β
(1 − β)
2
σ(x) < ϕ(x) − ϕ(x) <
β
(1 − β)
2
σ(x),
302
σ(x) =
2n + 1
(1 − β)
2n
a
n
x
n
+
2n − 1
(1 − β)
2n−2
a
n−1
x
n−1
+ . . . + a
0
.
Отсюда оценка относительной погрешности
ϕ(x) − ϕ(x)
ϕ(x)
≤
β
(1 − β)
2
σ(x)
|ϕ(x)|
.
(2)
Правая часть (2) зависит от x. Чтобы избавиться от этой зависи-
мости, необходимо искать максимум правой части. При этом спра-
ведлива следующая
Теорема. При неотрицательных коэффициентах полинома f
отношение
σ(x)
ϕ(x)
возрастает.
Доказательство. Меняя индексацию, получаем
ϕ(x) =
n
k=0
a
k
x
k
,
σ(x) =
n
i=0
2i + 1
(1 − β)
2i
a
i
x
i
.
Отсюда
ϕ (x) =
n
k=1
ka
k
x
k−1
,
σ (x) =
n
i=1
(2i + 1)ia
i
(1 − β)
2i
x
i−1
.
Так как (
σ
ϕ
) =
σ ϕ−−σϕ
ϕ
2
, то
σ ϕ − σϕ =
n
k=0
n
i=1
(2i + 1)ia
i
a
k
(1 − β)
2i
x
k+i−1
−
−
n
i=0
n
k=1
(2i + 1)ka
i
a
k
(1 − β)
2i
x
k+i−1
.
Для унификации области значений индексов суммирования во
второй сумме меняем местами i и k. Тогда она примет вид
n
k=0
n
i=1
(2k + 1)ia
i
a
k
(1 − β)
2k
x
k+i−1
.
Отсюда
σ ϕ − σϕ =
n
k=0
n
i=1
(2i + 1)i
(1 − β)
2i
−
(2i + 1)i
(1 − β)
2k
a
i
a
k
x
i+k−1
.
303
Выделим член с k = 0:
n
i=1
(2i+1)i
(1−β)
2i
− i . Так как (1 − β)
2i
< 1, то
(2i + 1)i
(1 − β)
2i
− i > (2i + 1)i − i = 2i
2
> 0.
Оставшуюся сумму разобьем на две: c i > k и с i < k, слагаемые с
i = k аннулируются. Сумму с i > k просто перепишем, а в сумме с
i < k поменяем i и k местами ввиду их равноправия и сложим эти
две суммы:
i>k
ω
ik
,
ω
ik
=
(2i + 1)i
(1 − β)
2i
−
(2i + 1)i
(1 − β)
2k
+
(2k + 1)k
(1 − β)
2k
+
(2i + 1)k
(1 − β)
2k
.
Сгруппировав в ω
ik
первое слагаемое с четвертым и третье со вто-
рым, получаем
ω
ik
=
(2i + 1)(i − k)
(1 − β)
2i
+
(2k − 1)(k − i)
(1 − β)
2k
= (i − k)(
2i + 1
(1 − β)
2i
−
2k + 1
(i − β)
2k
.
Так как i > k, то первая дробь больше второй. Поэтому
i>k
> 0,
следовательно, σ ϕ − σϕ > 0, что и требовалось доказать.
Следовательно, на рассматриваемом базовом отрезке x
δ
= [0, x
δ
0
]
этот максимум достигается при x = x
δ
0
, и справедлива оценка
ϕ(x) − ϕ(x)
ϕ(x)
≤
β
(1 − β)
2
σ(x
δ
0
)
ϕ(x
δ
0
)
= ξ.
2. Формирование локализующего интервала для значе-
ния функции на базовом промежутке. Предположим, что неко-
торое значение x уже содержится в БП. Тогда f через ϕ и погреш-
ности выражается следующим образом:
f (x) = ϕ(x) + (f (x) − ϕ(x))
1
+ (ϕ(x) − −ϕ(x))
2
.
Здесь (f (x) − ϕ(x))
1
– методическая погрешность, (ϕ(x) − ϕ(x))
2
–
трансформированная инструментальная.
Рассмотрим два случая:
1. Для величины (как правило остатка ряда) r(x) = (f (x)−ϕ(x))
1
стали известны границы r(x), r(x);
2. Для (ϕ(x) − −ϕ(x))
2
оценена относительная величина (в соот-
ветствии с предыдущей частью)
ϕ(x) − ϕ(x)
ϕ(x)
≤ ξ.
304
Выразим оценку относительной погрешности через ξ:
ϕ − ϕ
ϕ
=
ϕ
ϕ
ϕ − ϕ
ϕ
≤ ξ
ϕ
ϕ
= ξ/ 1 +
ϕ − ϕ
ϕ
,
т.е.
ϕ − ϕ
ϕ
≤ α =
ξ
1 − ξ
,
−αϕ ≤ (ϕ(x) − ϕ(x))
2
≤ αϕ.
Отсюда следует включение для f :
f (x) ∈ [(1 − α)ϕ(x) + r(x), (1 + α)ϕ(x) + r(x) = F
0
(x).
В приведенной схеме целесообразным представляется проводить
вычисление в неинтервальной манере только значения ϕ(x), а даль-
нейшие манипуляци для получения конечного результата проводить
уже в интервальной манере с какой-либо обработкой возможных слу-
чаев неоправданного округления. Такие меры необходимы, напри-
мер, в Java [3], где направление округления системой не гаранти-
руется. В качестве такой обработки могут использоваться один или
несколько подходящих методов, например, мажоризация интервала
в сторону расширения через единицу младшего разряда.
Литература
1. Виноградов Е.В. Стандарт IEEE Std 754-1985 и версия по-
стулируемых свойств машинной арифметики для обеспечения
интервально-локализующих вычислений. // Процессы управле-
ния и устойчивость: Труды 36-й научной конференции аспиран-
тов и студентов / Под ред. Н.В. Смирнова, В.Н. Старкова. – СПб.:
Изд-во СПбГУ, 2005. С. 256–260.
2. Меньшиков Г.Г. Локализующие вычисления: Конспект лекций.
Выпуск 1. Введение в интервально-локализующую организацию
вычислений. СПб.: ООП НИИ Химии СПбГУ, 2003. 89 c.
3. The Java Language Specification, Third Edition.
http://java.sun.com/docs/books/jls/third_edition/html/j3TOC.html
305
Грацилевский В.Д., Прилипко Т.А.
Санкт-Петербургский государственный университет
Управляющие системы контроля знаний
Рекомендовано к публикации доцентом Кривцовым А.Н.
1. Актуальность темы. В связи с развитием системы образова-
ния появилась необходимость программных управляющих комплек-
сов, предназначенных для ведения интерактивного обучения в режи-
ме on-line. В процессе разработок интерактивного обучения возникли
противоречия: существующим разработкам недостает организации
в плане проведения учебных занятий и одновременного проведения
организационного процесса в целом.
Предложения заключаются в следующем:
1. Разработать методический аппарат на основе математических
методов;
2. На основе этой математической модели разработать алгоритм
программной реализации;
3. Создать единый комплекс, включающий в себя управляющую
систему обучения и контроля знаний, состоящую из:
– обучающего блока;
– тестирующего блока;
– управляющего блока;
– блока статистической обработки данных;
– блока конструирования предметной области обучения.
2. Математическая модель. Математическую модель можно
представить с помощью динамического программирования на основе
метода решения задач об оптимальном наборе высоты и скорости.
2.1. Описание. Цель – достичь некоторый уровень знаний за
определенное количество вопросов, следовательно, узнать соответ-
ствует ли уровень студента требуемому (рис. 1). При этом существу-
ет 2 состояния: знает или не знает. Значит, каждый вопрос имеет
весовую единицу по уровню. Более того, считается, что при тести-
ровании желаемый уровень может быть достигнут за определенное
время.
306
Рис. 1. Общее строение
Основная задача состоит в том, каким образом можно опти-
мально подобрать вопросы и сгруппировать их в соответствии с те-
мой, т.е. как найти оптимальную траекторию организации учебного
процесса. При прохождении теста разными людьми можно узнать
затраченное ими время на тот или иной вопрос и таким образом
накапливать статистические данные о затраченном времени при по-
ложительном или отрицательном ответе на каждый вопрос.
Рис. 2. Возможные траектории
С математической точки зрения, данная задача может быть ре-
шена с помощью метода динамического программирования, который
307
базируется на двух формулировках основной теоремы Р. Беллмана.
Первая формулировка: оптимальная стратегия (поведение) системы