close

Вход

Забыли?

вход по аккаунту

?

1442.Студенческие заметки по информатике и математике Вып 2

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П.Г. Демидова
Факультет информатики и вычислительной техники
Студенческие заметки
по информатике и математике
Материалы научной конференции
студентов и аспирантов факультета ИВТ
Выпуск 2
Ярославль 2008
С.В. Алешин
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 51(091)
ББК В1я43
С 88
Рекомендовано
Редакционно-издательским советом университета
в качестве научного издания. План 2007 года
С 88
Студенческие заметки по информатике и математике : Материалы научной конференции студентов и аспирантов факультета ИВТ / отв. ред. А.Н. Морозов ;
Яросл. гос. ун-т. – Ярославль : ЯрГУ, 2008. – Вып. 2.–
124 с.
В сборник включены материалы научной конференции, представленные аспирантами и студентами факультета ИВТ. Темы докладов касаются важных направлений развития математики, информатики и вычислительной техники.
УДК 51(091)
ББК В1я43
Редакционная коллегия:
В.А. Бондаренко
В.В.Майоров
А.Н. Морозов (ответственный редактор)
В.А. Соколов
© Ярославский государственный университет, 2008
2
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача планирования пути наибольшего
веса на правильной квадратной решетке
С.В. Алешин
В работе рассмотрена задача планирования пути наибольшего веса на правильной квадратной решетке и предложен алгоритм, реализующий поиск такого пути. Данная работа может
найти практическое применение в МЧС для эффективного спасения людей на водах, в роботехнике для построения путей роботов. Рассматриваемую задачу следует отнести к задачам поиска
пути на графе [1], но в такой постановке, как в данной работе, в
доступной литературе не встречается.
Постановка задачи
Рассмотрим на плоскости правильную квадратную решетку
N×N. Обозначим множество узлов решетки через {V}, а общее их
количество через |V|.
Каждый узел решетки обозначим как Vij, где i – это номер
строки, а j – номер столбца решетки. Окрестностью узла Vij назовем множество узлов {Vокр}ij={Vi-1 j-1, Vi-1 j, Vi-1 j+1, Vi j-1, Vi j+1, Vi+1
j-1, Vi+1 j, Vi+1 j+1} такое, что для любого узла Vkl из {Vокр}ij выполнено 0≤k,l≤N-1. В частности, окрестность узла V00 состоит из
трех узлов: {V01, V10, V11}.
Дугу, соединяющую узлы Vij и Vkl, где Vkl принадлежит
{Vокр}ij, обозначим через . Длины всех дуг положим равными 1.
Путем из узла Vij в узел Vkl назовем чередующуюся последовательность узлов и дуг Vij Vab … Vyz Vkl и обозначим через
. Длиной пути назовем количество дуг, входящих в него и обозначим как | |.
С.В. Алешин
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пусть каждому узлу Vij приписан некий вес Mij≥0. Рассмотрим множество P путей, начинающихся в Vij и имеющих длину
не более заданной величины T. Задача состоит в определении пути Pk из множества P, в т.ч.
была наибольшей.
Заметим, что поскольку длина дуги равна 1, то на прохождение этого маршрута уходит не более T тактов времени.
Идея алгоритма
Рассмотрим область G, содержащую начальный узел Vij и узлы Vkl такие, что | |≤T, т.е. узлы, которые могут быть достигнуты из начальной вершины за время T. Обозначим через M множество узлов, входящих в G и имеющих положительные веса.
Последовательно для каждого узла Vmn из M проведем оценку. Рассмотрим область Q, содержащую узел Vmn и узлы Vst такие, что | |≤T-| |. Множество узлов, входящих в M\Q и имеющих положительные веса, обозначим через R, а количество таких
узлов обозначим через |R|.
Вычислим сумму весов узлов из множества R. Обозначим ее
как SUM(R). Сумма имеет следующий смысл: масса, которую
теоретически можно потерять, если из начального узла передвинуться в узел Vmn. Вычислим величину равную отношению
SUM(R) и |R|, обозначим ее через ρ. Эта величина имеет следующий смысл: чем она больше, тем меньше узлов с большей массой
расположено в области R.
Таких отношений у нас будет столько же, сколько узлов содержится во множестве M. Двигаться из начального узла надо в
такой узел Vmn, которому соответствует наименьшее отношение ρ
и сумма SUM(R). Если таких узлов несколько, то составим из них
список SP1. Если таких узлов нет, то составляем список SP2, в
который включаем узлы, соответствующие одному из условий.
В качестве начального узла на следующем шаге выбираем
первый элемент из непустого списка. Полагаем, что в узле Vmn
вес стал нулевым, Vmn стал начальным узлом, в качестве T берем
T-| |.
Повторяем описанный выше алгоритм до тех пор, пока T не
станет равно нулю либо пока на очередном шаге множество M не
4
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
окажется пустым. В итоге определяется путь, массу которого помещаем в массив m.
Далее в качестве начального узла выбираем следующий элемент из списка и аналогично для него проводим описанный выше
алгоритм. В итоге в массиве m будут записаны все найденные
массы путей. Выберем из него путь, соответствующий наибольшей массе.
При реализации алгоритма была построена нейронная сеть.
Для выделения нужных областей на решетке использовалась способность нейронов генерировать и передавать импульсы [2, 3, 4].
Пример работы алгоритма
Начальное состояние решетки.
Темно-серым выделен начальный
узел, а светло-серым – узлы с положительным весом. Т=4.
Темно-серым выделен начальный
узел, серым – множество G (узлы, которые могут быть достигнуты из начального), светло-серым – узлы множества M.
С.В. Алешин
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Первый шаг.
Для узла с весом 5 SUM(R)=6, ρ=2,
что является минимумом. В качестве
начального теперь берется этот узел.
Теперь T=2.
Итог работы алгоритма. Всего сделано 3 шага.
Выделен путь.
 Литература
[1] Мельников О.И. [и др]. Лекции по теории графов. М.: Наука. Гл.
ред. физ.-мат. лит., 1990. 384 c.
[2] Короткин А.А. Математические модели искусственных нейронных сетей: уч. пособие. Ярославль: Яросл. гос. ун-т, 2000. 55 с.
[3] Майоров В.В., Шабаршина Г.В. Сети W-нейронов в задаче ассоциативной памяти // Журнал выч. матем. и матем. физики. Т. 41, № 8. 2001.
С. 1289–1299
[4] Майоров В.В., Шабаршина Г.В. Сообщение о сетях W-нейронов
// Моделирование и анализ информационных систем. 1997, Вып. 4. С. 37–
50.
6
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алгоритм построения
интерполяционных изображений,
основанный на методе кодирования IFS
А.А. Великанова
Хранение и обработка графической информации связаны с
большими затратами машинных ресурсов. Размеры требуемой
памяти можно существенно уменьшить благодаря кодированию
изображений. С развитием видеотехники особенно актуальным
становится кодирование набора взаимосвязанных изображений
(кадров), таких, например, как видеофильм. Обычно на рядом
расположенных кадрах видеофильма изображения меняются незначительно. Можно было бы запоминать не каждый кадр из последовательности, а лишь некоторые и недостающие изображения восстанавливать по оставшимся изображениям.
В данный момент нет общепризнанного метода построения
промежуточных изображений.
Если два изображения закодированы методом IFS, т.е. представлены наборами коэффициентов аффинных преобразований,
то можно рассмотреть переходные наборы аффинных преобразований.
Рассмотрим два изображения G* и G**, закодированные методом IFS.
Пусть
G* = lim F0 (G ) ,
G** = lim F1 (G ) ,
n →∞
n→∞
где F0 и F1 – отображения, задаваемые аффинными коллажами:
m
F0 =  Ai (G ) ,
i =1
m
F1 =  Bi (G ) .
i =1
Ai(G) и Bi(G) – аффинные образы множества G.
 x   a11i
Ai   =  i
 y   a 21
a12i  x   a1i 
  +  i  ,
i  
 
a 22
 y   a 2 
А.А. Великанова
λ1i , 2 < 1 ,
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 a11i
где λ – собственные значения матрицы  i
 a 21
 x   b i b12i  x   b1i 
  +  i  ,
Bi   =  11i
i  
 
y
b
b
   21 22  y   b2 
i
1, 2
μ1i, 2
a12i 

i .
a 22

μ1i, 2 < 1 ,
 b11i b12i 

– собственные значения матрицы  i
i .
b
b
 21 22 
Изучим промежуточный (интерполяционный) аффинный
m
t
коллаж F =  C i (G ) между
t
i =1
F0
и
F1 ,
определяемый аффинными
преобразованиями
 x   ci
C it   =  11
i
 y   c 21
c12i  x   c1i 
  +  i  .
i  
 
c 22
 y   c 2 
В результате должна получаться последовательность интерполяционных коллажей Ft, 0≤t≤1, в которой значению t=0 соответствует исходный коллаж (изображение G*), а значению t=1 –
конечный коллаж (изображение G**).
Будем подробнее изучать интерполяционные матрицы, а точнее их собственные значения. Для того чтобы аффинный коллаж
задавал какое-то изображение, нужно, чтобы преобразование было сжимающим, т.е. собственные значения интерполяционных
матриц должны быть по модулю меньше 1. Учитывая то, что исходные матрицы соответствуют этому условию, попробуем узнать, выполняется ли это для интерполяционных матриц.
Для произвольных матриц довольно сложно подобрать ограничения на коэффициенты, при которых собственные значения
этих матриц были бы по модулю меньше единицы. Поэтому
предлагается рассматривать класс симметрических матриц. Эти
матрицы обладают особыми свойствами, которые можно использовать при решении поставленной задачи.
Пусть матрица А принадлежит одному из аффинных преобразований, кодирующих начальное изображение, матрица В – кодирующих конечное изображение матрицы C t .
8
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Теорема
Для того чтобы собственные значения симметрической мат а11
рицы  а

а 
 были по модулю меньше единицы, необходимо и
а 22 
достаточно выполнения следующих условий:
−
p 2 − 4q
≤a≤
4
a11 =
p±
p 2 − 4q
4
p 2 − 4(a 2 + q)
2
где точка ( p, q) ∈ G = {( p, q) : − 1 < p < 1
изображенной на рисунке:
a 22 = p − a11 ,
p − 1 < q < p2
},
Разработан алгоритм построения интерполяционных матриц между двумя симметрическими при помощи интерполяции собственных векторов и собственных значений. В основе алгоритма
лежит тот факт, что каждая симметрическая матрица второго порядка имеет два ортогональных собственных вектора, соответствующих различным собственным значениям. Известно, что симметрическую матрицу можно представить в виде произведения
трех матриц, коэффициенты двух их которых состоят из координат собственных векторов, а третья – диагональная – собственных значений и нулей.
А.А. Великанова
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Матрицу A раскладываем в произведение матриц
 λ1 0  /  v1 v 2  λ1

 ⋅ T = 
A = T ⋅ 
 0 λ2 
 v3 v 4  0
0  v1 v3 
,

λ 2  v 2 v 4 
где λ1 и V 1 (v1 , v 2 ) , λ2 и V 2 (v3 , v 4 ) соответствующие собственные значения и собственные векторы. μ1 и U 1 (u1 , u 2 ) , μ 2 и U 2 (u3 , u 4 ) соответствующие собственные значения и собственные векторы для
матрицы В.
Матрицу C t будем находить, начиная с построения её разложения
в произведение матриц, аналогичное разложению A и B.
Собственные значенияτ 1 , τ 2 интерполяционной
( 0 ≤ t ≤ 1 ) найдем по формулам:
матрицы
Ct
τ 1t = (1 − t )λ1 + tμ1
τ 2t = (1 − t )λ2 + tμ 2
Из геометрического смысла линейного преобразования, осуществляемого симметрической матрицей, будем искать собственные
векторы матрицы C t , как интерполяционные между собственными векторами матриц A и B.
Обозначим собственные векторы матрицы
Ct
как
W1t = ( x1 , y1 )
W1t = ( x 2 , y 2 )
x1 = v1 ⋅ cos(α ) − v 2 ⋅ sin(α )
x 2 = v3 ⋅ cos(α ) − v 4 ⋅ sin(α )
y1 = u1 ⋅ sin(α ) + u 2 ⋅ cos(α )
y 2 = u 3 ⋅ sin(α ) + u 4 ⋅ cos(α )
где α – угол между соответственными векторами (для правильного сопоставления собственных векторов (их нумерации) выбираем их так, чтобы знаки векторных произведений [V1 , V2 ] и [U 1 , U 2 ]
совпадали. Далее в качестве собственных векторов интерполяционных матриц рассматриваем интерполяционные векторы между
V1 и U 1 , V2 и U 2 ).
 x1

 y1
10
x 2 τ 1

y 2  0
0  x1

τ 2  x 2
y1   x12τ 1 + x 22τ 2
=
y 2   x1 y1τ 1 + x 2 y 2τ 2
x1 y1τ 1 + x 2 y 2τ 2 


y12τ 1 + y 22τ 2

Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример
Начальное изображение:
Интерполяционное изображение:
Конечное изображение:
 Литература
1. Алимов Ш.А. Принцип сжатых отображений (Методы прикладного
анализа). М.: Знание, 1983. 64 с.
2. Цифровая обработка телевизионных и компьютерных изображений
/ Под ред. Ю.Б. Зубарева, В.П. Дворковича. M., 1997. 216 с.
3. Беллман Р. Введение в теорию матриц. М.: Наука, 1969. 368 с.
А.А. Великанова
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Об одном стиле программирования,
основанном на использовании
высокоуровневых конечных автоматов
Р.А. Виноградов
В статье предлагается расширение иерархической модели [1]
автоматных программ. Использование новых элементов позволит
сократить графы переходов автоматов без ущерба для понимания
логики автоматных программ.
Рассмотрим систему взаимодействующих детерминированных конечных автоматов A = (A0, A1, …, An).
Обозначим EA = {e1, …, ek} множество всех имён событий, на
которые реагирует автомат A. Определим на множестве EA переменную событий e, в которую будет помещаться имя произошедшего события для автомата A. Текущее значение переменной
e будем обозначать EA(e).
Введём множество XA = {x1, …, xm} запросов автомата A к
объектам управления (входных воздействий).
Также введём ZA = {z1, …, zr} множество выходных воздействий автомата A. Воздействия zi подразделяются на две группы.
Первая группа – это воздействия непосредственно на объект
управления. Воздействия второго типа – передача управления
одному из автоматов модели с некоторым событием (генерация
события для автомата). В этом случае выходное воздействие zi
имеет вид A′(e′j), где A′ – один из автоматов модели, а e′j – сгенерированное автоматом A событие для автомата A′, которому будет передано управление для обработки этого события.
Тогда автомат A управляющей системы автоматов A представляет собой набор (Σ, Q, q0, E, X, Z, δ), где
• Q = {q0, q1, …, qn} – конечное множество состояний автомата A;
• q0 – начальное состояние;
12
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
дов;
• Σ = {a1, a2, …, ak} – конечный алфавит пометок дуг перехо-
• δ : Q × Σ → Q – функция переходов из одного состояния в
другое.
Каждый переход срабатывает по определённому правилу.
Прежде чем описывать правила переходов, введём ещё ряд обозначений.
Для метки перехода a ∈ Σ обозначим E(a) событие, на которое автомат A реагирует при срабатывании перехода с меткой a.
Пусть Z* – множество конечных последовательностей выходных воздействий, тогда для a ∈ Σ обозначим Z*(a) ∈ Z* последовательность выходных воздействий, которую необходимо выполнить при срабатывании перехода с пометкой a.
Также для произвольного состояния q автомата A введём
обозначение Z*(q) ∈ Z* для последовательности выходных воздействий, которая должна выполняться при попадании (переходе)
автоматом в состояние q.
Введем функцию Stack.Add над множеством Z*, означающую
занести последовательность выходных воздействий в стек. Эта
последовательность может быть занесена в стек сразу целиком
или поэлементно помещаться в вершину стека в обратном порядке в зависимости от конкретной реализации стека.
И, наконец, пусть XY(a) – предикат, зависящий от состояний
вложенных автоматов и от значений входных воздействий как
булевых, так и целочисленных, истинность которого необходима
для срабатывания перехода с пометкой a.
Правило перехода из состояния q в состояние q′ по метке a
имеет вид:
q, a: if e = E(a) and XY(a) = true then Stack.Add(Z*(a), Z*(q′)); goto q′.
Правило перехода в новое состояние в общем случае можно
описать следующим образом. После получения события автомат
в зависимости от своего текущего состояния реагирует (или никак не реагирует) на событие, опрашивает параметры объектов
управления (входные переменные), учитывает состояния других
автоматов модели. Затем помещает последовательность выходР.А. Виноградов
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ных воздействий, включая и те выходные воздействия, которые
необходимо совершить при попадании в новое состояние, в стек
и переходит в новое состояние (которое в случае петли может
быть тем же самым). Таким образом, в отличие от иерархической
модели [1], автомат переходит в новое состояние еще до выполнения первого выходного воздействия, указанного на сработавшем переходе.
Стек работает по правилам. Каждое следующее выходное
воздействие берется на выполнение из вершины стека. Выходное
воздействие первого типа, направленное на объект управления,
считается сразу же осуществлённым после его применения, и оно
удаляется из вершины стека. Выходное воздействие второго типа,
представляющее собой передачу управления с событием любому
автомату модели, считается выполненным только лишь после реакции этого автомата на это событие, которая заключается в том,
что оно удаляется из вершины стека, затем либо автомат переходит в новое состояние (срабатывает один из переходов вложенного автомата), либо событие игнорируется автоматом (ни один из
переходов сработать не может). Если стек пуст, то генерируется
событие для одного из автоматов системы – выходное воздействие второго типа помещается в вершину стека.
Расширение иерархической модели [1] новыми элементами
на основе UniMod[2].
Метка на переходе имеет вид
a: E(a) [XY(a)] / Z*(a)
В качестве события может быть символ ‘*’ (однако его можно не указывать), который означает, что переход может сработать
по любому событию, если ни один из переходов, где указано
конкретное событие, сработать не может. Для такого перехода в
качестве выходного воздействия можно указать вызов автомата с
событием ‘*’, что означает, если данный переход сработает, то
указанному автомату будет передано то событие, с которым этот
переход сработал.
Задаются целочисленные входные воздействия, при их использовании необходимо задать область значений.
14
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вводятся следующие типы состояний автомата. Начальное
состояние – обязательное и единственное в автомате, при этом в
такое состояние не должна входить ни одна дуга, а выходить
должна единственная дуга, на которой не должно быть гарда и в
качестве события допустима лишь ‘*’. Конечное состояние – необязательное и может быть не единственное в автомате, при этом
из такого состояния не должна выходить ни одна дуга.
Любой объект управления может генерировать любое событие любому автомату в системе взаимодействующих автоматов.
Генерация события заключается в помещении выходного воздействия второго типа в вершину стека. Реакция автомата на сгенерированное объектом управления событие аналогична реакции
автомата на вызов его любым автоматом с событием. Полуавтомат, или объект с неявно выделенными состояниями. Обычно в
автоматных программах выделяют системно независимую часть,
представленную взаимодействующими автоматами, и системно
зависимую часть – объекты управления, код которых дописывается программистом в текст программы, полученный по системно
независимой части.
Предлагается возможность выделять в объекте управления
системно независимую часть путем реализации некоторых его
входных и выходных воздействий. В качестве входного воздействия может выступать логическая или целочисленная (с указанием
ее области значений) переменная или выражение над другими
входными воздействиями. В качестве выходного воздействия
предлагается использовать элементарное действие над переменной объекта: присвоение ей определенного значения, сложение,
вычитание, умножение или деление ее на число.
Примером такого объекта служит счетчик из автоматной
программы “Ханойские башни”. Он имеет одно входное (целочисленная переменная) и три выходных воздействия (присвоение
значения, сложение и вычитание единицы). По сути, этот объект
имеет 8 состояний по числу значений переменной от 1 до 8 и может быть реализован автоматом, который получает 3 события и
имеет 24 перехода. Причем некоторые из состояний будут недостижимы в зависимости от выбранного в начале количества колец,
а если возникнет необходимость увеличить максимальное значеР.А. Виноградов
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ние переменной, скажем до 16, то придется выполнить в два раза
больше состояний и переходов (16 и 48 соответственно).
Ханойские башни
Ниже приведена автоматная программа, реализующая известный рекурсивный алгоритм “Ханойские башни” [3] и отличающаяся от приведенных в работе [4]. Даны три стержня (A, B и
C), на стержень A нанизано N колец. Необходимо переместить
все кольца на стержень B.
Автомат A0 реализует рекурсию алгоритма “Ханойские башни”. Для этого он использует объект управления – счетчик, реализованный в виде входной целочисленной переменной n и тремя
выходными воздействиями set_n (инициализация), inc_n (увеличить n на 1), dec_n (уменьшить n на 1). Счетчик необходим для
вычисления глубины рекурсии и ее остановки.
Автомат A0 инициализируется событием start, которое посылает ему объект управления Form, при этом инициализирует объекты управления Counter и Rings, и в стек также заносятся два
вызова A0(eAB) и A0(start). Второй вызов появляется из-за того,
что переход осуществляется из начального состояния, и выполнение этого же вызова завершит работу системы автоматов, т.к.
автомат A0 перейдет в конечное состояние. Вызов автомата A0 с
событием eAB ... означает переместить n колец со стержня A на
стержень B ... Если нужно переместить одно кольцо (в частности
n == 1), то автомат A0 вызовет автомат A1 с событием eAB ..., которое означает переместить одно кольцо со стержня A на стержень B … Граф переходов автомата A0 представлен на рис. 1.
Рис. 1. Автомат управления алгоритмом A0
Автомат A1 отвечает за перемещение одного кольца, при
этом проверяет, возможно ли полученное действие. Для проверки
16
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
автомат использует входные воздействия xA, … (есть ли кольцо
на стержне A) и xAB, … (меньше ли верхнее кольцо на стержне
A кольца на стержне B, т.е. возможно ли переместить кольцо со
стержня A на стержень B). В случае если автомат A1 получил на
выполнение некорректное перемещение, то он перейдет в состояние “ошибка”, и сигнал об ошибке будет отображен на экране.
Если полученное действие возможно выполнить, то автомат A1
проверяет с помощью входных воздействий xA7, … какое кольцо
находится сверху, т.е. выбирает номер кольца для его перемещения. Затем совершается собственно перемещение выбранного
кольца: Form. – отобразить перемещение на экране, ztake – забрать выбранное кольцо, zput – положить выбранное кольцо.
Граф переходов автомата A1 представлен на рис. 2.
Рис. 2. Автомат управления перемещением кольца A1
Р.А. Виноградов
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Диаграмма взаимодействия автоматов и объектов управления
представлена на рис. 3.
По построенной модели “Ханойские башни” формально и
вполне однозначно строится программный модуль. Чтобы получить готовую программу, необходимо реализовать всего лишь
объект Form: генерацию события start для автомата A0, инициализацию входной переменной N (количество колец), процедуры
Error и AB7, …
Почему предложенная модель является системой взаимодействующих конечных автоматов? Все дело в используемом стеке –
он также является конечным автоматом, только очень сложной
структуры. Количество “рекурсивных” вызовов автомата (глубина рекурсии) зависит от какого-либо параметра (в примере это n).
Приведенный пример показывает, что предлагаемая технология далеко не идеальна, получающиеся программы выглядят довольно громоздко. В дальнейшем возможно появление входных и
выходных воздействий и даже событий с параметрами (хотя бы
целочисленными), циклов, перебирающих значения параметров,
наборов объектов управления одного типа, сложных структур
данных.
18
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 3. Диаграмма взаимодействия автоматов и объектов управления
Р.А. Виноградов
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 Литература
1. Кузьмин Е. В. Иерархическая модель автоматных программ // Моделирование и анализ информационных систем. Ярославль, 2006. Т. 13,
№ 1. С. 27–34.
2. Гуров В.С., Мазин М.А., Нарвский А.С., Шалыто А.А. UML.
SWITCH-технология. Eclipse // Информационно-управляющие системы,
2004. № 6. С. 12–17.
3. Волченков С.Г., Богомолов Ю.В. Методы построения эффективных
алгоритмов: Учебное пособие. Ярославль: Яросл. гос. ун-т., 2004. 127 с.
4. Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Ханойские башни и
автоматы // Программист. 2002. № 8. С. 82–90.
Задача о нахождении
безопасного пути робота в среде
с динамическими препятствиями
А.В. Вяткин
I. В данной статье рассматривается задача о нахождении пути
(маршрута) для робота на плоскости, содержащей препятствия. В
качестве области на плоскости, в которой перемещается робот,
возьмём квадратную решётку N × N. Предположим, что все клетки
поля пронумерованы. Тогда клетка с индексом (i, j ) в любой момент времени может иметь один из ниже перечисленных статусов:
• 0 – клетка свободна, «пустая»,
• 1 – клетка помечена как препятствие (клетка является «препятствием»),
• 2 – клетка помечена как робот (в клетке находится робот),
• 3 – клетка помечена как выход их лабиринта, т.е. конечная
клетка, куда стремится попасть робот. Предполагаем, что клетка
с данным статусом никогда его не поменяет.
В любой момент времени «пустая» клетка с индексом (i, j )
может стать препятствием с вероятностью ρ и остаться в этом
20
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
статусе k тактов. Тогда в k+1 момент времени клетка принимает
статус 0 и так далее. То есть получаем следующие условия динамического развития (i, j ) клетки в моменты времени t и t+1 соответственно:
Статус в момент времени t
Статус в момент времени t+1
0
1 с вероятностью ρ ,
0
0 с вероятностью 1 - ρ ,
1
1 с вероятностью q=1 - ρ ,
1
0 с вероятностью ρ =1 – q.
Робот занимает одну клетку, как и препятствия. Для робота
указаны начальное и конечное положения: левый нижний угол A
решетки и верхний правый угол B соответственно. Под перемещением робота будем понимать сдвиг (смещение) его в одну из
соседних клеток с общей стороной.
Правила перехода для робота. Предполагаем, что робот перед перемещением проверяет соседние клетки, начиная с крайней
правой и против часовой стрелки.
1. Если мы оказались в ситуации, когда все соседние клетки
имеют статус «препятствие», то робот остается в этой клетке, и в
каждый следующий момент времени проверяет, не освободилась
ли хотя бы одна из соседних клеток. Если да, то перемещается в
нее.
2. Если в окрестности есть свободная клетка, то с использованием волнового алгоритма проверяем, существует ли путь в
конечную клетку. Если нет, то переходим к следующей свободной клетке.
3. Если свободных клеток в настоящий момент больше нет,
то робот переходит в состояние ожидания, оставаясь в той же
клетке.
Данную последовательность действий продолжаем до тех
пор, пока не достигнута клетка со статусом «выход».
Заметим, что путь робота должен быть безопасным. А использование волнового алгоритма позволяет нам сделать попытку выбрать путь минимально возможной длины.
Для нахождения оптимального маршрута используется сеть,
состоящая из элементов, называемых W-нейроны. Описание их
приведено в [0]. W-нейрон в любой момент времени t находится в
А.В. Вяткин
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
одном из трёх состояний: состояние ожидания, состояние возбуждения, состояние рефрактерности. Оно определяется функцией
u(t), называемой мембранным потенциалом. Если в момент t 0
u (t 0 ) > p 0 ( p0 – пороговое значение), то W-нейрон в следующий момент времени переходит в состояние возбуждения. Оно длится
1 такт. Считаем, что W-нейрон здесь генерирует ненулевой выходной сигнал и передает его связанным с ним элементам. Далее
W-нейрон переходит на определенное количество тактов в рефрактерное состояние (состояние невосприимчивости к воздействию со стороны других нейронов). Здесь u(t)=0. После окончания
рефрактерного периода элемент переходит в состояние ожидания
(u(t)=0) и остается в нем, пока на вход не поступит внешний ненулевой сигнал. Заметим, что входящие сигналы суммируются с
ненулевыми весами. Если вследствие этого u (t ) ≥ p0 , то W-нейрон
опять генерирует сигнал.
Алгоритм нахождения безопасного (оптимального)
маршрута для робота
Вернемся к правилу 0 перехода робота. Аналогично работе
[0], приведем описание выбора оптимального пути робота на
плоскости с препятствиями. В клетках нашей квадратной решетки размещены W-нейроны, каждый из которых может оказывать
действие на соседние с ним элементы в соответствии со структурой сети. Будем считать, что нейроны, соответствующие препятствиям, имеют безусловно тормозящие синаптические входы, остальные – суммирующие. Обозначим через wik, ,jl синаптический
коэффициент воздействия (k , l ) -го нейрона на (i, j ) -ый нейрон, граничащий с ним соседней стороной. Будем считать связи между
нейронами сети симметричными, т.е. wik, ,jl = wki ,,lj . Первоначально положим все синаптические веса равными единице.
Пусть в нулевой момент времени все W-нейроны находятся в
состоянии покоя. Подадим на нейрон А единичный внешний сигнал xвн (t ) = 1 . В момент времени t = 1 нейрон сгенерирует импульс.
Будем считать, что пороговые значения мембранных потенциалов
у каждого элемента сети одинаковы и равны 1 ( u 0 = 1 ). Значит, в
момент времени t = 2 W-нейроны окрестности нейрона A перейдут
22
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
на один такт в возбужденное состояние или на r0 тактов в рефрактерное состояние, если они соответствовали препятствиям.
Сам нейрон А переходит в рефрактерное состояние. Процесс генерации импульсов ведет за собой изменение синаптических весов. Если нейрон получает сигнал от другого нейрона вследствие
чего становится активным, то вес связи между этими нейронами
согласно правилу Хебба [3] следует увеличить. Иначе связь между ними не увеличивается.
Процесс генерации импульсов нейронами сети заканчивается, как только волна возбуждения достигает клетки В. На этом
такте мы получаем длину минимального пути и, значит, приблизительный маршрут передвижения робота с текущим расположением препятствий. В соответствии с полученным маршрутом, робот перемещается в клетку, нейрон которой имеет наибольший
синаптический вес. На втором такте ненулевой сигнал подадим
на внешний вход нейрона В. Пороговое значение мембранных
потенциалов полагаем равными u 0 = 2 , то есть в возбужденное состояние будут переходить только те нейроны, синаптические
входы которых имеют достаточный вес. Изменение синаптических весов происходит аналогично изменениям на первом такте.
Такт заканчивается, когда импульс (волна возбуждения) от
нейрона, соответствующего текущему положению робота (или
т. В), достигает нейрона, соответствующего точке В (или текущего положения робота). Основная идея алгоритма (распространения волны, генерации импульсов) заключается в изменении синаптических весов.
II. Так как препятствия в модели возникают случайным образом, то длина найденного пути – случайная величина, для которой естественно рассмотреть математическое ожидание. Эта задача в двумерном случае сложна. Поэтому в работе рассматривается линейный аналог этой задачи.
На прямой располагается N пронумерованных точек, а точки
А и В являются начальным и конечным положениями перемещающегося объекта. В каждый момент времени в любой точке
прямой может появиться препятствие с вероятностью p, и оно остается в ней (них) ровно k тактов (моментов времени). Робот перемещается из i-той точки в i+1, если точка свободна, то есть в
А.В. Вяткин
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ней не присутствует препятствие, в противном случае робот
ждет, пока препятствие в точке i+1 не исчезнет. Предполагается,
что робот не может переходить в точку i-1, ибо это не целесообразно.
В линейном случае нас интересует не сколько длина пути,
ибо она константа и всегда равна N, а время робота, требуемое
для прохождения прямой. Для линейного случая проведены соответствующие расчеты математического ожидания времени пребывания в пути робота (с учетом остановок).
i i+1
A
N штук
B
В
заключение
хочу
выразить
благодарность
Г.В. Шабаршиной за большое внимание к работе и помощь, оказанную в составлении статьи.
 Литература
1. Майоров В.В., Шабаршина Г.В., Анисимова И.М. Сети W-нейронов
в задаче планирования оптимальных путей для точечных роботов
// МАИС. Ярославль. Т. 9, № 2. 2002.
2. Майоров В.В., Шабаршина Г.В. Анисимова И.М. Планирование
безопасных путей для точечных роботов с использованием нейронной сети.
3. Hebb D.O. The organization of Behavior. N.Y.: Wiley. 1949.
Исследование одного алгоритма
для прогнозирования объёма продаж
А.Ю. Грицевич
Любая организация, составляя план действий на некоторую
перспективу, должна оценить тенденции в своей работе, просчи24
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
тать результаты усилий, понять, на что она может и должна рассчитывать в будущем.
Экономическое прогнозирование представляет собой сложный многоступенчатый процесс, в котором необходимо использовать сочетание самых разнообразных методов. Прогнозирование –
важнейший компонент аналитической работы, позволяющий
предсказать вероятное развитие событий, а также оценить, какие
меры воздействия приведут к тем или иным результатам. Правильный выбор метода прогнозирования – залог получения качественной информации для принятия стратегических решений.
При всем многообразии методов прогнозирования наиболее
значимыми, достоверными и часто используемыми являются экстраполяционные методы, базирующиеся на временных рядах.
Временные ряды – статистические данные, отображающие
развитие во времени изучаемого явления. В каждом временном
ряду имеется два основных элемента:
– показатель времени t;
– уровни развития изучаемого явления y, соответствующие
показателю времени t.
Временные ряды обычно служат для расчета четырех различных типов изменений в показателях: трендовых, сезонных,
циклических и случайных.
Тренд – это изменение, определяющее общее направление
развития, основную тенденцию временных рядов.
Сезонные колебания – повторяющиеся из года в год изменения показателя в определенные промежутки времени.
Циклические колебания – колебания, отражающие конъюнктурные циклы перехода от более или менее благоприятной рыночной ситуации к кризису, депрессии, оживлению и снова к благоприятной ситуации.
Разница между циклической и сезонной компонентой состоит в том, что сезонная имеет регулярную периодичность, тогда
как циклические факторы обычно имеют более длительный эффект, который к тому же меняется от цикла к циклу.
Конкретные функциональные взаимосвязи между трендом,
сезонными, циклическими и случайными компонентами могут
иметь самый разный вид. Однако можно выделить два основных
А.Ю. Грицевич
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
способа, с помощью которых они могут взаимодействовать: аддитивность и мультипликативность.
Пусть F – прогнозируемое значение, T – тренд, S – сезонность, E – шум (случайная компонента). Тогда аддитивную модель можно представить как
F =T +S +E,
а мультипликативную модель как
F =T ∗S ∗E .
Разница между моделями заключается в следующем: аддитивной модели присуща практически постоянная сезонная вариация, а у мультипликативной она возрастает или убывает.
Изучив методы прогнозирования объема продаж, проведя их
классификацию и анализ, выявив основные факторы, влияющие
на общую динамику продаж и ее составляющие, предлагается
следующий алгоритм для прогноза.
Итак, по имеющимся данным n наблюдений за совместным
изменением двух параметров t и y {( t i , yi ), i=1,2,...,n} необходимо
определить аналитическую зависимость y t =f(t), наилучшим образом описывающую данные наблюдений и сделать прогноз на k
значений вперед. Без ограничения общности будем рассматривать мультипликативную модель (иначе прологарифмируем
уравнение мультипликативной модели и получим аддитивную
модель).
Прогнозный алгоритм включает в себя следующие шаги: определение семейств уравнений для тренда в общем виде; выявление наилучшего тренда в каждом семействе; из отобранных
уравнений определение наилучшим образом описывающего
входные данные; расчет сезонности; с помощью полученного
уравнения и с учетом сезонности выполнение экстраполяции на
заданный период; расчет доверительного интервала прогноза.
В качестве тренда целесообразно использовать функции, не
содержащие большое количество параметров, так как в противном случае тренд будет отражать случайные колебания, а не основную тенденцию развития явления. Поэтому для выравнивания
временных рядов предлагается использовать линейную, параболическую, гиперболическую, степенную, показательную и логарифмическую функции.
26
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для наилучшего восстановления по исходным статистическим данным неизвестной функции yt и наилучшего сглаживания используем метод наименьших квадратов, в котором в качестве решения принимается точка минимума суммы квадратов
отклонений между теоретическим и эмпирическим уровнями:
2
S =  ( yt, − yi ) → min.
Таким образом, получаем 6 трендов. Из них необходимо выбрать тот, который наилучшим образом описывает входные данные. Для оценки тренда существует множество критериев. Рассмотрев такие критерии, как показатель детерминации, среднюю
ошибку аппроксимации и F-критерий Фишера, можно сделать
вывод, что в результатах, которые показывают эти критерии, нет
принципиальных различий, а именно, если один критерий говорит, что данный тренд наилучший из представленных, то об этом
говорят и другие критерии. Поэтому для оценки тренда можно
использовать любой критерий.
После выбора тренда, наилучшим образом приближающего
входные данные, делаем прогноз на заданный период. Однако такой прогноз не учитывает сезонную составляющую. Для учета
сезонной составляющей уровень, полученный в результате экстраполяции, умножим на индекс сезонности, который рассчитаем
как среднее отношений фактических данных к трендовым за одноименные месяцы. Таким образом, получился точечный прогноз. Для того чтобы иметь более полное представление о поведении прогнозируемого показателя в будущем, рекомендуется
построить доверительный интервал прогноза
По результатам проведенных исследований по данному алгоритму можно сделать ряд выводов.
– Точность прогноза напрямую зависит от количества входных данных, а именно, чем их больше, тем выше точность прогноза, и наоборот.
– Тренд, наилучшим образом приближающий входные данные, зависит от самих данных. Причем линейные среднеквадратические приближения и среднеквадратические приближения полиномами второй степени в большинстве случаев лучше интерполируют и экстраполируют входные данные. Было замечено,
А.Ю. Грицевич
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
если относительно стабильны разности между соседними значениями ряда, выравнивание чаще всего выполняется линейным
трендом; иначе – квадратной параболой. Однако стоит отметить,
что если значения ряда имеют сильные выбросы и их природа не
случайна, то в ряде случаев наилучшим оказывался гиперболический тренд.
– Показатель детерминации для линейного и параболического тренда в большинстве случаев отличаются на тысячные или
десятитысячные доли, поэтому для прогнозирования можно обходиться более простой линейной моделью.
– Все оценки тренда одновременно говорят о значимости или
не значимости уравнения тренда в целом, следовательно, можно
пользоваться только одной из них.
– Для более широкого представления о будущих тенденциях
развития предприятия, спроса на товар и объемы реализации следует строить не точечный, а интервальный прогноз.
 Литература
1. Гмурман В.Е. Теория вероятностей и математическая статистика.
учеб. пособие для вузов. Изд. 7-е, стер. М.: Высш. шк., 2001. 479 с.
2. Кендэл М. Временные ряды. М.: Финансы и статистика, 1981.
3. Андерсон Т. Статистический анализ временных рядов. М.: Мир,
1976.
Прогнозирование объема продаж в MS Excel
А.И. Гущина
Спрос на прогнозные разработки имел место всегда, поскольку интересно заглянуть в будущее, связать с этим свои намерения и в соответствии с этим строить планы. На современном
этапе преобразований, происходящих с достаточно высокой скоростью, и в институциональной среде, и в системе бизнеса, и в
обществе в целом возрастает спрос на качественные и оперативные прогнозные разработки.
28
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
По оценкам некоторых ученых насчитывается более 150 методов прогнозирования. Базовых методов гораздо меньше, многие из «методов» скорее относятся к отдельным способам и процедурам прогнозирования либо представляют собой набор отдельных приемов, отличающихся от базовых методов количеством частных приемов и последовательностью их применения.
Хотя выбор и использование метода являются основным этапом в разработке прогноза, они не гарантируют окончательных
достоверных результатов.
Из всего многообразия методов прогнозирования давайте
рассмотрим метод сезонной декомпозиции. Основная идея сезонной декомпозиции проста. В общем случае временной ряд можно
представить себе состоящим из четырех различных компонент:
• тренда (обозначается Tt , где t обозначает момент времени),
• циклической компоненты ( Ct ),
• сезонной компоненты ( St ),
• случайной, нерегулярной компоненты или флуктуации ( I t ).
Для построения будем использовать аддитивная модель:
X t = TCt + St + I t
где X – значение временного ряда на момент времени t,
TC – тренд-циклическая компонента.
Для построения тренда обычно используют следующие функции: линейную, полиномиальную, степенную, логарифмическую,
экспоненциальную. Было доказано, что линейный тренд, хотя и
имеет наименьший коэффициент детерминации, и, следовательно,
хуже объясняет тесноту статистической зависимости, но он лучше
показывает тенденцию в целом. То есть линейная модель практически всегда подходит для построения модели прогноза.
Для примера хотелось бы рассмотреть два временных ряда с
различной природой. Первый временной ряд основан на объемах
продаж сыра, а второй – туристических палаток. Во временном
ряде объема продаж сыра сезонная составляющая явно не видна,
а продажи туристических палаток имеют явно выраженный сезонный характер.
Для прогнозирования объема продаж предлагается следующий алгоритм построения прогнозной модели.
А.И. Гущина
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Построение модели Ft = TCt + St + I t включает в себя следующие этапы:
1. Определение тренда T.
2. Определение величины сезонной компоненты S = T – R.
3. Расчет ошибок модели I = R − T − S , где R – фактические
значения объемов продаж.
4. Нахождение среднеквадратической ошибки модели
I2

.
E=
2
(
T
+
S
)

5. После нахождения среднеквадратической ошибки модели
мы можем делать вывод о точности модели в целом. Точность
модели рассчитывается по формуле: M = (1 − E ) * 100% , где M –
точность модели.
6. На основе полученных данных модели для построения
прогноза необходимо:
– продолжить трендовую компоненту Т до 36 месяцев;
– учесть сезонную компоненту S, рассчитанную для модели,
которая остается неизменной для 25 – 36 месяцев.
7. Для учета ошибок воспользуемся доверительным интервалом
модели,
который
рассчитывается
по
формуле:
D = (F * [1 − E ]; F * [1 + E ]) , где D – доверительный интервал.
8. Определение константы сглаживания возможно несколькими способами:
– самостоятельный расчет индексов стабильности экономики
и учет всех рисков изменения конъюнктуры рынка и отрасли, в
которой находится предприятие. При этом возможно использование и внутренней информации предприятия, и информации государственных статистических органов;
– использование ранее рассчитанных показателей стабильности рынка. Таких как, динамика индекса цен, индекс инфляции,
показатели покупательской способности, банковская учетная
ставка и т.д.
Константа сглаживания, т.е. «вероятность сохранения существующей рыночной конъюнктуры», рассчитывается как α = 1 –
(учетная ставка Центрального Банка). На 29.04.2008 г. учетная
ставка Центрального банка РФ составляла 10,5%.
30
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
9. Далее необходимо скорректировать прогнозные значения
ряда с использованием экспоненциального сглаживания. Это позволяет учесть возможное будущее изменение экономических
тенденций, на основе которых построена трендовая модель.
Сущность данной поправки заключается в том, что она нивелирует недостаток адаптивных моделей, а именно, позволяет быстро учесть наметившиеся новые экономические тенденции.
Fпр _ t = α * Fф _ t −1 + (1 − α) * Fм _ t , где Fпр _ t – прогнозное значение объёма продаж.
В качестве среды прогнозирования будем использовать пакет
прикладных программ MS Excel, т.к. этот пакет имеется практически у любого офисного работника. Описанный выше алгоритм
достаточно легко реализовать стандартными средствами MS Excel: использование встроенных опций, таблиц, формул, диаграмм.
Определяя тренд, воспользуемся общепринятой линейной
функцией и трендом с периодической составляющей. Для построения линейного тренда в MS Excel используется опция «Добавить линию тренда», где вычисляются коэффициенты линейного уравнения и коэффициент детерминации. Но, т.к. периодического тренда нет в наборе стандартных трендов, его необходимо
построить самостоятельно. Для этого периодическую функцию
представим в виде суммы гармонических функций, т.е. ряда Фурье: x = A + B * sin (
2π
(t − C )) , где x – функция тренда, А – сме12
щение синусоиды относительно нуля, В – амплитуда синусоиды,
С – начальная фаза колебания.
Чтобы избежать ошибок, поручим MS Exsel подобрать наилучшие значения А, В и С. Для этого, выделив ячейку с подсчитанной суммой квадратов отклонений, в меню «Сервис» выбираем команду «Поиск решения…». В переключателе «равной» выбираем «минимальному значению», а в поле «Изменяя ячейки»
указываем ячейки с числами А, В и С и нажимаем кнопку «Выполнить», далее «Сохранить».
Теперь необходимо вычислить коэффициент детерминации
2
R полученного тренда с базовым рядом. Вычислим коэффициент
критерием Пирсона с помощью статистической функции MS Excel.
А.И. Гущина
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Но нельзя точно утверждать, что у нас период именно 12 месяцев. Возможно, период составляет 6 месяцев или 3, или 4, а
также наблюдается возрастающая или убывающая общая тенденция. Периоды 6, 3, 4 месяцев выделяются аналогично году, а для
линейного тренда используем функции MS Excel «ОТРЕЗОК» и
«НАКЛОН». Чтобы получить итоговое уравнение линии тренда,
необходимо сложить линейный и все периодические тренды. Далее в соответствии с алгоритмом ППП MS Excel считает прогнозные значения.
Для построенных прогнозов с заданными линиями тренда
получились следующие точности модели:
– для объемов продаж сыра с линейным трендом 96,5% и
97,36% с трендом с периодической составляющей;
– для объемов продаж туристических палаток с линейным
трендом 96,35% и 96,87% с трендом с периодической составляющей.
Если точность модели колеблется в районе 90 – 100%, то
можно утверждать, что модель достаточно точная. Хотя исходные данные для прогнозирования, на первый взгляд, были разными по природе, но прогнозные значения получились достаточно близкими.
180000
160000
140000
120000
100000
80000
60000
40000
20000
0
1
3
5
7
9
11 13 15 17 19 21 23 25 27 29 31 33 35
Объем продаж
Линейная модель (96,50%)
Периодическая модель (97,36%)
Рис. 1. Сравнение прогнозов объема продаж сыра
для построенных моделей
32
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
60000,00
50000,00
40000,00
30000,00
20000,00
10000,00
0,00
1
3
5
7
9 11 13 15 17 19 21 23 25 27 29 31 33 35
-10000,00
Линейная модель (96,35%)
Объем продаж
Периодическая модель (96,87%)
Рис. 2. Сравнение прогнозов объема продаж туристических палаток
для построенных моделей
По полученным моделям видно, что достаточно точными из
стандартных линий тренда является линейный тренд. А также
можно сделать вывод, что использование периодического тренда
вместе с линейным дает прогноз с высокой точностью.
Для учёта новых экономических тенденций рекомендуется
регулярно уточнять модель на основе мониторинга фактически
полученных объёмов продаж, добавляя их или заменяя ими данные статистической базы, на основе которой строится модель.
Во многих случаях ни один из методов сам по себе не может
обеспечить требуемую степень достоверности и точности прогноза, но, будучи использованным в определенных сочетаниях с
другими, оказывается весьма эффективным – достоинства одного
метода компенсируют недостатки другого, либо они используются в развитии.
А данный алгоритм показывает, как в MS Excel можно построить модель с практически любой функциональной зависимостью.
В целом сравнение разных методов прогнозирования свидетельствует о том, что ни один из них не является заведомо лучше
остальных. Скорее на предпочтительность использования того
А.И. Гущина
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
или иного метода оказывает влияние ряд факторов, в том числе
устойчивость конкретных данных, временной интервал, возможность использования компьютеров и степень устранения сезонности.
 Литература
1. Рабочая книга по прогнозированию / Отв. ред. И.В. Бестужева-Лада.
М.: Мысль, 1982.
2. Янч Э. Прогнозирование научно-технического процесса. М.: Прогресс, 1974.
3. Четыркин Е.М. Статистические методы прогнозирования. Изд. 2-е
перер. и доп. М.: Статистика.
4. Марк У. Джонстон, Грег У. Маршалл. Управление отделом продаж.
Планирование. Организация. Контроль. 7-е изд., пер. с англ. М.: Издательский дом «Вильямс», 2005.
5. www.cfin.ru.
6. www.management.com.ua.
7. www.statsoft.ru.
Исследование основных свойств
и разрешимости массовых алгоритмических
проблем для супер-двойственных сетей
Петри и сетей активных ресурсов
Ю.В. Диль
Супер-двойственные сети Петри были введены в 2005 г. в работе Колера и Рольке [4]. Основным их отличием от «обычных»
сетей Петри стало введение активности позиций, что придало
этим сетям дополнительную функциональность. Переходы наравне с позициями могут помечаться фишками (покенами), что
позволяет регулировать число их срабатываний. Условие срабатывания следующее: входной набор позиции (перехода) должен
быть помечен и сама позиция (переход) должны быть помечены.
34
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Оба варианта – срабатывание переходов или срабатывание мест –
могут происходить за один шаг.
Определение 1. Супер-двойственная сеть (структура) –
это кортеж SD = (P, T, F, G), где:
– P – набор позиций (мест);
– T – набор переходов, причем P ∩ T = 0;
– F ⊆ (P ×T U T × P) – функция F-дуг и
– G ⊆ (P × Т U T × P) – функция G-дуг.
Пример 1. Супер-двойственная сеть SD с начальной разметкой (3,0,1,1,0 | 2,0).
t1
p1
p2
p3
p4
t2
p5
Определение 2. Место (переход) q в супер-двойственной сети Петри SD = (P, T, F, G, Mo), где Mo – начальная разметка сети,
называется ограниченным, если существует число n, такое, что
для любой достижимой в сети разметки M справедливо неравенство M(q) ≤ n.
Определение 3. Супер-двойственная сеть Петри SD = (P, T,
F, G, Mo) называется p-ограниченной сетью, если любое ее место ограничено, и t-ограниченной сетью, если любой ее переход
ограничен.
Определение 4. Супер-двойственная сеть Петри SD = (P, T,
F, G, Mo) называется ограниченной сетью, если все ее места и
переходы ограничены.
Заметим, что p-ограниченность супер-двойственных сетей
Петри не связана с t-ограниченностью. Определения безопасности, консервативности, потенциальной живости и устойчивости
являются расширениями соответствующих определений для «традиционных» сетей Петри (рассматриваются как переходы, так и
позиции). Каждое из них можно применить как ко всей SD-сети,
Ю.В. Диль
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
так и к ее F- или G-компоненте. Доказано, что обычное и полное
покрывающее дерево супер-двойственной сети строится по тем же
правилам, что и для «обычной» сети Петри с учетом возможности
срабатывания не только переходов, но и позиций и является конечным. Путем построения и исследования этих деревьев разрешаются следующие основные алгоритмические проблемы.
Теорема 1. В супер-двойственных сетях Петри разрешимы
проблемы:
1) ограниченности сети;
2) ограниченности некоторого места или перехода в сети;
3) безопасности сети;
4) потенциальной живости мест и переходов в сети.
Теорема 2. Для супер-двойственных сетей Петри существуют следующие алгоритмы распознавания:
1) получит ли данное место (переход) хотя бы одну фишку;
2) может ли данное место (переход) сработать сколь угодно большое число раз.
Разделение позиций и переходов в супер-двойственных сетях
выглядит несколько искусственно, ведь в силу симметричности
определений позиции и переходы в таких сетях обладают одинаковыми свойствами. Формализм, представляющий собой результат полного «слияния» понятий позиции и перехода, вводится
В.А. Башкиным в его работе [8] и назван сетями активных ресурсов. В сетях этого вида появляется возможность «двойного» использования фишки: не только в качестве пассивного ресурса, но
и в качестве активного агента. Формулировки здесь сокращаются
по сравнению с супер-двойственными сетями благодаря отказу от
требования двудольности графа.
На практике использование активных ресурсов может оказаться полезным при моделировании систем с динамической модификацией структуры действий (например, в системах адаптивного управления процессами).
Определение 5. Сетью активных ресурсов (AR-сетью) назовем набор AR = (V, I, O), где
• V – конечное множество вершин (ресурсов);
• I: V×V → Nat – множество потребляющих дуг;
• О: V×V → Nat – множество производящих дуг.
36
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 2. Сеть активных ресурсов с начальной разметкой
(1,1,0,0).
v2
v1
v3
v4
Некоторый ресурс в сети активных ресурсов является активным, если сам он помечен и в потребляемых узлах содержится достаточное количество фишек.
Определения ограниченности, безопасности, консервативности, потенциальной живости и устойчивости сети и ресурсов в
ней являются расширениями соответствующих определений для
«традиционных» сетей Петри (вместо позиций и переходов рассматриваются вершины-ресурсы). Доказано, что обычное и полное покрывающее дерево сети активных ресурсов строятся по тем
же правилам, что и для «обычной» сети Петри, и является конечным. Путем построения и исследования этих деревьев разрешаются следующие основные алгоритмические проблемы.
Теорема 3. В сетях активных ресурсов разрешимы проблемы:
1) ограниченности сети;
2) ограниченности некоторого ресурса в сети;
3) безопасности сети;
4) потенциальной живости ресурсов в сети.
Теорема 4. Для сетей активных ресурсов существуют следующие алгоритмы распознавания:
1) получит ли данный ресурс хотя бы одну фишку;
2) может ли данный ресурс сработать сколь угодно большое
число раз.
Интересно исследовать модификации Р- и Т-инвариантов для
супер-двойственных сетей Петри и сетей активных ресурсов.
Р- и Т-инварианты в супер-двойственных сетях можно рассматривать применительно к F-, G-компоненте сети или ко всей
сети. Назовем эти инварианты соответственно MF-, MG-, MQ-,
Ю.В. Диль
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
NF-, NG-, NQ-инвариантами. Их определения являются расширениями соответствующих определений для «обычных» сетей Петри с учетом того, что срабатывать могут не только переходы, но и
позиции, а на сам факт срабатывания накладывается дополнительное условие: место или переход должны быть помечены. Вычисляются инварианты в сетях рассматриваемого вида с помощью матрицы инцидентности супер-двойственной сети. Доказано, что MQ-инвариант может использоваться для суждения о qограниченности супер-двойственной сети, существование NQ-инварианта – необходимое условие для q-живости ограниченной
супер-двойственной сети.
Рассмотрим, во что превращаются инварианты в сетях активных ресурсов.
Определение 6. R – инвариант (инвариант ресурсов) для
сети активных ресурсов AR = (V, I, O, M0) – это отношение
InvR : V → Z, сопоставляющее ресурсам некоторые целочисленные «веса», такое, что ∀ μ, μ́∈ R(AR) и v∈V, если μ [v> μ́, тогда
∑ InvR (v)μ(v) = ∑ InvR (v) μ́(v).
v∈V
v∈V
Другими словами, срабатывание любого ресурса не меняет
«взвешенную» сумму фишек в вершинах сети.
Определение 7. A – инвариант (инвариант агентов) для
сети активных ресурсов AR = (V, I, O, M0) – это отношение
InvA : V → N, сопоставляющее ресурсам некоторые неотрицательные «веса», такое, что
∑ InvA (v)(∆ (v)) = 0.
v∈V
Здесь ∆ (v) = μ – μ0, при условии, что μ0 [v> μ.
Иными словами, срабатывания каждого ресурса некоторое
число раз, определяемое A-инвариантом, возвращают сеть AR к
ее начальной разметке.
R- и A-инварианты могут быть вычислены с помощью матрицы инцидентности сети активных ресурсов по тем же правилам, что и для «обычных» сетей Петри. Доказано, что R-инвариант может использоваться для суждения о структурной ограниченности сети активных ресурсов, существование А-инвариан38
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
та – необходимое условие для живости ограниченной сети активных ресурсов.
В работе [4] доказана эквивалентность супер-двойственных
сетей «обычным» сетям Петри, а в работе [8] – эквивалентность
«обычных» сетей Петри и сетей активных ресурсов. В данной работе установлено, что ряд свойств супер-двойственных сетей и
сетей активных ресурсов являются расширениями аналогичных
свойств для «обычных» сетей Петри. Построены алгоритмы решения соответствующих алгоритмических проблем, не предусматривающие преобразования супер-двойственных и сетей активных ресурсов в обыкновенные сети Петри. Определены и исследованы понятия инвариантов в сетях данных видов, доказана
возможность их применения для исследования ограниченности и
живости сетей.
 Литература
1. Котов В.Е. Сети Петри М.: Наука. Глав. ред. физ.-мат. лит, 1984.
2. Ломазова И.А. Сети Петри и анализ поведенческих свойств распределенных систем. Ярославль: ЯрГУ, 2002.
3. Питерсон Дж. Сети Петри и моделирование систем. М.: Мир. 1984.
4. Koehler M., Roelke H. Super-dual nets. Proc. of Concurrency Specification & Programming (CS&P'2005). Warsaw. 2005. С. 271–281.
5. Kurt Lautenbach. Duality of marked place/transition nets. Technical Report Is, Universitat Koblenz-Landau, 2003.
6. Rudiger Valk. Self-modifying nets, a natural extension of Petri
nets. In Ausiello, G. and Bohm, C-. editors, Automata, Languages and
Programming, volume 62 of lecture Notes in Computer Science. Springer-Verlag, 1978.
7. Rudiger Valk. Object Petri nets: Using the nets-within-nets paradigm. In Jorg Desel, Woligang Reisig, and Grzegorz Rozenberg, editors,
Advanced Course on Petri Nets, 2003, volume 3098 of Lecture Notes in
Computer Science. Springer-Verlag, 2003.
8. Башкин В.А. Сети активных ресурсов. Ярославль: ЯрГУ,
2007.
9. Hsu-Chun Yen. Introduction to Petry Net Theory. Dept. of Electrical Engineering National Taiwan University. Taipei, Taiwan, R.O.C.
С. 9–11.
Ю.В. Диль
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сеть нейронных клеточных автоматов
в задаче сегментации
черно-белых пиксельных изображений
Д.С. Дыбин
Очевидно, что задачи машинного зрения являются достаточно актуальными в силу широкого применения в различных сферах деятельности человека. Информация по проблемам машинного зрения обсуждается в [1]. Задача сегментации изображений является важным предварительным шагом, облегчающим
последующее решение задач анализа зрительных сцен, таких как
распознавание образов и т.д.
Сегментация пиксельного изображения – это процесс его
разделения на однородные области, в каждой из которых пиксели
имеют аналогичные свойства с точки зрения интенсивности, цвета и т.п. Отсюда следует, что разные (разнородные) области
должны иметь разные свойства. Решение задачи должно обладать
достаточной устойчивостью к шумам на изображении, что существенно усложняет проблему.
Хотя люди используют единообразные интуитивные стратегии сегментации, дать формальное универсальное и объективное
определение ее качества вряд ли возможно. Одним из подходов к
решению подобных задач является имитация биологических процессов мозга человека, где наибольшее развитие получила теория
нейронных сетей. Достаточно подробный обзор задач, связанных
с сегментацией, кластеризацией и выделением краев изображений приведен в [2].
Для решения данной задачи предлагается использовать нейронную сеть, состоящую из биологически правдоподобных элементов, нейронных клеточных автоматов (НКА), модель которых
предложена в [3]. Данный выбор обусловлен тем, что свойства
этих элементов предполагают образование в сети из НКА синхронно работающих ансамблей, состоящих из нейронов, которые
40
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
в начальный момент времени имели схожие характеристики. Таким образом, близкие НКА со схожими параметрами влияют друг
на друга и в определенный момент времени синхронизируются.
В качестве тестовых образцов рассматривались черно-белые
изображения, градация серого цвета от 0 (черный цвет) до
255 (белый цвет), размером 100 на 100 пикселей. Каждому пикселю был сопоставлен один НКА в сети.
Каждый элемент расположен в узлах плоской решетки, каждый НКА связан с восемью ближайшими элементами сети. Определены статические параметры, одинаковые для всех нейронов сети: пороговое значение p(t), время рефрактерности TR , время спайка Tsp, значение мембранного потенциала в период рефрактерности
u0(t), синаптический вес i,j-нейрона на связанном с ним qij.
В связи с тем, что нейроны сети работают в цикле и последовательно меняют состояния во времени, зависящем от их мембранного потенциала, шум в однородной области может раньше
области сгенерировать спайк и активировать свою локальную окрестность, которая в свою очередь также раньше области сгенерирует спайк и т.д., пока нейроны области не перейдут в состояние спайка, но тогда они, возможно, уже не смогут подавить увеличивающийся шум. Будем использовать динамические связи для
уменьшения такого эффекта и улучшения выделения однородных
областей.
1. Если нейрон ассоциирован с шумом на изображении, то
его влияние на ближайшие нейроны отключается, чтобы не дать
ему возможность активировать свою локальную окрестность.
2. Если нейрон ассоциирован с пикселем на границе областей, то отключается воздействие нейронов разных областей друг
на друга, чтобы сохранить четкость границы и не дать области с
более ранним временем спайка влиять на область с более поздним.
Для данного изображения (рис. 1) видно, что черный квадрат
и его белый фон абсолютно четко отделяются сетью. В разное
время сегменты изображения находятся в разных состояниях, то
есть образуют синхронные ансамбли.
Д.С. Дыбин
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 1
Рассмотрим аэрофотоснимок Ярославля (рис. 2). На нем части, представляющие берега, имеют очень сильную зашумленность и неоднородность. Однако границы сегмента, представляющего Волгу и Которосль, видны достаточно четко. Из-за высокой зашумленности и неоднородности для отделения речки и
берегов потребовалось большое количество шагов и времени работы программы.
Рис. 2
 Литература
[1] http://graphics.cs.msu.ru/ru/library/cv/cv_intro.html
[2] Научная сессия МИФИ – 2008. Нейроинформатика 2008. X Всероссийская научно-техническая конференция. Лекции по нейроинформатике. Ч. 2. М., 2008.
[3] Шабаршина Г.В. Самоорганизация в полносвязной однородной сети нейронных клеточных автоматов возбудительного типа // Автоматика и
телемеханика. 1999. № 2. С. 112–119.
42
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Биологически мотивированная
нейросетевая модель выделения
краев изображений на основе
вейвлетных преобразований
С.В. Егоров
Объектом исследования являются нейронные сети как эффективный механизм для моделирования процессов работы мозга, в частности зрительного аппарата человека.
Цель работы – построение модели для обнаружения краев,
биологически обоснованной и работоспособной.
В результате исследования исходя из биологических данных
о функционировании человеческого мозга была разработана нейросетевая модель для выделения краев, научная новизна и уникальность которой заключается в следующем:
– используются специфические сенсорные окрестности и
«круговые» вейвлетные1 преобразования,
– усовершенствована система анализа информации, моделирующая обработку сигналов в первичной зрительной коре мозга:
применяется так называемая повторная фильтрация.
В процессе работы проводились аналитические исследования
предложенной модели, был построен программный имитатор, наглядно иллюстрирующий и экспериментально подтверждающий
полную работоспособность. Результаты рассматриваются в сравнении с другой известной методикой выделения краев [4].
Полученные результаты являются актуальными в связи с растущим интересом к системам, работа которых во многом схожа с
функционированием человеческого мозга. В частности, задача
машинного зрения давно привлекает внимание исследователей,
тем не менее эта проблема является малоизученной.
1
Вейвлеты – это семейство функций, которые обладают рядом замечательных свойств.
С.В. Егоров
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Построенная модель может быть усовершенствована путем
рассмотрения различных вейвлет и различных окрестностей.
Результаты исследования могут найти применение в разных
сферах деятельности общества, в той или иной степени использующих машинное зрение для восприятия и анализа образов/изображений окружающего мира. Наиболее явное применение – в компьютерной графике.
Итак, для экспериментов рассматривались изображения в
градациях серого. Цифровое изображение есть не что иное, как
набор точек растра (пикселей). То есть любое растровое изображение можно представить в виде прямоугольной решетки. Искусственные нейроны, имитирующие активность клеток зрительного анализатора, расположены в узлах таких решеток.
Для представления образов использовались стандартные битовые матрицы (bitmap).
Значимыми параметрами для программы являются: радиус
сенсорного поля s, величины полуосей ориентационного эллипса2
(R1 и R2), величины сторон ориентационного прямоугольника3
(R3 и R4), число углов K (чем их больше, тем точнее определяется
направление края), пороговое значение ε. Вариации значений
этих параметров приводят к различным результатам. Если ответ
микроколонки, содержащей сложные клетки, превосходит порог
ε, то узел закрашивается в черный цвет.
Ниже для ряда текстур представлены результаты экспериментальных исследований, которые получились при различных
значениях входных параметров (рис. 1 и 2). После просмотра результатов очевидным становится тот факт, что модель работоспособна.
Слева – исходное изображение. В центре – результат, когда
ответы ганглиозных нейронов4 подаются на вход сложным клеткам. Справа – результат повторной фильтрации, когда ответы
2
Ориентационный эллипс – область чувствительности простой клетки первичной зрительной коры мозга.
3
Ориентационный прямоугольник – область чувствительности сложной клетки первичной зрительной коры мозга.
4
Ганглиозные клетки являются единственными нервными волокнами,
несущими зрительную информацию в мозг.
44
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ганглиозных нейронов подаются сначала на вход простым клеткам, а затем сложным.
Рис. 1: Слева – исходное изображение размером 120×100.
В центре: s=5, R3=4, R4=2, K=20, ε=0.004.
Справа: s=5, R1=3, R2=1, R3=4, R4=2, K=24, ε=0.005
Рис. 2: Слева – исходное изображение размером 120×100.
центре: s=4, R3=3, R4=2, K=28, ε=0.003.
права: s=6, R1=3, R2=2, R3=2, R4=1, K=32, ε=0.006
При сравнении построенной модели с детектором края
А.В. Сергина исследователь пришел к выводу, что ни одна из моделей не является совершенной. При различных значениях входных параметров недостатки и достоинства имеет каждая модель.
При использовании повторной фильтрации результаты выглядят
заметно лучше и могут конкурировать с результатами Сергина.
 Литература
1. Николлс Дж. Г. Мартин А.Р., Валлас Б. Дж., Фукс П.А. От нейрона
к мозгу. М.: Едиториал УРСС, 2003.
2. Загородний Е.С. Принцип работы мозга. М.: КомКнига, 2006.
С.В. Егоров
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Хьюбел, Д. Глаз, мозг, зрение. М.: Мир, 1990.
4. Сергин, А.В. Биологически правдоподобный нейросетевой детектор
края: статья. М.: Институт прикладной математики им. М.В. Келдыша
РАН, 2006.
5. Tang, Y.Y. Wavelet Theory and Its Application to Pattern Recognition
/ Y.Y. Tang, L.H. Yang, J. Liu, H. Ma. World Scientific Publishing Co. Ptc.
Ltd., 2000.
6. Петухов, А.П. Введение в теорию базисов всплесков: учеб. пособие.
СПб: Изд-во СПбГТУ, 1999.
Расстояния и другие меры близости
на множестве черно-белых
цифровых изображений
И.А. Каплий, О.С. Куликов
Строится серия функций на множестве пар черно-белых цифровых изображений, являющихся либо расстоянием, либо аналогом расстояния. Предложенные функции позволяют, с одной стороны, решать задачи различения изображений, с другой – дают
некую меру сходства. Рассмотрены приложения такого подхода к
текстурам.
размеПод изображением A будем понимать матрицу
ра m*n с элементами, принимающими значения либо 0, либо 1.
как условный экран и следуя подРассматривая матрицу
ходу работы [5], введем возможными традиционными способами
экранные расстояния между парами пикселов:
,
,
.
Исходя из интерпретации изображения как подмножества
и используя соответствующие сжатия плоскости ,
46
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
можно считать, что
. И, следовательно,
можно ввести приведенные расстояния на множестве пар условных пикселей:
,
.
Классическим расстоянием между компактными подмножествами метрического пространства является расстояние Хаусдорфа [1, 2, 5]. Используя соответствующие экранные расстояния
, стандартным образом определим аналоги расстояния Хаусдорфа на условном экране между изображениями
и
для p=1,2,3:
Соответствующие приведенные расстояния имеют вид:
Расстояния
не характеризуют различие или
сходство форм изображений A и B, так как зависят от их взаимного расположения на условном экране. Обозначим через T некоторый класс преобразований изображений, сохраняющих их форму
и, естественно, не выводящих изображения за пределы условного
экрана. Как представляется, величины
характеризуют различия или близость форм изображений A и B.
На основе понятия характеристического набора коэффициентов
черно-белого цифрового изображения для изображения A строится шестнадцатимерный набор неотрицательных целочисленных
указывает число
коэффициентов
, где
фрагментов размера 2*2 изображения A.
И.А. Каплий, О.С. Куликов
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Фрагментом размера 2*2 изображения A назовем любую под,
матрицу матрицы A, состоящую из элементов
которые могут принимать значения 0 или 1. Очевидно, что всего
существует 16 различных фрагментов.
Естественным образом можно определить расстояния на
множестве таких наборов для изображений A и B:
Кроме этого, так как имеет место соотношение
для любого изображения на условном экране размера m x n, то
соответственно возможно введение приведенных расстояний:
в значительной
Введенные таким образом функции
степени и характеризуют различия изображений, но в строгом
смысле не являются расстоянием между изображениями, так как
существуют примеры двух различных изображений A и B, для косовпадают.
торых характеристические наборы
Но если меру близости
легко вычислить для любой пары изображений, то вычисление расстояний на основе расстояния
Хаусдорфа представляет трудности для текстур, так как множество преобразований T может оказаться пустым в силу того, что
любой сдвиг текстуры будет выводить текстуру за пределы условного экрана. Поэтому предлагается сравнивать текстуры, раз. В данном случае текстуры
бивая их на некие блоки
разбиваются на четверти.
Рассмотрим теперь в качестве T множество целочисленных
сдвигов изображений
Дополнительно введем еще изображения
48
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
и положим вне этого блока значения пикселов равными нулю.
не
Безусловным требованием является то, что изображения
выводятся за пределы условного экрана. Определим еще изобрана всех пикселах из блока
, и пожение , совпадающее с
ложим вне этого блока значения пикселов равными нулю. Тогда
определим расстояния
Вычислим соответственно величины
Определим теперь для текстур A и B расстояния:
Ниже приведены некоторые примеры численных результатов, вычисления расстояний и их аналогов для черно-белых изображений размера 50*50 пикселов (рис. 1 и 2).
Рисунок 1, изображения букв (1,2):
ρ1(A,B)= 239.4, ρ2(A,B)= 432, ρ3(A,B)= 183
H1(A,B)= 22.2, H2(A,B)= 31, H3(A,B)= 24,
Рисунок 1, изображения букв (1,3):
ρ1(A, A')= 80.2, ρ2(A, A')= 138, ρ3(A, A')= 67
H1(A, A')= 16.4, H2(A, A')= 22, H3(A, A')= 24,
Рисунок 2, текстуры (1,3):
ρ1(1,3)= 80.2, ρ2(1,3)= 2060, ρ3(1,3)= 1030
R1(1,3)= 2.8, R 2(1,3)= 22, R 3(1,3)= 2,
Рисунок 2, текстуры (1,2):
ρ1(1,3)= 80.2, ρ2(1,3)= 2418, ρ3(1,3)= 1093
R1(1,3)= 7.8, R 2(1,3)= 9, R 3(1,3)= 6,
И.А. Каплий, О.С. Куликов
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 1
Рис. 2
Полученные результаты, как представляется, показывают хорошее согласование введенных в настоящей работе мер близости
ρp, p=1,2,3 и расстояний, построенных на основе классической
метрики Хаусдорфа. Трудоемкость вычисления этих мер близости существенно меньше трудоемкости вычисления для метрик
классического типа.
 Литература
1. Куратовский К. Топология. Кн. 1, 2 М.: Мир, 1966, 1982.
2. Келли, Дж. Общая топология. М.: Наука, 1968.
3. Кроновер Р.М. Фракталы и хаос в динамических системах. М.: Техносфера, 2006.
4. Парфенов П.Г. О некоторых свойствах характеристического набора
коэффициентов черно-белого цифрового изображения // Моделирование и
анализ информационных систем. 2005. Т. 12, № 1. С.52-54.
5. Парфенов П.Г., Назарычев С.Л. Об одном подходе к различению
элементов из больших совокупностей традионных систем символов // Моделирование и анализ информационных систем. 2005. Т. 13, № 1. С. 46-48.
Разработка базовой части корпоративной
ERP/CRM-системы для службы услуг
А.Е. Капралов
В современном мире высокие технологии все больше и
больше проникают в повседневную жизнь. Некоторые сферы
деятельности уже трудно представить без применения компьютеров и вычислительных машин. Одним из аспектов такой интеграции является автоматизация бизнес-процессов, которая на дан50
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ный момент – один из основных элементов в борьбе за повышение производительности труда. Корпоративные системы автоматизации позволяют не только повысить эффективность работы
сотрудников, но и увеличить контроль руководства за деятельностью предприятия.
Одним из типов таких систем являются ERP-системы (англ.
Enterprise Resource Planning System – система планирования ресурсов предприятия). В основе ERP-систем лежит принцип создания единого хранилища данных, содержащего всю корпоративную бизнес-информацию и обеспечивающего одновременный
доступ к ней любого необходимого количества сотрудников
предприятия, наделенных соответствующими полномочиями.
Изменение данных производится через функции (функциональные возможности) системы. Использование ERP-системы позволяет использовать одну интегрированную программу вместо нескольких разрозненных. Единая система может управлять обработкой, логистикой, дистрибуцией, запасами, доставкой,
выставлением счетов-фактур и бухгалтерским учетом. Внедряемые в связке с CRM-системой (англ. Customer Relationship
Management System – система управления взаимоотношений с
клиентами) и системой контроля качества ERP-системы нацелены на максимальное удовлетворение потребностей компаний в
средствах управления бизнесом.
В настоящее время на рынке присутствует немалое количество подобных систем. Однако большая часть из них предназначена
для крупных предприятий, в то время как предприятия малого
бизнеса вынуждены прибегать к услугам фирм-разработчиков ПО
для создания индивидуальной корпоративной системы. У такого
подхода есть один минус, являющийся очень существенным для
предприятий данного уровня: дороговизна такой разработки.
Легко подсчитать примерную стоимость данного программного
продукта. Разработка системы с базовой функциональностью
займет у группы программистов из двух человек не менее месяца.
Если учесть, что заработная плата рядового программиста на сегодняшний день составляет около $1000, то такая система обойдется малому предприятию в $2000. В то время как вложение таких средств, например, в рекламу, может принести более очевидА.Е. Капралов
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ный (тем не менее недальновидный) прирост прибыли. Из чего
становится понятным, что покупка и внедрение таких систем
редко рассматриваются руководителями предприятий малого
бизнеса.
Таким образом, необходимость в малых ERP-системах для
малого бизнеса существует. При этом такая система должна быть
в некоей мере универсальной, чтобы обеспечить окупаемость и
сохранить дешевизну. Но возникает естественная проблема: универсальное решение всегда хуже индивидуального. Поэтому такая система должна обладать гибкостью с точки зрения ее модификации и настройки под отдельное предприятие. Данную цель
можно достичь, обеспечив модульность программного продукта,
а также использование слабой связанности между крупными элементами, например, за счет языка XML для обмена данными.
Целью данной работы является разработка базовой части
ERP-системы для предприятия малого бизнеса, занимающаяся
оказанием различного рода услуг. Однако основной задачей является не столько разработка самой системы, сколько сам процесс разработки, архитектура и подходы к программированию. С
этой точки зрения с самого начала разработки необходимо учитывать, что, как известно, создать систему трудно, но еще труднее избавиться от нее. Поэтому архитектура должна быть тщательно продумана, дабы избежать огромных правок вплоть до переделывания всего проекта. С другой стороны, в процессе
разработки необходимо избавляться от нежелательного (излишнего или низкокачественного) кода, несмотря на то, что его удаление слишком «дорого» или будет иметь непредсказуемые последствия. Так как увеличение такого кода будет происходить со
скоростью геометрической прогрессии, и, следовательно, «стоимость» избавления от такого кода будет только возрастать. Такие
ситуации являются анти-паттерном и носят название «Поток лавы» (Lava flow).
Разрабатываемая система предназначена для предприятий,
занимающихся оказанием различного рода услуг. Поэтому основным элементом такой системы должно быть оформление,
проведение и сопровождение заказа. Также в связи с бизнесстратегией CRM такая система должна обладать списком клиен52
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
тов, которым могут начисляться «бонусы», оказание услуг в кредит и т. п.
Чаще всего в фирмах подобного рода оформление и сопровождение заказа осуществляется сотрудниками в офисе, которых
можно именовать как диспетчеров. Они, например, принимают
звонок от клиента и оформляют заказ, при этом могут либо зарегистрировать нового клиента, либо оформить заказ на уже зарегистрированного клиента. Далее диспетчер может указывать ход
выполнения заказа, завершить или отменить заказ. Таким образом, выделяется часть системы, предназначенная для диспетчера.
Это программа с графическим интерфейсом для операционной
системы Windows.
Выполнение заказов невозможно без исполнителей. Диспетчер может связываться с исполнителями различными способами.
Это может быть, например, бумажный документ, телефон или
рация. Первому способу не хватает динамичности, а именно этот
документ не может измениться в случае изменения заказа или его
отмены. Второй и третий способы по своей сути одинаковы, но
тоже имеют свой недостаток: при получении информации исполнителем возникает необходимость в том, чтобы записать полученные данные. А это не всегда возможно или удобно, например,
исполнитель может в этот момент вести автомобиль. С появлением дешевых мобильных телефонов с поддержкой GPRS и Javaприложений возникает новый способ получения информации о
заказе: через специальное приложение, которое получает данные
о заказе от некоего сервера через интернет. Такой способ лишен
недостатков предыдущих способов. Итак, очевидно наличие еще
одной части системы, предназначенной для исполнителя. Это
Java-приложение для мобильных телефонов.
Клиент исполнителя подразумевает наличие сервера, который будет по запросам, а также при изменении каких-либо полезных исполнителю данных отдавать ему полезную информацию, а также принимать различную информацию от исполнителя,
такую как, например, изменение хода выполнения заказа, его завершение или отмена. Появляется еще одна часть – сервер. Это
консольное приложение для операционной системы Windows.
А.Е. Капралов
53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При общении клиента исполнителя и сервера наиболее очевидным представляется использование сообщений на языке
XML, передаваемых по протоколу TCP/IP. При разработке необходимо учесть тот момент, что протокол может измениться
вплоть до отказа от использования XML вообще и перехода на
бинарный протокол. Такое может понадобиться в случае, когда
тестирование покажет, что передаваемые данные занимают
слишком большой объем, так как размер XML документа существенно больше бинарного представления тех же данных в связи
с избыточностью синтаксиса XML.
Так как без хранения данных эта система была бы бессмысленна, то появляется еще одна часть, которая будет преобразовывать данные из БД в объекты и обратно. Под объектами здесь понимаются структуры данных с точки зрения парадигмы объектно-ориентированного программирования.
В связи с тем, что сервер будет реализовывать логику обработки XML-сообщений и изменения данных, а также с тем, что
количество различных клиентских приложений может возрастать
(например, может возникнуть необходимость в web-клиенте), разумным решением будет совместить всю логику обработки данных в сервере, а получение данных всеми клиентами производить
через сервер посредством XML-протокола.
Таким образом, в понятиях архитектуры MVC (англ. ModelView-Controller – модель-вид-контроллер), в широком смысле,
сервер представляет модель, а клиенты – вид и контроллер.
В результате проделанной работы получилась функционирующая система. В ней диспетчер может добавлять заказ, изменять его состояние, просматривать завершенные заказы, редактировать список клиентов, а исполнитель может получать назначенный заказ, изменять его состояние, указывать свое
местоположение.
Для того чтобы данная система была коммерчески успешной,
ее необходимо дополнить рядом функций и возможностей. Например, расчет смен и заработной платы, формирование отчетов
и перевод их в необходимый формат (Excel, Word).
Однако целью данной работы было создание базовой части,
на основе которой можно строить различного масштаба инфор54
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
мационную систему. Данная задача была выполнена. Теперь для
внесения новых функций не потребуется построения новых модулей или изменения архитектуры. Необходимо лишь сформировать особый запрос, обработать его на сервере и получить ответ.
А так как основные элементы уже написаны, то нужно лишь внести корректировки в подобные запросы, создав новый.
В процессе работы над данным проектом были на практике
апробированы объектно-ориентированное программирование,
многопоточность, модульность, создание приложений с графическим интерфейсом, работа по сети, разработка приложений для
мобильных устройств.
Полученный проект представляет собой хорошую базу для
создания крупного коммерческого проекта, способного удовлетворить нужды по автоматизации предприятий малого бизнеса.
 Литература
1. Страуструп Б. Язык программирования C++. Специальное издание.
Пер. с англ. М.: ООО «Бином-Пресс», 2005. 1104 с.
2. Васильчиков В.В. Программирование в Visual C++ с использованием библиотеки MFC: учеб. пособие. Ярославль: ЯрГУ, 2006. 222 с.
3. Васильчиков В.В. Основы разработки сетевых Windows-приложений: учебное пособие; Ярославль: ЯрГУ, 2006. 234 с.
4. Парамонов И.В. Язык программирования Java и Java-технологии :
учебное пособие; Ярославль: ЯрГУ, 2006. 89 с.
5. Дейтл X.M., Дейтел П.Дж., Сантри С.И. Технологии программирования на Java2: Книга 2. Распределенные приложения. Пер. с англ. М.:
ООО «Бином-Пресс», 2003. 464 с.
6. Дейтл X.M., Дейтел П.Дж., Сантри С.И. Технологии программирования на Java2: Книга 3. Корпоративные системы, сервлеты, JSP, Webсервисы. Пер. с англ. М.: ООО «Бином-Пресс», 2003. 672 с.
7. Буткевич Е.Л. Пишем программы и игры для сотовых телефонов.
СПб.: Питер, 2006. 204 с.
8. Саттер, Герб. Новые сложные задачи на C++. : Пер. с англ. М.: Издательский дом «Вильямс», 2005. 272 с.
9. George Reese. Database Programming with JDBC and Java, 2nd edition.
O'Reilly & Associates, Inc., 2000. 348 c.
10. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектноориентированного проектирования. Паттерны проектирования = Design
Patterns: Elements of Reusable Object-Oriented Software. СПб: «Питер», 2007.
366 c.
А.Е. Капралов
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
11. MSDN Library for Visual Studio 2005. Microsoft Corporation, 2005.
12. Ciprian Miclaus. Encapsulating Win32 threads in C++ // CodeProject.
Free source code and programming help: http://www.codeproject.com/. – 2001.
1 веб-страница –
URL:
http://www.codeproject.com/KB/threads/thread_
win32.aspx .
13. Jonathan Knudsen. Parsing XML in J2ME // Sun Microsystems – Sun
Developer Network (SDN): http://developers.sun.com/. 2002. 1 веб-страница.
URL: http://developers.sun.com/mobility/midp/articles/parsingxml/ .
14. Анти-паттерн // Википедия. Свободная энциклопедия: http://ru.wikipedia.org/ – 2008. 1 веб-страница. – URL: http://ru.wikipedia.org/wiki/ Анти-паттерн.
Разработка биологически правдоподобной
нейронной сети, выделяющей контуры
(пиксельного) изображения
И.О. Колотухин
В последнее время на тему так называемого машинного зрения опубликовано множество работ [1]. Машинное зрение теснейшим образом взаимодействует с областью обработки изображений. Одной из задач, рассматриваемых в рамках машинного
зрения, является выделение на изображениях краев – резких переходов яркости [2]. Описываемая нейронная сеть опирается на
биологические данные о функционировании клеток сетчатки глаза млекопитающих.
Обработка зрительной информации устроена сложным образом. Она воспринимается и обрабатывается слоями сетчатки глаза, один из которых слой ганглиозных клеток. Ниже рассмотрены
модели:
– ганглиозной клетки;
– клетки, чувствительной к границе между светлым и темным, проходящей в фиксированном направлении;
– микроколонки (группа клеток, чувствительных к границе с
всевозможными ориентациями).
56
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Некоторая область сетчатки глаза называется рецептивным
полем ганглиозной клетки. Воздействуя на нее светом, можно
повлиять на активность данной клетки. Рецептивное поле представляет собой круг и прилегающее к нему кольцо. Различают
два типа клеток с рецептивными полями: с on-центром и offцентром. On-клетка проявляет наибольшую активность при освещении центра ее рецептивного поля. А освещение периферии
подавляет ее активность. Поведение off-клетки противоположно:
освещение периферии увеличивает ее активность, а освещение
центра – подавляет.
Рассмотрим равномерную решетку на прямоугольнике
– это множество точек
,
.
где
Нейроны, моделирующие активность ганглиозных клеток,
клеток, чувствительных к границе, микроколонок, расположены в
узлах таких решеток. Также в узлах решетки задаются значения
яркости
исходного изображения. Яркость может принимать
значения от 0 (черный) до 1 (белый).
моделируемого нейрона onОпределим скалярный выход
клетки как свертку весовой функции
со значениями яркости:
где
Здесь
– радиус центра рецептивного поля,
– внешний
радиус периферии рецептивного поля, – число узлов, попавших в центр рецептивного поля, а – число узлов, попавших в
периферию рецептивного поля. Аналогичным образом выглядит
весовая функция моделируемого нейрона off-клетки:
И.О. Колотухин
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В итоге получаем, что скалярный выход модели off-клетки
.
( ) отличается от выхода on-клетки только знаком:
Введем понятие идеального края. Идеальным краем называется такая прямая
, что яркость
где – угол наклона прямой, – расстояние от прямой до начала
координат.
Входной информацией для модельной клетки
, чувствительной к границе между светлым и темным, является активность
решетки, через который
on- и off-клеток. Пусть для узла
, будет выполнено
проходит край с параметром
где
определяют прямоугольники, по узлам внутри которых
производится суммирование, – число слагаемых в сумме. Пусть
модельная клетка настроена на угол
. Необходимо, чтобы отубывал по мере отклонения угла навет модельной клетки
клона края от угла и по мере удаления края от узла
. Та.
в
ким требованиям удовлетворяет функция
случаях, когда край перпендикулярен оптимальному направле, настронию и внутри однородной области. Клетка в узле
отличается поворотом прямоугольников военная на угол
на угол
.
круг точки
решеток располагаются моВ одних и тех же узлах
дельные клетки с ориентационной чувствительностью. Они на. Эти мостроены на разные ориентации края
58
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
дельные клетки сгруппированы в микроколонки. За ответ целой
микроколонки примем максимальный из ответов входящих в нее
. Тогда высокая активность микроклеток:
колонки означает наличие края.
Работа представленной нейронной сети продемонстрирована
на рис. 1. и 2.
Рис. 1. Слева – матрица яркости 400 300 узлов.
Справа – результат выделения краев с параметрами
. Порог черного пикселя 0,034
Рис.2. Слева – матрица яркости 400 300 узлов.
Справа – результат выделения краев с параметрами
. Порог черного пикселя 0,038
 Литература
[1] Научная сессия МИФИ – 2008. Нейроинформатика 2008. X Всероссийская научно-техническая конференция. Лекции по нейроинформатике. Ч. 2. М., 2008.
[2] Сергин А.В. Биологически правдоподобный нейросетевой детектор края. М., Институт прикладной математики им. М.В. Келдыша РАН,
И.О. Колотухин
59
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Исследование поведения
характеристического набора черно-белого
изображения при его повороте
Д.А. Кудинкин
Одной из самых динамично развивающихся областей вычислительной математики является раздел, решающий вопросы компьютерного видения и анализа сцен. Со времен формирования
данной области науки был сделан огромный прогресс в анализе
изображений, анализе сцен и поиске объектов на сценах. Для выявления объектов на сцене, представленной на изображении,
классическим подходом является использование метрики Хаусдорфа. Однако метрика Хаусдорфа кроме преимуществ имеет несколько ключевых недостатков: высокую трудоемкость и плохое
приложение к поиску трансформированных объектов на сцене.
Помимо метрики Хаусдорфа для поиска и распознавания трансформированных изображений на сцене предложено использовать
набор коэффициентов, задающий количество фрагментов размера
2х2 соответствующих типов для черно-белого цифрового изображения.
Представим черно-белое изображение в виде матрицы A, в
которой каждый элемент xij ∈ A равен 1, если соответствующая
точка изображения имеет черный цвет, 0 – иначе. Фрагментом S i
размера 2*2 будем называть подматрицу
ai j ai j+1
ai+1 j ai+1 j+1
матрицы А изображения. Всего существует 16 различных типов
фрагментов, обозначенных символами Si, i = 0,…,15. Построим
набор неотрицательных чисел Кi, i = 0,…,15, где Кi – количество
фрагментов типа Si. Этот набор будем называть характеристиче60
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ским набором коэффициентов изображения А, построенных по
системе фрагментов размера 2х2.
В работе [5] предложено находить меру сходства между черно-белыми изображениями на основе вычисленных характеристических наборов, используя расстояние Евклида и другие принятые расстояния.
Основной задачей данной работы было нахождение зависимости изменения характеристического набора изображения относительно его угла поворота. После исследования изменения характеристических наборов различных изображений при их повороте было замечено, что набор изменяется линейно в промежутке
между углами, кратными 45 градусов. Эмпирическим путем была
найдена следующая функциональная зависимость:
k ( Si ) = k0 ( Si ) ∗ a + k1 ( Si ) ∗ ( 1 − a ) + Θ ,
где k ( Si ) – количество фрагментов типа Si в итоговом наборе,
k ( Si ) – количество фрагментов типа Si в наборе для первого
ключевого угла,
k ( Si ) – количество фрагментов типа Si в наборе для второго
ключевого угла,
Θ – погрешность, связанная с погрешностью алгоритма интерполяции изображения, используемого при повороте.
a – коэффициент интерполяции характеристического набора,
который может быть вычислен следующим образом:
a = ( α − α0 ) / 45 ,
где α – угол поворота изображения.
Данная зависимость имеет наименьшую погрешность при работе с изображениями, имеющими четкие контуры с минимальным количеством шумов. То есть эту зависимость можно использовать для восстановления характеристического набора для изображений символов, повернутых на некоторый угол.
На основе полученной зависимости был построен алгоритм
восстановления характеристического набора повернутого изображения, и его программная реализация была протестирована на
Д.А. Кудинкин
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
символах латинского алфавита размером 50x50 пикселей. Тесты
продемонстрировали хорошее восстановление набора. Качество
восстановления оценивалось с помощью приведенного евклидова
расстояния на множестве характеристических наборов, которое
было описано в работе [5].
На основе алгоритма восстановления набора был построен
алгоритм распознавания угла поворота изображения. Входными
данными для такого алгоритма являются изображение с некоторым образом и изображение с этим же образом, повернутым на
некоторый угол. Выходными данными являются предположения
об угле поворота изображения. Работа алгоритма заключается в
восстановлении характеристического набора исходного изображения, повернутого на углы, взятые с некоторым шагом, с последующим нахождением расстояния между вычисленным для каждого угла набором и набором, вычисленным на рассматриваемом
изображении. В итоге получается функция F, отображающая
множество взятых углов на множество расстояний между вычисленным набором и набором повернутого изображения. Минимум
данной функции характеризует минимальное различие между
восстановленным набором и набором повернутого изображения,
вследствие чего указывает на вероятный угол поворота. Всего
функция F может иметь до 8 минимумов (это связано с особенностями вычисления характеристического набора, затронутыми в
работе [4]), и поэтому алгоритм предоставляет до 8 предположений. Впрочем, неверные предположения можно отсеять, основываясь на вычисленных мерах близости.
Данный алгоритм был протестирован на изображениях символов латинского алфавита и дал следующие результаты:
протестировано изображений: 26
распознано углов с допустимой погрешностью ( ± 10 градусов): 92%
средняя погрешность определения угла (среди распознанных): 2.4 градуса
минимальная погрешность: 0 градусов
максимальная погрешность: 8 градусов.
При работе с изображениями символов латинского алфавита
данный алгоритм не смог распознать углы поворота для изобра62
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
жений букв «О» и «С». Характеристические наборы этих изображений незначительно меняются относительно угла поворота, поэтому существующая погрешность вычисления характеристического набора не позволяет определить углы поворота для этих
изображений.
Приведенная погрешность и количество предположений в
сумме с низкой трудоемкостью позволяют говорить о возможности практического применения данного алгоритма в качестве
предварительного шага по конкретизации области поиска для
классических алгоритмов распознавания трансформированных
изображений.
Основываясь на алгоритмах, описанных ранее, также был
разработан алгоритм, распознающий смещенные и повернутые на
некоторый угол изображения символов.
Входными данными для алгоритма является коллекция изображений различных символов, совокупность которых назовем
алфавитом, и изображение, содержащее смещенный на некоторый вектор и повернутый на некоторый угол символ из входного
алфавита. Выходными данными работы этого алфавита является
набор предположений о символе, который изображен на тестируемом изображении, и угол его поворота.
Данный алгоритм является расширением для предыдущего
алфавита: к каждому символу из алфавита применяется предыдущий алгоритм, и после этого выбираем символ, минимально
отличный набор которого является минимально отличным во
всем алфавите. Результатом работы алгоритма на различных алфавитах является упорядочивание символов алфавита по убыванию степени сходства вычисленного характеристического набора
на основе изображения символа и набора распознаваемого изображения. Используя разные пороговые фильтры, из упорядоченного таким образом алфавита можно затем выбрать нужное
количество предположений с разной степенью близости. Это
также говорит о потенциальной возможности практического использования алгоритма.
Разработанные алгоритмы в общем случае не дают однозначного ответа, но позволяют резко сузить область поиска для классических алгоритмов распознавания изображений, основанных на
Д.А. Кудинкин
63
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
расстоянии Хаусдорфа [2] или других трудоемких подходах. Основным преимуществом данных алгоритмов является их низкая
трудоемкость, так как они работают не с самими изображениями,
а с их представлениями в виде характеристических наборов,
представляющих собой 16-мерные векторы и имеющих линейную трудоемкость вычисления на основе матрицы пикселей изображения. Поэтому можно предложить использовать эти алгоритмы в качестве предварительного шага работы классических
алгоритмов для конкретизации области поиска и отсеивания заведомо неверных вариантов.
 Литература
1. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир,
1976.
2. Daniel P. Huttenlocher, Сomparing images using the Hausdorff distance.
М.: IEEE Transactions on pattern analysis and machine intelligence. V. 15, № 9,
1993.
3. Wim H. Hesselink, A Euclidean distance transform in linear time. M.:
Dept/ of mathematics and computer science. RijksuniversiteitGroningen, 1998.
4. Парфенов П.Г. Некоторые числовые характеристики изображений,
инвариантные относительно сдвигов и поворотов // Моделирование и анализ информационных систем. Ярославль, 1998. № 5. С. 58–61.
5. Парфенов П.Г., Каплий И.Ф., Куликов О.С. Расстояния и другие
меры близости на множестве черно-белых изображений // Моделирование
и анализ информационных систем. Т. 13, № 1. Ярославль, 2007. С. 52–54.
Реализация трёхмерной модели персонажа
с высокой детализацией
Е.А. Кукушкин
Сегодня анимация персонажа занимает лидирующие позиции
в трёхмерном моделировании. Также она занимает не последнее
место в создании современных фильмов. Широкое применение
компьютерной анимации персонажа можно встретить и в производстве мультфильмов. Кроме этого анимация персонажа полу64
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
чила своё распространение в индустрии компьютерных игр. Кинематография, мультипликация, создание компьютерных игр –
вот далеко не полный список областей, где используется компьютерная анимация персонажа.
При такой популярности и актуальности компьютерной анимации возникает необходимость создания систем, которые позволят пользователям создавать самих персонажей и наделять их
движениями. Понятно, что создание таких сложных систем не
под силу отдельным разработчикам, этим занимаются крупные
корпорации, которые создают программные продукты, ориентированные специально на создание трёхмерной графики. Наиболее
известными и популярными на сегодняшний день являются: 3D
Studio Max, Maya и Poser.
Моей задачей при разработке игр является создание трёхмерных объектов, элементов рельефа, существ, персонажей и их
анимаций, а также их реализации в рекламных и технических целях. В курсовых работах мною были описаны некоторые этапы
действий, которые необходимо выполнить, чтобы в результате
получился гармоничный и приятный трёхмерный игровой мир.
Один из новых проектов требовал решить задачу более узкого
плана, но с наличием других требований, которые несли в себе
необходимость изучения нового материала по разработке трёхмерных моделей, ориентированных на высокую детализацию.
Одной из главных проблем, которые стояли передо мной в
данных работах – это проектирование модели персонажа и оживления его путём создания анимаций. Проект «Во времени» как
раз и требовал первостепенно решить эту задачу, получившую
расширение и изменение требований к результату. В итоге у нас
должна быть создана анимированная модель персонажа с высокой детализацией с наложенным на неё набором текстур.
Результаты проделанной работы будут использованы как в
игре, так и в коммерческом арте, и помогут визуально представить проект. Созданные картинки на основе данного персонажа
будут использоваться в презентациях и концепт-документах.
Также данная модель будет конвертирована в движок, и в игре
можно будет увидеть модель персонажа, у которой есть возможЕ.А. Кукушкин
65
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ность осуществлять какие-либо действия в зависимости от желаний пользователя.
Для реализации данных задач, главным образом, будем использовать программный продукт 3D Studio Max, а также другие
программы для работы с трёхмерной графикой и плоскими изображениями.
Создание персонажа делится на несколько этапов, которые
иногда должны выполняться только в определённой последовательности.
Первый этап в разработке – это создание так называемых
скетчей (рисунков-ориентиров). Они нужны для уточнения каких-либо особенностей и деталей той или иной модели. В крупных компаниях эту работу осуществляют специальные художники, которые рисуют персонажей для дальнейшего их создания
следующими участниками. Их задача – придумать на основе требований определённый образ, который станет прототипом для
модели. В современной индустрии компьютерных игр качество
скетчей достигло больших высот и теперь их зачастую используют в рекламных целях.
Следующими участниками в разработке можно назвать модельеров. Они на основе скетчей создают трёхмерные геометрические модели. На данном этапе проектирования можно выделить главные особенности в расстановке и распределении полигонов:
1. Сетка (каркас) модели должна преимущественно состоять
из четырёхугольных полигонов (граней).
2. Полигоны всей модели не должны сильно отличаться размером друг от друга – это требование обусловлено удобством в
дальнейших этапах разработки. В основном это необходимо для
корректности создания карты нормалей и равномерного отображения текстур на модели.
3. Необходимо создавать основной силуэт, поэтому не нужно
выделять мелкие детали полигонами, т.к. они будут созданы текстурированием. Для примера к мелким деталям в новом проекте
можно отнести ремни, швы, пуговицы и т.п.
66
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Эта структура возникла при моделировании модели с высокой детализацией и соответственно использовалась при её реализации.
Для редактирования каркаса в среде 3D Studio Max существует модификатор Editable Poly, объединяющий в себе удобство
планирования вершин и точность контроля. В данном методе
можно установить интерполяцию полигонов путём увеличения
автоматических граней между установленными вершинами.
Главным удобством является возможность добавления новых
вершин и полигонов, тем самым позволяя создавать нужное количество правильно сочетаемых вершин и полигонов.
Детализация модели зависит от требований проекта. В проекте с высокой детализацией необходим этап создания карты нормалей – это добавляет эффект высокого качества созданной модели без усложнения геометрии.
Карту нормалей можно создать, используя приложение
ZBrush от компании Pixologic. Процесс работы в ZBrush происходит в следующей последовательности:
1. Конвертирование созданной модели из 3D Studio Max.
2. Разбиение полигонов – это основная идея данного приложения. Увеличение полигонов позволяет делать высокую детализацию модели, что впоследствии станет опорным элементом для
получения необходимой карты нормалей.
3. Редактирование каркаса. Использование высокополигональной модели для создания мелких деталей и элементов рельефа.
4. Конвертирование детализации высокополигональной модели в карту нормалей.
Модель без набора текстур не является приемлемой, поэтому
создание текстур и их наложение на модель является следующим
этапом в проектировании. Иногда эту работу выполняют отдельные люди – текстураторы, но также этим могут заниматься и сами модельеры, что, на наш взгляд, зачастую бывает удобней.
Создание модели и набора необходимых текстур является самой
основной частью в разработке персонажа.
Когда у нас есть модель с необходимым набором текстур,
можно приступать к её оживлению (однако наличие текстур не
Е.А. Кукушкин
67
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
является необходимым для начала). Для этого необходимо создание или взятие готового скелета, с помощью которого можно будет заставить персонаж двигаться. Данный скелет можно использовать и на других персонажей с похожей физиологией. Этот
подход значительно экономит время для создания движений разнообразных персонажей. Анимация, которая будет создана для
скелета, также будет приемлема для любых персонажей с этим
скелетом. Таким образом, продолжая говорить о плане разработки, следующим этапом можно назвать создание скелета для существующей модели.
После того, когда у нас будет модель и скелет, их надо заставить контактировать, а точнее сделать так, чтобы модель зависела
от этого скелета. Данный процесс можно назвать – скинингом (от
англ. skin – кожа). После прохождения этого этапа моделью можно будет управлять при помощи скелетной деформации.
Последним этапом в проектировании модели является её
анимирование, т.е. создание определённого набора анимаций, которые будут отражать те или иные состояния персонажа. Этим
занимаются аниматоры.
В общих чертах данные этапы могут применяться не только к
персонажам, но и любым элементам игрового окружения. Даже
строения в процессе создания проходят большинство из перечисленных моментов. Несмотря на то что дома, казалось бы, не нуждаются в анимации, зачастую приходится каким-то образом
оживлять статическое здание, к примеру, вывеска над входом
может раскачиваться ветром.
В итоге создание персонажа можно рассмотреть в виде плана.
Общий план разработки включает восемь основных пунктов:
1. Создание скетчей (разработка визуального образа и создание рисунков).
2. Создание трёхмерной модели (в среде 3D Studio Max).
3. Создание развёртки текстур (в среде 3D Studio Max модификатор unwrap UVW).
4. Создание карты нормалей (пакет ZBrush).
5. Разработка текстур (пакет Corel Photo-Paint).
а. Текстура цвета на основе карты нормалей.
b. Текстура освещения на основе карты нормалей.
68
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
c. Текстура бликов на основе карты нормалей.
6. Создание скелета (приложение Character Animation
Toolkit).
7. Привязка модели к скелету (в среде 3D Studio Max модификатор Skin).
8. Создание анимаций на основе скелетной деформации
(приложение Character Animation Toolkit).
В результате выполнения всех пунктов и соблюдения описанных технологий можно создать любую трёхмерную модель
хорошего качества. Также необходимо учитывать определённые
требования, предлагаемые на каждом этапе проектирования.
 Литература
1. Русскоязычный сайт о приложении Zbrush: http://www.zbrush.ru/
2. Проект по разработке и дизайну компьютерных игр:
http://www.gamedev.ru/
3. On-line-журнал по 3D графике и анимации: http://www.render.ru/
Разработка трехмерных сцен и изучение
программной среды 3d studio MAX
В.В. Лебедев, Ф.А. Разумный
Цели и постановка задач
Разработка алгоритма построения сложной трехмерной сцены:
– моделирование сложных объектов;
– текстурирование сложных объектов;
– освещение трехмерной сцены;
– постановка камер;
– анимация трехмерной сцены;
– работа с модулем reactor2;
– визуализация сложных объектов и т.д.
В.В. Лебедев, Ф.А. Разумный
69
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Общие сведения о трехмерной графике
и программной среде 3d studio max
Программа 3ds max характеризуется продуманным интерфейсом и относительной легкостью в освоении. Этим можно объяснить ее большую популярность. Богатый инструментарий дает
разработчику трехмерной графики возможность реализовать в
программе любую задумку.
Трехмерная графика позволяет создавать трехмерные макеты
различных объектов, повторяя их геометрическую форму и имитируя материал, из которого они созданы. Чтобы получить полное представление об определенном объекте, необходимо осмотреть его со всех сторон, с разных точек, при различном освещении.
Трехмерная графика настолько прочно вошла в нашу жизнь,
что мы сталкиваемся с ней, порой даже не замечая ее. Разглядывая интерьер комнаты на огромном рекламном щите, янтарный
блеск льющегося пива в рекламном ролике, наблюдая, как взрывается самолет в остросюжетном боевике, многие не догадываются, что перед ними не реальные съемки, а результат работы
мастера трехмерной графики. Область применения трехмерной
графики необычайно широка: от рекламы и киноиндустрии до
дизайна интерьера и производства компьютерных игр.
При создании рекламы трехмерная графика помогает представить продвигаемый товар в наиболее выгодном свете, например, с ее помощью можно создать иллюзию идеально белых рубашек, кристально чистой минеральной воды, аппетитно разломленного шоколадного батончика, хорошо пенящегося моющего
средства и т. д. В реальной жизни рекламируемый объект может
иметь какие-нибудь недостатки, которые легко скрыть, используя
в рекламе трехмерных «двойников». Вы наверняка замечали, что
после применения моющего средства посуда блестит не так ярко,
как в рекламе, а волосы после использования шампуня не выглядят так красиво, как на экране телевизора. Причина этого проста:
слишком чистая посуда – всего лишь просчитанное компьютером
изображение, такие тарелки в реальности не существуют.
70
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Использование компьютерных технологий при проектировании и разработке дизайна интерьера помогает увидеть конечный
вариант задолго до того, как обстановка будет воссоздана.
Трехмерная графика позволяет создать демонстрационный
ролик, в котором будет запечатлена виртуальная прогулка по
этажам будущего коттеджа, только начинающего строиться.
Что же касается киноиндустрии, то в этой отрасли компьютерная графика сегодня незаменима.
Для создания трехмерной графики используются специальные программы, которые называются редакторы трехмерной графики, или 3D-редакторы. 3ds max является одной из таких программ. Результатом работы в любом редакторе трехмерной графики, в том числе и в 3ds max , является анимационный ролик
или статичное изображение, просчитанное программой. Чтобы
получить изображение трехмерного объекта, необходимо создать
в программе его объемную модель.
Модель объекта в 3ds max отображается в четырех окнах
проекций. Такое отображение трехмерной модели используется
во многих редакторах трехмерной графики и дает наиболее полное представление о геометрии объекта. Если вы видели чертежи
деталей, то могли заметить, что на чертеже объект представлен
сверху, сбоку и слева. Интерфейс 3ds max напоминает такой чертеж. Однако в отличие от чертежа на бумаге, вид объекта в каждом окне проекций можно изменять и наблюдать: как выглядит
объект снизу, справа и т. д. Кроме этого, можно вращать все виртуальное пространство в окнах проекций вместе с созданными в
нем объектами. Работа в 3ds max напоминает компьютерную игру, в которой пользователь передвигается между трехмерными
объектами, изменяет их форму, поворачивает, приближает и т.д.
Виртуальное пространство, в котором работает пользователь
3ds max, называется трехмерной сценой. То, что вы видите в окнах проекций, – это отображение рабочей сцены. Работа с трехмерной графикой очень похожа на съемку фильма, при этом разработчик выступает в роли режиссера. Ему приходится расставлять декорации сцены (то есть создавать трехмерные модели и
выбирать положение для них), устанавливать освещение, управВ.В. Лебедев, Ф.А. Разумный
71
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
лять движением трехмерных тел, выбирать точку, с которой будет производиться съемка фильма и т.д.
Любые трехмерные объекты в программе создаются на основе имеющихся простейших примитивов – куба, сферы, тора и др.
Создание трехмерных объектов в программе 3ds max называется
моделированием. Для отображения простых и сложных объектов
3ds max использует так называемую полигональную сетку, которая состоит из мельчайших элементов – полигонов. Чем сложнее
геометрическая форма объекта, тем больше в нем полигонов и
тем больше времени требуется компьютеру для просчета изображения. Если присмотреться к полигональной сетке, то в местах
соприкосновения полигонов можно заметить острые ребра. Поэтому чем больше полигонов содержится в оболочке объекта, тем
более сглаженной выглядит геометрия тела. Сетку любого объекта можно редактировать, перемещая, удаляя и добавляя ее грани,
ребра и вершины. Такой способ создания трехмерных объектов
называется моделированием на уровне подобъектов.
В реальной жизни все предметы, окружающие нас, имеют
характерный рисунок поверхности и фактуру – шершавость, прозрачность, зеркальность и др. В окнах проекций 3ds max видны
лишь оболочки объектов без учета всех этих свойств. Поэтому
изображение в окне проекции далеко от реалистичного. Для каждого объекта в программе можно создать свой материал – набор
параметров, которые характеризуют некоторые физические свойства объекта.
Чтобы получить просчитанное изображение в 3ds max, трехмерную сцену необходимо визуализировать. При этом будут учтены освещенность и физические свойства объектов.
Созданная в окне проекции трехмерная сцена визуализируется либо непосредственно из окна проекции, либо через объектив
виртуальной камеры, представляющей собой вспомогательный
объект, обозначающий в сцене точку, из которой можно произвести визуализацию проекта. Для чего нужна виртуальная камера?
Визуализируя изображение через объектив виртуальной камеры,
можно изменять положение точки съемки. Подобного эффекта
невозможно добиться, визуализируя сцену из окна проекции.
Кроме этого, виртуальная камера позволяет использовать в сце72
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
нах специфические эффекты, похожие на те, которые можно получить с помощью настоящей камеры (например, эффект глубины резкости).
Качество полученного в результате визуализации изображения во многом зависит от освещения сцены. Когда происходят
съемки настоящего фильма, стараются подобрать наиболее удачное положение осветительных приборов таким образом, чтобы
главный объект был равномерно освещен со всех сторон, и при
этом освещение съемочной площадки выглядело естественно.
Программа 3ds max позволяет устанавливать освещение
трехмерной сцены, используя виртуальные источники света – направленные и всенаправленные. Источники света являются такими же вспомогательными объектами, как виртуальные камеры.
Их можно анимировать, изменять их положение в пространстве, управлять цветом и яркостью света. Еще одна важная деталь, благодаря которой источники света придают сцене большую реалистичность, – отбрасываемые объектами тени.
Работать с источниками света бывает порой очень сложно,
поскольку не всегда удается правильно осветить трехмерную
сцену. Например, слишком яркие источники света создают сильные и неправдоподобные блики на трехмерных объектах, а большое количество теней, направленных в разные стороны, выглядят
неестественно.
Подобно огромному зданию, построенному из маленьких
кирпичиков, программа 3ds Max позволяет создавать разноплановые сцены, используя в качестве строительных блоков примитивы (параметрические объекты). Можно использовать стандартные параметрические объекты для начала любой работы. После
создания к ним можно применять модификаторы, строить составные объекты, разрезать, редактировать на уровне подобъектов и выполнять многие другие операции.
Объектами в программе 3ds Max являются любые геометрические фигуры, кривые, камеры, вспомогательные объекты, объемные деформации, системы и источники света, которые могут
включаться в состав сцены.
Мы создали 3D сцену с ландшафтом местности и элементами
архитектуры. В сцене присутствуют такие объекты, как: сам
В.В. Лебедев, Ф.А. Разумный
73
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ландшафт, здания, стадионы, деревья, мост, фонари, детский городок, кемпинг.
Процесс создания сложной архитектуры достаточно трудоёмкий.
Моделирование начинается с создания контура, который основывается на чертежах или планах реального здания. Далее из
контура выращивается каркас здания, затем большая часть времени уходит на детализацию (окна, балконы, карнизы, крыша,
двери и т.д.), для того чтобы модель была максимально приближена к оригиналу. После этого модель текстурируется.
Процесс текстурирования представляет собой наложение
нужной картинки на выбранный объект. Для этого используется
Material Editor (редактор материалов). Затем для корректного
отображения текстуры на объекте используется модификатор
UVW Map.
Создание динамических характеристик – это одна из функций 3ds max, связанная с анимацией. Сцены, в которых используется просчет динамических составляющих (например, изображение разбивающихся предметов, развевающейся на ветру ткани,
движений марионеток), – это анимационные проекты. Поскольку
в реальном мире движение любого объекта подчиняется законам
физики, для создания реалистичной трехмерной анимации необходимо учитывать влияние многих физических факторов – гравитацию, массу тел, направление ветра и т. д. С помощью 3ds max
можно просчитывать анимацию объектов, которая будет подчиняться законам физики. При этом в настройках объектов указываются их физические свойства, на основе которых происходит
просчет их поведения и взаимодействия. Просчет таких сложных
сцен происходит с использованием модуля reactor 2.
Правильно выставленный свет может значительно улучшить
сцену, и наоборот, если источники света расставлены произвольным образом, даже хорошо смоделированная сцена покажется
бедной. Грамотное освещение определяет общую атмосферу изображения. При помощи света можно передать настроение, напряженность, радость, тоску, подчеркнуть достоинства и скрыть
недостатки, а также сделать многое другое.
74
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Визуализация – это последний, а значит, самый ответственный этап создания трехмерного проекта. Неудачно выполненная
визуализация может «свести на нет» все многодневные усилия по
моделированию, освещению и текстурированию сцены.
Пример сцены с правильно поставленным светом
и визуализацией в 3d studio max
Если сравнивать работу в 3ds Max с видеосъемкой, то важность правильного выбора настроек визуализатора можно сопоставить с важностью выбора пленки, на которой снимается материал. Точно так же, как на двух пленках разных фирм могут получаться яркий и блеклый снимки, результат работы аниматора
может быть красивым или посредственным в зависимости от того, какой алгоритм просчета изображения выбран. Именно поэтому визуализации уделяется особое внимание. Визуализация
трехмерной сцены может иметь множество решений, поэтому
помимо стандартного алгоритма просчета существует множество
альтернативных визуализаторов. После просчета трехмерной
сцены становятся видны такие свойства материалов, как отражение, преломление света и др. Если требуется добиться высокой
степени реалистичности, то в качестве алгоритма просчета следует использовать альтернативные визуализаторы.
На продолжительность процесса просчета трехмерной сцены
влияет множество факторов, среди которых – количество используемых в сцене источников освещения, способ визуализации теней, сложность полигональной структуры объектов и т. д. В программу 3ds Max интегрирован визуализатор mental ray 3.4, который позволяет имитировать все основные визуальные эффекты –
В.В. Лебедев, Ф.А. Разумный
75
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
эффект каустики (Caustics), подповерхностного рассеивания
(Sub-Surface Scattering) и глубины резкости (Depth of Field).
Данную работу можно использовать как методические указания при проектировании архитектуры, трехмерных сцен, рекламных видеороликов, фотореалистичных изображений и т. п. в программной среде 3d studio MAX.
 Литература
1. Мэрдок К.Л. 3ds Max 5 Библия пользователя (+ CD-ROM). Изд.
дом «Вильямс». 2003.
2. Соловьев М.М. 3ds Max 6 Мир трехмерной графики. М.: Солон –
Пресс, 2004.
3. Слободецкий И.М. 3D Studio МАХ 6.0: Практический курс. 2004.
(Серия «Ваш персональный компьютер»).
4. Верстак В.А., Бондаренко С.В., Бондаренко М.Ю. 3ds Max 8 на
100% (+ CD-ROM). СПб.: Питер-пресс. 2005.
5. Бондаренко С.В., Бондаренко М.Ю. 3ds Max 8 Библиотека пользователя (+CD). СПб.: Питер, 2006.
6. www.discreet.com
7. www.render.ru
Разработка механической системы принятия
решений на основе индикатора MACD
А.С. Лишатова
Исследование графиков рыночных цен имеет познавательное,
практическое и научное значение. Как правило, тенденции в тех
или иных сегментах рынка являются предвестниками изменений
состояния экономики в целом. Важной особенностью рыночного
ценообразования является наличие существенной «стихийной»
составляющей в ценах. Поэтому наряду с методами фундаментального анализа при прогнозировании цен разрабатываются
специальные методы. Технический анализ можно определить как
систему прогнозирования цен, основанную не на экономических
расчетах, а на математической обработке ценового графика. В
76
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
нём выделяют две основные группы методов: графические и аналитические (методы индикаторов).
Индикатор – это результат математических расчетов на основе показателей цены и/или объема. Полученная величина используется для прогнозирования ценовых изменений.
Этому определению вполне отвечает понятие скользящего
среднего: оно представляет собой результат математических расчетов на основе ценовых показателей и может использоваться для
прогнозирования ценовых изменений. Скользящее среднее значение – это средняя цена бумаги за определенный период.
Скользящая средняя – основная конструкция в техническом
анализе, на основе которой построено большинство индикаторов.
Существует несколько видов скользящих средних: простая,
экспоненциальная и другие виды средних.
Простая (или арифметическая) скользящая средняя рассчитывается при помощи суммирования цен закрытия ЦБ за определенный период времени и последующем делении полученной
суммы на число дней в этом периоде.
C1 , , Cn − последовательность значений цен закрытий.
C +  + CN
– значение простой скользящей средней с
S NS = 1
N
периодом равным N.
Экспоненциальная (или экспоненциально-взвешенная) скользящая средняя рассчитывается как сумма сегодняшней цены закрытия, умноженной на процент, с вчерашним значением скользящей средней, умноженным на процент.
S NE – значение экспоненциальной скользящей средней с периодом равным N.
S NS = СN * k + S NE −1 * (1 − k ) ;
Эта формула переписывается следующим образом:
N −1
S NS = СN * k + CN −1 * k (1 − k ) + CN − 2 * k (1 − k )2 +  + C2 * k (1 − k )N − 2 + C1 (1 − k ) ,
2
где k =
;
N +1
Экспоненциальная скользящая средняя характеризуется возрастанием веса значений ряда в направлении к последней дате
А.С. Лишатова
77
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
(концу ряда) и его уменьшением в направлении к первым датам
(началу ряда). Такого нет у простой скользящей средней.
Ярким представителем, выражающим подход к анализу графиков, является индикатор MACD (moving average convergence
divergence), что переводится как схождение – расхождение (конвергенция – дивергенция) скользящих средних.
Индикатор MACD рассчитывается как разница между средними ценами за недавний период и средними ценами за более
долгий период. Полученные при этом результаты еще раз усредняются с порядком равным 9. Данный график называется сигнальной линией.
Таким образом, значение индикатора MACD вычисляется как
разность между двумя значениями скользящих средних:
C
+  + Cn C1 +  + Cn
MACD = n − k +1
−
,
k
n
где C1 , , Cn – последовательность значений цен.
C +  + Cn
C
+  + Cn
Sn = 1
; S k = n − k +1
;
n
k
Sn – среднее значение цены за период равный n,
Sk – среднее значение цены за период равный k.
Основная функция индикатора MACD – генерация сигналов
покупки или продажи (получается при пересечении индикатора
MACD и его сигнальной линии). Но генерация сигнала покупки
или продажи может быть ложной или запаздывающей. Требовалось выяснить наилучшее соотношение между коэффициентами
двух скользящих средних в индикаторе MACD и возможные модификации индикатора MACD, чтобы улучшить характеристики
работы.
С помощью математических выводов было определено наиболее оптимальное соотношение между коэффициентами двух
скользящих средних в индикаторе MACD как 2 к 1. Данный вывод был подтвержден на практике.
В современной программе технического анализа MetaStock
Professional 7.0 были протестированы различные формулы модифицированного индикатора MACD. Был сделан вывод, что наилучшим результатом является формула вида: сам индикатор
78
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
MACD находится как разность между экспоненциальной скользящей средней малого периода и простой скользящей средней
большего периода, а сигнальную линию находим от этого модифицированного индикатора MACD как простую скользящую
среднюю. Преимущество данной формулы также теоретически
было доказано.
Одно из ключевых положений, лежащих в основе разработки
«адаптивного» индикатора, заключается в том, что универсальных настроек коэффициентов в индикаторе MACD для различных
графиков быть не может. Это следует также из теории Эллиотта.
Используя данные фондового рынка в качестве своего главного инструмента, Ральф Нельсон Эллиотт открыл, что, казалось
бы, постоянно меняющаяся траектория рыночных цен всегда выписывает некоторый структурированный рисунок. На основе этого открытия он разработал рациональную систему рыночного
анализа. Эллиотт выделил основную модель движения цен, которая снова и снова возникает на графиках, повторяется по форме,
но не обязательно по времени или амплитуде.
Данный закон волн сейчас носит его имя "Закон волн Эллиотта".
В несколько упрощенном виде основной постулат теории
гласит: рыночная цена подчиняется повторяющемуся ритму –
пять движений в растущем тренде и три движения в коррекционном. Почти такой же важной характеристикой волн, как устойчивая модель их сочетания, является степень соответствующей тенденции. Важнейшее правило теории волн гласит: независимо от
А.С. Лишатова
79
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
степени тенденция всегда будет развиваться по основному восьмиволновому циклу. Каждая волна подразделяется на меньшие
волны, которые в свою очередь также разбиваются на волны –
еще меньшей степени. Естественно, отсюда следует, что каждая
из волн фактически является частью большей, следующей в волновой иерархии.
Умение различать трехволновые и пятиволновые модели –
основа практического применения теории волн. От него зависят
все дальнейшие действия трейдера. Количество волн подсказывает, чего следует ожидать на рынке.
Выявление на ценовых графиках волн и их идентификация
являются весьма не простой задачей, тем более для механической
системы.
Томас Р. Демарк выделяет максимальную цену закрытия за
13 дней, такую, что она выше ценовых максимумов всех предшествующих 13 дней. Далее он выделяет первую цену закрытия
(после максимальной цены закрытия за 13 дней), которая является минимальной за 8 дней, то есть ниже всех цен закрытия за
предыдущие 8 дней. Если эти точки определены, первую волну
можно считать завершенной. Вторая волна начинается тогда, когда регистрируется максимальная цена закрытия за 21 день, такая, что она выше всех цен закрытия за предшествующий
21 день. Вторая волна считается завершенной, когда зафиксирована наименьшая цена закрытия за 13 дней, такая, что она ниже
всех цен закрытия за предшествующие 13 дней. И, наконец, третья волна начинается, когда реализуется 34-дневный максимум –
максимальная цена, превышающая максимальные цены за предшествующие 34 дня. Третья волна считается завершенной, когда
регистрируется 21-дневный ценовой минимум, такой, что он ниже всех минимальных цен за предшествующий 21 день.
Практически наиболее эффективным и ценным подходом к
анализу графиков является разработка механических систем, способных генерировать сигналы к покупке и продаже.
Было выявлено, что лучшим большим периодом простой
скользящей средней в индикаторе MACD является период равный
длине волны (которая для каждого цикла на графике индивидуальна). В результате этого было принято решение о написании
80
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
программы (торговой системы), которая автоматически выдаёт
сигналы о продаже или покупке акций. Данная программа проводит настройки коэффициентов индикатора MACD по первой волне. По результатам настроек программа выбирает один из наиболее подходящих индикаторов MACD, строит его и выдает нам
сигналы о покупке или продаже акций.
Для анализа тенденций цен на фондовом рынке можно использовать не только собственные программы, но и современные
программы технического анализа.
Например, можно передавать информацию о динамике торгов в современные программы технического анализа, такие как
MetaStock Professional 7.0, в режиме реального времени.
Данную программу можно не только использовать для анализа тенденций цен на фондовом рынке, но и программировать в
ней, создавая собственные индикаторы и модифицируя уже существующие.
 Литература
1. Акелис С. Технический анализ от А до Я (электронный вариант)
2. Демарк Т. Технический анализ – Новая наука (электронный вариант)
3. Рубцов Б.Б. Мировые рынки ценных бумаг. М.: Экзамен, 2002.
448 с.
4. Перекрестова Л.В., Романенко Н.М., Сазонов С.П. Финансы и кредит: Учеб. пособие для студ. проф. учеб. заведений. 2-е изд., стер. М.: Академия, 2004. 288 с.
5. http://www.finam.ru.
А.С. Лишатова
81
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
О телефонном центре,
центроиде и псевдоцентроиде
вершинно-взвешенного связного графа
З.В. Наханов, Г.М. Бродский
Настоящая заметка является непосредственным продолжением работы [2] и, если не оговаривается противное, использует
терминологию, обозначения и соглашения последней.
Под вершинно-взвешенным (реберно-взвешенным) графом
будем понимать пару (G , p ) (соответственно (G , q ) ), где G –
граф, а p : V(G ) → R (соответственно q : E(G ) → R ) – функция,
называемая вершинным (реберным) взвешиванием; в отличие от
[2] всегда будет предполагаться, что р принимает только положительные целые значения, а q – только неотрицательные целые.
Модифицируем некоторые определения из [2] применительно к рассматриваемым здесь объектам. Предполагая, что
Е (G ) ≠ ∅ , реберное взвешивание q : E(G) → R назовем согласованным с вершинным взвешиванием p : V(G ) → R , если q (E (G, u )) ≤ p(u )
для всех u ∈ V(G) . Множество всех реберных взвешиваний графа
(G , p ) , согласованных с p , обозначим через S (G , p ) . Реберное
взвешивание q'∈ S(G, p) назовем наибольшим, если q' (G ) ≥ q(G ) для
всех q ∈ S(G, p) . Число q' (G ) , не зависящее от выбора наибольшего
реберного взвешивания q'∈ S(G, p) , обозначим через G, p . Число
Gv , p назовем коммутаторным числом вершины v вершинновзвешенного связного графа (G, p) и обозначим через sb (v) . В случае μ (v) ≤ 1 полагаем sb(v) = 0 . Подграф Teℓ (G, p) графа (G, p) , порожденный множеством всех вершин v ∈ V(G) , для которых sb (v)
максимально, назовем телефонным центром вершинновзвешенного связного графа (G, p) . Это понятие является обобще82
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
нием телефонного центра дерева [8], растения [1] и связного графа [4]. Связанная с ним оптимизационная задача допускает прикладные интерпретации.
Условимся через [а] обозначать целую часть числа a ∈ R .
Теорема 1. Если (G , p ) – вершинно-взвешенный связный граф
и v ∈ V(G ) , то
  p(G ) − p(v) 

sb (v) =min  
,
p
(
G
)
−
p
(
v
)
−
m
(
v
)
,

2



где m(v ) – вес минитяжелой миниветви вершины v.
В доказательстве теоремы 1 ключевую роль играет
Лемма. Пусть (G, p) – вершинно-взвешенный полный граф
мощности G = n ≥ 2 и V (G ) = {v1 ,..., vn } , причем p1 ≥ p 2 ≥ ... ≥ p n , где
pi = p (vi ) (1 ≤ i ≤ n ) . Тогда
  p (G ) 

G , p =min  
, p (G ) − p1  .

 2 

Теорема 2. Если (G, p) – вершинно-взвешенный связный граф,
то его телефонный центр Teℓ (G, p) является подграфом псевдоцентроида P (G, p) .
Следствие 1 (Г.М. Бродский, М.Г. Хоменко [4]). Если G –
связный граф, то
1) его телефонный центр Teℓ (G, p) совпадает с центроидом
Z (G ) ;
2) V(Teℓ (G ) ) =

 G − 1 
v ∈ V (G ) sb(v ) = 
 .

 2  
Следствие 2. В любом вершинно-взвешенном связном графе
(G , p )
существует блок, содержащий телефонный центр
Teℓ (G, p) , обменный центр Т (G, p) , центроид Z (G, p) , коцентроид
Z* (G, p) , антицентроид Z~ (G, p) , псевдоцентроид P (G, p) и копсевдоцентроид P* (G, p) .
З.В. Наханов, Г.М. Бродский
83
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Следствие 2 является аналогом ряда давно известных результатов. Например, центр связного графа лежит в блоке [6]. Аналогичные утверждения верны для медианы [3] и s-центра [7].
Известно, что для любого графа G существует связный граф
Н, центр которого изоморфен G [5]. Таким же свойством обладает медиана [9]. Однако для телефонного центра, т.е. центроида,
аналогичное утверждение оказывается неверным. А именно, для
графа G существует связный граф H, телефонный центр которого
изоморфен G тогда и только тогда, когда G – блок. Тем не менее
справедлива
Теорема 3. Для любого графа G существует вершинновзвешенный связный граф ( H , p ) , телефонный центр которого
изоморфен G и является подграфом, порожденным множеством
всех вершин веса 1.
Формулировки и доказательства результатов заметки аналогичны формулировкам и доказательствам соответствующих
свойств обменного центра вершинно-взвешенного связного графа
[2].
 Литература
1. Борисова Л.Н. О телефонном центре и центроиде растения // Вопр.
теории групп и гомол. алгебры. Ярославль: ЯрГУ, 1985. С. 152–153.
2. Бродский Г.М. Об обменном центре, центроиде и псевдоцентроиде
графа // Актуальные проблемы математики и информатики: Сб. статей к
20-летию факультета ИВТ. Ярославль: ЯрГУ, 2007. С. 20–25.
3. Бродский Г.М., Китаева О.Р. О центроиде графа // Вопр. теории
групп и гомол. алгберы. Ярославль: ЯрГУ, 1991. С. 99–103.
4. Бродский Г.М., Хоменко М.Г. О телефонном центре и центроиде
связного графа // VII Всесоюз. конф. «Проблемы теоретической кибернетики». Тез. докл. Ч. 1. Иркутск, 1985. С. 33–34.
5. Копылов Г.Н., Тимофеев Е.А. О центрах и радиусах графов // Успехи мат. наук. 1977. Т. 32, № 6. С. 226.
6. Harary F., Norman R.Z. Dissimilarity characteristic theorems for graphs
// Proc. Amer. Math. Soc. 1960. V. 11. P. 332–334.
7. Melter R.A. Tomescu I. Remarks on distances in graphs // An. sti. Univ.
Iasi. Sec. 1a. 1981. V.27, № 2. P. 407–410.
84
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
8. Mitchell S.L. Another characterization of the centroid of a tree // Discrete Math. 1978. V. 24, № 3. P. 277–280.
9. Slater P.J. Medians of arbitrary graphs // J. Graph Theory. 1980. V. 4,
№ 4. P. 389–392.
Ограничения на целевые функции
для эффективного решения задачи
целочисленного программирования
на многограннике, ассоциированном
с задачей 3-выполнимость
А.В. Николаев
Одно из важных направлений исследования комбинаторных
задач состоит в изучении ассоциированных с задачами выпуклых
многогранников (см., например [1, 2]). В работе [3] определяется
релаксационный многогранник Pn,m ⊆ R 6 mn задачи 3-ВЫПОЛНИМОСТЬ, линейные ограничения для которого имеют вид:
(1)
 xik, ,jl = 1
k ,l
3,1
i, j
xi1,,1j + xi2, ,j1 + x
= xi1,,t1 + xi2,t,1 + xi3,,t1
xik, ,j1 + xik, ,j2 = xsk,,1j + xsk,,j2
xik, ,jl ≥ 0
(2)
(3)
(4)
где k=1,2,3 l=1,2 i,s=1,2…m j,t=1,2…n
Нетрудно заметить, что корневой полуметрический многогранник [2, 3, 5] изоморфен грани многогранника Pn,m .
1. Известно [3, 4], что координаты нецелых вершин корневого
полуметрического многогранника принимают значения только из
множества {0, 12 ,1} . В работах [7, 8], показывалось, что данное
свойство не сохраняется для многогранника Pn , m . А именно, была
А.В. Николаев
85
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
сформулирована теорема об экспоненциальном росте максимального знаменателя координат вершин с увеличением размерности
пространства. Следствием теоремы является сложность описания
множества нецелочисленных вершин многогранника Pn ,m . Частичным решением проблемы может служить сформулированный ниже характерный признак элементов этого множества.
Теорема 1. Необходимое условие нецелочисленности.
Вершина многогранника Pn,m является нецелочисленной тогда
и только тогда, когда:
∃1 ≤ j ≤ n, 1 ≤ l ≤ n, 1 ≤ i ≤ m, 1 ≤ k ≤ m (i ≠ k , j ≠ l ),
∃a, b, c, d ∈ {1, 2,3} (a ≠ b, c ≠ d ) :
xia,1j > 0, xib, 2j > 0, xia, 2j + xib,1j = 0, xka,1j + xkb,2j = 0,
xic,1l > 0, xid,l2 > 0, xic,l2 + xid,l1 = 0, xkc,2l + xkd,1l = 0.
2. Важнейшей составной частью линейного программирования является задача целочисленного программирования, т.е. нахождение решения в целых числах. От общей задачи она отличается прежде всего своей труднорешаемостью. В то время как для
линейного программирования были найдены эффективные (полиномиальные) алгоритмы [9], задача целочисленной оптимизации не просто была охарактеризована как NP-полная, но и включена Карпом в список 21 основных NP-полных задач. Тем не менее для специфических целевых функций эту задачу можно
решить с помощью стандартных алгоритмов линейного программирования.
Теорема 2. Если целевая функция имеет вид:
I = {1,..., m} = I1 ∪ I 2 и I1 ∩ I 2 = ∅,
∀1 ≤ j ≤ n ∀1 ≤ t ≤ 2 ∃at , j , bt , j , ct , j ∈ {−1,1} ∀i ∈ I t :
at , j ( xi11, j + xi22, j ) ≥ at , j ( xi12, j + xi21, j ),
bt , j ( xi11, j + xi32, j ) ≥ bt , j ( xi12, j + xi31, j ),
ct , j ( xi21, j + xi32, j ) ≥ ct , j ( xi22, j + xi31, j ),
a3−t , j = − at , j , b3−t , j = −bt , j , c3−t , j = −ct , j ,
86
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
то на многограннике Pn ,m она принимает свой максимум в целой
вершине.
Теорема 2 открывает новые возможности в построении эффективных алгоритмов для задач комбинаторной оптимизации.
Если для некоторой задачи X ее геометрической интерпретацией
окажется задача целочисленного программирования на многограннике Pn ,m и при этом целевая функция будет иметь описанный выше специфический вид, то для решения задачи X достаточно будет воспользоваться детально разработанными алгоритмами линейного программирования, высокая эффективность
которых хорошо известна.
 Литература
1. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, 1981.
2. Бондаренко В.А. Полиэдральные графы и сложность в комбинаторной оптимизации. Ярославль: ЯрГУ, 1995.
3. Бондаренко В.А., Урываев Б.В. Об одной задаче целочисленной оптимизации // Автоматика и телемеханика, 2007 № 6.
4. Бондаренко В.А. Об одном комбинаторном многограннике // Моделирование и анализ вычислительных систем: Сб. науч. тр. Ярославль:
ЯрГУ, 1987. С. 133–134.
5. Padberg M.V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. 1989. V. 45. P. 139–172.
6. Деза М.М., Лоран М. Геометрия разрезов и метрик / Пер. с англ.
Е. Пантелеевой и П. Сергеева / Под ред. В. Гришухина. М.: МЦНМО, 2001.
7. Дунаева О.А., Николаев А.В. Некоторые свойства релаксационного
многогранника задачи 3-выполнимость // Студенческие заметки по информатике и математике. Ярославль: ЯрГУ, 2007. С. 7-9.
8. Дунаева О.А., Николаев А.В. Некоторые свойства релаксационного
многогранника задачи 3-выполнимость // VIII Всероссийская конференция
молодых ученых по математическому моделированию и информационным
технологиям. Программа и тезисы докладов. Новосибирск, 2007. С. 19-20.
9. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании // ЖВМ и МФ. 1980. Т. 20, № 1. С. 51-69.
А.В. Николаев
87
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Язык математических формул DIM-FL
Динамической Информационной Модели
Д.С. Писаренко
Динамическая информационная модель DIM [1] – система,
позволяющая описывать любые дискретные объекты и детерминированные процессы, происходящие с этими объектами. Она
является новой технологией СУБД, которая имеет гибкий и
удобный механизм, учитывающий динамику свойств объектов
предметной области, позволяет структурировать данные и методы их обработки, динамически изменять тип и методы обработки
данных, сохраняя при этом их «историю». Динамика свойств
объектов предметной области и методы обработки данных описываются с помощью взаимодействий [2] системы DIM. Каждое
взаимодействие системы DIM может содержать 4 основные составляющие:
• Откуда – объекты, явлющиеся источником взаимодействия;
• Куда – объекты, являющиеся направлением взаимодействия;
• Что – объекты взаимодействия;
• Как – сценарий взаимодействия.
Одной из процедур, определяемых сценарием взаимодействия, может быть проведение расчетов различных физикомеханических, физико-химических, а также многих других показателей и параметров, описанных в стандартах точным языком
(например, ГОСТы). Многочисленные специальные методики
непостоянны: одни меняются, другим, устаревшим, на смену
приходят новые. Реализация обновления или замены методик
требует наличия большого штата специальных сотрудников для
их описания и сопровождения в любой информационной системе.
Эта проблема может быть решена, если обычный пользователь
системы DIM сможет самостоятельно описывать методику расчета в системе.
88
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Нашей целью является создание такого языка, который позволил бы в простой и удобной для пользователя системы DIM
форме описывать различные методики расчетов и связанные с
ними математические вычисления и формулы. При этом язык
должен обеспечить возможность использования данных из системы DIM при проведении этих самых расчетов и сохранение результатов вычислений в системе. Также нашей целью является
разработка программного обеспечения, позволяющего создавать,
модифицировать и хранить файлы расчетов, описанных на этом
языке, производить такие расчеты, определяя в интерактивном
режиме данные из системы DIM для расчетов и для сохранения
результатов.
Все расчеты состоят из математических формул, поэтому
язык математических формул динамической информационной
модели назовем DIM-FL (DIM Formula Language).
Необходимо сразу оговориться, что для описания алгоритма
расчетов на языке DIM-FL, пользователю будут предоставляться
две возможности:
• непосредственное описание алгоритма на языке DIM-FL в
текстовом редакторе (быстрый способ, для более опытных пользователей системы),
• использование специального мастера, позволяющего в
форме диалога с пользователем составить описание алгоритма
расчетов на языке DIM-FL (менее быстрый способ для начинающих пользователей системы);
Язык DIM-FL должен позволять делать описания алгоритмов
расчетов наиболее близкими к самим методикам, но его синтаксис не должен иметь большого количества редко используемых
операторов. После проведения анализа нескольких различных
методик расчетов [3, 4, 5], определенных гостами и другими
стандартами, были сформулированы требования к языку DIM-FL.
Язык DIM-FL должен позволять:
1) выполнять простейшие математические операции и другие
несложные численные вычисления;
2) манипулировать не только единичными значениями, но и
наборами таких числовых значений, иметь несложные конструкции для оперирования такими наборами;
Д.С. Писаренко
89
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3) на определенном шаге делать ветвление вычислений в зависимости от результатов выполнения предыдущих шагов;
4) использовать в расчетах данные системы DIM и вносить
изменения в данные системы DIM на основе проведенных вычислений.
По аналогии с языками программирования язык DIM-FL будет использовать переменные и массивы. В названиях переменных и массивов языка DIM-FL могут использоваться символы
русского и латинского алфавитов, арабские цифры, а также символ «_» (нижнее подчеркивание). Причем нижний и верхний регистр различаются. Названия переменных и массивов не могут
начинаться с цифры и должны быть уникальными. Для повышения удобочитаемости описания расчетов и ускорения понимания
их алгоритма рекомендуется давать переменным имена, соответствующие обозначениям в методиках или соспоставляемым данным из системы DIM.
Переменные и элементы массивов могут иметь только числовые значения, которые находятся в диапазоне значений констант
MinFloat и MaxFloat c точностью до FloatPrecision десятичных
знаков. Константы MinFloat, MaxFloat и FloatPrecision являются
скрытыми и предопределенными реализацией языка DIM-FL.
Язык DIM-FL будет иметь три типа переменных и массивов:
1) переменные и массивы, значения которых берутся из системы DIM или в ней сохраняются;
2) переменные и массивы, значения которых вводятся пользователем перед выполнением расчетов;
3) переменные, которые принимают свои значения в ходе
выполнения расчетов.
Для удобства использования массивы первого и третьего типов в языке DIM-FL будут иметь динамический размер, т.е. длина
массива будет увеличиваться при каждом задании значения новому элементу массива.
Рассмотрим каждый из типов переменных подробнее.
Переменные и массивы первого типа, принимающие значения из системы DIM, будут получать свои значения из свойств
объектов класса взаимодействия [2] Откуда, определяемых на
90
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
этапе создания взаимодействия, и должны объявляться следующим образом:
<имя переменной> :: <название свойства>
<имя массива> “[]” :: <название свойства>
В случае переменной будет учитываться значение свойства
только первого объекта. Длина массива будет равна количеству
объектов класса взаимодействия Откуда.
Переменные и массивы первого типа, значения которых будут сохранены в системе DIM, свои значения будут сохранять в
свойствах объектов класса взаимодействия [2] Куда, определяемых на этапе создания взаимодействия, и должны объявляться
следующим образом:
<имя переменной> == <название свойства>
<имя массива> “[]” == <название свойства>
В случае переменной значение будет сохранено в параметре
объекта, соответствующего указанному свойству, только первого
объекта. Длина массива не обязана равняться количеству объектов класса взаимодействия Куда.
Переменные и массивы второго типа объявляются следующим образом:
<имя переменной> : <подсказка>
<имя массива> “[” <длина массива> “]” : <подсказка>
Значения таких переменных и массивов будут вводиться
пользователем перед выполнением расчетов. Для пояснения запрашиваемых у пользователя величин будет использоваться
<подсказка> – строка символов, поясняющая пользователю, ввод
каких данных необходим системе DIM для выполнения расчетов.
Для большей ясности пояснения рекомендуется в качестве <подсказки> использовать обозначение переменной из методики расчета.
Размерность массивов второго типа в ходе выполнения расчетов не изменяется.
Переменные третьего типа явным образом не объявляются,
свои значения они получают в ходе выполнения программы простым присвоением значения имени новой переменной:
<имя новой переменной> = <значение>
Д.С. Писаренко
91
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Все переменные и массивы могут объявляться в любом месте
описания алгоритма, но обязательно перед их использованием.
Математическая формула представляет собой выражение со
следующим синтаксисом:
<переменная> = <математическое выражение>
В качестве <переменной> в математической формуле может
использоваться и элемент массива. Конструкция <математическое выражение> может включать переменные, элементы массивов, функции (при выполнении которых возвращаются числовые
значения) и знаки арифметических операций. Используются четыре основные арифметические операции: + (сложение), – (вычитание), / (деление) и * (умножение). В математических выражениях также могут участвовать круглые скобки, определяющие
приоритет арифметических операций.
Чтобы не возникало путаницы в математических формулах
при описании алгоритма расчетов, они (математические формулы) должны отделяться друг от друга знаком “,”(запятая). Рекомендуется каждую математическую формулу писать с новой
строки.
В язык DIM-FL вводятся алгебраические, тригонометрические и логарифмические функции.
Набор арифметических функций, который при необходимости может быть дополнен, первоначально включает следующие
функции:
• abs – возвращает абсолютное значение параметра;
• div – возвращает целую часть результата деления первого
параметра на второй параметр;
• mod – возвращает остаток от деления своего параметра на
второй параметр;
• sqrt – возвращает квадратный корень параметра;
• pow – возводит первый параметр в степень, указанную вторым параметром;
• min – возвращает минимальный из параметров;
• max – возвращает максимальный из параметров.
Тригонометрические функции sin, cos, tg, ctg, asin, acos, atg,
actg имеют по одному параметру и возвращают синус, косинус,
тангенс, котангенс, арксинус, арккосинус, арктангенс и арккотан92
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
генс своих параметров соответственно. При вычислении функций
sin, cos, tg, ctg их параметры указывают значения в радианах, и
результатом вычисления asin, acos, atg, actg будут градусные меры угла в радианах.
Набор логарифмических функций состоит из следующих
функции:
• exp – возвращает значение равное экспоненте параметра;
• ln – возвращает натуральный логарифм параметра;
• lg – возвращает десятичный логарифм параметра;
• log – возвращает логарифм первого параметра по основанию, указанному вторым параметром.
Для удобства использования массивов в язык DIM-FL введены следующие функции:
• length – возвращает количество элементов массива, переданного параметром;
• avg – возвращает среднее арифметическое всех элементов
массива, переданного параметром;
• std – возвращает среднее квадратичное всех элементов массива, переданного параметром;
• armin – возвращает минимальный элемент массива, переданного параметром;
• armax – возвращает максимальный элемент массива, переданного параметром.
Возможно, при дальнейшем использовании языка DIM-FL
возникнет потребность в новых вычислительных возможностях.
Тогда язык DIM-FL будет дополнен недостающими функциями.
Для выполнения одинаковых операций над всеми элементами
массива язык DIM-FL будет иметь оператор цикла for, синтаксис
которого таков:
for (<массив> [, <массив> …] ) [not more <количество итераций>]
<математическая формула>[,<математическая формула >…];
Если указаны необязательные ключевые слова not more и параметр <количество итераций> и он меньше минимальной размерности указанных массивов, то количество выполнений математических формул цикла for равно этому параметру. В противД.С. Писаренко
93
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ном случае количество выполнений математических формул цикла for равно минимальной размерности указанных массивов. В
каждой i-ой итерации цикла for будут использоваться i-ые элементы каждого из указанных массивов. В математических формулах внутри цикла for допустимо использовать имя любого из
указанных <массивов> как обычной переменной. Для каждой iтой итерации использованное имя <массива> будет равнозначно
использованию обозначения i-того элемента <массива>.
Иногда при проведении вычислений, основываясь на какихто условиях, мы выбираем алгоритм дальнейших расчетов, например, если некоторые полученные значения достаточно малы,
то нужно использовать более точные алгоритмы вычислений. Для
таких случаев в язык DIM-FL вводится условный оператор if, который имеет следующий синтаксис:
if (<выражение сравнения>)
<математическая формула> [,<математическая формула> …];
<выражение сравнения> ::= <величина> <знак сравнения>
<величина>
<величина> ::= <переменная> | <элемент массива> | <числовое значение>
<знак сравнения> ::= { = | < | > | <> | <= | >= }
<математические формулы> условного оператора if выполняются в том и только том случае, если <знак сравнения> в <выражении сравнения> соответствует соотношению <величин>,
участвующих в <выражении сравнения>.
Язык DIM-FL будет позволять в описании алгоритма расчетов использовать поясняющие комментарии. Комментарий будет
начинаться с символов “//”. Все, что будет написано после этих
символов до конца строки, будет считаться комментарием.
Рассмотрим пример одного из многочисленных ГОСТов. Это
ГОСТ [3], описывающий методы расчета предельно допустимых
шумовых характеристик стационарных машин.
6.1. Приведенный уровень ударного шума под перекрытием
без покрытия LПО в дБ следует определять как среднее арифметическое значение результатов трех измерений.
94
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6.2. Приведенный уровень ударного шума под перекрытием с
рулонным или плиточным покрытием в третьоктавных полосах
частот LП в дБ следует определять по формуле
S
LП = LП +
tα (n) ,
n
где:
среднее арифметическое значение
– приведенного уровня ударного шума
под перекрытием с покрытием, полученное по результатам испытаний трех образцов, измеренных три
раза;
– приведенный уровень ударного шума
под перекрытием с покрытием, полученный при испытании одного образца, измеренного один раз;
среднее квадратичное отклонение
– результатов измерений приведенного уровня ударного шума под перекрытием с рулонным или плиточным
покрытием;
– критерий Стьюдента при доверительной вероятности α=0,8;
– количество результатов измерений
(три образца, измеренных три раза).
Вот как будут выглядеть расчеты на основе приведенного ранее примера ГОСТа на языкe DIM-FL:
// объявим массивы и свяжем их с нужными свойствами из
базы данных
L[n] := Уровень ударного шума,
LП[] : = Приведенный уровень ударного шума,
// определим константу, равную критерию Стьюдента
// при необходимой доверительной вероятности
Д.С. Писаренко
95
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
t = 1.4,
Lп = avg(L),
nL = L,
for (nL)
nL = pow(nL – Ln, 2);
S = sqrt( sum(nL) / (n – 1) ),
LП = Ln + (S/ sqrt(n)) * t;
Автор приносит благодарность своему руководителю В.С.
Рублеву за помощь и постоянное внимание.
 Литература
1. Рублев В.С. Юсупов А.Р. Концепции объектной динамической информационной модели DIM // Математика в Ярославском университете:
Сборник обзорных статей к 30-летию математического факультета. Ярославль: ЯрГУ, 2006. С. 335–354
2. Писаренко Д.С. Рублев В.С. Концепция взаимодействия Динамической информационной модели DIM // Актуальные проблемы математики и
информатики: Сборник статей к 20-летию факультета ИВТ. Ярославль:
ЯрГУ, 2007. С. 75–80
3. ГОСТ 30530-97 Методы расчета предельно допустимых шумовых
характеристик стационарных машин (rgost.ru).
4. ГОСТ 12.1.016-79* Воздух рабочей зоны. Требования к методикам
измерения концентраций вредных веществ.
5. Постановление правительства Московской области о методике расчета стандартов предельной стоимости жилищно-коммунальных услуг,
применяемых при составлении прогноза консолидированного бюджета
Московской области на соответствующий финансовый год в системе жилищно-коммунального хозяйства.
96
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Относительные параперманенты
с приложениями к умножению матриц
и решению рекуррентных уравнений
М.О. Семенов, Г.М. Бродский
В работах [1, 2] Р.А. Заторский рассмотрел некоторые функции, заданные на множестве вещественных треугольных матриц,
являющиеся аналогами классических функций определителя и
перманента и названные параопределителем и параперманентом.
Здесь дается определение параперманента n × n -матрицы над
кольцом R относительно произвольной функции, заданной на
множестве квадратных матриц над R и принимающей значения в
R . Частными случаями оказываются параперманенты и некоторые их модификации из [1, 2]. Цель настоящей заметки – исследование двух других частных случаев: f1 -параперманента и
f 2 -параперманента, включающее построение алгоритмов их вычисления и указанные в заглавии приложения.
Всюду ниже R – ассоциативное кольцо с единицей и m, n, k –
натуральные числа. Обозначения: R m×n – множество m × n матриц над R ; M – число элементов конечного множества M ;
n = { 1, 2,..., n } ; P ( n ) – множество упорядоченных разбиений числа
n, т.е. строк ( α1 ,..., α r ) , где r , α1 , ..., α r ∈ n и α1 + ... + α r = n;
r ( α ) и α1 ,..., α r ( α ) – длина и компоненты строки α ∈ P ( n ) . С лю-
быми матрицей A ∈ R n×n и разбиением α ∈ P ( n ) свяжем строку
(A
α1
)
,..., Aα r ( α ) , где Aαt ( t ∈ r ( α ) ) – подматрица матрицы A, рас-
положенная в пересечении строк и столбцов с номерами
β + 1, β + 2,..., β + αt , где β = α1 + ... + α t −1 .
Пусть задана функция
М.О. Семенов, Г.М. Бродский
97
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
f:
∞
 R s× s → R .
s =1
Назовем параперманентом (порядка n) относительно f (или,
короче, f-параперманентом) функцию
f - pper : R n×n → R ,
определяемую условием
f - pper ( A) =  f ( Aα 1 ) f ( Aα 2 )... f (Aαr (α ) ) .
α ∈P ( n )
В отличие от перманента n × n -матрицы, определяемого как
сумма n! слагаемых, f-параперманент оказывается суммой
P ( n ) = 2 n −1 слагаемых. Используя идеи из [1, 2], можно было
бы дать и определение f-параопределителя. Не развивая теорию
f-параперманентов относительно произвольной функции f, перейдем к изучению двух важных частных случаев, когда в качестве f
берется одна из функций f1 и f 2 , где
f1 (B ) = b1s ;
s× s
для всех B = ( bij ) ∈ R .
b1s , если s = 1,
f 2 (B ) = 
b1s bs1 , если s > 1
n×n
Матрицу A = ( aij ) ∈ R
назовем нижнетреугольно расслаи-
ваемой, если для любых соседних элементов ai , j −1 и aij некоторой
строки, лежащих ниже главной диагонали (т.е. 3 ≤ i ≤ n и
2 ≤ j ≤ i − 1 ), ai , j −1 = u i , j −1 aij для некоторого u i , j −1 ∈ R .
Теорема 1. Пусть A = ( aij ) ∈ R n×n – нижнетреугольно расслаиваемая матрица, и элементы ui , j −1 ∈ R таковы, что
a i , j −1 = u i , j −1 a ij , где 3 ≤ i ≤ n и 2 ≤ j ≤ i − 1 . Положим u j +1, j = a j +1, j для
всех j ∈ n − 1 . Тогда
где
и для i ∈ n \ {1}
98
f 2 - pper ( A) = A(1) A(2 ) ... A(n ) ,
A(1) = ( a11 , a12 , ... , a1n ) ∈ R1×n
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 aii ai ,i +1  ain 


u
0


i
,
i
−
1




ui +1,i −1
( n −i + 2 )×( n −i +1)
A( i ) = 
∈ R


.





u
0


n ,i −1 

n×n
Следствие. Для произвольной матрицы A = ( aij ) ∈ R
f1 - pper ( A) = A(′1) A(′2 ) ... A(′n ) ,
где
и для i ∈ n \ {1}
A(′1) = ( a11 , a12 , ... , a1n ) ∈ R1×n
 aii ai ,i +1

1 
A(′i ) = 
1


0 

 ain 

 0 
 ∈ R( n −i + 2 )×( n −i +1)
.



 1 
Теорема 1 и следствие являются аналогами теоремы Юрката–
Райзера о разложении перманента в произведение матриц [3, с.
112, теорема 1.1]. Отметим, что в упомянутом разложении перманента участвуют матрицы существенно больших размеров
n  n

 ×   , где i ∈ n .
i
−
1

 i 
Рассмотрим задачу о вычислении произведения Φ k Φ k −1 Φ1
верхних хессенберговых матриц следующего специального вида:
 a1(i ) a 2(i )  a n(i−)1 a n(i ) 

 (i )
0  0
0 
 u1
n×n
Φ i =  0 u 2(i )  0
0  ∈ R

 
  
 


0  u n(i−)1 0 
 0
М.О. Семенов, Г.М. Бродский
99
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
для всех i ∈ k . Положив a m(i ) = u m(i −) 1 = 0 для всех i ∈ k и m > n , для
каждого l ∈ n рассмотрим нижнетреугольно расслаиваемую матk ,l
k ×k
рицу An = ( α ij ) ∈ R с элементами
a (jk−−i +i +11) , если i, j ∈ k − 1 и i ≤ j ,

ui(−k −j j )ui(−k −j −j1−1) ... u1( k −i +1) , если i, j ∈ k − 1 и i > j ,

α ij = 
k −i +1
ak( −i +l ) , если i ∈ k и j = k ,
 ( k − j ) ( k − j −1)
(1)
uk − j +l −1uk − j +l − 2 ... ul , если i = k и j ∈ k − 1
k ,l
и ее f 2 -параперманент p n .
Теорема 2. Первая строка матрицы Φ k Φ k −1 Φ1 имеет вид
( pnk ,1, pnk ,2 , ... , pnk ,n ) . Если k ≥ n , то
0
1



(k )
 u1



k
k −1
Φ k Φ k −1  Φ1 = 
u2( )u1( )






( k ) ( k −1)
( k −n+ 2) 
0
...
u
u
u
1
n −1 n − 2


 pnk ,1
pnk ,2  pnk ,n 
 k −1,1

pnk −1,2  pnk −1,n 
 pn
 k − 2,1

pnk − 2,2
pnk − 2,n  .
 pn
 

 
 k − n +1,1 k − n +1,2

k − n +1,n 
p

p
p
n
n
 n

Отметим, что формула для Φ k Φ k −1 Φ1 при k < n получается
несложной модификацией формулы для случая k ≥ n .
(k + n )
Теорема 3. Пусть заданы числа m,n и элементы a i , bi ∈ R
( k ∈ m; i ∈ n ). Положим ai(i ) = bi для всех i ∈ n , a (ji ) = 0 для всех
i, j ∈ n таких, что i > j , и a (ji ) = 0 для всех i ∈ n + m \ n и j ∈ i \ n . То-
гда последовательность
(i )
 a1

 0
xi = f1 - pper

 0

f1 -параперманентов
(i )
a2
a1(i −1)

0
ai(i ) 

 ai(−i −11) 
  
 a1(1) 

( 1≤ i ≤ m + n )
является решением линейного рекуррентного уравнения n-го порядка.
100
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
x k + n = a1(k + n ) x k + n −1 + ... + a n(k + n ) x k
с начальными условиями xi = bi
( i∈n ).
( k ∈m )
Теоремы 2.1 и 2.2 из [2], дающие решение линейного рекуррентного уравнения с помощью параперманентов, справедливы
лишь для уравнений с ненулевыми постоянными коэффициентами, принадлежащими некоторому полю.
 Литература
1. Заторський Р.А. Паравизначники та параперманенти трикутних матриць // Матем. студii. 2002. Т. 17, № 1. С. 45–54.
2. Заторский Р.А. Определители треугольных матриц и траектории на
диаграммах Ферре // Мат. заметки. 2002. Т. 72, № 6. С. 834–852.
3. Минк Х. Перманенты. М.: Мир, 1982. 216 с.
Поиск дубликатов в результатах выдачи
поисковых машин
Ю.А. Спиридонов
Вопрос о том, насколько уникален документ, особенно острым стал с появлением Интернета, где информация общедоступна и никто не препятствует ее копированию и распространению
на других серверах. В Интернете дубликатов огромное количество, по некоторым источникам до 30% от общего объема информации, что непосредственно влияет на качество результатов, выдаваемых поисковыми машинами. Обычно копирование происходит с нарушением авторских прав и частичным изменением,
осознанным или нет, чтобы внести правки, которые с точки зрения копирующих необходимы или для специального затруднения
обнаружения дублирования материалов. Кроме прямого копирования, один и тот же документ на одном или разных серверах
может отличаться по техническим характеристикам, например,
Ю.А. Спиридонов
101
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
быть представлен в разных кодировках и форматах; может содержать переменные вставки – оформление, рекламу, ссылки.
Наиболее активно копируются и редактируются ленты новостных агентств, документация и юридические документы, прейскуранты магазинов, ответы на часто задаваемые вопросы. Среди
таких документов популярны изменения: корректура, реорганизация, ревизия, реферирование, раскрытие темы.
Дубликат документа – это точная копия одного или нескольких других документов. Нечеткий текстовый дубликат (НТД) документа – это частично измененный документ в содержательной
части и/или в части форматирования с использованием одного
или нескольких документов. С математической точки зрения
НТД определяются на основе отношения сходства на парах документов. Два документа сходны, если некоторая числовая мера
их сходства превышает некоторый порог.
Все случаи дублирования нужно выявлять и соответственно
применять различные санкции. Например, если дело касается поисковых систем или новостных лент, то не выводить дубликаты в
поиске.
В магистерской диссертации «Технология поиска и удаления
текстовых дубликатов по результатам работы поисковых машин
Яндекс и Google», написанной автором статьи, было предложено
удалять дубликаты из результатов выдачи поисковых систем Яндекс и Google. Основным препятствием для успешного решения
задачи поиска дубликатов в Интернет и в результатах работы поисковых систем является гигантский объем данных в Интернет и
в базах современных поисковых машин. Такой объем делает
практически невозможным (в разумное время) «прямое» решение
задачи путем попарного сравнения текстов документов. Поэтому
в последнее время большое внимание уделяется разработке методов снижения вычислительной сложности создаваемых алгоритмов за счет выбора различных данных. Например, хеширования
определенного фиксированного набора «значимых» слов/предложений документа, также имеет место обход только части документов, выделенных при условии наличия общих ссылок между
документами.
102
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В работе автором предложено удалять дубликаты документов
при поиске в поисковых системах не только на этапе индексирования страниц, как это делается в современных машинах, но и на
этапе обработки запроса пользователя, что является довольно
перспективным решением. Так как в настоящий момент ни одна
поисковая система не способна удалить все дубликаты из своей
БД документов на этапе индексирования веб-страниц из-за огромного их количества.
В диссертации рассмотрены алгоритмы поиска дубликатов,
отдельный акцент сделан на алгоритме шинглов. Предложена
модификация алгоритма, которая может быть использована при
устранении дубликатов из поисковой выдачи результатов. Модификация основана на использовании поискового запроса пользователя во время удаления дубликатов. Перед применением алгоритма шинглов предложено выделять окрестность в документе
вокруг ключевого слова. Окрестность Е указывает, что вокруг
ключевого слова с каждой стороны нужно взять Е слов. Во время
экспериментов наилучшие показатели по сравнению с экспертной оценкой показал параметр E = 5 . Данная модификация привела к уменьшению времени работы алгоритма шинглов более
чем в 2 раза за счет уменьшения количества обрабатываемых
данных, а также повысило качество определения дубликатов
примерно на 20%.
Предложены и подробно описаны механизмы по предварительной обработке документов, чтобы для любых страниц можно
было применять алгоритмы анализа текста, в том числе и поиск
дубликатов. Исследовались механизмы определения кодировки
(предложен механизм определения кодировки на основе трех методов: с помощью заголовка, который вернул сервер; с помощью
HTML заголовка; на основе анализа частоты встречаемых слов в
документе при помощи программы universalchardet) и преобразования документов в одинаковую кодировку, удаление HTML
разметки и стоп-слов, приведение слов в начальную форму.
В качестве примера предложенного подхода (удаление дубликатов из выдачи результатов поисковых систем на этапе выдачи и использование поискового запроса в качестве выделения содержательной части документа с точки зрения пользователя) авЮ.А. Спиридонов
103
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
тором реализован сервис «searchdublicates», который удаляет
дубликаты и объединяет дубликаты документов в кластеры. Данная программа показала хорошие результаты на экспериментах.
Тестирование программы проходило по таким ключевым словам,
как: «str_replace», «программы для работы с видео», «защита сети», «обзор nokia prism», «ассоциативный массив», «linux», «windows», «узлом сервера» и многим другим. Дополнительным плюсом реализованного сервиса «searchdublicates» является собираемая статистика по запросам, по веб-серверам, возвращаемым
сервером значениям, и по кодировкам страниц.
В случае реализации подхода в поисковых системах, описанного в данной работе, в виде поиска НТД в результатах выдачи
поисковых систем и их кластеризации на выделенных серверах
обеспечивает бесшовное внедрение функциональности поиска
нечетких текстовых дубликатов веб-документов без изменения
уже имеющихся алгоритмов поиска и структуры хранения и индексирования.
Сравнение алгоритма шинглов и модифицированного алгоритма шинглов произведено на основе стандартных метрик,
предлагаемых Российским семинаром по Оценке методов информационного поиска (использовались метрики: точность, полнота, F-мера). Хорошие результаты, показанные в экспериментах,
позволяют утверждать, что при реализации данного подхода в
поисковых системах качество выдачи результатов поисковыми
системами значительно увеличится.
Предложенные алгоритмы и методики внедрены в УЦИ ЯрГУ им. П.Г. Демидова в рамках гранта «Создание распределенной информационной системы поиска на основе тематикоориентированных методов в пиринговых сетях» № 05-07-90266-в
в качестве методов устранения дубликатов в наборе документов
на основе запроса пользователя и определения кодировки файла
и его последующего преобразования в единый вид. Реализованный в рамках магистерской диссертации онлайновый сервис
«searchdublicates» внедрен как отдельный проект в УЦИ ЯрГУ
им. П.Г. Демидова.
104
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 Литература
1. Manber U. Finding Similar Files in a Large File System. Winter USENIX Technical Conference, 1994.
2. Broder A.Z., Glassman S.C., Manasse M.S., Zweig G. Syntactic Clustering of the Web // Сервер лаборатории компании HP http://www.hpl.
hp.co.uk – 1 pdf-документ. – URL: http://www.hpl.hp.co.uk/techreports/ Compaq-DEC/SRC-TN-1997-015.pdf, 1997.
3. Сегалович И. Как работают поисковые системы // Сервер компании
Яндекс: http://company.yandex.ru – 1 веб-страница. – URL: http://company.
yandex.ru/ articles/ article10.html.
4. Ilyinsky S., Kuzmin M., Melkov A., Segalovich I. An efficient method
to detect duplicates of Web documents with the use of inverted index // Сервер
компании
Яндекс:
http://yandex.ru –
1
веб-страница.
URL:
http://company.yandex.ru/articles/article7.html.
5. Официальные метрики РОМИП 2006 // ТРУДЫ РОМИП’2006 СПб.:
НУ ЦСИ, 2006.
Разработка графического движка
реального времени
И.С. Спогреев
Все рассмотренные в данной статье тематики актуальны на
сегодняшний день и являются последними достижениями в индустрии разработки компьютерных игр. Изложенный материал основывается не только на большом количестве исследованного
материала, но и на моем опыте работы в качестве программиста
компьютерной графики. Я попытался на простой задаче отобразить все основные сложности в создании графического движка.
При этом мною были учтены специфичные особенности конкретной разработки, платформы и целевой аудитории.
На сегодняшний момент практически не существует материалов на русском языке по данной тематике. Большинство проблем и способов их решения изложены в различных книгах и документах на английском языке. Главным тематическим материалом является серия книг от компании NVIDIA “GPU Gems”,
И.С. Спогреев
105
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
изданная на сегодняшний день в четырех частях. В ней изложены
самые последние разработки в направлении программирования
компьютерной графики. Некоторые статьи из этих книг легли в
основу моей работы.
Моя работа имеет не только теоретический, но и практический вес. Так как в результате мной был создан графический
движок современного уровня. Этот движок в настоящее время
успешно используется компанией Sonar Games для создания игровых прототипов.
Работа над игрой и над графическим движком, в частности,
сложный процесс. Необходимо не просто понимать и разбираться
в предметной области, но и четко представлять для себя поставленные цели и возможности по их решению. В ходе работы над
игровым проектом, который требовал сложных технологических
решений, было ясно, что необходимо сделать работающий протопип по графике, чтобы оценить возможности в реализации и
будущие сложности.
Так как игра планировалась для выхода на персональных
компьютерах, то выбор был сделан в сторону Direct3D. Его я и
положил в основу графического движка.
В ходе работы над поставленной задачей мною был разработан графический движок, позволяющий получить картинку нужного качества и реализующий в себе все вышеперечисленные
технологии. Полученный движок способен отрисовывать сцены,
созданные в современных пакетах моделирования 3ds Max и
Maya, настраивать источники света и материалы.
Весь процесс отрисовки разделен на несколько этапов:
1. Первым делом сцена отрисовывается в камеры, отвечающие за карты теней.
2. Сцена рисуется в главную камеру.
3. Главная камера передается на обработку системе постэффектов.
4. Система постэффектов, используя данные из главной камеры, начинает обрабатывать изображение. Обработка также
разделена на этапы:
1) Расчет солнечного освещения.
2) Расчет освещения от источников света (deferred shading).
106
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3) Компоновка сцены.
4) Наложение дополнительных постэфектов.
5. Вывод обработанного изображения на экран.
Создание
карт теней
Рендер
сцены
в главную камеру
Расчет
солнечного
освещения
Освещения
от источников
света
Обработка
отрисованной
сцены
Компоновка
сцены
Вывод
изображения
на экран
Дополнительные
постэффекты
Схема рендеринга
Свет – это очень сложная система, чтобы смоделировать ее в
совершенстве. Именно поэтому мы редко можем видеть созданные компьютером трехмерные изображения, которые были бы
по-настоящему фотореалистичны. Во всех случаях чем сложнее и
реалистичнее создаваемая виртуальная сцена, тем больше вычислений мы должны произвести и тем медленнее она будет воспроизводиться на экран.
Для расчета освещения была реализована технология
Deferred Shading, которая позволяет обрабатывать большое количество источников света при малых затратах, но и накладывает
некоторые ограничения на рабочую систему. Можно выделить 4
основные стадии в deferred shading: фаза вывода геометрии, фаза
освещения, пост-обработка и финальная стадия формирования
изображения.
Имея все необходимые данные в сформированном буфере (Gбуфере), мы можем рассчитать освещения для каждого отдельного пикселя. Для этого нам необходимо нарисовать квадрат на
весь экран. При этом рассчитывается каждый соответствующий
пиксель экрана. Для этого вывода мы устанавливаем все текстуры из нашего G-буфера и передаем параметры источника света:
позиция, направление, цвет, коэффициент яркости и др. Необходимо помнить, что так как все данные в G-буфере подсчитаны в
И.С. Спогреев
107
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
пространстве камеры, то и данные источника света также необходимо передавать в пространстве камеры.
Для построения теней использовался алгоритм «каскадные
карты теней». Каскадные тени позволяют справиться с проблемой ступенчатых теней при нехватке разрешения путем создания
нескольких карт глубины: большой – для ближних объектов и
маленькой – для дальних. Мы разделяем дальность видимости
камеры на несколько частей и для каждой части строим собственную карту глубины.
CSM обычно используют для построения теней от солнца на
больших открытых пространствах. Полный расчет в одну карту
требует слишком большого разрешения. Однако можно строить
несколько карт глубины, большого разрешения для ближайших
объектов, меньшего – для более далеких. Такой подход вполне
оправдан, так как дальние объекты занимают на экране мало места и плохое качество тени незаметно.
При
финальном
проходе мы производим
все эти вычисления и
получаем картинку с освещенной сценой от
многих источников света.
В ходе работы мною
была разработана собственная реализация технологии Screen Space
Ambient
Occlusion,
предложенной компанией CryTek.
Наш метод затеняет только те участки, на которые действительно влияют другие поверхности. При этом он по-прежнему
работает как постэффект и применим для любой сцены.
По результатам проделанной работы был создан графический
движок реального времени. Была выполнена большая работа, исследовано множество различных технологий и проведены раз108
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
личные исследования. Поставленная задача по воссозданию художественной картинки полностью выполнена.
 Литература
1. Онлайн версия первой части книги «GPU Gems» http://http. developer.nvidia.com/GPUGems/gpugems_pref02.html
2. Русскоязычный
сайт,
посвященный
разработке
игр
http://gamedev.ru/
3. Англоязычный сайт, посвященный разработке игр http://gamedev.ru/
Создание трехмерного низкополигонального
уровня для игры
М.А. Спогреева
На сегодняшний день работа по созданию трехмерных моделей очень высоко ценится на рынке компьютерной индустрии.
Востребованы специалисты в данной области, а программные
продукты с компьютерными играми заполонили все прилавки магазинов, специализирующихся в этой области. Индустрия компьютерных игр сегодня широко развивается, и отечественные
компании все в большем количестве выходят на зарубежный, в
особенности европейский, рынок.
Для создания полноценной качественной компьютерной игры
необходимо правильно продумать ее концепцию, изучить спрос и
ажиотаж на рынке, создать достойный функционал, чем занимаются программисты, ну и конечно, красивую картинку, захватывающий игровой мир, который понравился бы даже самому придирчивому игроку. Для того чтобы создать этот игровой мир
нужны такие специалисты, как модельеры, они проектируют виртуальную реальность, создают трехмерные объекты.
Проектирование трехмерных объектов является сложной работой, требующей больших затрат, как физических, так и материальных. На сегодняшний день существует несколько программных продуктов по созданию трехмерной графики, но наиболее
М.А. Спогреева
109
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
известными и популярными среди них являются такие, как 3D
Studio Max, Maya и Poser.
Возложенная на меня задача включает в себя именно создание того самого игрового мира, то есть разработка трехмерных
моделей в одном из пакетов моделирования. Поэтому изложенный мною материал является актуальным и востребованным.
Важно отметить, что главной проблемой в реализации игрового пространства современных компьютерных игр является противоречие между желаемой степенью детализации трехмерных
объектов игрового мира и скоростью обработки графической информации. Это подразумевает под собой то, что не всегда красивая, содержащая высокодетализированные трехмерные объекты
игра будет обладать высокой производительностью.
Возникает задача создания низкополигональных моделей с
достаточной степенью реалистичности.
В своей работе я описываю этапы по созданию трехмерного
низкополигонального игрового уровня для прототипа компьютерной игры в жанре «автосимулятор» под названием «Скорость
успеха». В создание игрового уровня входят обязанности по разработке трехмерной модели гоночной машины, модели гоночной
трассы и моделей высотных зданий, окружающих гоночную
трассу. Особенностью этой работы является то, что в силу специфичности области, для которой создавался уровень, на его разработку накладывается очень много ограничений, которые не
предъявляются к моделям для других сфер деятельности. Можно
отметить, что процесс моделирования для игр сильно отличается
от моделирования для фильмов, реклам, картин и прочих видов
деятельности. При обычных подходах художнику важно получить финальное изображение и зачастую его не интересует, как
оно было получено. Но в игровом моделировании на первое место выходит не картинка, которую мы можем получить в пакете
моделирования 3D Studio Max, а сами модели, которые сохраняются и в дальнейшем используются в игре. Здесь крайне важно,
как модель построена, сколько в ней треугольников, сколько текстур и какой объем памяти она занимает. И главное, чтобы снижение количества полигонов в модели не сильно сказывалось на
качестве результата, то есть всегда необходимо искать «золотую
110
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
середину». Можно выделить следующие критерии оценки качества модели:
– полигонаж, то есть количество полигонов в модели;
– топология подразумевает характер расположения полигонов;
– анимация, то есть движение объекта;
– материалы или набор текстур для модели.
Поэтому основной моей задачей было создание такого игрового уровня, который имел бы незначительное количество полигонов, но при этом сохранялось качество изображения.
Моя работа имеет не только теоретический, но и практический интерес. Так как в результате мной была создана трехмерная
модель игрового уровня для прототипа игры «Скорость успеха»
от компании «Sonar Games». Модель полностью соответствует
поставленным требованиям и удачно подошла для отладки как
графической, так и физической части игрового движка.
Еще одним из способов уменьшения полигонажа игровых
моделей является создание уровней детализации (Levels of
Details).
В самую первую очередь при создании низкополигональной
модели необходимо определить, какое имеется ограничение по
полигонам. Много современных игр при разработке используют
большое число треугольников на объект, так как все более мощные и современные компьютеры позволяют это делать. Но нужно
определиться, насколько важен тот или иной объект во всей сцене, какое число полигонов необходимо, чтобы он выглядел хорошо. Например, скала на краю дороги не так важна и может состоять всего из 100 – 300 полигонов. Однако фонтан или маленькое здание являются объектами, на которых акцентируется
внимание игрока и требуют гораздо большей детализации, они
могут состоять из 3500 – 5500 треугольников или больше. Все зависит от размеров и необходимой детализации зданий.
Финальным фактором должна служить скорость игры в самый загруженный момент времени, то есть когда камера захватывает максимальное количество объектов и графический движок пытается просчитать большое количество треугольников. Но
сейчас на рынке компьютеров представлено огромное количество
М.А. Спогреева
111
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
различных конфигураций. Компьютеры варьируются от средних
офисных для работы с документами до мощных игровых станций, способных обрабатывать большое количество данных на
предельных скоростях. Все это заставляет разработчиков заботиться о том, чтобы каждый пользователь с собственной конфигурацией компьютера мог насладиться приемлемым качеством
при хорошей скорости игры. Таким образом, необходимо позаботиться, чтобы обладатель слабой «машины», запустив игру, не
имел так называемое слайдшоу, а обладатель мощной станции
получал максимальное качество и производительность, на которую способен его компьютер. Это является одним из факторов
создания нескольких вариантов одной и той же модели с различным числом полигонов, то есть создание уровней детализации.
При этом одна и та же модель, но с различным количеством полигонов и представляет собой уровни детализации.
Другой необходимостью в подобном подходе является желание разработчиков сделать картинку максимально красивой и
реалистичной. А это требует больших затрат по полигонам для
каждой игровой модели. Чтобы снизить затраты видеосистемы на
отрисовку такого огромного числа треугольников, расположенные на дальнем плане объекты выводятся в меньшем качестве с
меньшим полигонажем, но из-за своего маленького размера на
экране, разница остается практически не замеченной.
Все это вынуждает разработчиков позаботиться о создании
нескольких наборов моделей и получить при этом наилучший результат.
Таким образом, создание низкополигональных моделей для
компьютерных игр является актуальной проблемой на сегодняшний день.
 Литература
1. Online-журнал по 3D графике и анимации: http://www.render.ru/
2. Сайт по компьютерной графике: http://www.3dmir.ru/
3. Русскоязычный сайт по разработке и дизайну компьютерных игр:
http://www.gamedev.ru/
112
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Об одной модели сегментации пиксельных
изображений
И.А. Чупанов
Одной из наиболее популярных задач искусственного интеллекта является задача сегментации изображений. За последнее
время на эту тему опубликовано множество статей, с обзором по
этой тематике можно ознакомиться, например, в [1], автоматические методы сегментации изображений рассмотрены в [2].
Обычно сегментацией изображения называют разбиение изображения на непохожие по некоторому признаку области. Предполагается, что области соответствуют реальным объектам или
их частям, а границы областей соответствуют границам объектов.
Сегментация считается важным предварительным шагом, существенно облегчающим последующее решение задач анализа зрительных сцен, таких как распознавание образов, запоминание,
обнаружение заданных объектов и т. д.
Особо сложной считается задача сегментации реальных изображений, то есть таких, где объекты могут пересекаться, где нет
четкой границы между соседними объектами, а также между объектами и фоном. В обзоре [1] рассматриваются разнообразные
модели для решения поставленной задачи. Одна из них представляет собой сеть, каждый элемент которой описывается дискретной переменной с конечным числом состояний. Эту переменную
называют спином. Далее будем отождествлять элемент и переменную и называть элемент спином. Между спинами и пикселями изображения устанавливается взаимно однозначное соответствие. Величины взаимодействия между спинами зависят от разности интенсивностей соответствующих пикселей. Описание
модели в [1] достаточно лаконично. Ниже мы приводим свою
реализацию спиновой модели.
Рассматривается двумерная решетка, в узлах которой расположены спины. Припишем каждому элементу решетки индекс
И.А. Чупанов
113
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
I = 1, 2, …,N. Каждый спин wi может принимать q различных состояний. Номер состояния рассматривается как метка спина.
Целью сегментации является такое распределение меток,
чтобы разным объектам были присвоены различные метки, а все
спины, представляющие один объект, имели одну и ту же метку.
Сеть будем характеризовать набором состояний (меток) всех
ее спинов W = {w1, ... ,wN}. Этот набор назовем конфигурацией
сети. Введем понятие энергии системы. Пока мы не рассматриваем конкретную динамику взаимодействия спинов, но будем считать, что в процессе эволюции система стремится к понижению
энергии. Вообще говоря, искомое состояние должно характеризоваться как состояние с минимумом энергии. Следуя [1], определим энергию конфигурации W как
N
E (W ) =  (K i −
j =1
J δ
j∈ N i
ij ωi ω j
),
(1)
где wi, wj– метки спинов i и j соответственно; Jij – сила взаимодействия между спинами i и j; δωi ω j = 1, если wi = wj , в противном
случае δωi ω j = 0; Ni – окрестность спина i некоторого радиуса R.
Величина Ki определяется формулой:
α
Ki =
N
N
δ
j =1
ωi ω j
,
(2)
где α – некоторый заранее заданный положительный параметр. В
формуле (1) величины Jij характеризуют силу связи между элементами сети. Их значения стараемся определить так, чтобы положительные значения соответствовали пикселям с близкими
значениями интенсивности, а отрицательные значения – пикселям, интенсивности которых значительно различаются. Исходя из
этих соображений величину Jij можно задать формулой:
J ij = 1 −
gi − g j
θ
,
(3)
где gi и gj – интенсивности пикселей, а коэффициент θ определен
как
114
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
θ=
1
N ((2 R + 1) 2 − 1)
N
  gi − g j ,
(4)
j =1 ij
где (2 R + 1) 2 − 1 – число соседей спина.
Будем считать, что спины с одинаковыми метками образуют
кластеры. Через сi будем обозначать один кластер. Тогда
С={с1,…,сМ}, где М<N – набор или конфигурация кластеров. Г –
это пространство всех возможных конфигураций кластеров. Любая конфигурация C ∈ Г .
Мы начинаем со случайного распределения меток. Это означает, что каждому спину i присваивается случайным образом
значение qi. Затем происходит формирование кластеров. Здесь
мы должны оценить, имеет ли смысл данную пару спинов отнести к одному кластеру или нет. Для этого вычисляем вероятность
РВ того, что два соседних спина объединятся в один кластер. Эта
вероятность зависит от того, насколько сильна связь между спинами Jij и от величины Т, которую мы вводим для регулирования
размера кластера. При увеличении Т считаем, что вероятность РВ
уменьшается (ситуация соответствует кластерам маленьких размеров), при уменьшении Т средний размер кластера увеличивается. Здесь, следуя классической теории, будем называть величину
Т температурой. Исходя из вышесказанного определим вероятность РВ формулой

 − 0.5 J ij δ ωi ω j
PB ,<ij > = 1 − exp
T



  .

(5)
После того как кластеры сформированы, включается алгоритм
модификации кластеров. Подобно (1) мы определяем энергию
подконфигурации Wkc , предполагая, что все спины в кластере c
получили метку wk. Это сделано, рассматривая взаимодействие
спинов кластера со спинами вне кластера, но в пределах радиуса
R от него. Далее вычисляются относительные энергии для различных меток, и из сравнения их между собой выбирается метка
кластера. В каждый момент времени происходит модификация
одного кластера при фиксированных метках соседних кластеров
[1].
И.А. Чупанов
115
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
На иллюстрации представлена работа алгоритма на реальном
изображении.
 Литература
1. Казанович Я.Б. Сегментация изображений с помощью динамических нейронных сетей. М.: МИФИ, 2008. 164 с.
2. Баринова О.С., Вежневец А.К. Методы сегментации изображений:
автоматическая сегментация. Графика и Мультимедиа, 2006. 12 с.
Реализация алгоритма Литтла решения
задачи коммивояжера с помощью
рекурсивно-параллельных средств
разработки программ
А.В. Шубин
Программа, реализующая алгоритм Литтла решения задачи
коммивояжера, была разработана и использована как тестовая
для оценки качества работы новой полнофункциональной версии
библиотеки параллельного исполнения rpC-программ для платформы Win32.
116
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При выборе задачи для тестирования библиотеки параллельного выполнения принимались во внимание следующие пожелания к самой задаче и соответствующему рекурсивнопараллельному (РП) алгоритму:
• Задача должна быть достаточно трудоемкой, чтобы разработка параллельного алгоритма выглядела оправданной, а накладные расходы на РП-организацию вычислительного процесса
были относительно невелики.
• Трудоемкость порождаемых параллельных ветвей программы была различной и заранее не предсказуемой. Это необходимо для проверки качества работы алгоритма динамической балансировки загрузки.
• Алгоритм должен предполагать активное использование
как распределенной общедоступной, так и статической памяти.
Всем этим требованиям удовлетворяет алгоритм Литтла решения задачи коммивояжера, основанный на методе ветвей и
границ. Поскольку решение о том, продолжать или нет вычисления на конкретной ветви программы, зависит от значения текущего рекорда (вычисленного асинхронно), оценить априори трудоемкость данной ветви принципиально невозможно. Для хранения матрицы расстояний разумно использовать статическую
память, а для хранения информации о лучшем найденном решении – РОП.
Формулировка задачи коммивояжера (1934 г.):
Коммивояжер должен выйти из первого города, посетить по
разу в неизвестном порядке города 2, 3, …, n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
В терминах теории графов задачу можно сформулировать
так: имеется полный ориентированный граф G = (V, E), каждой
дуге (u, v) которого сопоставлен вес c(u, v). Требуется найти в
этом графе гамильтонов цикл наименьшей стоимости.
А.В. Шубин
117
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Распараллеливание алгоритма
Как уже было отмечено ранее, алгоритм Литтла основан на
методе ветвей и границ [2]. Идея метода состоит в следующем:
решая дискретную экстремальную задачу, разобьем множество
всех возможных вариантов на подмножества и построим оценки
для них. В результате становится возможным отбрасывать решения целыми подмножествами, если их оценка хуже некоторого
рекордного значения.
Назовем классом некоторое подмножество множества всех
возможных туров. Идея обычного последовательного алгоритма
Литтла заключается в том, что на каждом шаге какой-либо класс
разбивается на два более мелких, при этом уменьшается размерность задачи или уточняется нижняя оценка. Разбиение класса на
два более мелких класса как раз и лежит в основе распараллеливания процесса вычисления.
Для организации процесса распараллеливания была создана
параллельная процедура RP_Algo. В качестве входного параметра ей передается некоторый класс – подмножество множества
всех туров. Эта процедура разбивает исходный класс на два более
мелких класса, находит для них нижние оценки и вызывает саму
себя для новых классов.
При разбиении класса на два более мелких выбирается некоторое ребро-кандидат. Затем класс разбивается на два: класс, туры которого содержат ребро-кандидата, и класс туров, которое не
содержащих этого ребра.
Для нахождения нижних оценок и ребра-кандидата на включение или не включение в тур используются те же алгоритмы,
что и для обычного алгоритма Литтла.
Процесс распараллеливания можно представить в виде бинарного дерева, в узлах которого будут находиться вызовы процедуры RP_Algo. Рекурсивный процесс продолжается до тех пор,
пока максимальное расстояние от корня до листа дерева не станет
равным некоторому фиксированному числу. Это число называется глубиной рекурсии и является входным параметром при запуске программы. После этого распараллеливание прекращается, и
118
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
происходит вызов функции, реализующей последовательный алгоритм.
Результаты тестирования
Алгоритм Литтла был запрограммирован на языке rpC [1],
отлажен в последовательном режиме и использован как тестовый
пример для оценки качества работы библиотеки поддержки параллельного режима выполнения. В качестве средства для компиляции и сборки использовалась среда Microsoft Visual C++ 6
версии, под управлением ОС Windows XP.
Тестирование производилось на сети из компьютеров с процессорами Intel Pentium 4 с тактовой частотой 3 Ггц и объемом
ОЗУ 1 Гбт. Эксперименты производились на сети из 1, 2, 4, 6, 8
компьютеров. Решалась задача коммивояжера для 40 городов. В
качестве глубины рекурсии использовались значения от 0 до 12.
Результаты экспериментов позволяют сделать выводы о надежной работе алгоритмов реализации основных функций библиотеки. Наиболее эффективно задача решалась в том случае, если число ПМ в системе (N) было равно степени двойки, а глубина
рекурсии равнялась log 2 N . При этом наблюдалось существенное
ускорение решения задачи, причем, как правило, в большее число
раз, чем количество использованных компьютеров. Это объясняется спецификой метода ветвей и границ. Действительно, если на
одной из параллельных ветвей было получено достаточно хорошее решение, объем вычислений на всех остальных заметно
уменьшался за счет отсечения неперспективных вариантов. Это
еще один довод в пользу разработки именно параллельных алгоритмов решения такого класса задач.
Для оценки работы алгоритма динамической балансировки
загрузки задача запускалась с глубиной рекурсии от 6 до 12. При
увеличении значения глубины рекурсии наблюдалось некоторое
замедление работы программы. Это явление связано с увеличением числа активаций параллельных процедур и, как следствие, с
увеличением нагрузки на коммутационную сеть. При этом наблюдалась достаточно неплохая загрузка процессорных модулей.
А.В. Шубин
119
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Недетерминированность параллельного вычислительного
процесса данной задачи не позволяет на основании полученных
данных произвести количественную оценку накладных расходов
на организацию параллельного процесса и обмен информацией
по сети. Для получения этой оценки нужно провести тестирование библиотеки на других более детерминированных задачах.
P.S. Выражаю особую благодарность своему научному руководителю Васильчикову Владимиру Васильевичу за помощь при
подготовке дипломной работы.
 Литература
1. Васильчиков В.В. Средства параллельного программирования для
вычислительных систем с динамической балансировкой загрузки. Ярославль: ЯрГУ, 2001.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Издательский дом «Вильямс», 2001.
120
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание
Задача планирования пути наибольшего веса
на правильной квадратной решетке
С.В. Алешин .................................................................................. 3
Алгоритм построения интерполяционных изображений,
основанный на методе кодирования IFS
А.А. Великанова............................................................................ 7
Об одном стиле программирования, основанном
на использовании высокоуровневых конечных
автоматов
Р.А. Виноградов ......................................................................... 12
Задача о нахождении безопасного пути робота в среде
с динамическими препятствиями
А.В. Вяткин ................................................................................ 20
Исследование одного алгоритма для прогнозирования
объёма продаж
А.Ю. Грицевич ............................................................................ 24
Прогнозирование объема продаж в MS Excel
А.И. Гущина................................................................................ 28
Исследование основных свойств и разрешимости массовых
алгоритмических проблем для супер-двойственных
сетей Петри и сетей активных ресурсов
Ю.В. Диль ................................................................................... 34
Сеть нейронных клеточных автоматов в задаче
сегментации черно-белых пиксельных изображений
Д.С. Дыбин ................................................................................. 40
А.В. Шубин
121
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Биологически мотивированная нейросетевая модель
выделения краев изображений на основе
вейвлетных преобразований
С.В. Егоров ................................................................................. 43
Расстояния и другие меры близости на множестве чернобелых цифровых изображений
И.А. Каплий, О.С. Куликов ........................................................ 46
Разработка базовой части корпоративной
ERP/CRM-системы для службы услуг
А.Е. Капралов ............................................................................. 50
Разработка биологически правдоподобной нейронной сети,
выделяющей контуры (пиксельного) изображения
И.О. Колотухин ......................................................................... 56
Исследование поведения характеристического набора
черно-белого изображения при его повороте
Д.А. Кудинкин............................................................................. 60
Реализация трёхмерной модели персонажа с высокой
детализацией
Е.А. Кукушкин ............................................................................ 64
Разработка трехмерных сцен и изучение программной
среды 3d studio MAX
В.В. Лебедев, Ф.А. Разумный .................................................... 69
Разработка механической системы принятия решений на
основе индикатора MACD
А.С. Лишатова .......................................................................... 76
О телефонном центре, центроиде и псевдоцентроиде
вершинно-взвешенного связного графа
Г.М. Бродский, З.В. Наханов..................................................... 82
122
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ограничения на целевые функции для эффективного
решения задачи целочисленного программирования
на многограннике, ассоциированном с задачей
3-выполнимость
А.В. Николаев ............................................................................. 85
Язык математических формул DIM-FL Динамической
Информационной Модели
Д.С. Писаренко .......................................................................... 88
Относительные параперманенты с приложениями к
умножению матриц и решению рекуррентных
уравнений
М.О. Семенов, Г.М. Бродский ................................................... 97
Поиск дубликатов в результатах выдачи
поисковых машин
Ю.А. Спиридонов ..................................................................... 101
Разработка графического движка реального времени
И.С. Спогреев ........................................................................... 105
Создание трехмерного низкополигонального уровня
для игры
М.А. Спогреева ......................................................................... 109
Об одной модели сегментации пиксельных изображений
И.А. Чупанов ............................................................................ 113
Реализация алгоритма Литтла решения задачи
коммивояжера с помощью рекурсивно-параллельных
средств разработки программ
А.В. Шубин ............................................................................... 116
А.В. Шубин
123
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Научное издание
Студенческие заметки
по информатике и математике
Выпуск 2
Материалы научной конференции
студентов и аспирантов факультета ИВТ
Редактор, корректор М.В. Никулина
Компьютерная верстка И.Н. Ивановой
Подписано в печать 21.07.2008. Формат 60х84/16.
Бумага тип. Усл. печ. л. 7,21. Уч.-изд. л. 5,71.
Тираж 60 экз. Заказ
Оригинал-макет подготовлен
в редакционно-издательском отделе ЯрГУ.
Ярославский государственный университет.
150000 Ярославль, ул. Советская, 14.
Отпечатано
ООО «Ремдер» ЛР ИД № 06151 от 26.10.2001.
г. Ярославль, пр. Октября, 94, оф. 37
тел. (4852) 73-35-03, 58-03-48, факс 58-03-49.
124
Студенческие заметки по информатике и математике. Вып. 2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А.В. Шубин
125
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Студенческие заметки
по информатике и математике
Выпуск 2
Материалы научной конференции
студентов и аспирантов факультета ИВТ
126
Студенческие заметки по информатике и математике. Вып. 2
Документ
Категория
Без категории
Просмотров
59
Размер файла
2 022 Кб
Теги
информатика, студенческие, вып, математика, заметка, 1442
1/--страниц
Пожаловаться на содержимое документа