Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец
Предложено обобщение известной задачи удовлетворения ограничений в терминах операций коммукативного полукольца. Показано, что известный полиномиально разрешимый подкласс задач с мажоритарным полиморфизмом разрешим и для обобщенной задачи. Запропоновано узагальнення відомої задачі задовільнення обмеж...
Saved in:
| Published in: | Управляющие системы и машины |
|---|---|
| Date: | 2015 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2015
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/112574 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец / Е.В. Водолазский // Управляющие системы и машины. — 2015. — № 6. — С. 3–7, 42. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860236228482301952 |
|---|---|
| author | Водолазский, Е.В. |
| author_facet | Водолазский, Е.В. |
| citation_txt | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец / Е.В. Водолазский // Управляющие системы и машины. — 2015. — № 6. — С. 3–7, 42. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Предложено обобщение известной задачи удовлетворения ограничений в терминах операций коммукативного полукольца. Показано, что известный полиномиально разрешимый подкласс задач с мажоритарным полиморфизмом разрешим и для обобщенной задачи.
Запропоновано узагальнення відомої задачі задовільнення обмежень в термінах операцій комукативного напівкільця. Показано, що відомий поліноміально розв’язний підклас задач з мажоритарним поліморфізмом є розв’язним і для узагальненої задачі.
The article generalizes the known constraint satisfaction problems in terms of a commutative semiring. It is shown that a known track table subclass with a majority polymorphism is also track table in the generalized problem. The constraint satisfaction problems can be defined as computing the disjunction over the set of all variable values of all constraints conjunction. This definition can be generalized to computing the sum of products in a commutative semi ring. One of the track table subclasses of the classical constraint satisfaction problems semering are problems with a majority polymorphism. The article generalizes the definition of polymorphisms to commutative semi rings with the idempotent sum and product and defines a track table subclass for the generalized problem. Many of the useful properties of the classical polymorphisms proved to be true with the generalized polymorphism definition. It is shown that any generalized constraint satisfaction problem with a majority polymorphism can be solved in polynomial time. An algorithm that solves the problem is given and is based on the equivalent star to simplex transformations of the problem by excluding variables one at a time.
|
| first_indexed | 2025-12-07T18:25:01Z |
| format | Article |
| fulltext |
УСиМ, 2015, № 6 3
Теоретические проблемы обработки и распознавания
образов
УДК 519.6
Е.В. Водолазский
Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого
класса полуколец
Предложено обобщение известной задачи удовлетворения ограничений в терминах операций коммукативного полукольца.
Показано, что известный полиномиально разрешимый подкласс задач с мажоритарным полиморфизмом разрешим и для обоб-
щенной задачи.
Ключевые слова: задача удовлетворения ограничений, полиморфизмы, инварианты.
Запропоновано узагальнення відомої задачі задовільнення обмежень в термінах операцій комукативного напівкільця. Показано, що
відомий поліноміально розв’язний підклас задач з мажоритарним поліморфізмом є розв’язним і для узагальненої задачі.
Ключові слова: задача задоволення обмежень, поліморфізми, інваріанти.
Введение. Задачи удовлетворения ограниче-
ний – мощный и достаточно хорошо изучен-
ный инструмент для решения многих приклад-
ных задач в самых разных областях вычисли-
тельной техники. В своей общей формулиров-
ке задачи удовлетворения ограничений пред-
ставляют NP-полный класс задач. Тем не менее,
известны полиномиально разрешимые подклас-
сы [1]. Ранее решение практических задач тре-
бовало некоторого ослабления задачи удовле-
творения ограничений, что привело к форму-
лировке задачи (max, min) разметки [2], для
которой так же удалось сформулировать поли-
номиально разрешимый подкласс. Данная ста-
тья посвящена дальнейшему обобщению задачи
удовлетворения ограничений и для этой обоб-
щенной задачи показано существование поли-
номиально разрешимого подкласса.
Об используемых обозначениях
В статье идет речь о коммутативных полу-
кольцах (,, S). Для упрощения чтения формул
символ часто опускается, так что вместо запи-
си a b используется запись ab. Во многих мес-
тах, где происходит сложение или умножение по
какому-либо множеству, само множество может
быть не указано. Считается, что множество, по
которому происходит сложение или умножение,
должно быть ясно из контекста. Например, в
статье можно встретить запись
x
вместо
Xx
.
Формулировка задачи
Многие задачи вычислительной математики
могут быть сформулированы как задачи раз-
метки на коммутативных полукольцах.
Определение 1. Обобщенная задача размет-
ки на коммутативном полукольце ),,( S –
это четверка , , 2 , ( : | ) ,T T
TX T f X S T
где T – конечное множество переменных, X –
конечное множество значений переменных, Tf ,
T – функции ограничения. Необходимо вы-
числить значение
k Tx X
))(( TxfT для задан-
ной задачи.
У обобщенной задачи разметки есть два до-
статочно хорошо изученных частных случая:
задача удовлетворения ограничений и задача
min-max разметки.
Задача удовлетворения ограничений – это
задача разметки на полукольце (, , {0, 1}) [3,
4]. Функции fT определяют ограничения на под-
множествах переменных T . Вычисление зна-
чения
TkXx
( ( )) = &T
k Tx X
f x T
))(( TxfT экви-
валентно определению, возможно ли приписать
такие значения
*
x переменным, чтобы не на-
рушить ни одно из ограничений *
( ( )) =1,Tf x T
T , т.е. необходимо решить систему логиче-
4 УСиМ, 2015, № 6
ских уравнений. Значения
*
x переменных на-
зываются решением системы ограничений.
Отметим, что для обобщенной задачи разметки
из определения 1 нет понятия решения задачи.
Задача max-min разметки – обобщение за-
дачи удовлетворения ограничений. Во многих
практических приложениях задача удовлетворе-
ния ограничений не имеет решения, но все же
требуется получить какой-либо разумный ответ.
В этом случае строгие ограничения можно ре-
лаксировать так, чтобы каждое ограничение ука-
зывало степень допустимости того или иного на-
бора значений переменных. В задаче max-min
разметки следует найти такой набор значений
*
x , который бы как можно меньше нарушал все
ограничения [2]. Иными словами, следует найти
такой ,
*
x который максимизирует значение
min ( ) .TT
f x T
Это эквивалентно решению
обобщенной задачи разметки на полукольце
(max, min, R).
И задача удовлетворения ограничений, и за-
дача max-min разметки – NP-полные. Тем не ме-
нее, известны некоторые разрешимые подклас-
сы этих задач [2–4]. Автор же укажет один из
полиномиально разрешимых подклассов обоб-
щенной задачи разметки для коммутативных
полуколец (,, S), у которых обе операции
и идемпотентны (a a = a и aa = a). Есте-
ственно, и полукольцо (, , {0, 1}), и полуколь-
цо (max, min, R) обладают этим свойством.
Ключевым понятием для определения опи-
сываемого подкласса задач есть понятие поли-
морфизма, обобщенное определение которого
дается в следующем разделе.
Полиморфизмы и инварианты
Статья оперирует функциями вида
fT : X
T
S, которые также иногда будут назы-
ваться ограничениями. Для того чтобы опреде-
лить понятие полиморфизма, удобно ввести
функции вида p : X X X X, которые будут
называться операторами. Для удобства после-
дующего изложения, операторы p : X X X
X на тройках расширяются до операторов на
тройках кортежей p : Xk
Xk
Xk
Xk примене-
нием оператора p поэлементно
1 1 1
2 2 2
( , , ) = ( ( , , ),
( , , ), , ( , , )).k k k
p x y z p x y z
p x y z p x y z
Определение 2. Оператор p : X X X X –
полиморфизм функции f : X
k
S (или f – инва-
риант p) тогда и только тогда, когда равенство
)),,((=)),,(()()()( zyxpfzyxpfzfyfxf (1)
выполняется для всех kXzyx ,, .
Множество всех полиморфизмов функции f
обозначается Pol{ f }, а множество всех инва-
риантов оператора p – Inv{ f }.
Если оператор p – полиморфизм всех функ-
ций–ограничений задачи, то тогда говорится,
что p – полиморфизм задачи разметки.
Определение 2 – прямое обобщение класси-
ческого определения полиморфизма [1, 3, 5, 6]
для полукольца (, , {0, 1}). Действительно,
выражение (1) превращается в )(xf & )(yf &
)),,((=)),,(()( zyxpfzyxpfzf и эквивалентно
выражению )()()( zfyfxf ( ( , , )).f p x y z
У полиморфизмов на полукольцах с идем-
потентными операциями есть два важных свой-
ства, которые сформулированы в леммах 1 и 2.
Лемма 1. Пусть f : X
k
S и g : X
k
S – функ-
ции, инвариантные относительно оператора p.
Тогда функция ( )( ) = ( ) ( )f g x f x g x также
инвариантна относительно p.
Доказательство. =)),,(()),,(( zyxpgzyxpf
))],,(()()()([= zyxpfzfyfxf
=))],,(()()()([ zyxpgzgygxg (2)
))],,(()()()([= zyxpfzfyfxf
))],,(()()()([ zyxpgzgygxg (3)
=)()()()()()( zgzfygyfxgxf
)]()()][()()][()([= zgzfygyfxgxf
)).,,(()),,(( zyxpgzyxpf (4)
Равенство (2) получено из (1). Если рас-
крыть скобки в (2), то одно из слагаемых будет
.)()()()()()( zgzfygyfxgxf Следовательно, ввиду
идемпотентности , это слагаемое можно до-
бавить еще раз, не изменив значения суммы. И
наконец, (4) получается применением равенст-
ва (1) еще раз.
УСиМ, 2015, № 6 5
Определение 3. Функция fXn : X
n S назы-
вается проекцией функции f : X
n
X
m
S на n
переменных, если ),(=)( yxfxf
mXy
nX
.
Лемма 2. Если функция f : X
n
X
m
S инва-
риантна относительно некоторого оператора p,
то ее проекция g : X
n
S на n переменных
также инвариантна относительно p.
Доказательство.
)],()][,()][,([ 3
3
2
2
1
1
tzftyftxf
ttt
=)),,,(( tzyxpf
t
),(),(),(= 321
321
tzftyftxf
ttt
=)),,,(( tzyxpf
t
(5)
),(),(),([= 321
321
tzftyftxf
ttt
))],,(),,,(( 321 tttpzyxpf
=)),,,(( tzyxpf
t
(6)
)),,(),,,((= 321
321
tttpzyxpf
ttt
=)),,,(( tzyxpf
t
(7)
).),,,((= tzyxpf
t
(8)
Равенство (5) получено раскрытием скобок.
Поскольку слагаемое )),,(),,,(( 321 tttpzyxpf
уже присутствует в сумме )),,,(( tzyxpf
t
для любых Xttt 321 ,, , то это слагаемое мож-
но добавить еще раз, не изменив значение
суммы. Следовательно, равенство (6) справед-
ливо. Поскольку p – полиморфизм f, то выпол-
няется равенство (7). Равенство (8) справедли-
во в силу тех же причин, что и равенство (6).
Мажоритарный полиморфизм
Определяемый в статье класс полиномиаль-
но разрешимых задач опирается на понятие
мажоритарных полиморфизмов.
Определение 4. Оператор p : X X X X на-
зывается мажоритарным оператором, если для
любых x, y X
.=),,(=),,(=),,( xxxypxyxpyxxp (9)
У мажоритарных полиморфизмов на полу-
кольцах с идемпотентными операторами есть
одно очень полезное свойство.
Лемма 3. Любую функцию f трех или более
переменных инвариантную относительно ма-
жоритарного оператора p можно представить в
виде произведения трех функций меньшего чис-
ла переменных. Более того, эти три функции
также инвариантны относительно p.
Доказательство. Докажем, что любую функ-
цию ),,( zyxf от трех наборов переменных
nmk XzXyXx ,, можно представить как
произведение трех проекций.
=),,( zyxf ),,(),,( 1
1
1
1
zyxfzyxf
mXykXx
).,,( 1
1
zyxf
nXz
(10)
Действительно,
=),,(),,(),,( 1
1
1
1
1
1
zyxfzyxfzyxf
zyx
=),,(),,(),,(= 111
111
zyxfzyxfzyxf
zyx
),,(),,(),,([= 111
111
zyxfzyxfzyxf
zyx
(11)
=))],,(),,,(),,,(( 111 zzzpyyypxxxpf
=)),,(),,,(),,,((= 111
111
zzzpyyypxxxpf
zyx
(12)
),,(=),,(=
111
zyxfzyxf
zyx
(13)
Поскольку p – мажоритарный оператор, то
тройка )),,(),,,(),,,(( 111 zzzpyyypxxxp в точ-
ности равна ),,( zyx . Слагаемое ),,( zyxf уже
присутствует в сумме. Следовательно, это сла-
гаемое можно добавить еще раз в виде
)),,(),,,(),,,(( 111 zzzpyyypxxxpf и значение
суммы не изменится. Таким образом, равенст-
во (11) справедливо. Равенство (12) получается
применением свойства (1). Наконец, (13) спра-
ведливо в силу идемпотентности сложения. Сле-
дует также заметить, что вследствие леммы 2
каждая из трех функций инвариантна p.
Из леммы 3 следует теорема.
6 УСиМ, 2015, № 6
Теорема. Любую функцию f : X
k
S, инва-
риантную относительно мажоритарного опера-
тора p, можно выразить как произведение функ-
ций двух переменных:
)(=),(),,(=)(
=
=:1,,
yfxxfxxfxf
jxjy
ixiyy
jiijjiij
kji
,
причем, каждая из этих функций есть проекция
f и инвариантна относительно p.
Доказательство. Согласно лемме 2 функ-
цию f можно разбить на три функции меньше-
го числа переменных. Поскольку f инвариант-
на относительно p, каждая из этих функций
также инвариантна относительно p и в свою
очередь также может быть разбита на функции
меньшего числа переменных. Повторяя этот
процесс разбиения функций, будут получены
функции двух переменных, инвариантные от-
носительно p. Если для некоторой пары пере-
менных получится более одной функции, зави-
симой от этой пары, то такие несколько функ-
ций можно заменить их произведением в соот-
ветствии с леммой 1.
В теореме показан способ преобразования
любой задачи с мажоритарным полиморфиз-
мом в другую задачу с тем же полиморфиз-
мом, но функциями–ограничениями лишь на
две переменные.
Преобразование звезды в симплекс
Подобно тому, как это делается для max-min
задачи разметки [2], основной процедурой для
решения обобщенной задачи разметки с мажо-
ритарным полиморфизмом есть преобразова-
ние звезды в симплекс. Приведенный рисунок
показывает пример такого преобразования, где
переменные изображены как окружности, а
функции–ограничения как линии, соединяю-
щие эти окружности. Звезда – это набор пере-
менных с одной центральной переменной и
набор таких ограничений, каждое из которых
зависит только от центральной переменной и
еще какой-то одной переменной из набора. Те
переменные, которые не являются центром,
называются лучами. Преобразование звезды в
симплекс заменяет функции–ограничения эк-
вивалентным набором таких ограничений, ко-
торые не зависят от центральной переменной.
Рис.
Пусть множество переменных T с централь-
ной переменной t
образуют звезду. Преобразо-
вание звезды в симплекс заменяет ограничения
ftt, t T на эквивалентный набор ограничений
ft1t2, t1, t2 T. Иными словами,
)).(),((=))(,( 2121
2
1
*
*
*
txtxftxxf tt
Tt
Tttt
Ttx
(14)
Это прямое обобщение преобразования звез-
ды в симплекс для полукольца (max, min, R) [2].
Поскольку функция ))(,( *
*
*
txxf
tt
Ttx
есть
проекцией ))(,( *
* txxf
tt
Tt
, то согласно леммам 1
и 2 она инвариантна относительно мажоритар-
ного оператора. Следовательно, функции–огра-
ничения можно заменить на функции ft1t2 , вы-
брав ft1t2 равными проекциям ))(,( *
*
*
txxf
tt
Ttx
на пары переменных t1, t2 согласно теореме.
*
1 2 *1 2 \{ , } *1 2
( ( ), ( )) = ( , ( )).t t t tT t t t Txx X
f x t x t f x x t
(15)
Обозначим * *
*( ) = ( , )t t t
x X
x f x x
. Тогда выра-
жение (15) превращается в =))(),(( 2121
txtxf tt
* * *
* 1 * 2
1 2* 1
2
( ) ( , ( )) ( , ( )) =t t t t tt tx
t t
x f x x t f x x t
* * *
* 1 * 2
1 2* 1
2
= [ ( , ( )) ( , ( )) ( )].tt t t t t tx
t t
f x x t f x x t x
Все значения t (x
) могут быть вычислены за
время O(| T || X |
2). Прямой подход к вычислению
каждого значения ft1t2(x(t1), x(t2)) требует O(| T || X |)
времени, что в сумме дает O(| T |
3| X |
3) для всех
значений. Однако это время можно уменьшить
до O(| T |
2| X |
3), применив достаточно стандарт-
ный программистский трюк. Пусть множество
T будет упорядочено T = {t1, t2,, tn} (порядок
не играет решающей роли). Тогда
УСиМ, 2015, № 6 7
1 1
* * * *
=1 = 1 = 1
* * *
( ) = ( ) ( ) ( ) =
(1, 1, ) ( 1, 1, ) ( 1, , ),
a b n
t t t ti i it t i i a i ba
t tb
x x x x
q a x q a b x q b n x
где * *
=
( , , ) = ( )
b
tii a
q a b x x , а все q могут быть
вычислены по O(| T |
2| X |) с использованием ди-
намического программирования. Теперь необ-
ходимо лишь O(| X |) для вычисления каждого f,
а все преобразование звезды в симплекс требу-
ет O(| T |
2| X |
3) времени.
Процедура исключения переменной из за-
дачи выполняется следующим образом:
1. Выбрать переменную и все функции ог-
раничения, в которые переменная входит. Эта
переменная будет центром звезды. Все другие
переменные, на которые наложены выбранные
ограничения, станут лучами звезды.
2. Применить преобразование звезды в сим-
плекс, исключив тем самым одну переменную
в задаче.
3. Если для какой-то пары переменных ока-
жется больше одного ограничения, заменить
эти ограничения их произведением.
Алгоритм решения обобщенной задачи раз-
метки последовательно исключает переменные
одну за одной, применяя преобразование звез-
ды в симплекс до тех пор, пока в задаче не оста-
нется три переменные. Пусть эти переменные
будут пронумерованы 1, 2, 3 и пусть f12, f13, f23,
будут ограничениями, полученными после ис-
ключения остальных переменных. Тогда ответ
может быть получен прямым вычислением фор-
мулы .),(),(),( 322331132112
321
xxfxxfxxf
XxXxXx
По
скольку операция исключения переменной
применяется O(| T |) раз, алгоритм вычисляет
значение
2TTXx
))(( TxfT для любой задачи
с мажоритарным полиморфизмом за время
O(| T |
3| X |
3).
Отметим, что проблема поиска мажоритарно-
го полиморфизма для данной задачи может ока-
заться очень нетривиальной. Одно из преиму-
ществ предложенного алгоритма – то, что для
его применения нет необходимости знать соб-
ственно полиморфизм. Если такой полиморфизм
существует, то алгоритм вычислит правильное
значение
2TTXx
))(( TxfT , не зная полимор-
физма.
Заключение. До сих пор был известен разре-
шимый подкласс для задачи удовлетворения ог-
раничений и для задачи max-min разметки. Дан-
ная статья объединяет и обобщает эти две зада-
чи, показывая, что достаточным свойством для
существования полиномиально разрешимого под-
класса есть идемпотентность операций полуколь-
ца. Обобщенная задача разметки на полукольце
с идемпотентными операциями с мажоритарным
полиморфизмом может быть сведена к задаче с
тем же полиморфизмом, но ограничениями, каж-
дое из которых применяется только к паре пере-
менных. Полученная задача может быть решена
за время O(| T |
3| X |
3) предложенным алгоритмом.
1. Bulatov A. Jeavons P. Tractable constraints closed
under a binary operation. Techn. Rep. PGR-TR-12-00
Oxford University Comp. Lab., Oxford, 2000. – 27 p.
2. Vodolazskii E.V., Flach B., Schlesinger M.I., Minimax
problems of discrete optimization invariant under ma-
jority operators // Comp. Mathem. and Mathem. Phy-
sics. – 2014. – 54, N 8. – P. 1327–1336.
3. Rossi F., P. Van Beek, Walsh T. Handbook of Con-
straint Programming, Elsevier Science, New York,
2006. – P. 13–28.
4. Shcherbina O.A. Constraint satisfaction and constraint
programming // Intellekt. Sist. – 2011. – 15(1–4). –
P. 53–170.
5. Bulatov A. Tractable conservative constraint satisfac-
tion problems // Proc. of the 18th Annual IEEE Symp.
Logic in Computer Science LICS’03, Washington,
DC, USA, 2003. – P. 321–330.
6. Bulatov A. Complexity of conservative constraint sat-
isfaction problems // ACM Trans. Comput. Logic
12(4), 24:1–24:66, July 2011
Тел. для справок: +38 044 502-6314 (Киев)
© Е.В. Водолазский, 2015
Окончание на стр. 42
42 УСиМ, 2015, № 6
Окончание
статьи
Е.В. Водолазского
UDC 519.6
Ye.V. Vodolazskiy
Generalized Labelling Problems with a Majority Polymorphism for a Certain Class of Semirings
Keywords: constraint satisfaction problems, polymorphism, invariant.
The article generalizes the known constraint satisfaction problems in terms of a commutative semiring. It is shown that a
known tracktable subclass with a majority polymorphism is also tracktable in the generalized problem.
The constraint satisfaction problems can be defined as computing the disjunction over the set of all variable values of all
constraints conjunction. This definition can be generalized to computing the sum of products in a commutative semiring. One
of the tracktable subclasses of the classical constraint satisfaction problems semering are problems with a majority polymor-
phism. The article generalizes the definition of polymorphisms to commutative semirings with the idempotent sum and prod-
uct and defines a tracktable subclass for the generalized problem. Many of the useful properties of the classical polymor-
phisms proved to be true with the generalized polymorphism definition. It is shown that any generalized constraint satisfac-
tion problem with a majority polymorphism can be solved in polynomial time. An algorithm that solves the problem is given
and is based on the equivalent star to simplex transformations of the problem by excluding variables one at a time.
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-112574 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Russian |
| last_indexed | 2025-12-07T18:25:01Z |
| publishDate | 2015 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Водолазский, Е.В. 2017-01-23T16:18:18Z 2017-01-23T16:18:18Z 2015 Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец / Е.В. Водолазский // Управляющие системы и машины. — 2015. — № 6. — С. 3–7, 42. — Бібліогр.: 6 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/112574 519. 6 Предложено обобщение известной задачи удовлетворения ограничений в терминах операций коммукативного полукольца. Показано, что известный полиномиально разрешимый подкласс задач с мажоритарным полиморфизмом разрешим и для обобщенной задачи. Запропоновано узагальнення відомої задачі задовільнення обмежень в термінах операцій комукативного напівкільця. Показано, що відомий поліноміально розв’язний підклас задач з мажоритарним поліморфізмом є розв’язним і для узагальненої задачі. The article generalizes the known constraint satisfaction problems in terms of a commutative semiring. It is shown that a known track table subclass with a majority polymorphism is also track table in the generalized problem. The constraint satisfaction problems can be defined as computing the disjunction over the set of all variable values of all constraints conjunction. This definition can be generalized to computing the sum of products in a commutative semi ring. One of the track table subclasses of the classical constraint satisfaction problems semering are problems with a majority polymorphism. The article generalizes the definition of polymorphisms to commutative semi rings with the idempotent sum and product and defines a track table subclass for the generalized problem. Many of the useful properties of the classical polymorphisms proved to be true with the generalized polymorphism definition. It is shown that any generalized constraint satisfaction problem with a majority polymorphism can be solved in polynomial time. An algorithm that solves the problem is given and is based on the equivalent star to simplex transformations of the problem by excluding variables one at a time. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Теоретические проблемы обработки и распознавания Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец Узагальнені завдання розмітки з мажоритарних поліморфізмом для деякого класу півкілець Generalized Labelling Problems with a Majority Polymorphism for a Certain Class of Semirings Article published earlier |
| spellingShingle | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец Водолазский, Е.В. Теоретические проблемы обработки и распознавания |
| title | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_alt | Узагальнені завдання розмітки з мажоритарних поліморфізмом для деякого класу півкілець Generalized Labelling Problems with a Majority Polymorphism for a Certain Class of Semirings |
| title_full | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_fullStr | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_full_unstemmed | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_short | Обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| title_sort | обобщенные задачи разметки с мажоритарным полиморфизмом для некоторого класса полуколец |
| topic | Теоретические проблемы обработки и распознавания |
| topic_facet | Теоретические проблемы обработки и распознавания |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/112574 |
| work_keys_str_mv | AT vodolazskiiev obobŝennyezadačirazmetkismažoritarnympolimorfizmomdlânekotorogoklassapolukolec AT vodolazskiiev uzagalʹnenízavdannârozmítkizmažoritarnihpolímorfízmomdlâdeâkogoklasupívkílecʹ AT vodolazskiiev generalizedlabellingproblemswithamajoritypolymorphismforacertainclassofsemirings |