Модифицированная алгебра алгоритмов и инструментальные средства обработки формул алгебры алгоритмов
Для решения задач повышения эффективности обработки структур данных и формул алгоритмов аксиоматическим методом определены алгебры секвенционных алгоритмов первого и второго порядков, использование которых показано на примерах. Описаны эффективные инструментальные средства компьютерного синтеза и оп...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2013
|
| Schriftenreihe: | Управляющие системы и машины |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/83126 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Модифицированная алгебра алгоритмов и инструментальные средства обработки формул алгебры алгоритмов / А.В. Овсяк, В.К. Овсяк // Управляющие системы и машины. — 2013. — № 1. — С. 27-36. — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-83126 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-831262015-06-16T03:44:57Z Модифицированная алгебра алгоритмов и инструментальные средства обработки формул алгебры алгоритмов Овсяк, А.В. Овсяк, В.К. Новые методы в информатике Для решения задач повышения эффективности обработки структур данных и формул алгоритмов аксиоматическим методом определены алгебры секвенционных алгоритмов первого и второго порядков, использование которых показано на примерах. Описаны эффективные инструментальные средства компьютерного синтеза и оптимизации формул алгоритмов. The algebra of sequential algorithms of the first and second order are defined to solve the problems of improvement of the efficiency in processing the data structures and the formulas of algorithms by means of the axiomatic method. The application of the algebras is illustrated by means of the examples. The derived effective tools of computer aided synthesis and the optimization of formulas of algorithms are briefly described. Для розв’язання задач підвищення ефективності опрацювання структур даних і формул алгоритмів аксіоматичним методом означено алгебри секвенційних алгоритмів першого та другого порядків, застосування яких проілюстровано прикладами. Описано створені ефективні інструментальні засоби комп’ютерного синтезу та оптимізації формул алгоритмів. 2013 Article Модифицированная алгебра алгоритмов и инструментальные средства обработки формул алгебры алгоритмов / А.В. Овсяк, В.К. Овсяк // Управляющие системы и машины. — 2013. — № 1. — С. 27-36. — Бібліогр.: 18 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/83126 004.421 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| 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 |
2013 |
| topic_facet |
Новые методы в информатике |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/83126 |
| citation_txt |
Модифицированная алгебра алгоритмов и инструментальные средства обработки формул алгебры алгоритмов / А.В. Овсяк, В.К. Овсяк // Управляющие системы и машины. — 2013. — № 1. — С. 27-36. — Бібліогр.: 18 назв. — рос. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT ovsâkav modificirovannaâalgebraalgoritmoviinstrumentalʹnyesredstvaobrabotkiformulalgebryalgoritmov AT ovsâkvk modificirovannaâalgebraalgoritmoviinstrumentalʹnyesredstvaobrabotkiformulalgebryalgoritmov |
| first_indexed |
2025-07-06T09:51:14Z |
| last_indexed |
2025-07-06T09:51:14Z |
| _version_ |
1836890691685318656 |
| fulltext |
УСиМ, 2013, № 1 27
УДК 004.421
А.В. Овсяк, В.К. Овсяк
Модифицированная алгебра алгоритмов и инструментальные средства
обработки формул алгебры алгоритмов
Для решения задач повышения эффективности обработки структур данных и формул алгоритмов аксиоматическим методом опреде-
лены алгебры секвенционных алгоритмов первого и второго порядков, использование которых показано на примерах. Описаны эф-
фективные инструментальные средства компьютерного синтеза и оптимизации формул алгоритмов.
The algebra of sequential algorithms of the first and second order are defined to solve the problems of improvement of the efficiency in processing
the data structures and the formulas of algorithms by means of the axiomatic method. The application of the algebras is illustrated by means of the
examples. The derived effective tools of computer aided synthesis and the optimization of formulas of algorithms are briefly described.
Для розв’язання задач підвищення ефективності опрацювання структур даних і формул алгоритмів аксіоматичним методом
означено алгебри секвенційних алгоритмів першого та другого порядків, застосування яких проілюстровано прикладами.
Описано створені ефективні інструментальні засоби комп’ютерного синтезу та оптимізації формул алгоритмів.
Введение и формулирование задач исследо-
вания. Информационные технологии интен-
сивно развиваются и нашли практическое при-
менение в различных сферах человеческой дея-
тельности. Математической основой информа-
ционных технологий есть теория алгоритмов.
Наиболее известными и наиболее часто исполь-
зуемыми методами описания алгоритмов есть
вербальный и блок-схемный методы. Кроме них
известны и другие методы, которые по исполь-
зуемым ими средствам можно разбить на две
группы. Это методы, не использующие алгебра-
ическую методологию и методы, которые ее ис-
пользуют. Исторически неалгебраические мето-
ды появились первыми. К ним, кроме упомяну-
тых вербального и блок-схемного представления
алгоритмов, принадлежат и такие, как методы ре-
курсивных функций [1], исчисления лямбда [2],
виртуальных машин Тьюринга [3] и Поста [4],
алгоритмов Маркова [5], машин Колмогорова
[6], Шенхаге [7], Ахо–Улльмана–Хопкрофта [8]
и универсальных алгоритмов Криницкого [9].
Известно [10, 11], что алгебраическими ме-
тодами описания алгоритмов служит система
алгебраических алгебр Глушкова, модифициро-
ванная система алгебраических алгебр (алгеб-
ра алгоритмов Цейтлина), алгебры Дейкстры,
Калужнина и Янова, а каждая из них имеет со-
ответствующий клон. Алгебра алгоритмики –
это двухуровневая система с неинтерпретиро-
ванными схемами верхнего уровня и необхо-
димостью построения прикладных алгебр на
нижнем уровне [12].
Алгебраические в сравнении с неалгебраи-
ческими методами описания алгоритмов имеют
то преимущество, что над формулами алгорит-
мов могут быть автоматически выполнены то-
ждественные преобразования на основе свойств
операций, как над произвольными математи-
ческими выражениями. Результаты этих пре-
образований – уменьшение затрат памяти на
сохранение и времени на выполнение.
Исследованием [13] начато формирование
метода описания алгоритмов, который базиру-
ется на идее создания операций упорядочения
на базе индексов. Метод со временем развит до
прикладной алгебры секвенционных алгорит-
мов [14]. Многолетняя практика использования
прикладной алгебры секвенционных алгорит-
мов в разных областях науки и техники пока-
зала целесообразность упрощения алгоритмов,
что обеспечивает сокращение затрат на реали-
зацию алгоритмов. Результаты практики исполь-
зования послужили основанием для развития
специализированной алгебры секвенционных
алгоритмов, рассмотренной в настоящей статье.
Алгебра секвенционных алгоритмов пер-
вого порядка
Систему обозначений образуют: – сек-
венцирование; – элиминирование; –
реверсирование; – параллелирование; пе-
ременные: A, B, С, …; логические переменные:
u,uo ,…, uj , u
i
j ,…; – пустой знак; разделители
переменных (запятая, точка с запятой и двоето-
чие); индексы порядка α и β.
28 УСиМ, 2013, № 1
В определениях двоеточие как разделитель
может быть заменено запятой или точкой с за-
пятой.
Определение 1. Операция, обладающая свой-
ствами: идемпотентности: поглощения
пустого знака: ; коммутативности:
; ассоциативности:
поглощения упорядоченных переменных:
, – по-
глощения переменной логическим значением
0: поглощения логического значения
1: образования пар с одинаковыми
индексами порядка: ; об-
разования пар с различными индексами поряд-
ка: {{X, α}, {Y, β}} называется секвенци-
рованием.
Определение 2. Операция, обладающая
свойствами: идемпотентности: ; по-
глощения пустого знака: ; коммута-
тивности: ; ассоциативности:
; выноса переменной:
= , – поглощения
логического значения: – образования
пар с одинаковыми индексами порядка:
; образования пар с
различными индексами порядка:
= } называется параллелированием.
Определение 3. Операция, обладающая свой-
ствами: выбора переменной:
где v0, v1, … vn–1 – значения w; идемпотентно-
сти: = X; выбора логи-
ческой переменной: =
= дистрибутивности:
= ,
= =
= , =
= поглощения пере-
менной: =
=
=
=
называется элиминированием.
Определение 4. Операция, обладающая
свойствами: преобразования секвенцирования:
; преобразования параллелирова-
ния: u1: u2=u1: u2; двойного преобразования:
отрицания элиминирования:
= =
= – замены 0: 0 = 1; образова-
ния логического значения 0: связи
операций , называется ре-
версированием.
Определение 5. Переменные или их значе-
ния с приписанными им операциями секвенци-
рования, элиминирования и параллелирования
индексами порядка называются унитермами.
Определение 6. Формулой (структурой) есть
только такое выражение, для которого это мож-
но показать применением конечного количест-
ва раз пп. 1–3:
1. Если X и Y – сменные или унитермы, то
и – формулы;
2. Если A, B, …, Z – переменные, унитермы
или формулы, а u, w – унитермы условий, то
, , – фор-
мулы;
3. Если A, B, Q, L, ..., T – унитермы или
формулы, а u, w – унитермы
условий, то , , , ,
– формулы.
X; Y =
X; Y; …Z; w-?=
X, если (w = v0) –?,
Y, если (w ≠ v0)&(w = v1),
…
Z, если (w≠v0)&(w≠v1)&…(w≠vn – 1);
B; A; u-?,
A; B; u-?,A: B A: B BA
X; Y; u–? =
X, если u = 1,
Y, если u = 0;
X; 1 =X;
X: 0 = X;
u, u = 0;
A;C;K;…I;w-?,
X; X;…X; w-?
X: Y, Z =
X, Y, Z;
X; Y, Z;
X: 0 =0;
{{X, γ},{Y, δ}
X, Y ={{X, γ}, {Y, γ}}
X, Y ={{X, α}, {Y, α}}
B; A; …; Z; w - ?B; A; u - ?A; B; u-?
X: YX: Y
X; Y; u-?=u;X, u;Y
R; S; …; Z; w-?;
R; S; …; Z; w-?u1; u2; u3-?, u1; u2; u3-?
u = u;
u1: u2=u1:u2
A; B; …Z; I; w-?,A; B; …Z; Q; L; …I; w-?; w-?
A; B; …Z; w-?; C; K; …I; w-?
X; Z; u-? , X; Y; u - ?; Z; u-?
X; Z; u-? ,X; Y; Z; u - ?; u-?
A; C; …; N; w-?: B;
A:B; C:B; …; N:B; w-?A: B; C; …; N; w-?
A:B; A:C; … A:N; w-?S; T; u-?: R ,
S: R; T; R; u-? R: S; T; u-? R: S; R: T; u-?
X; Y; u1-?; u2-?; u3-?;
X; Y; u1-?; X; Y; u2-?; u3-?
X; X; u-?=X,
X: Z, Y: Z = X, Y: Z; X: Y, X: Z
X, Y, Z = X, Y, Z
X, Y = Y, X
*, X = X
X, X = X
X; Y, X; Z =X; Y, Z; Y = X, Z; Y
X, Y, Z = X, Y = Y, X
*: X = X
X, X =X;
X; Y =
УСиМ, 2013, № 1 29
Переменные формул могут заменятся пе-
ременными или формулами одновременно
всюду, где они входят в формулу, в которой
выполняется замена.
Алгеброй секвенционных алгоритмов
первого порядка есть система операций сек-
венцирования, элиминирования, параллелиро-
вания и реверсирования над переменными,
унитермами и формулами.
Пример 1. Пусть переменные X и Y прини-
мают значения из секвенционной области
и упорядочиваются индексами поряд-
ка α и β. В этом случае переменным X и Y опе-
рациями секвенцирования и параллелирования
могут быть приписаны индексы Xα, Yα, Xβ и Yβ.
В предложенных определениях операций для
большей наглядности формул, индексы упоря-
дочений переменных опущены, а в табл. 1 они
заданы явно. Для ориентации упорядочений
α β (возможна противоположная ориентация, а
именно β α, реверсивная к предыдущей ориен-
тации) заданы все возможные значения индек-
сированных переменных и некоторые возмож-
ные упорядочения.
Элементы секвенционной логики [15]
Определение 7. Операция, обладающая свой-
ствами: идемпотентности: ; комму-
тативности: = ; образования
логического значения: = 0; выэлими-
нирования операции: = 0; ассоциатив-
ности: = ; получения
переменной: = X, назовем секвенцион-
ной конъюнкцией.
Определение 8. Операция, обладающая свой-
ствами: идемпотентности: ; коммута-
тивности: = ; образования ло-
гического значения: ; выэлиминиро-
вания операции: ; выэлиминирования
значения: ; ассоциативности:
= ; дистрибутивности:
= , называется сек-
венционной дизъюнкцией.
Определение 9. Операция, обладающая свой-
ствами: получения из секвенционной конъюнк-
ции секвенционной дизъюнкции: =
= ; образования логического значения
0: ; двойного преобразования: , на-
зывается секвенционным инвертированием.
Секвенционная логика – это система опе-
раций секвенционных конъюнкций, дизъюнк-
ции и инвертирования над секвенционными ло-
гическими значениями и переменными.
В табл. 1 представлены истинностные зна-
чения секвенционных операций конъюнкции и
дизъюнкции над упорядоченными логическими
переменными и значениями.
Теорема 1. Имеется формула:
Доказательство. Пусть секвенционная пе-
ременная u имеет значение 1. Тогда из конъ-
юнкции заменой переменной u ее зна-
чением 1 получим формулу , из которой
на основании свойства получения переменной
операции конъюнкции выведем X. Из секвен-
ционной конъюнкции подстановкой
вместо переменной u ее значения 1 выводим
формулу . Отсюда на основании преоб-
разования логического значения операции сек-
венционного инвертирования выводим ,
откуда, использовав свойство выэлиминирова-
ния операции секвенционной конъюнкции, по-
лучаем ноль. Подставляя полученные значения
секвенционных конъюнкций в секвенционную
дизъюнкцию формулы утверждения, выводим
выражение . Отсюда, используя свойство
выэлеминирования значения операции секвен-
ционной дизъюнкции, получаем X. Получен-
ная переменная совпадает с переменной опре-
деления операции элиминирования на основа-
нии свойства выбора переменной по логиче-
ской переменной. При u = 0 аналогично выво-
дится совпадение переменной Y. Теорема до-
казана.
Пример 2. Известен [10] «пузырьковый»
алгоритм для сортирования массива. Рассмот-
рим, как сортирование массива 5 2 3 1. 4 может
быть описано с использованием алгебры сек-
венционных алгоритмов. Цифра 1 с точкой оз-
начает, что это – число десятичной системы.
X; 0
& 0; X
& 1; X
& u; X
& 1; X
& u; X
X; Y; u - ? = & u,
;
Y
& u
;
Y.
u = u0 = 1
u0: u1
& u0:u1
& u: u0, u1 & u: u0, & u: u1
u0, u1, u2 u0, u1, u2
u, 0 = u
u, 1 = 1
u, u = 1
u0, u1 u1, u0
u, u = u
& X: 1
& & u0, u1, u2 & u0, & u1, u2
& u: 0
& u: u
& u1, u0 & u0, u1
& u, u = u
Q = 0, 1
30 УСиМ, 2013, № 1
Сначала опишем этот массив в виде формулы
алгебры секвенционных алгоритмов с исполь-
зованием операции секвенцирования, что обу-
словлено одновременным наличием всех эле-
ментов массива, которые разделим запятой:
. Применив к ней свойство ассо-
циативности операции секвенцирования, вы-
ведем формулу , к которой приме-
ним свойство коммутативности операции сек-
венцирования, что дает . К полу-
ченному выражению еще семь раз применим
свойства ассоциативности и коммутативности,
в результате чего получим отсортированный
массив . Описанные преобразова-
ния тождественны, что можно записать как:
= = = … =
= .
Рассмотренный пример иллюстрирует воз-
можности использования алгебры секвенцион-
ных алгоритмов для описания и преобразова-
ния структур данных.
Алгебра секвенционных алгоритмов вто-
рого порядка. Систему обозначений образу-
ют: знаки алгебры алгоритмов первого поряд-
ка; циклического секвенцирования (); цикли-
ческого элиминирования ( ); циклического
параллелирования (Ø); знака равенства (=);
функциональные переменные F(a), ,
, …, зависящие от индивидных пере-
менных a, b, …, упорядоченных операциями
секвенцирования и параллелирования.
Операция равенства имеет известное опре-
деление (X = X, если X = Y, то Y = X, если X = Y,
а Y = Z, то X = Z).
Определение 10. Операция со свойствами:
реверсирования: = ; секвен-
цирования: = , для
xQ = ; пустого цикла: , на-
зовем циклическим секвенцированием.
Индивидные переменные, расположенные
под знаками циклических операций, названы
связанными этими операциями, а не связанные
переменные – свободными.
Определение 11. Операцию со свойствами:
реверсирования: = ; парал-
лелирования: Ø x F(x) = , для
x Q = ; пустого цикла: ,
назовем циклическим параллелированием.
Определение 12. Операцию со свойствами:
элиминирования: =
= , для xQ =
1., 2, 3, 4, 5
2, 5, 3, 1., 4 5, 2, 3, 1., 45, 2, 3, 1., 4
1., 2, 3, 4, 5
2, 5, 3, 1., 4
5, 2, 3, 1., 4
5, 2, 3, 1., 4
F(i); F(j); F(k); … uk - ?; uj - ?; ui - ?
ux F(x)
Ø x *x = *i: j: k: …
i: j: k: …
F(i): F(j): F(k): …
x F(x) Ø x F(x)
F(i): F(j): F(k): … x F(x)
Ø x F(x) x F(x)
H k; p, r
G a; c
Т а б л и ц а 1. Упорядочения операциями секвенцирования, параллелирования и операции секвенционной логики
Индексы
Переменные
№
Xα Yα Xβ Yβ
0 0 0 0 0 0 1 1 0 0 0 1 1
1 0 0 0 1 0 1 1 0 0 1 1 1
2 0 0 1 0 0 1 1 0 0 0 1 1
3 0 0 1 1 0 1 1 0 0 1 1 1
4 0 1 0 0 0 1 1 0 0 0 1 1
5 0 1 0 1 0 1 1 0 0 1 1 1
6 0 1 1 0 0 1 1 0 1 0 1 1
7 0 1 1 1 0 1 1 0 1 1 1 1
8 1 0 0 0 0 1 1 0 0 1 1 1
9 1 0 0 1 0 1 1 1 0 1 0 0
10 1 0 1 0 0 1 1 0 0 1 1 1
11 1 0 1 1 0 1 1 1 0 1 0 0
12 1 1 0 0 1 0 0 0 0 1 1 1
13 1 1 0 1 1 0 0 1 0 1 0 0
14 1 1 1 0 1 0 0 0 1 1 1 1
15 1 1 1 1 1 0 0 1 1 1 0 0
X,Y&X;Y X,Y &Y;X&X;YXα,YαXα,YαXα,Yα
x *x = *
УСиМ, 2013, № 1 31
= ; пустого цикла: , назовем
циклическим элиминированием.
Определение 13. Функциональные перемен-
ные, упорядоченные операциями секвенциро-
вания, элиминирования, параллелирования, цик-
лическим секвенцированием, элиминировани-
ем и параллелированием – функциональные
унитермы.
Определение 14. Алгоритм это выражение,
для которого необходимо применить пп. 1–5
конечное количество раз:
1. Если D, K – переменные или функцио-
нальные унитермы или формулы, то и
D = K – алгоритмы.
2. Если и – функцио-
нальные унитермы, зависящие от одной или
нескольких индивидных переменных, то
и –
алгоритмы.
3. Если , , …,
– функциональные переменные или алгорит-
мы, а u, w – унитермы условий, то
,
и – алго-
ритмы.
4. Если , , ,
, …, – логические функцио-
нальные унитермы или алгоритмы, а u, w –
унитермы условий, то , ,
, ,
,
и ,
– ал-
горитмы.
5. Если x, a, … – переменные, –
функциональный унитерм или алгоритм, а
– логическим функциональным уни-
термом или алгоритмом, то ,
, , и
, – алгоритмы.
В алгоритмах могут выполняться замены пе-
ременных их значениями, переменными, фор-
мулами и алгоритмами одновременно всюду,
где заменяемые переменные входят в алгоритм,
которым выполняется замена. Индивидные пе-
ременные функциональных унитермов могут
одновременно во всех вхождениях заменяться
их значениями или другими индивидными пе-
ременными. Функциональные переменные с не-
связанными операциями циклов индивидными
переменными могут одновременно во всех вхож-
дениях в алгоритм заменятся другими функ-
циональными унитермами с количеством не-
связанных переменных, не меньшим заменяе-
мого функционального унитерма. Связанные
операциями циклов индивидные переменные
могут одновременно во всех вхождениях заме-
нятся другими несвязанными индивидными пе-
ременными.
Алгеброй алгоритмов второго порядка есть
система операций секвенцирования, элимини-
рования, параллелирования, реверсирования, ра-
венства и операций циклов над унитермами.
Пример 3. Использование алгебры секвен-
ционных алгоритмов для синтеза и исследова-
ния алгоритмов рассмотрим на примере алго-
ритма Евклида для вычисления наибольшего об-
щего делителя двух натуральных чисел x и y.
Пусть N – секвенционная область нату-
ральных чисел (N = ). Проверку при-
надлежности введенных () переменных x и y
к натуральным числам запишем как и
. Для x и y должно выполняться соотно-
шение . Выполнение этих трех условий
обязательно, что запишем так:
,
(1)
где a и b – введенные значения переменных x и
y; *K0, *K1 и *K2 – сообщения о невыполнении
условий; – поиск наибольшего общего
делителя вычислением остатка от деления x на
F x: a: …
F x; y
← x; a;
← y; b; *K0; x; N - ? ;
F x; y; *K2; > x; y - ?; *K1; y; N - ?
> x; y
y, N
x, N
1, 2, …
x F x: a: …
x F x: a: …
Ø x F x: a: …
Ø xА x: a: … xА x: a: …
x А x: a: …
F x: a: …
Q q: p: …; L g: h: …; …, T r: k: …; w - ?
Q q: p: …; L g: h: …; …, T r: k: …; w - ?
B c: d: …; A a: b: …; u-?A a: b: …; B c: d: …; u-?
A a: b: … : B c: d: …A a: b: … : B c: d: …
B c: d: …A a: b: …
T r: k: … L g: h: …
Q q: p: …B c: d: … A a: b: …
A a: b: …; B c: d: …; … ; Z k: f: …; w - ?
B c: d: …; A a: b: …; u-?A a: b: …; B c: d: …; u-?
Z k: f: … B c: d: … A a: b: …
F a: b: … : P c: d: …F a: b: … : P c: d: …
P c: d: … F a: b: …
x *x = * i: j: k: …
= D; K
32 УСиМ, 2013, № 1
y, что запишем как , где % – обозначение
функционального унитерма поиска остатка от
деления. Приписывание остатка переменной r
имеет вид . Проверка значения остат-
ка на неравность нулю имеет такое описание
. Если остаток не равен нулю, то пере-
менной x приписывается значение переменной
y ( ), а переменной y – значение остатка r
( ), и происходит возврат в цикл на вы-
числение нового остатка от деления. Если же
остаток равен нулю, то делитель и есть иско-
мым наибольшим общим делителем ( ).
Этот процесс описывается формулой алгорит-
ма
(2)
Подстановка формулы (2) в выражение (1)
дает такую формулу
Полученной формулой опишем поиск наи-
большего общего делителя для отдельных зна-
чений переменных x и y. Для того чтобы она
описала поиск наибольшего общего делителя
для всех натуральных чисел, ее индивидные
переменные x и y необходимо связать опера-
циями циклов. Индивидные переменные x и y
свяжем операцией циклического секвенциро-
вания, а индивидную переменную r – операци-
ей циклического элиминирования, что даст та-
кую формулу алгоритма:
(3)
Теорема 2. Формула (3) описывает алго-
ритм выполнения условий и вычисление наи-
большего общего делителя всех натуральных
чисел.
Доказательство. Условиями есть принад-
лежность индивидных переменных x и y к нату-
ральным числам, и то, что значение x больше
значения y. Если не выполняется хотя бы одно
из условий, например, , то на основании
теоремы 1 из формулы (1) получаем выраже-
ние, которое в дальнейшем преобразуется с
учетом свойств операций секвенционных конъ-
юнкций, дизъюнкции и инвертирования:
=
= =
= =
Первая после знака равенства формула по-
лучается в результате замены условного сек-
венционного унитерма его значением –
нулем, а его инвертирование дает единицу. По-
лученный алгоритм содержит присвоенное пе-
ременной x введенное значение и сообщение
*K0 о том, что значение x не есть натуральным
числом. Таким образом, алгоритмом есть не-
= r; % x; y
;
= x; y; = n; y; ≠ r; 0 - ?
;
= x; r
F x; y = r
x; N
← x; a;
*K0.
← x; a;
0, *K0,
← x; a;
& 0, ← y; b, & 1; *K0,
F x; y; *K2; > x; y - ?; *K1; y; N - ?
← x; a;
& x; N, ← y; b, & x; N; *K0,
F x; y; *K2; > x; y - ?; *K1; y; N - ?
x; N
x y
← x; b;
← y; b; *K0; x; N - ? ;
r; *K2; > x; y - ?; *K1; y; N - ?
= r; % x; y
;
= x; y; = n; y; ≠ r; 0 - ?
;
= x; r
← x; b;
← y; b; *K0; x; N - ? ;
r; *K2; > x; y - ?; *K1; y; N - ?
= r; % x; y
;
= x; y; = n; y; ≠ r; 0 - ?
;
= x; r
= n; y
= y; r
= x; y
≠ r; 0
= r; % x; y
% x; y
УСиМ, 2013, № 1 33
выполнение условия. Аналогично устанавли-
вается невыполнение остальных условий.
Теперь рассмотрим случаи, когда условия
выполняются. В таком случае из формулы (1)
получим
аналогично тому, как при невыполнении усло-
вий. Секвенцирование полученного выражения
с формулой (2) – второй частью формулы (3),
дает формулу, которая и есть алгоритмом по-
иска наибольшего общего делителя двух нату-
ральных чисел. Доказательство второй части
теоремы выполним на основе метода трансфи-
нитной математической индукции [15, 16].
Сначала покажем, что формула (3) описы-
вает поиск наибольшего общего делителя для
начальных значений переменных x и y. На-
чальными значениями x и y есть два и 1. (деся-
тичный знак). Подстановка этих значений в
алгоритм (3) дает формулу
Очевидно, что унитерм принимает ну-
левое значение, а путем элиминирования по
этим условиям получаем , что показыва-
ет приписывание переменной значение наиболь-
шего общего делителя, равное единице. Следо-
вательно, для начальных значений переменных
формула (3) корректно описывает вычисление
наибольшего общего делителя.
Аналогично устанавливается описание фор-
мулой (3) наибольшего общего делителя для
произвольных значений переменной x и на-
чального значения переменной y.
Выполним анализ алгоритма для i-го зна-
чения индивидной переменной x и j-го значе-
ния индивидной переменной y. Первая часть
алгоритма (3) – формула (1), проанализирован-
ная ранее, и для данных значений индивидных
переменных она не отличается. Относительно
ее второй части – формулы (2), то после под-
становки значений переменных для первой
итерации получим
Если значением функционального унитерма
eсть 0, то этот случай уже рассмотрен –
наибольшим общим делителем есть j. Если же
= 1, то имеем выражение
которое описывает приписывание переменной
x значения j, а переменной y – значения r. Та-
кое задание значений переменных связано с тем,
что наибольший общий делитель следующей
итерации не может быть большим остатка те-
кущей итерации. Возвращение в цикл по опе-
рации циклического элиминирования приво-
дит к формуле
Этот процесс будет повторяться до тех пор
(показано тремя точками), пока остаток от де-
ления не будет равным нулю, а последнее уже
рассмотрено. Тем самым формула описывает
вычисление наибольшего общего делителя i-го
= r; % i; j; = r; % x; y; …; ≠ r; 0 - ?; ≠ r; 0 - ?
;
= x; j = x; y; = n; y; ≠ r, 0 - ?
; ;
= y; r = y; r.
= r0; % i; j
;
= x; j
;
= y; r,
≠ r, 0
≠ r, 0
= r0; % i; j
;
& ≠ r; 0 , & ≠ r; 0
; ;
= x; j = n; j
;
= y; r.
= n; 1.
≠ 0, 0
← x; 2
← y; 1.
r
= r; % 2; 1.
;
= x; y; = n; 1.; ≠ 0, 0 - ?
;
= x; r .
← x; a;
← y; b
F x; y,
34 УСиМ, 2013, № 1
значения переменной x и j-го значения пере-
менной y.
Теперь необходимо доказать, что формула
(3) описывает вычисление наибольшего общего
делителя для всех значений переменных x и y.
Для доказательства используем принцип сово-
купной математической индукции [16], что обу-
словлено наличием трех переменных. Третьей
переменной есть r, для которой теорема дока-
зана. Поскольку N – секвенционная область на-
туральных чисел (N = ), упорядоченная
операцией секвенцирования, то относительно
формулы (3) можно использовать трансфи-
нитную математическую индукцию [16]. Обу-
словлено это тем, что доказательство для на-
чальных и иных значений переменных x и y –
аналогично. Для формулы (3) доказано, что
она выполняется для произвольных значений i
и j переменных x и y. Следовательно, на осно-
вании трансфинитной индукции, можно ут-
верждать, что формула (3) описывает выпол-
нение условий и вычисление наибольшего об-
щего делителя всех натуральных чисел. Тео-
рема доказана.
Инструментальные
средства синтеза фор-
мул алгебры секвенци-
онных алгоритмов
Система обозначе-
ний алгебры секвенци-
онных алгоритмов –
специфическая. Напри-
мер, знак операции сек-
венцирования имеет
форму эллипса, ширина
(h) которого зависит от
его длины (l) и вычис-
ляется по формуле h =
/ 2l , у которой два
– количество пикселов
экрана монитора [17,
18], а зависимость ши-
рины от длины знаков
операций элиминиро-
вания и параллирования
описываются выражением h / 2l [16, 18].
Знаки операций секвенцирования, элиминиро-
вания и параллелирования имеют горизон-
тальную ( , , ) и вертикальную
( , , ) ориентации. Геометрические размеры
знаков зависят от геометрических размеров
унитермов, которые упорядочиваются этими
операциями. Для выбора и редактирования
формул алгебры секвенционных алгоритмов
могут быть использованы универсальные ком-
пьютерные системы: Word, Coral Draw и др. В
связи с необходимостью выполнения большо-
го количества действий, связанных с рисова-
нием и масштабированием знаков операций,
использование универсальных компьютерных
систем для синтеза и редактирования формул
алгебры секвенционных алгоритмов – мало-
эффективны. В связи с этим для синтеза фор-
мул алгебры секвенционных алгоритмов соз-
даны специальные инструментальные средст-
ва.
Главное окно созданной системы компью-
терного синтеза формул алгебры секвенцион-
ных алгоритмов показано на рисунке. В его
верхней части обозначено название системы –
1, 2, …
Рис. Главное окно инструментальных средств
УСиМ, 2013, № 1 35
Генератор коду формул алгоритмів, меню ко-
манд с опциями: Файл, Операції, Дії, Налаш-
тування, Створення систем, Візуалізатор.
Непосредственно под меню команд – инстру-
менты, предназначенные для автоматического
создания знаков операций: секвенцирования,
элиминирования, параллелирования, цикличе-
ских секвенцирования, элиминирования, па-
раллелирования и равенства. Выполнение та-
ких действий, как замена унитермов, их ревер-
сирования и элиминирование, задания группо-
вых свойств, открытия доступа к базе алгорит-
мов, инициализации мастера создания баз дан-
ных из формул алгоритмов и перестройки упо-
рядочений. Под инструментами расположено
рабочее поле для синтеза и визуализации фор-
мул алгоритмов. На рабочем поле изображены
синтезированные формулы алгоритмов. Ниже
рабочего поля расположен рабочий стол для
создания интерфейсов компьютерных систем.
На рабочем столе показан тривиальный интер-
фейс компьютерной системы. В левой части
окна расположена панель элементов с одним
абстрактным графическим элементом (AddAb-
stract) и другие типичные графические унитер-
мы (кнопка – AddButton, этикетка – AddLabel,
элемент безальтернативного выбора – AddRadio-
Button, элемент альтернативного выбора – Add-
ChecBox и др.), предназначенные для создания
графических интерфейсов компьютерных сис-
тем. В правой части окна расположены списки
свойств (Properties) и событий (Events) абст-
рактных и типовых графических унитермов.
В табл. 2 показана сравнительная оценка эф-
фективности по количе-
ству технологических
операций, которые необ-
ходимо выполнить при
синтезе алгоритма реше-
ния квадратного уравне-
ния созданными инстру-
ментальными средствами
и информационной тех-
нологией в сравнении с
использованием универ-
сальной (Word) и спе-
циализированных ком-
пьютерных систем Абстрактал [17] и Модал
[18].
На основании инструментальных средств
разработаны системы компьютерной оптими-
зации формул алгебры секвенционных алго-
ритмов по количеству унитермов и генериро-
вания реляционных баз данных по формулам
алгебры секвенционных алгоритмов.
Заключение. Впервые в алгебру алгорит-
мов введено определение операции реверсиро-
вания с установлением связей между опера-
циями секвенцирования, элиминирования и па-
раллелирования, что обеспечило оптимизацию
и наглядность, уменьшение затрат на реализа-
цию формул алгоритмов. Впервые операция
элиминирования описана формулой секвенци-
онной логики над упорядоченными логиче-
скими переменными, которая может быть ис-
пользована для доказательства непротиворечи-
вости алгебры секвенционных алгоритмов.
Алгебра секвенционных алгоритмов перво-
го порядка обеспечивает формализованное опи-
сание и обработку структур драных. Алгеброй
секвенционных алгоритмов второго порядка
формально описываются и обрабатываются
алгоритмы, результат которых – компьютер-
ный синтез и оптимизация, исследование и
реализация алгоритмов с использованием ин-
струментальных средств.
Созданы эффективные инструментальные
средства и информационная технология синте-
за, редактирования и оптимизации по количе-
ству унитермов формул алгебры секвенцион-
ных алгоритмов.
Т а б л и ц а 2. Сравнение эффективности инструментальных средств
Инструментальные средства и информационная технология
Microsoft Word АбстрактАл Модал
Количество
операций
при наборе
Созданные инст-
рументальные
средства и ин-
формационная
технология
Количе-
ство
опера-
ций
Уменьше-
но (раз)
Коли-
чество
опера-
ций
Уменьше-
но (раз)
Коли-
чество
опера-
ций
Уменьше-
но (раз)
Унитермов 60 110 1,80 75 1,20 99 1,65
Знаков опера-
ций секвен-
цирования
25 96 3,90 45 1,80 60 2,40
Знаков опера-
ций секвен-
цирования
12 30 2,50 36 3,00 40 3,30
Алгоритма в
целом
97 236 2,40 156 1,50 199 2,00
36 УСиМ, 2013, № 1
Перспективны решения на основании ал-
гебры секвенционных алгоритмов задач дина-
мического программирования, компьютерного
исследования достоверности информационных
систем и генерирования программного кода из
формул алгоритмов.
1. Kleene S.C. Origins of recursive function theory //
Annals of the Theory of Computing. – Jan.1981. –
N 1, 3. – P. 52–67.
2. Church A. An unsolvable problem of elementary num-
ber theory // American J. of Mathematics. – 1936. –
vol. 1, 58. – P. 345–363.
3. Turing A.M. On computable numbers, with an applica-
tion to the Entscheidungs problem // Proc. of London
Mathematical Soc. – 1936–1937. – Ser. 2, 42. –
P. 230–265.
4. Post E.L. Finite Combinatory Processes – Formulation 1
// J. of Symbolic Logic. – 1936. – N 1. – P. 103–105.
5. Марков А.А. Теория алгорифмов // Тр. МИАН. –
1951. – Т. 38. – С. 176–189.
6. Колмогоров А.Н. О понятии алгоритма // УМН. –
1953. – Т. 8, 4 (56). – С. 175–176.
7. Schönhage A. Universelle Turing Speicherung / Auto-
matentheorie und Formale Sprachen / J. Dörr, G. Hotz
(Eds.) // Mannheim: Bibliogr. Institut, 1970. – P. 369–
383.
8. Aho A.V., Hopcroft J.E., Ullman J.D. The design and
analysis of computer algorithms. – Addison–Wesley
Publ. Comp., 1974. – 470 p.
9. Криницкий Н.А. Алгоритмы вокруг нас. – М.: Нау-
ка, 1984. – 224 с.
10. Цейтлин Г.Е. Введение в алгоритмику. – К.: Сфе-
ра, 1998. – 310 с.
11. Цейтлин Г.Е., Захария Л.М. Алгебраические аспек-
ты полноты: абстракции, биология и экология // Про-
блеми програмування. – 2008. – № 2–3. – С. 31–36.
12. Цейтлин Г.Е., Мохница А.С. Что такое алгебраиче-
ская алгоритмика? // Проблеми програмування. –
2009. – № 2–3. – С. 52–58.
13. Овсяк В.К. Программа имитации функционирова-
ния многозначных логических структур (УПОРЯДО-
ЧЕНИЯ). № АП0159. – Киев: Укр. РФАП, 1987. –
450 с.
14. Овсяк В.К. Засоби еквівалентних перетворень ал-
горитмів інформаційно-технологічних систем // Доп.
НАН України. – 1996. – № 9. – С. 83–89.
15. Овсяк В., Овсяк О., Петрушка Ю. Секвенційна логіка
// Комп’ютерні технології друкарства. – 2011. – № 27. –
С. 74–80.
16. Математическая энциклопедия / Гл. ред. И.М. Ви-
ноградов. – Т. 3. – М.: Советская энциклопедия, 1982.
– 1183 с.
17. Василюк А.С. Підвищення ефективності математич-
ного і програмного забезпечення редактора формул
алгоритмів: Автореф. дис. канд. тех. наук. –
Львів, 2008. – 20 с.
18. Бритковський В.М. Моделювання редактора фор-
мул секвенційних алгоритмів: Автореф. дис.
канд. тех. наук. – Львів, 2003. – 18 с.
Поступила 12.05.2012
Тел. для справок: +38 032 223-6766, +38 097 109-3444,
+38 097 110-1090 (Львов)
E-mail: ovsyak@rambler.ru, ovsjak@ukr.net
© О.В. Овсяк, В.К. Овсяк, 2013
<<
/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
|