О минимизации автоматов алгоритмом Хопкрофта
Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в эт...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2016
|
| Назва видання: | Управляющие системы и машины |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/113327 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-113327 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1133272025-02-23T17:14:54Z О минимизации автоматов алгоритмом Хопкрофта Про мінімізацію автоматів алгоритмом Хопкрофта On Automata Minimization by Hopcroft’s Algorithm Чеботарев, А.Н. Программная инженерия и программные средства Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в этом дереве. Розглянуто алгоритм Хопкрофта для мінімізації детермінованих всюди визначених скінченних автоматів. Дано зрозуміле до ведення коректності алгоритму та оцінки часової складності. Доведення базується на запропонованому понятті дерева розщеплень і методі розповсюдження «закритих» вузлів у цьому дереві. The algorithm for minimizing deterministic complete finite state automata proposed by J. Hopcroft is considered. Although the existence of this algorithm is widely known, its theoretical justification is not that obvious. The aim of this study is to give a clear and understandable presentation of the algorithm focusing on the firm theoretical basis, rigorous correctness proof and time complexity analysis. The algorithm is based on the partition notion of the automaton states which defines the equivalence relation. It constructs a sequence of such partitions by a stepwise refinement of some initial partition. The last partition in this sequence corresponds to the maximal congruence on the automaton’s states, i.e., the equivalence stable with respect to the transition function of the automaton. To prove correctness of the algorithm it is necessary to show that the final constructed partition is a congruence, and that this congruence is maximal. In the first part of this proof, the introduced notion of binary splitting tree is used whose nodes are classes of the partitions constructing by the algorithm and a technique for extending the so called “closed” nodes of this tree. The second part is based on the proposition concerning the order on partitions. It is proved that every partition in the sequence generated by the algorithm is greater than or equal to the partition corresponding to the maximal congruence. It is show that Hopcroft’s algorithm can be implemented to worst-case time complexity O (kn log n) for an automaton with n states over a k-letter alphabet. This statement relies on the fact that the total number of actions refining the partitions over all steps of algorithm execution is of the order of O(kn log n). The data structures which allow obtaining this time complexity is presented. The last section describes the algorithm features for minimizing Moore and Mealy automata. 2016 Article О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/113327 519.713 ru Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Программная инженерия и программные средства Программная инженерия и программные средства |
| spellingShingle |
Программная инженерия и программные средства Программная инженерия и программные средства Чеботарев, А.Н. О минимизации автоматов алгоритмом Хопкрофта Управляющие системы и машины |
| description |
Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в этом дереве. |
| format |
Article |
| author |
Чеботарев, А.Н. |
| author_facet |
Чеботарев, А.Н. |
| author_sort |
Чеботарев, А.Н. |
| title |
О минимизации автоматов алгоритмом Хопкрофта |
| title_short |
О минимизации автоматов алгоритмом Хопкрофта |
| title_full |
О минимизации автоматов алгоритмом Хопкрофта |
| title_fullStr |
О минимизации автоматов алгоритмом Хопкрофта |
| title_full_unstemmed |
О минимизации автоматов алгоритмом Хопкрофта |
| title_sort |
о минимизации автоматов алгоритмом хопкрофта |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2016 |
| topic_facet |
Программная инженерия и программные средства |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/113327 |
| citation_txt |
О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT čebotarevan ominimizaciiavtomatovalgoritmomhopkrofta AT čebotarevan promínímízacíûavtomatívalgoritmomhopkrofta AT čebotarevan onautomataminimizationbyhopcroftsalgorithm |
| first_indexed |
2025-11-24T02:20:30Z |
| last_indexed |
2025-11-24T02:20:30Z |
| _version_ |
1849636505655443456 |
| fulltext |
УСиМ, 2016, № 3 61
УДК 519.713
А.Н. Чеботарев
О минимизации автоматов алгоритмом Хопкрофта
Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны по-
нятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном
понятии дерева расщеплений и методе распространения «закрытых» вершин в этом дереве.
Ключевые слова: алгоритм Хопкрофта, минимизация автомата, разбиение, конгруэнция, временная сложность, дерево расщеплений.
Розглянуто алгоритм Хопкрофта для мінімізації детермінованих всюди визначених скінченних автоматів. Дано зрозуміле до-
ведення коректності алгоритму та оцінки часової складності. Доведення базується на запропонованому понятті дерева розще-
плень і методі розповсюдження «закритих» вузлів у цьому дереві.
Ключові слова: алгоритм Хопкрофта, мінімізація автомата, розбиття, конгруенція, часова складність, дерево розщеплень.
Введение. Минимизация конечных автоматов
имеет существенное значение при решении
задач, использующих автоматные модели, та-
кие как синтаксический анализ текстов, проек-
тирование дискретных систем управления и
многие другие. Проблема минимизации вполне
определенных автоматов впервые была сфор-
мулирована в 50-х годах прошлого века в ра-
ботах Хаффмена [1] и Мура [2]. Муром был
предложен подход к построению минимально-
го автомата. С тех пор опубликовано много
работ, описывающих и уточняющих алгоритм
минимизации. Простые рассуждения показы-
вают, что временная сложность этого алгорит-
ма оценивается как O(n2) или точнее O(kn2),
где k – мощность входного алфавита, а n – ко-
личество состояний автомата. Ввиду распро-
страненности применения процедуры миними-
зации, естественно желание уменьшить слож-
ность алгоритма. В 1971 г. Дж. Хопкрофт пред-
ложил алгоритм, сложность которого в худ-
шем случае оценивается как O(kn log n). Этот
результат до сих пор остается лучшим. Подход
Хопкрофта, хотя идейно близок к подходу
Мура, существенно отличается от него и, если
последний воспринимается естественно и кор-
ректность его достаточно очевидна, то более
изощренный метод минимизации Хопкрофта
требует больших усилий для его осмысления и
доказательства корректности.
В оригинальной работе Хопкрофта [3] было
дано довольно сложное описание алгоритма и
не очень строго обосновывалась его коррект-
ность и оценка временной сложности. Поэтому
за ней последовал ряд работ, например [4–7], в
которых алгоритм изложен более ясно и пред-
ложено более строгое и менее громоздкое обос-
нование его корректности и оценки временной
сложности. Первая такая попытка была сделана
Грисом [4] в 1973 г. В этой работе вопросы, свя-
занные с обоснованием и анализом алгоритма
Хопкрофта, изложены более строго. Однако и
эта работа в дальнейшем вызвала некоторые на-
рекания. Кроме того в русскоязычной литерату-
ре практически отсутствует простое описание
алгоритма Хопкрофта и, тем более, его обосно-
вание.
Задачей настоящей статьи является доста-
точно простое и ясное изложение как самого
алгоритма, так и доказательства его коррект-
ности и оценки временной сложности. С этой
целью предложены новые (по мнению автора,
более простые) доказательства утверждений,
необходимых для обоснования корректности
алгоритма. Обычно алгоритм Хопкрофта фор-
мулируется для минимизации автомата-распо-
знавателя, в статье рассматриваются также его
особенности при минимизации автоматов Му-
ра и Мили. Следует заметить, что приведенные
в литературе оценки сложности алгоритма спра-
ведливы при выполнении определенных тре-
бований к структурам данных, используемых
при реализации алгоритма. Поэтому в статье
приведены эти требования и описаны удов-
летворяющие им структуры данных.
Основные понятия
Разбиением множества Q называется такое
семейство = {B1, B2, ..., Bn} непустых, попар-
62 УСиМ, 2016, № 3
но непересекающихся подмножеств множества
Q, что Q = B1 B2 ... Bn. Подмножества
Bi (i = 1, ..., n) называются классами разбиения
. Разбиение множества B на два непустых под-
множества будем называть расщеплением B.
Понятие разбиения множества связано с по-
нятием отношения эквивалентности на этом
множестве так, что каждый класс разбиения
совпадает с классом соответствующей эквива-
лентности. Таким образом, между разбиения-
ми множества Q и эквивалентностями на нем
имеется взаимно однозначное соответствие.
Произведением разбиений 1 и 2 (обозначает-
ся 1 2) называется разбиение , классы ко-
торого представляют собой попарные пересе-
чения классов 1 с классами 2. На множестве
разбиений следующим образом определен час-
тичный порядок: разбиение 1 уточняет (re-
fines) разбиение 2 (1 2), если каждый класс
разбиения 1 содержится в некотором классе
разбиения 2. Частичный порядок на множест-
ве разбиений определяет частичный порядок
по включению () на множестве соответст-
вующих эквивалентностей. Пусть разбиениям
1, 2 соответствуют эквивалентности 1, 2,
тогда из 1 2 следует 1 2.
Утверждение 1. Пусть 1 и 2 – эквивалент-
ности на Q. Если для любых a, b Q из (a, b)
1 следует (a, b) 2, то 2 1.
Далее рассматривается конечный детермини-
рованный вполне определенный автомат-распо-
вит, Q – множество состояний, :QX Q –
функция переходов, а F Q – множество заклю-
чительных состояний. Ниже понадобится поня-
тие обратной функции переходов –1: QX 2Q,
определяемой как –1(q,x) = {q | (q, x) = q}.
Для множества B Q обозначим (B, x) = {(q,
x) | q B} и –1(B, x) = }),(|{ BxqQq .
Пусть X* – множество всех слов в алфавите
X, а X* – пустое слово. Определим расши-
ренную функцию переходов *:QX* Q
следующим образом: *(q, ) = q, *(q, wx) =
= (*(q, w), x), где w X*, x X. Каждому со-
стоянию q Q ставится в соответствие множе-
ство слов }),(|{)( FwqXwqL , распо-
знаваемых автоматом в этом состоянии. Со-
стояния q1 и q2 называются эквивалентными
(обозначается q1 q2), тогда и только тогда,
когда L(q1) = L(q2).
Любое отношение эквивалентности на
множестве состояний автомата A называется
конгруэнцией, если для всех q, q Q и x X
из qq следует (q, x) (q, x) и множество F
является объединением некоторых классов эк-
вивалентности . Несложно показать, что оп-
ределенная ранее эквивалентность является
максимальной (относительно включения) кон-
груэнцией на Q, которую обозначим Q.
Утверждение 2. Разбиение = {B1, B2, ..., Bm}
множества Q соответствует конгруэнции тогда
и только тогда, когда Bi x X Bj
((Bi, x) Bj).
Автомат A называется минимальным, если
для любой пары (q, q) его различных состоя-
ний L(q) L(q), другими словами, это автомат,
не имеющий эквивалентных состояний. Ре-
зультат минимизации автомата A – автомат,
состояния которого представляют собой клас-
сы эквивалентности конгруэнции Q.
Алгоритм Хопкрофта
Минимизация детерминированного вполне
определенного автомата A = X, Q, , F со-
стоит в нахождении максимальной конгруэн-
ции Q на множестве его состояний. Построе-
ние требуемой конгруэнции начинается с раз-
биения 0 = {F, Q\F}, которое затем последо-
вательно уточняется путем расщепления неко-
торых классов до получения разбиения, соот-
ветствующего конгруэнции.
Условием расщепления класса B разбиения
является наличие таких C и x X, что
(B, x) C и (B, x) C. Такую пару (C, x)
будем называть сплитером класса B. Для вы-
ражения –1(C, x) введем сокращение x–1C. Рас-
щепление класса B на два класса B = B
x–1C = {q B | (q, x) C} и B = B \ x–1C =
={q B | (q, x) C} назовем расщеплением по
сплитеру (C, x).
УСиМ, 2016, № 3 63
Используя введенные понятия, можно сфор-
мулировать понятие конгруэнции на множестве
Q. Разбиение = {B1, B2, ..., Bm} множества Q
соответствует конгруэнции, если ни один класс
Bi не удовлетворяет условию расщепления,
т.е. ни для каких Bi, Bj и x X (Bi, x) не яв-
ляется сплитером класса Bj (не расщепляет Bj).
Расщепление всех классов разбиения , рас-
щерляемых по сплитеру (C, x), назовем шагом
расщеплений.
Процесс минимизации представляет собой
построение последовательности разбиений 0,
1, ..., k , в которой каждое разбиение i+1 (i 0)
получается из предыдущего в результате вы-
бора блока C i и последовательного выпол-
нения шагов расщеплений по сплитерам (C, x)
для всех x X. Для каждого класса B разбие-
ния, полученного в результате выполнения ша-
га расщепления по (C, x), либо q B (q, x)
C, либо q B (q, x) C. Отсюда следует,
что дальнейшие расщепления по (C, x) выпол-
нять не требуется.
Пусть C = C1 C2 и C1 C2 = . Обозна-
чим С разбиение, полученное из в результа-
те расщепления его классов по сплитеру (C, x).
Аналогично обозначим
1C и
2C разбиения,
полученные путем расщепления классов со-
ответственно по сплитерам (C1, x) и (C2, x).
Лемма 1. Для любого x X справедливо
С
1C = С
2C =
1C
2C .
Доказательство. Пусть класс B расще-
пляется по сплитеру (C, x) на B = B x–1C и
B = B \ B, по сплитеру (C1, x) – на 1B= B
x–1C1 и 1B = B \ 1B , а по сплитеру (C2, x) –
на 2B = B x–1C2 и 2B = B \ 2B . Фигурирую-
щие здесь классы, на которые расщепляется B,
удовлетворяют следующим соотношениям:
21 BBB , 21 BB , 11 \ BBBB =
= 2BB , 22 \ BBBB = 1BB .
В разбиении С 1C класс B разбивается на
1 1( , ) ( , )B B B B = 1 1 1{( ), ( ), ( ),B B B B B B
1( )}B B = },,,{ 21 BBB .
В разбиении С
2C класс B разбивается
на 2 2( , ) ( , )B B B B = 2 2{( ), ( ),B B B B
2 2( ), ( )}B B B B },,,{ 12 BBB .
Аналогично для
21 CC имеем 1 1( , )B B
2 2( , )B B = 1 2{( ),B B 1 2( ),B B 1 2( ),B B
1 2( )}B B },,,{ 21 BBB .
Таким образом, в каждом из разбиений С
1C , С
2C ,
1C
2C класс B разбивается
на одни и те же классы. Если по какому-либо
из сплитеров (C1, x) или (C2, x) класс B не рас-
щепляется, то все три произведения разбиений
совпадают с разбиением С. Поскольку классы
разбиения расщепляются независимо, отсю-
да вытекает справедливость леммы 1.
На этой лемме основывается алгоритм Хоп-
крофта, поэтому она существенно использует-
ся в доказательстве его корректности.
Последовательность шагов расщеплений по
сплитерам (C, x) для всех x X будем называть
циклом расщеплений по классу C. Поскольку
нет необходимости выполнять расщепления по
всем классам, порождаемым в процессе уточ-
нения разбиений, то параллельно с уточнением
текущих разбиений строится и изменяется
множество L классов, по которым следует
осуществлять расщепления.
Алгоритм минимизации автомата A = X, Q, , F.
P := {F, Q\F};
if |F| |Q\F| then
L := {F}
else
L := {Q/F};
while L do
выбрать в L класс (скажем C) и удалить его из L
for каждого x X do
for каждого класса B P, для которого B ∩ x–1C и B \ x–1C
do
заменить B в P двумя классами B = B ∩ x–1C и B = B \ x–1C
if B L then
заменить B в L классами B и B
else
if |B| |B| then
добавить B в L
else
добавить B в L
end for;
end for;
end while;
64 УСиМ, 2016, № 3
В процессе работы алгоритма итеративно
преобразуются два множества: текущее раз-
биение i = {B1, ..., Bm} и текущее множество Li
тех классов разбиения i, по которым следует
выполнять расщепления.
В каждом цикле while L выполняются
следующие операции. Из Li выбирается и уда-
ляется какой-либо из классов C, затем в каж-
дом шаге расщеплений по сплитеру (C, x), x
X, каждый класс B текущего разбиения i,
который расщепляется на B и B, заменяется
парой классов B и B и, если B Li, он заме-
няется в Li на B и B, в противном случае в Li
добавляется меньший по мощности класс из B
и B. Поскольку в каждом цикле while из L
удаляется один класс, количество которых ко-
нечно, то алгоритм заканчивает работу, когда
Li = .
Пример 1. Автомат A задан следующей таб-
лицей переходов.
Т а б л и ц а 1
0 1 2 3 4 5 6 7 8 9
a 1 5 1 4 5 5 2 8 4 5
b 3 5 5 7 3 2 9 8 9 6
Здесь X = {a, b}, F = {6, 7, 9}. Множество
состояний {q1, q2, ..., qk} будем записывать в
виде (q1q2...qk). Исходное разбиение 0 = {B1 =
= (0123458), B2 = (679)}, L0 = {(679)}.
Первый цикл: C = (679).
x = a. a–1(679) = .
x = b. b–1(679) = (3689). Расщепляются оба
класса.
(0123458) {(01245), (38)}, (679) {(69), (7)}.
1 = {(01245), (38), (69), (7)}, L1 = {(38), (7)}.
Второй цикл: C = (7).
x = a. a–1(7) = .
x = b. b–1(7) = (3). Расщепляется класс (38)
{(3), (8)}.
2 = {(01245), (3), (8), (69), (7)}, L2 = {(3), (8)}.
Третий цикл: C = (3).
x = a. a–1(3) = .
x = b. b–1(3) = (04). Расщепляется класс
(01245) {(125), (04)}.
3 = {(125), (04), (3), (8), (69), (7)}, L3 = {(8),
(04)}.
Четвертый цикл: C = (04).
x = a. a–1(04) = (38).
x = b. b–1(04) = . Расщепления не происходят.
4 = {(125), (04), (3), (8), (69), (7)}, L4 = {(8)}.
Пятый цикл: С = (8).
x = a. a–1(8) = (7).
x = b. b–1(8) = (7). Расщепления не происходят.
5 = {(125), (04), (3), (8), (69), (7)}, L5 = .
На этом работа алгоритма заканчивается.
Получаем автомат с шестью состояниями, за-
ключительным состояниям которого соответ-
ствуют классы (69) и (7).
Доказательство корректности алгоритма
Следует доказать, что алгоритм Хопкрофта
решает поставленную задачу, т.е., что
получаемое им разбиение соответствует
конгруэнции относительно функции переходов;
эта конгруэнция максимальна.
Для рассматриваемого варианта алгоритма
несколько изменим понятие сплитера. Если
существует такой x X, что (C, x) расщепляет
класс B, то класс C будем называть сплитером
класса B. Так, чтобы показать, что полученное
алгоритмом разбиение соответствует конгру-
энции, достаточно показать, что ни один класс
разбиения не является сплитером ни для ка-
кого класса этого разбиения. Для этой цели
удобно ввести понятие бинарного дерева рас-
щеплений, представляющего последователь-
ность всех расщеплений, выполненных в про-
цессе работы алгоритма.
Вершинами этого дерева являются классы
разбиений, порождаемых при работе алгорит-
ма. Корень дерева соответствует множеству Q.
Два его потомка – классы F и Q\F. Потомки
вершины, соответствующей классу B, пред-
ставляют классы B и B , на которые он
расщепляется при выполнении некоторого ша-
га расщеплений. Все вершины, соответствую-
щие классам, по которым осуществлялись рас-
щепления, называются закрытыми и обозна-
чаются черными кружками, а все остальные
(открытые) – белыми. Классы разбиения, по-
УСиМ, 2016, № 3 65
лученного после окончания работы алгоритма,
представлены листьями дерева расщеплений.
Очевидно, что вид дерева зависит от последо-
вательности выполненных расщеплений. Воз-
можное дерево расщеплений для примера 1
приведено на рис. 1.
(125)
(0-5,8)
(01245)
(679)
(7)
(04) (3) (8)
(69) (38)
Q
Рис. 1
Введем правила распространения закрытых
вершин, позволяющих все вершины дерева счи-
тать закрытыми.
B
B B B B
а б
B
Рис. 2
Рассмотрим два фрагмента дерева расщеп-
лений, приведенные на рис. 2. На рис. 2, а по-
казано, что по сплитерам B и B выполнялись
расщепления. Из леммы 1 следует, что цикл
расщеплений по B не изменяет полученного
разбиения, поэтому вершину B также мож-
но считать закрытой. Аналогичная ситуация
приведена на рис. 2, б. Поскольку расщепле-
ния выполнялись по B и B , то цикл рас-
щеплений по B полученного разбиения не при-
ведет к его изменению. Таким образом, вер-
шину B также можно считать закрытой.
Покажем, что, выполнив распространение
закрытых вершин сначала в соответствии с
правилом 2, б, а затем согласно правилу 2, а,
получим дерево, все вершины которого будут
закрытыми. Если все вершины-листья закры-
ты, то ни один из классов полученного разбие-
ния не может служить сплитером ни для како-
го класса этого разбиения, из чего следует, что
полученное разбиение соответствует конгру-
энции на множестве Q.
Для доказательства этого утверждения рас-
смотрим процесс построения дерева расщеп-
лений в соответствии с последовательностью
шагов расщеплений, начиная с корня Q. На
каждом шаге расщеплений к построенной час-
ти дерева добавляются вершины, полученные
на этом шаге в результате расщеплений клас-
сов. Вершины, добавляемые на каждом шаге
расщеплений, назовем первичными, если соот-
ветствующие им классы добавляются во мно-
жество L, и вторичными в противном случае.
После окончания процесса построения дерева
расщеплений, все первичные вершины, по ко-
торым осуществлялись расщепления, будут
закрытыми. Первичная вершина не будет за-
крытой только в том случае, если она была ра-
сщеплена до того как ее выбрали в качестве
сплитера. Очевидно, что оба ее потомка – так-
же первичные вершины.
Утверждение 3. В построенном дереве ра-
сщеплений после всех возможных применений
правила 2, б все первичные вершины будут за-
крытыми.
Доказательство. Пусть Т – минимальное
поддерево дерева расщеплений, порожденное
открытой первичной вершиной В, т.е. не со-
держащее других открытых первичных вер-
шин. Очевидно, что в силу минимальности Т
оба потомка вершины B закрыты. После при-
менения правила 2, б, вершина В также стано-
вится закрытой. Применим это правило ко
всем таким минимальным поддеревьям. Пусть
теперь T1 – наименьшее поддерево, порожден-
ное открытой первичной вершиной, не содер-
жащее других открытых первичных вершин.
Потомки его корня либо изначально были за-
крытыми вершинами, либо стали такими после
предыдущих применений правила 2, б. Приме-
нение этого правила делает его корневую вер-
шину закрытой, и, таким образом, все первич-
ные вершины поддерева T1 будут закрытыми.
Очевидно, что после применения правила 2, б
в таком порядке, все первичные вершины де-
рева расщеплений станут закрытыми.
Утверждение 4. Если в дереве расщеплений
все первичные вершины закрыты, то в резуль-
тате всех возможных применений правила 2, а
все его вершины станут закрытыми.
66 УСиМ, 2016, № 3
Это утверждение достаточно очевидно. На-
чиная применение правила 2, а с фрагмента,
образованного вершиной Q и двумя ее потом-
ками, и двигаясь затем в направлении роста
дерева, получим все вершины в дереве расще-
плений закрытыми.
Из этих утверждений следует справедли-
вость утверждения 1.
Для дерева на рис. 1 распространение за-
крытых вершин выполняется в следующем по-
рядке. Сначала делаем закрытой вершину (38)
(правило 2, б), затем согласно правилу 2, а –
вершины (0–5,8), (69), (01245) и (125).
Итак, в процессе работы алгоритма строится
последовательность разбиений, соответствую-
щих эквивалентностям 0 1 ... k = k+1
Ранее показано, что k – конгруэнция на Q.
Остается показать, что k совпадает с наиболь-
шей конгруэнцией Q. Сначала, используя ут-
верждение 1, покажем, что i Q для всех i 0.
Индукцией по последовательности эквива-
лентностей докажем, что для всех i 0 из
(a,b) i следует (a, b) Q. Это очевидно для
0, так как пара, состоящая из заключительного
и незаключительного состояний, не принадле-
жит Q. Предположим, что это утверждение вы-
полняется для всех 0 l i. Поскольку i+1 i,
то найдется такая пара (a, b) i, что (a, b)
i+1, а значит, для некоторого x X (x(a),
x(b)) i (условие расщепления, приводящего
к i+1). Отсюда согласно индуктивному пред-
положению следует, что (x(a), x(b)) Q. Так
как Q – конгруэнция, то в силу (x(a), x(b))
Q пара (a, b) также не принадлежит Q. Та-
ким образом, (a, b) i+1 (a, b) Q и, сле-
довательно, 0 1 ... k Q. Поскольку
Q – наибольшая конгруэнция на Q, а k – кон-
груэнция, то k = Q.
Анализ временной сложности алгоритма
Утверждение 5. Для автомата с n состоя-
ниями и k-буквенным алфавитом алгоритм
Хопкрофта может быть реализован в худшем
случае с временной сложностью O(kn log n).
Для получения этой оценки процесс построе-
ния конгруэнции Q должен быть реализован так,
чтобы используемые в нем основные операции
имели следующие временные характеристики:
• доступ к классу, которому принадлежит
заданное состояние, осуществляется за время,
определяемое константой;
• просмотр всех элементов класса осуще-
ствляется за время, пропорциональное его раз-
меру (мощности);
• добавление или удаление элемента множе-
ства осуществляется за время, определяемое
константой.
Существует несколько реализаций структур
данных, удовлетворяющих указанным времен-
ным ограничениям. Такие структуры данных
описаны в [3, 5, 6].
Прежде всего покажем, что при выполнении
указанных требований один шаг расщеплений
по сплитеру (C, x) может быть реализован за
время O(|(x−1C)|). Ниже приведен возможный
вариант такой реализации.
Для каждого состояния q x−1C класс B,
содержащий q, отмечается как кандидат на ра-
сщепление, состояние q добавляется в список
состояний, удаляемых из B, и счетчик количе-
ства состояний в этом списке увеличивается на
единицу.
Отмеченный класс расщепляется, если ко-
личество состояний в списке отличается от
размера класса. При этом состояния, имею-
щиеся в списке, удаляются из класса B и обра-
зуют новый класс B′′.
Множество L реализуется так, что наличие в
нем рассматриваемого сплитера проверяется за
константное время, и сплитер добавляется и
удаляется также за константное время. Это по-
зволяет заменить сплитер B сплитерами B′ и B′′
за это же время, поскольку B′ представляет со-
бой модифицированный процедурой расщеп-
ления класс B, и достаточно добавить только
сплитер B′′.
С учетом всех замечаний приведем основ-
ную часть доказательства утверждения 5. Класс
из L, содержащий состояние q, назовем q-спли-
тером. Для некоторого выполнения алгоритма
рассмотрим последовательность q-сплитеров,
по которым осуществлялось расщепление. Ка-
ждый новый такой q-сплитер добавляется в L
УСиМ, 2016, № 3 67
только после удаления из L предшествовавше-
го q-сплитера в начале выполнения цикла рас-
щеплений по нему. Если расщепление класса
происходит до его удаления из L, то этот класс
не используется в качестве сплитера и в рас-
сматриваемую последовательность не входит.
Очевидно, что каждый последующий член
рассматриваемой последовательности по мощ-
ности не менее чем в два раза меньше преды-
дущего. Таким образом, количество q-сплите-
ров, по которым осуществлялось расщепление,
не превышает log n.
Утверждение 6. Суммарное количество со-
стояний во всех множествах вида x –1C, где
(C, x) – сплитер, по которому осуществлялось
расщепление, не превышает kn log n.
Доказательство. Рассмотрим какой-либо пе-
реход, скажем, из состояния q в состояние q,
соответствующий qxq ),( . Если (C, x) – q-
сплитер, то состояние q принадлежит x –1C.
Очевидно, что множествам x –1C, где (C, x) не
является q-сплитером, оно не принадлежит.
Ранее было показано, что количество q-спли-
теров, по которым проводилось расщепление,
не превышает log n. Таким образом, состояние
q может встречаться во множествах x –1C, где
(C, x) – q-сплитеры, по которым проводилось
расщепление, не более log n раз. Поскольку в
автомате имеется ровно kn переходов, то сум-
ма мощностей всех множеств x –1C не превос-
ходит kn log n. Заметим, что не для каждого
перехода в состояние q имеется q-сплитер, по
которому проводилось расщепление.
Итак, суммарное время выполнения всех
шагов расщепления ограничено сверху вели-
чиной O(kn log n). Исходя из аналогичных рас-
суждений, можно показать, что суммарное вре-
мя, затрачиваемое на построение всех множе-
ств вида x –1C, имеет такую же верхнюю оценку.
Временная сложность каждой из остальных
операций, время выполнения которых не опре-
деляется константой, оценивается как O(kn).
Следовательно, время работы всего алгоритма
оценивается сверху величиной O(kn log n).
Выполнение алгоритма недетерминировано,
поскольку выбор очередного сплитера из мно-
жества L может быть произвольным. Различные
стратегии этого выбора могут давать различное
время работы алгоритма, однако не изменяют
оценку его временной сложности. В работе [8]
показано, что эта оценка достижима для некото-
рого класса автоматов при определенной страте-
гии выбора элемента из множества L.
Реализация структур данных
Далее описаны структуры данных [6], удов-
летворяющие требованиям, необходимым для
получения приведенной ранее оценки времен-
ной сложности алгоритма.
Имена состояний и классов разбиений пред-
ставляются числами 0, 1, 2, ... Подмножества
множества Q представляются как сегменты
массивов фиксированной длины.
Отношение x–1(q) задается двумя матрица-
ми: inv_head и inv_elts.
inv_elts – (|X||Q|)-матрица элементов сегмен-
тов, соответствующих значениям x–1(q). В стро-
ках этой матрицы состояния перечислены в том
порядке, как они встречаются в таблице x–1(q).
inv_head – (|X||Q|)-матрица заголовков се-
гментов. Заголовок сегмента – это пара i, k,
где i – индекс в массиве inv_elts [x] первого
элемента сегмента, а k – количество элементов
сегмента, уменьшенное на еденицу. Этой паре
соответствуют поля first и size в записи, со-
стоящей из двух элементов.
Обратное отношение переходов x–1(q) для
примера 1 представлено таблицей:
Т а б л и ц а 2
0 1 2 3 4 5 6 7 8 9
a (02) (6) (38) (1459) (7)
b (5) (04) (12) (9) (3) (7) (68)
Для рассматриваемого примера матрица
inv_elts имеет вид
0 1 2 3 4 5 6 7 8 9
a 0 2 6 3 8 1 4 5 9 7
b 5 0 4 1 2 9 3 7 6 8
Таблица inv_head
0 1 2 3 4 5 6 7 8 9
a 0,1 2,0 3,1 5,3 9,0
b 0,0 1,1 3,1 5,0 6,0 7,0 8,1
68 УСиМ, 2016, № 3
Например, inv_elts [a][inv_head [a][8].first] =
= 7, где inv_head [a][8].first = 9.
Аналогично представляются и разбиения
множества Q.
cls_head – массив размера |Q| заголовков
классов разбиений. Индексами массива явля-
ются имена классов (0, 1, ...). Заголовок сег-
мента (класса) имеет четыре поля: first, size,
counter и move. В поле counter для класса B
подсчитывается количество состояний в x–1C
B, а в поле move строится список, представ-
ляющий множество x–1C B.
cls_elts – массив размера |Q| состояний, сег-
менты которого соответствуют классам.
Для разбиения 1 = {(01245), (38), (69), (7)}
соответствующие массивы имеют вид
Массив cls_elts
0 1 2 3 4 5 6 7 8 9
0 1 2 4 5 3 8 6 9 7
Массив cls_head
0 1 2 3 4 5 6 7 8 9
0,4,0 5,1,0 7,1,0 9,0,0
Здесь в заголовках поле move не представ-
лено.
Исходное разбиение 0 = {(0123458), (679)}
задается следующим образом:
Массив cls_elts
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 8 6 7 9
Массив cls_head
0 1 2 3 4 5 6 7 8 9
0,6,0 7,2,0
Каждому состоянию q Q соответствует
класс, которому оно принадлежит. Это соот-
ветствие задается массивом states, каждый
элемент states[q] которого содержит следую-
щие поля:
cls_of – номер соответствующего класса и
idx_of – индекс состояния q в соответству-
ющем сегменте массива cls_elts.
Для разбиения 1 = {(01245), (38), (69), (7)}
массив states имеет вид
0 1 2 3 4 5 6 7 8 9
0,0 0,1 0,2 1,5 0,3 0,4 2,7 3,9 1,6 2,8
Классы исходного разбиения 0 = {F, Q\F}
нумеруются соответственно числами 0 и 1.
При расщеплении класса 0 получаются клас-
сы 0 и 2, а при расщеплении класса 1 – 1 и 3. Та-
ким образом, значения номеров классов не пре-
вышают |Q| –1.
Минимизация автоматов Мура и Мили
Автоматы рассматриваемых классов имеют
следующий вид:
Автомат Мура ,,,, YQXA , где X, Q,
Y – соответственно входной алфавит, множест-
во состояний и выходной алфавит, :Q X
Q – функция переходов, – функция выхо-
дов (отметок состояний).
Автомат Мили ,,,, YQXA , где X, Q,
Y, – то же, что и выше, а функция выходов
имеет вид : Q X Y.
Поскольку задача минимизации автомата
основывается на понятии эквивалентности со-
стояний, приведем соответствующие опреде-
ления для рассматриваемых автоматов.
Для автомата Мура q1 q2, если w X*
(*(q1, w)) = (*(q2, w)).
Для автомата Мили q1 q2, если w X*
*(q1, w)) = *(q2, w)). Здесь *(q, x1 x2... xm)) =
= (*(q, x1 x2... xm–1), xm), где x1 x2... xm X*.
Для того чтобы по эквивалентности ~ на
множестве Q можно было построить мини-
мальный автомат, она должна быть конгруэн-
цией. Соответствующие конгруэнции для ав-
томатов Мура и Мили определяются следую-
щими требованиями.
Для автомата Мура из q1 q2 следует
1 2( ( , ) ~ ( , ))x X q x q x и )()( 21 qq , т.е.
все состояния в каждом классе эквивалент-
ности должны быть отмечены одним и тем
же выходным сигналом. Для автомата Мили
из q1 q2 следует 1 2( ( , ) ~ ( , ))x X q x q x и
)),(),(( 21 xqxqXx . Пусть множество X
линейно упорядочено, т.е. X = kxx ,,1 . Для
каждого q Q рассмотрим вектор 1( , ,q x
УСиМ, 2016, № 3 69
, ( , )kq x , который обозначим )(q , тогда
вторую часть условия конгруэнтности для авто-
мата Мили можно записать так: из q1 q2 сле-
дует )()( 21 qq , т.е. для всех состояний,
принадлежащих одному и тому же классу кон-
груэнции, векторы )(q должны совпадать. Та-
ким образом, каждый класс начального разби-
ения 0 в алгоритме Хопкрофта для автомата
Мура определяется значением выходного сиг-
нала на его состояниях, а для автомата Мили –
значением вектора )(q . Итак, для автомата-
распознавателя |0| = 2, для автомата Мура
|0| = k , для автомата Мили |0| |Y|k. С этим же
связано и различие в начальных значениях мно-
жества L, которое состоит из всех, кроме одного,
элементов начального разбиения. Остальная
часть алгоритма для всех случаев совпадает. Ес-
ли время построения начального разбиения мно-
жества оценивается как O(kn), то оценка вре-
менной сложности алгоритма для всех рассмот-
ренных видов автоматов будет одной и той же.
Пример 2. Автомат Мили задан следующи-
ми таблицами переходов и выходов.
Т а б л и ц а 3
1 2 3 4 5 6 7 8
x 1 2 1 2 1 1 2 1
y 8 8 7 2 2 3 5 4
z 4 5 7 5 4 6 3 3
Т а б л и ц а 4
1 2 3 4 5 6 7 8
x u u u v v v u u
y v v v u u u u u
z u u u v v v v v
Как следует из таблицы выходов, имеется
три класса: (123), (456), (78), составляющих
исходное разбиение 0.
Построим таблицу, задающую отношение
x–1(q), обратное отношению переходов.
Т а б л и ц а 5
1 2 3 4 5 6 7 8
x 1,3,5,6,8 2,4,7
y 4,5 6 8 7 3 1,2
z 7,8 1,5 2,4 6 3
Итак, 0 = {(123), (456),(78)}. Пусть значе-
ние L0 равно {(123), (456)}.
Первый цикл: C = (123)
x–1(123) = Q, y–1(123) = (456), z–1(123) = (78).
Ни один класс не расщепляется.
1 = {(123), (456),(78)}, L1 = {(456)}.
Второй цикл: C = (456).
x–1(456) = , y–1(456) = (78), z–1(456) = (12456).
Расщепляется класс (123) (12), (3).
2 = {(12), (3), (456), (78)}, L2 = {(3)}
Третий цикл: C = (3).
x–1(3) = , y–1(3) = (6), z–1(3) = (78).
Расщепляется класс (456) (45), (6).
3 = {(12), (3), (45), (6), (78)}. L3 = {(6)}.
Четвертый цикл: C = (6).
x–1(6) = , y–1(6) = (), z–1(6) = (6).
Ни один класс не расщепляется.
4 = {(12), (3), (45), (6), (78)}, L4 = .
На этом работа алгоритма заканчивается.
После перенумерации состояний получаем ав-
томат, задаваемый следующими таблицами пе-
реходов и выходов.
Т а б л и ц а 6
1 2 3 4 5
x 1 1 1 1 1
y 5 5 1 2 3
z 3 5 3 4 2
Т а б л и ц а 7
1 2 3 4 5
x u u v v u
y v v u u u
z u u v v v
Заключение. Работа посвящена описанию и
анализу алгоритма минимизации конечных де-
терминированных вполне определенных автома-
тов, предложенного Дж. Хопкрофтом в 1971 г.
Из-за того, что в оригинальной работе Хоп-
крофта дано довольно громоздкое и недоста-
точно строгое описание как самого алгоритма,
так и его обоснования, появился ряд последую-
щих работ, в которых уточнялся алгоритм и да-
валось более строгое обоснование его коррект-
ности. Учитывая практическое отсутствие рус-
70 УСиМ, 2016, № 3
скоязычных работ такого рода, в настоящей ста-
тье сделана еще одна попытка дать довольно
простое обоснование как корректности алгорит-
ма, так и оценки его временной сложности.
Рассмотрен один из вариантов алгоритма, в
котором в качестве элементов списка сплите-
ров, по которым следует проводить расщепле-
ния, используются классы разбиений, а не па-
ры (класс, входной символ), как в оригиналь-
ном алгоритме и в ряде последующих публи-
каций. Приведено достаточно простое доказа-
тельство основной леммы (лемма 1), на кото-
рой основано получение временной сложности
O(kn log n). Из этой же леммы следует, что на-
чальное значение L0 множества L состоит из
одного класса, если множество Q рассматри-
вать как его тривиальное разбиение. Для обос-
нования одного из условий корректности алго-
ритма предложено использовать бинарное де-
рево расщеплений и метод распространения за-
крытых состояний. Поскольку полученная Хоп-
крофтом оценка временной сложности налагает
некоторые ограничения на реализацию алго-
ритма, в настоящей статье приведена форму-
лировка этих ограничений и возможный вари-
ант подходящей реализации используемых
структур данных.
1. Huffman D.A. The synthesis of sequential switching
circuits // J. Franklin Inst. – 1954. – 257, N 3. –
P. 161–190; N 4. – P. 275–303.
2. Moore E.F. Gedanken-experiments on sequential Ma-
chines // Automata studies, Princeton Univ. Press,
Princeton, N.J., 1956. – P. 129–153.
3. Hopcroft J. An n log n algorithm for minimizing states
in a finite automaton / Z. Kohavi, A. Paz (Eds.) // Proc.
Internat. Symp. on the Theory of Machines and Compu-
tations, Academic Press, New York, 1971. – P. 189–196.
4. Gries D. Describing an algorithm by Hopcroft // Acta
Inform. – 1973. – N 2. – P. 97–109.
5. Брауэр В. Введение в теорию конечных автоматов. –
М.: Радио и связь, 1987. – 392 с.
6. Knuutila T. Re-describing an algorithm by Hopcroft. //
Theoret. Comput. Sci. – 2001. – 250. – P. – 333–363.
7. Baclet M., Pagetti C. Around Hopcroft’s algorithm //
Lecture Notes in Comp. Sci. – 2006. – 4094, Springer-
Verlag. – P. 114–125.
8. Berstel J., Carton O. On the complexity of Hopcroft’s
state minimization algorithm // Ibid. – 2005 / – 3317,
Springer-Verlag. – P. 35–44.
Поступила 11.03.2015
Тел. для справок: +38 044 525-3677; 526-3204 (Киев)
E-mail:ancheb.@gmail.com
© А.Н. Чеботарев, 2016
UDC 519.713
A.N. Chebotarev
On Automata Minimization by Hopcroft’s Algorithm
Keywords: Hopcroft’s algorithm, automaton minimization, partition, congruence, time complexity, splitting tree.
The algorithm for minimizing deterministic complete finite state automata proposed by J. Hopcroft is considered. Al-
though the existence of this algorithm is widely known, its theoretical justification is not that obvious. The aim of this study
is to give a clear and understandable presentation of the algorithm focusing on the firm theoretical basis, rigorous correctness
proof and time complexity analysis.
The algorithm is based on the partition notion of the automaton states which defines the equivalence relation. It constructs
a sequence of such partitions by a stepwise refinement of some initial partition. The last partition in this sequence corre-
sponds to the maximal congruence on the automaton’s states, i.e., the equivalence stable with respect to the transition func-
tion of the automaton. To prove correctness of the algorithm it is necessary to show that the final constructed partition is a
congruence, and that this congruence is maximal. In the first part of this proof, the introduced notion of binary splitting tree is
used whose nodes are classes of the partitions constructing by the algorithm and a technique for extending the so called
“closed” nodes of this tree. The second part is based on the proposition concerning the order on partitions. It is proved that
every partition in the sequence generated by the algorithm is greater than or equal to the partition corresponding to the maxi-
mal congruence.
It is show that Hopcroft’s algorithm can be implemented to worst-case time complexity O(kn log n) for an automaton with n
states over a k-letter alphabet. This statement relies on the fact that the total number of actions refining the partitions over all
steps of algorithm execution is of the order of O(kn log n). The data structures which allow obtaining this time complexity is
presented. The last section describes the algorithm features for minimizing Moore and Mealy automata.
<<
/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
|