Решение задачи построения образов для линейной двухцветной мозаїки

Рассматривается проблема построения линейной мозаики для двухцветных шаблонов. Сначала рассматриваются два шаблона, а затем произвольное их количество. Составляются соответствующие линейные уравнения и приводится их решение....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2012
Автори:	Донец, А.Г., Шулинок, И.Э.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Назва видання:	Теорія оптимальних рішень
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/85017
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Решение задачи построения образов для линейной двухцветной мозаїки / А.Г. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 59-65. — Бібліогр.: 1 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-85017
record_format	dspace
spelling	irk-123456789-850172015-07-19T03:02:16Z Решение задачи построения образов для линейной двухцветной мозаїки Донец, А.Г. Шулинок, И.Э. Рассматривается проблема построения линейной мозаики для двухцветных шаблонов. Сначала рассматриваются два шаблона, а затем произвольное их количество. Составляются соответствующие линейные уравнения и приводится их решение. Розглядається проблема побудови лінійної мозаїки для двокольорових шаблонів. Спочатку розглядаються два шаблони, потім довільна їх кількість. Складаються відповідні лінійні рівняння та наводиться їх розв'язок. The problem of construction of the linear mosaic for dual color templates is considered. Two templates are considered first, then variable templates number. Appropriate linear equations are compounded and solved then. 2012 Article Решение задачи построения образов для линейной двухцветной мозаїки / А.Г. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 59-65. — Бібліогр.: 1 назв. — рос. XXXX-0013 http://dspace.nbuv.gov.ua/handle/123456789/85017 519.8 ru Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается проблема построения линейной мозаики для двухцветных шаблонов. Сначала рассматриваются два шаблона, а затем произвольное их количество. Составляются соответствующие линейные уравнения и приводится их решение.
format	Article
author	Донец, А.Г. Шулинок, И.Э.
spellingShingle	Донец, А.Г. Шулинок, И.Э. Решение задачи построения образов для линейной двухцветной мозаїки Теорія оптимальних рішень
author_facet	Донец, А.Г. Шулинок, И.Э.
author_sort	Донец, А.Г.
title	Решение задачи построения образов для линейной двухцветной мозаїки
title_short	Решение задачи построения образов для линейной двухцветной мозаїки
title_full	Решение задачи построения образов для линейной двухцветной мозаїки
title_fullStr	Решение задачи построения образов для линейной двухцветной мозаїки
title_full_unstemmed	Решение задачи построения образов для линейной двухцветной мозаїки
title_sort	решение задачи построения образов для линейной двухцветной мозаїки
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
url	http://dspace.nbuv.gov.ua/handle/123456789/85017
citation_txt	Решение задачи построения образов для линейной двухцветной мозаїки / А.Г. Донец, И.Э. Шулинок // Теорія оптимальних рішень: Зб. наук. пр. — 2012. — № 11. — С. 59-65. — Бібліогр.: 1 назв. — рос.
series	Теорія оптимальних рішень
work_keys_str_mv	AT donecag rešeniezadačipostroeniâobrazovdlâlinejnojdvuhcvetnojmozaíki AT šulinokié rešeniezadačipostroeniâobrazovdlâlinejnojdvuhcvetnojmozaíki
first_indexed	2025-07-06T12:10:28Z
last_indexed	2025-07-06T12:10:28Z
_version_	1836899460782751744
fulltext	60 Теорія оптимальних рішень. 2012 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается проблема по- строения линейной мозаики для двухцветных шаблонов. Сначала рассматриваются два шаблона, а затем произвольное их количе- ство. Составляются соответ- ствующие линейные уравнения и приводится их решение. о  А.Г. Донец, И.Э. Шулинок, 2012 ÓÄÊ 519.8 ÓÄÊ 519.8 À.Ã. ÄÎÍÅÖ, È.Ý. ØÓËÈÍÎÊ ÐÅØÅÍÈÅ ÇÀÄÀ×È ÏÎÑÒÐÎÅÍÈß ÎÁÐÀÇÎÂ ÄËß ËÈÍÅÉÍÎÉ ÄÂÓÕÖÂÅÒÍÎÉ ÌÎÇÀÈÊÈ Введение. В данной статье продолжается изучение двухцветных мозаик [1]. Зная алго- ритм построения любой единицы, покажем, как при этом получить решение для произ- вольной правой части системы (3) из [1]. Для удобства изложения рассмотрим при- мер 1 с параметрами { } ,=n,=S 115,8 { }.2,1 n,b,bb=B … Обозначим переменные для первого ша- блона ( )111,2 s+n,,=ix i −… , для второго шаблона – ( )2 2 11,2 s+n,,=jj+x s −… , где i и j координаты в строке меток соответ- ствующих шаблонов. Тогда система (3) при- мет конкретный вид x1+ x9 = b1 x1+ x2+ x 9+ x10 = b2 x1+ x2+ x3+ x 9+ x10+ x11 = b3 x1+ x2+ x3+ x4+ x 9+ x10+ x11+ x12 = b4 x1+ x2+ x3+ x4+ x5+ x 9+ x10+ x11+ x12 = b5 x2+ x3+ x4+ x5+ x6+ x 9+ x10+ x11+ x12 = b6 x3+ x4+ x5+ x6+ x 7+ x 9+ x10+ x11+ x12 = b7 x4+ x5+ x6+ x 7+ x9 x10+ x11+ x12 = b8 x5+ x6+ x 7+ x10+ x11+ x12 = b9 x6+ x 7+ x11+ x12 = b10 x 7+ x12 = b11 }mod . (1) Отметим особенности общей системы для двух шаблонов. Она естественным образом по столбцам делится на две подобные части. Левая часть состоит из 12 −s столбцов, в каждом из которых ровно 1s переменных. Все столбцы одинаковы, но сдвигаются вниз ровно на одну позицию по отношению к пре- дыдущему. Аналогично, правая часть состоит из 11 −s столбцов, в которых ровно 2s переменных. ПОСТРОЕНИЕ ОБРАЗОВ ДЛЯ ДВУХЦВЕТНОЙ МОЗАИКИ Теорія оптимальних рішень. 2012 61 В системе отсутствует переменная 2sx . В строке 1s переменных первого шаблона на одну больше, а переменных второго шаблона – одинаковое число. Тоже самое можно ска- зать и про строку 12 s+n − . Пусть ( )2mod0120 ≡≡ bb . Начиная со второй строки, при- бавим к ней предыдущую по 2mod . В результате получим новую систему в которой все строки, за исключением указанных выше, будут иметь по одной переменной от каждого шаблона, а в строках 1s и 12 s+n − ровно по одной переменной от первого шаблона. И добавим в систему последнее уравнение из (1) x 1 + � � � � � � + x 9 � � � = b 0 + b 1 � x 2 + � � � � � � + x 10 � � = b 1 + b 2 � � x3+ � � � � � � + x11 � = b2+ b3 � � � x 4+ � � � � � � + x12 = b3+ b4 � � � � x 5 + � � � � � � = b 4 + b 5 x 1 + � � � � x 6 + � � � � � = b 5 + b 6 � x 2+ � � � � x7+ � � � � = b6+ b7 � � x3 � � � � � � � � = b7+ b8 � � � x 4 + � � � + x 9 � � � = b 8 + b 9 � � � � x 5 + � � � + x 10 � � = b 9 + b 10 � � � � � x6+ � � � + x11 � = b10+ b11 � � � � � � x7+ � � � + x12 = b11+ b12 }mod 2 . (2) Получим непосредственное решение ( )( )2mod545 b+bx ≡ и ( )( )2mod873 b+bx ≡ . Подставляя эти значения в остальные уравнения, находим полное решение системы (2). Теорема 1. Решением системы (2) есть ( )( )2mod λ 1 1γγ∑ −≡ =j i b+bx . (3) Доказательство. Будем рассуждать по индукции. Для 1s x получаем ( )[ ] 1modλ 21 1 11 =s+sss= − ⋅ и ( )2mod1111      −≡ sss b+bx или конкретно ( ) 2mod455 b+bx ≡ . Переменная 5x встречается ниже на 5 позиций. Подставляя сюда значение 5x , получаем решение для 10x . Для него ( )[ ] 2mod2λ 21 1 11 =s+sss= − ⋅⋅ . Получа- ем ( )( )2mod1095410 b+b+b+bx ≡ . Дальше, поднимаясь на 8 позиций вверх, и подставляя значение 10x , получаем решение для 2x . Таким образом, получаем последовательное движение либо вниз на 1s позиций (при этом индексы увели- чиваются на 1s ), либо вверх на 2s позиций (при этом индексы уменьшаются на 2s ). Но ( )[ ]2112 mod s+sss ≡− , то есть в классе вычетов получается каждый раз увеличение индекса на 1s . В результате выражение 1ts , когда t пробегает все значения от 1 до 221 −s+s , пробегает все индексы переменных, а при 221 −s+s=t получаем А.Г. ДОНЕЦ, И.Э. ШУЛИНОК 62 Теорія оптимальних рішень. 2012 ( ) ( )[ ]2121211 mod1 s+ssss+ss=i ≡−≡− . Но у нас переменная 2 sx отсутствует. А предыдущая переменная имела индекс ( ) ( )[ ]211211 mod2s2 s+ss+ss=i −≡− . Для нашего примера это ( )13mod352 ≡⋅− . И для него справедливо ( )( ) ( )( )2mod2mod 87 11 8 1 13 b+bb+bx j j jj ≡≡ ∑ ≠ − − , что совпадает с непосредственным равенством в (2). Это и завершает доказа- тельство теоремы. Пример 2. Построение образа ( )11,1,0,1,0,0,0,1,1,0,=B для этих решений приведено на рис. 1. Согласно теореме имеем: ;=b+b=x 0545 ;=b+b+x=x 19849 ;=b+b+x=x 0109510 ;=b+b+x=x 11091 ;=b+b+x=x 121102 ;=b+b+x=x 16516 ;=b+b+x=x 07627 ;=b+b+x=x 11110611 ;=b+b+x=x 11211712 1;32113 =b+b+x=x 043124 =b+b+x=x . Напомним, что переменные jx для 8>j отвечают второму шаблону с метками 8−j . Так решается проблема для двух шаблонов при заданных двух цветах. Если 221 +n>s+s , то некоторые образы построить невозможно. В этом случае число уравнений больше числа переменных, что накладывает ограничения на правые части системы уравнений (3) [1]. Если они не выполняются, система не имеет решений. Здесь могут быть два принципиально отличающиеся случая в зависимости от значений 1s . Рассмотрим Пример 3. Пусть 108,7,1 =n=s2=s . Число переменных для первого шаблона, равно 10 + 1 – 7 = 4, для второго – 10 + 1 – 8 = 3. Обозначим их ( )1,2,3,4=ixi и ( )1,2,3=ix j . Составим для них систему типа (3) [1]. Здесь РИС.1. Построение образа В ПОСТРОЕНИЕ ОБРАЗОВ ДЛЯ ДВУХЦВЕТНОЙ МОЗАИКИ Теорія оптимальних рішень. 2012 63 61 2 71 =+ n =s ≥ . Это приводит к тому, что число переменных для первого ша- блона 14 s< . Система имеет матрицу размером 7×10 и её переменные образуют два касающихся параллелограмма, в каждом из которых левые нижние вершины находятся ниже правых верхних вершин. Если взять в качестве координат вер- шин номер столбца и номер строки матрицы системы уравнений, то для первого параллелограмма получим такие координаты вершин (1 ;1) , ( )11 11 s+n;s+n −− , ( )n;s+n 11 − и ( )11 s; , или (1;1), (4;4), (4;10) и (1;7). По- скольку 111 s<s+n − (то же имеет место и для второго шаблона), то матрица системы содержит одинаковые строки, начиная со строки 11 s+n − и кончая строкой 1s 2mod 1034 93243 8321432 73214321 63214321 53214321 43214321 3321321 22121 111              =+ =+++ =+++++ =++++++ =++++++ =++++++ =++++++ =+++++ =++++ =++ byx byyxx byyyxxx byyyxxxx byyyxxxx byyyxxxx byyyxxxx byyyxxx byyxx byx . (4) Здесь четыре одинаковых строки в матрице системы: 4, 5, 6 и 7, и определитель этой системы равен ( )2mod0 . Поэтому для существования решения системы необходимо, чтобы 7654 b=b=b=b . Если удалить из системы три зависимые строки, то получим систему такого вида 2mod 1034 93243 8321432 43214321 3321321 22121 111          =+ =+++ =+++++ =++++++ =+++++ =++++ =++ byx byyxx byyyxxx byyyxxxx byyyxxx byyxx byx (5) Эта система имеет размеры 7×7 и решается указанным выше способом для 7=n и { }54,=S . Если условие 1 2 1 + n s ≥ не выполняется, то определитель этой системы также равен ( )2mod0 , но найти зависимые строки в системе сложнее. А.Г. ДОНЕЦ, И.Э. ШУЛИНОК 64 Теорія оптимальних рішень. 2012 Если 121 +n<s+s , то появляется множество решений, так как путём сдвига шаблонов, которые являются базисом для 121 +n=s+s , можно получить базис для больших значений n . Вопрос о числе шаблонов больше двух решается аналогично. Пусть задано p шаблонов. Будем считать их упорядоченными по возрастанию. Очевидно, что для них также должно выполняться условие ( ) 1НОД 2,1, =s,ss p… . (6) Кроме того система типа (3) должна всегда иметь n переменных, чтобы решение было единственным. Но каждый шаблон может иметь ts+n −1 переменных. Поэтому необходимо ( ) n=s+n p =i i∑ − 1 1 , откуда ( ) ( ) p+np=s p =i i 1 1 −∑ . (7) Эти условия являются необходимыми. Вопрос о конкретном методе решения задачи для более двух шаблонов остается открытым. Возьмём для начала 3=p . Если среди них найдутся два взаимно простых шаблона, то составляем систему типа (3) для этих шаблонов и решаем задачу по теореме 1. Если из трёх шаблонов каждые два имеют общий делитель, а все вместе удовлетворяют условию (6), тогда составляем систему (3) для трёх шаблонов. Пусть существуют три неравных между собой множителя 1α , 2α и 3α . Тогда 211 αα ⋅=s , 312 αα ⋅=s и 323 αα ⋅=s удовлетворяют условию (6). Если брать произвольные множители, то не всегда удовлетворяется условие (7), поэтому простейший подходящий пример содержит достаточно большие числа, не дающие возможности наглядно представить систему типа (3). Пусть, например, 2α1 = , 3α2 = и 5α3 = . Тогда 61 =s , 102 =s и 153 =s . Из (5) следует, что .1,2 1 1 p,,=i;s> p ps =n i p =i i … − −∑ (8) Получаем 314 2 315106 s<= ++ =n − , что недопустимо. Однако, значения is не могут быть произвольными. Возьмём, например, 101 =s , 152 =s и 183 =s . Эти значения подходят для (8), так как при этом 20=n . Каждому шаблону соответствует is+n −1 положений на поле или такое же количество переменных. Если подставить значение 3=p в (8), то получим { }1,2,32, ∈− kj,i,s<s+s kji . (9) ПОСТРОЕНИЕ ОБРАЗОВ ДЛЯ ДВУХЦВЕТНОЙ МОЗАИКИ Теорія оптимальних рішень. 2012 65 Однако, даже если удовлетворяются все условия (7 – 9), то не всегда существует решение системы типа (3). Лемма 1. Если 1 2 1 + n s ≥ , то система типа (3), составленная для p шаблонов, удовлетворяющих условиям (7 – 9), имеет матрицу A, у которой ( )2mod0≡detA . Доказательство. Система типа (4) для p шаблонов будет состоять из p параллелограммов. Так как 1 2 1 + n s ≥ , то в первом параллелограмме левая нижняя вершина будут находиться ниже правой верхней. Поскольку is<s1 для 1>i , то это справедливо и для остальных параллелограммов. А это обеспечивает совпадение строк матрицы системы, начиная от строки 11 s+n − и кончая строкой 1s , что и дает значение ( )2mod0≡detA . Заключение. Полученные результаты показывают, что задача построения линейной мозаики на двухцветных шаблонах может быть решена путём состав- ления и решения систем уравнений по модулю 2. А.Г. Донець, І.Е. Шулінок РОЗВ'ЯЗАННЯ ЗАДАЧІ ПОБУДОВИ ОБРАЗІВ ДЛЯ ЛІНІЙНОЇ ДВОКОЛЬОРОВОЇ МОЗАЇКИ Розглядається проблема побудови лінійної мозаїки для двокольорових шаблонів. Спочатку розглядаються два шаблони, потім довільна їх кількість. Складаються відповідні лінійні рівняння та наводиться їх розв'язок. A.G. Donets, I.E. Shulinok A SOLUTION OF DUAL COLOR LINEAR MOSAIC CONSTRUCTION PROBLEM The problem of construction of the linear mosaic for dual color templates is considered. Two templates are considered first, then variable templates number. Appropriate linear equations are compounded and solved then. 1. И.Э.Шулинок. Проблемы построения двухцветной линейной мозаики // Теорія оптимальних рішень. – К.: Ін-т кібернетики ім. В.М. Глушкова НАН України, 2010. – С. 126-135. Получено 11.05.2012

Решение задачи построения образов для линейной двухцветной мозаїки

Репозитарії

Схожі ресурси