Вычислительная техника и прикладная математика

• Название: Вычислительная техника и прикладная математика
• Дата: 12.05.2023
• Размер: 0.78 Mb.
• Имя файла: razdel-3-33.pdf
• Тип: Документы; #1125413
• страница: 2 из 6

Алгоритмы или алгорифмы. При исполь- зовании аппарата нормальных алгоритмов Мар- кова возникает вопрос об их правильном именовании: «нормальные алгориТмы» или
«нормальные алгориФмы».
По всему ходу изложения в работе [1] используется термин «нормальные алгорифмы» как в отношении предложенной алгоритми- ческой модели, так и к алгоритмам вообще.
Исходя из утверждений, приведенных на стр. 135, 143, 399, можно сделать вывод понятие
«алгорифм» в работе [1] – синоним понятия
«алгоритм». Однако «алгоритм» является более употребительным термином, поэтому в данной работе используется термин
«нормальные алгоритмы».
Заключение. В данной статье проанализи- рованы известные модификации и обобщения нормальных алгоритмов Маркова.
Предложена модификация нормальных алго- ритмов Маркова, в которой введена возможность последовательного выполнения подстановок.
Предложенная модификация названа линейными нормальными алгоритмами.
На примере классических задач теории нормальных алгоритмов Маркова показано, что предложенная модификация позволяет сделать алгоритмы более эффективными по сравнению с нормальными алгоритмами Маркова, уменьшая как число шагов, необходимых для решения задачи, так и количество подстановок в схеме.
Показано, что любой линейный нормальный алгоритм имеет эквивалентный ему нормальный алгоритм Маркова.
Прикладное значение предложенной моди- фикации нормальных алгоритмов Маркова заключается в следующем:
1) линейные нормальные алгоритмы явля- ются алгоритмической моделью, и, следова- тельно, могут использоваться для описания алгоритмов;
2) линейные нормальные алгоритмы могут использоваться для оценки сложности алгорит- мов и сравнения их трудоемкости;
3) линейные нормальные алгоритмы – одна из простейших алгоритмических моделей, поэ- тому она может использоваться в учебных целях для обучения описанию решения задач в виде алгоритмов и определению их характеристик.
Библиографический список
1. Марков А.А., Нагорный Н.М. Теория алго- рифмов. – М.: Наука, 1984. – 432 с.

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
45 2. Нагорный H.M. Некоторые обобщения поня- тия нормального алгорифма // Тр. матем. ин-та
АН СССР им. В.А. Стеклова, 52. – М.-Л.: Изд.
АН СССР, 1958. – С. 66-74.
3. Цветков И.А. Обращающий самопополняе- мый слева алгорифм в алфавите с одной допол- нительной буквой // Математическое и программное обеспечение вычислительных систем: Межвуз. сб. науч. тр. / Под ред. А.Н. Пылькина. – М.: Горячая линия-Телеком, 2008. – С. 4-9.
4. Новичков В.С.,
Парфилова Н.И.,
Пыль-
кин А.Н. Алгоритмизация и программирование на
Турбо Паскале: учеб. пособие. – М.: Горячая линия –
Телеком, 2005. – 438 с.
5. Мощенский В.А. Лекции по математической логике. – Минск: Изд-во Белорус. ун-та, 1973. – 160 с.
УДК 681.3.06
А.И. Баранчиков, А.Ю. Громов
АЛГОРИТМ ГЕНЕРАЦИИ ФОРМАЛИЗОВАННОЙ МОДЕЛИ
ПРЕДМЕТНОЙ ОБЛАСТИ
Предлагается алгоритм генерации формализованной модели гипотети-
ческой предметной области с заданными параметрами для проверки
алгоритмов построения схем баз данных.
Ключевые слова: предметная область, реляционные базы данных,
модель, атрибут, функциональная зависимость.
Цель. Разработка математического и алго- ритмического обеспечения для программных средств тестирования алгоритмов проектиро- вания схем реляционных баз данных.
Введение. При разработке алгоритмов для построения баз данных [1,2], кроме проверки их сходимости и расчёта временной сложности, возникает задача их статистического анализа путём экспериментальных исследований. Под экспериментальными исследованиями понима- ется многократное применение разработанных алгоритмов к различным наборам входных данных, как для проверки их корректности, так и для анализа эффективности, при изменяемых параметрах экспериментов.
Предлагается алгоритм генерации формали- зованной модели гипотетической предметной области с заданными параметрами.
Описание алгоритма.
Вход:
 количество l функциональных зависимо- стей f F;
 вероятностные характеристики модели- руемых параметров.
Выход:
 множество атрибутов A = (a
1
, a
2
, …, a
n
);
 схема отношения R = (R
1
, R
2
, …, R
k
);
 множество функциональных зависимо- стей F= (f
1
, f
2
, …, f
m
).
Теоретические исследования
Классификация параметров, характери-
зующих семантическую сложность формали-
зованной предметной области. Основные пара- метры формализованных предметных областей, выступающие в качестве входных данных при проектировании реляционных баз данных, можно классифицировать следующим образом:
1) общее количество входных атрибутов
a  A.
От общего количества n входных атрибутов
a зависит как временная сложность реализации алгоритма S, так и сложность набора входных функциональных зависимостей f  F;
2) количество m функциональных зависи- мостей f  F.
От данного параметра зависит количество шагов, необходимых для поиска транзитивных зависимостей, а значит, и на временную слож- ность реализации алгоритма S;
3) количество атрибутов a  A в каждой функциональной зависимости f F.
Данный параметр влияет на сложность функциональных зависимостей f F, также от него зависит временная сложность обработки каждой функциональной зависимости.
Варианты с разным количеством атрибутов в каждой функциональной зависимости f F:
1. (BC, CDE, BF).
2. (BHCEFL, CDSKY, BKXFNQPW).

46
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
4) глубина транзитивности входного набора функциональных зависимостей f F.
От глубины транзитивности зависит слож- ность связей между функциональными зависи- мостями f F, а значит, и временная сложность обработки этих связей. Моделирование данного параметра является отдельной задачей и в данной работе не рассматривается.
Варианты наборов функциональных зависи- мостей f  F с разной глубиной транзитивности:
1. (BC, CD).
2. (BC, CD, DE, EF, FG).
1) количество ключей в каждой функцио- нальной зависимости:
1. (BC, CD).
2. (BСDE, FGH, IJKML).
2) количество секретных атрибутов в каж- дой функциональной зависимости (секретные атрибуты выделены подчеркиванием):
1. (BHCEFL, CDSKY, BKXFNQPW).
2. (BHCEFL, CDSKY, BKXFNQPW).
Далее будет рассмотрено моделирование следующих параметров:
 количество ключей
n
K
в каждой функциональной зависимости;
 количество открытых атрибутов n
A
в каждой функциональной зависимости;
 количество секретных атрибутов n
S
в каждой функциональной зависимости.
Вероятностная модель. В качестве инстру- мента моделирования рассмотренных ранее параметров использована вероятностная модель, основанная на нормальном законе распреде- ления случайной величины. Нормальный закон распределения выбран на основании экспертных оценок, данных специалистами в области проектирования реляционных баз данных.
Для задания параметров предметной области используем следующие вероятностные характе- ристики:
 - математическое ожидание конкретного параметра предметной области;
 - среднеквадратическое отклонение пара- метра;
f(x) - функция плотности вероятности данного параметра.
Пусть f(x)имеет вид нормального распре- деления [3] (рисунок 1):
)
2
)
(
(
2 2
2 1
)
(







x
e
x
f
(1)
Проквантуем данную функцию с шагом
h=0.5 (рисунок 2).
Рисунок 1 – Функция плотности вероятности
(=4, =1)
Рисунок 2 – Преобразование функции
плотности вероятности
С учетом правила трёх сигм[3] практически все значения нормально распределённой случай- ной величины лежат в интервале [-3;+3], где  - математическое ожидание случайной величины. Найдём вероятность событий x:
P(x)  Δx f(x),
Δx = 2h,
f(x) = (f(x - h)+ f(x + h))/2,
P(x) = 2h(f(x - h)+ f(x + h))/2 =
= h (f(x - h)+ f(x + h)).
(2)
В силу того, что данная вероятностная модель необходима для нахождения величин целочисленных неотрицательных параметров, то на неё накладываются следующие ограничения:
1. Величина среднеквадратического откло- нения  выбирается из следующего условия:
3  -1, данное неравенство обеспечивает минимальное значение параметра, равное единице.
2. Величина задаваемого математического ожидания является целочисленной и не должна быть менее 2:
  2.
3. Количество величин рассчитываемых вероятностей зависит от величины среднеквад- ратического отклонения :
m = 6 - 1.

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
47
В зависимости от заданных характеристик находим величины вероятностей P(x), где x – значение моделируемого параметра,
а S
P
— при- близительное значение площади фигуры под
f(x).
Цель разработки: разработать алгоритм генерации формализованной модели предметной области для проектирования схемы реляционных баз данных.
В настоящее время большинство алгоритмов построения схем реляционных баз данных основано на приведении входных отношений к третьей нормальной форме (3НФ) (в редких случаях к нормальным формам более высокого порядка), то есть на преобразовании входной схемы R = (R
1
, R
2
, …, R
k
) в схему R = (R
1
, R
2
,
…, R
p
), лишенную транзитивных зависимостей, которые в общем случае должна содержать генерируемая предметная область.
Под атрибутами понимается множество
A=(a
1
, a
2
, …, a
n
), которое впоследствии будут разделено на множество открытых
X и секретных Y (таблица 1).
Таблица 1
Атрибут
Секретность
Ключевой
1 0
1
…
n
0 0
Массив функциональных зависимостей заполняется в виде таблицы 2.
Таблица 2
Атрибут
Номер
ФЗ
Левая часть
Правая часть
1 1
1 0
…
2 1
1
n
2 1
0
Экспериментальные исследования
Алгоритм.
Вход:
 количество l функциональных зависи- мостей f F;
 математические ожидания моделируе- мых параметров.
Выход:
 множество атрибутов A = (a
1
, a
2
, …, a
n
);
 схема отношения R = (R
1
, R
2
, …, R
k
);
 множество функциональных зависи- мостей F = (f
1
, f
2
, …, f
m
).
Расчёт значений параметров xи вероят- ностей их появления P(x).
По введённым ранее ограничениям:
3   - 1    ( - 1)/3.
Наложим на

ещё одно ограничение:
  1.
P(x) = h (f(x - h)+ f(x + h)), где шаг квантования h = 0.5, то есть получаем:
P(x) = 0.5 (f(x – 0.5)+ f(x + 0.5)).
Значения x рассчитываются исходя из следующих выражений:
x
max
= + 3; x
min
= - 3.
Количество выборок m рассчитывается по формуле:
m = 6 - 1.
В результате получаем набор значений xи приблизительную вероятность их появления:
x = [x
1
; x
2
; …; x
m
],
P = [P
1
; P
2
; …; P
m
].
Полученные данные будут использоваться в виде таблицы 3:
Таблица 3
Значение параметра x
Границы вероятности P значения x
Левая граница
Правая граница
x
1 0
P
1
x
2
P
1
P
1
+ P
2
…
…
…
x
m
P
m-1
P
m
С помощью таблицы 3 и генератора случай- ных чисел происходит выбор значений пара- метров предметной области.
Шаг 1. Расчёт вероятностей значений пара- метров предметной области и заполнение соот- ветствующих массивов по образцу таблицы 3.
На данном шаге происходит заполнение таблиц вероятностей для следующих параметров предметной области:
 количество ключевых атрибутов в каждой функциональной зависимости f F;
 количество открытых атрибутов в каждой функциональной зависимости
f F;
 количество секретных атрибутов в каждой функциональной зависимости
f F.
Алгоритм Mod ();
вход: математическое ожидание
 моделируемого параметра;
выход: массив вероятностей P значений x моделируемого параметра;
begin
 = ( - 1) / 3;
if  > 1 then  = 1;

48
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
m = 2 ( - 1) - 1;
x =  - 3;
for i = 1 to m do
begin
if x =  then
Sp
i
=0.5(exp(-(x-)
2
/2
2
)/2
2
+exp(-
((x+0.5)-)
2
/2
2
)/2
2
);
else
Sp
i
=0.5(exp(-((x-0.5)-)
2
/2
2
)/2
2
+exp(-
((x+0.5)-)
2
/2
2
)/2
2
);
x = x+1;
Sa = Sa + Sp
i
;
end;
for i = 1 to m do P
i
= Sp
i
/Sa;
end;
Шаг 2. Заполнение массива функциональ- ных зависимостей f F.
Расчёт количества открытых атрибутов n
A
функциональных зависимостей f F по задан- ному значению математического ожидания
A
:
begin
y= Random(100);
if y  [P
i-1
; P
i
] then n
A
= x
i
;
end;
Расчёт количества ключевых атрибутов n
K
функциональных зависимостей f  F по задан- ному значению математического ожидания

K
:
begin
y= Random(100);
if y  [P
i-1
; P
i
] then n
K
= x
i
;
end;
Расчёт количества секретных атрибутов n
A
функциональных зависимостей f F по задан- ному значению математического ожидания 
A
:
begin
y = Random(100);
if y  [P
i-1
; P
i
] then n
S
= x
i
;
end;
Каждый атрибут а  Aможет принадлежать как к левой, так и к правой части функцио- нальной зависимости f  F либо сразу к обеим частям.
По полученным значениям параметров пред- метной области происходит построение мно- жества функциональных зависимостей.
Алгоритм Gen (n
F
, n
K
, n
A
, P, x);
вход:
 массив вероятностей P значений x моде- лируемого параметра;
 количество открытых n
A
, ключевых n
K
и секретных n
S
атрибутов;
выход:
 массив функциональных зависимостей f;
 массив атрибутов a;
 схема отношения R;
begin
z = 1;
for i = 1 to n
F
do
begin
y= Random(100);
if y  [P
i-1
; P
i
] then n
A
= x
Ai
;
y = Random(100);
if y  [P
i-1
; P
i
] then n
K
= x
Ki
;
y = Random(100);
if y  [P
i-1
; P
i
] then n
S
= x
Si
;
n = n
A
+ n
S
;
for j=1 to n
K
do
begin
K = a
z
 K;
z = z+1;
end;
for j=1 to n
S
do
begin
S = a
z