2021, випуск 1, c. 43-53

Одержано 18.01.2021; Виправлено 19.02.2021; Прийнято 25.03.2021

Надруковано 30.03.2021; Вперше Online 03.04.2021

https://doi.org/10.34229/2707-451X.21.1.4

Попередня  |  Повний текст  |  Наступна

 

УДК 512.562:007.001.33

Новий підхід до розв’язання задачі генерування множин складних структурних об’єктів на базі квазі-еквівалентного перетворення схеми розмітки

І.І. Ткачов ORCID ID favicon Big

Науково-учбовий центр прикладної інформатики НАН України, Київ

Листування: tЦя електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

В роботі викладаються результати теоретичного дослідження, пов’язаного з розробкою методів побудови породжуючих конструкцій на базі схем розмітки для генерування та розпізнавання множин складних структурних об’єктів. В теоретичному сенсі об’єктами, що породжуються є відображення множини об’єктів у множину міток, а в практичному аспекті ними можуть бути, зокрема, візуальні образи. Науково-практичний інтерес до породжуючих конструкцій полягає в тому, що вони можуть застосовуватись для визначення належності об’єктів певному класу, тобто для розв’язання задачі розпізнавання образів.

Задача побудови породжуючої схеми розмітки входить до широкого розділу сучасної прикладної інформатики, який об’єднує методи розв’язання задачі виконання обмежень (Constraint Satisfaction Problem) і споріднені теми [1–4]. Між тим саме ця задача раніше не ставилася і регулярних методів її розв’язання нині не існує.

Аналіз вищевказаних методів ведеться на базі формалізму задачі узгодженої розмітки [6, 10, 11], яка з одного боку – узагальнення багатьох постановок дискретних задач виконання обмежень, а з іншого – прозора теоретична конструкція з добре розробленим математичним підґрунтям.

Задачу побудови реляційної схеми (в даному випадку – схеми розмітки), що породжує задану множину відображень, за аналогією з лінгвістичними моделями можна називати задачею «відтворення граматики» [12–14].

В попередніх дослідженнях було показано, що для розв’язання цієї задачі має сенс використати еквівалентні перетворення схеми розмітки [11]. Це пояснюється тим, що початкова таблиця з переліком всіх складних об’єктів, що треба генерувати цільовою схемою, сама є тривіальним варіантом схеми з потрібною множиною узгоджених розміток. Тож початкова і цільова схема еквівалентні. Разом з тим одна з еквівалентних операцій – роз’єднання стовпчика – не може регулярно застосовуватися, оскільки потребує виконання певних умов щодо внутрішньої структури стовпчика.

В даному випадку для розширення можливостей чотирьох відомих еквівалентних перетворень схеми розмітки – викреслення та додавання несуттєвої розмітки, а також з’єднання та роз’єднання стовпчиків було додано нееквівалентне перетворення – «розфарбування розміток стовпчика».

Мета роботи. Ввести та дослідити операцію «розфарбування розміток», яка призводить до квазі-еквівалентного перетворення схеми розмітки. Продемонструвати доцільність використання відомих еквівалентних та введеного квазі-еквівалентного перетворення схеми розмітки для розв’язання задачі побудови породжуючих конструкцій на базі схем розмітки.

Результати. Введено перетворення схеми розмітки, яке отримало назву «розфарбування розміток стовпчика схеми». Показано, що його виконання приводить до квазі-еквівалентної схеми розмітки, за розв’язком якої можна однозначно відтворити розв’язок початкової задачі. Запропонований метод застосування нововведеної операції для перетворення схеми розмітки в квазі-еквівалентну схему, в якій стає можливим регулярне виконання операції роз’єднання стовпчика. Ця властивість операції розфарбування розміток відкриває шлях до створення метода розв’язання задачі відтворення схеми розмітки, яка генерує задану множину узгоджених розміток.

 

Ключові слова: реляційна схема, схема узгодженої розмітки, еквівалентні перетворення схеми розмітки, задача виконання обмежень.

 

Цитувати так: Ткачов І.І. Новий підхід до розв’язання задачі генерування множин складних структурних об’єктів на базі квазі-еквівалентного перетворення схеми розмітки. Cybernetics and Computer Technologies. 2021. 1. С. 43–53. https://doi.org/10.34229/2707-451X.21.1.4

 

Список літератури

           1.     Dechter R. Constraint processing. San Francisco: Morgan Kaufmann, 2003. 481 p.

           2.     Freuder E.C., Mackworth A.K. Constraint satisfaction: An emerging paradigm. Foundations of Artificial Intelligence. 2006. V. 2. P. 13–27. https://doi.org/10.1016/S1574-6526(06)80006-4

           3.     Tsang E. Foundations of Constraint Satisfaction. New York: Academic Press, 1993. 421 p.

           4.     Handbook of Constraints Programming. Elsevier B.V. 2006. 955 p.

           5.     Ткачов І.І. Спеціальні структури в схемах розмітки. ІІ Міжнар. конф. «Роль інновацій в трансформації образу сучасної науки». Київ: Інститут інноваційної освіти. 2018. С. 213–222. https://novaosvita.com/wp-content/uploads/2019/01/InnTrImModSc-Kyiv-Dec2018_v1.1.pdf

           6.     Ткачев И.И. Реляционные методы распознавания образов и задача гомоморфизма алгебраических моделей. Доклады АН Украинской ССР Сер. А. 1988. № 1. С. 76–78.

           7.     Ткачов І.І., Реляційні моделі для опису структур складних об´єктів у розпізнаванні образів. Міжнар. конф. «Наука, освіта, суспільство: актуальні питання і перспективи розвитку». Одеса: ГО «ІОМП». 2016. С. 164–169. https://en.calameo.com/read/0031683720c8ede790c06

           8.     Ткачов І.І. Узгоджені розмітки та гомоморфізми відношень в задачах аналізу структур складних об’єктів. ІІ Міжнар. конф. «Наука, освіта, суспільство: актуальні питання і перспективи розвитку». Київ: Інститут інноваційної освіти. 2016. С. 187–192. https://ru.calameo.com/read/0031683726793adec3caa

           9.     Ткачев И.И. Реляционные методы распознавания: две фундаментальные постановки. "Математические методы распознавания изображений" тезисы докладов. Киев: Ин-т кибернетики АН Украины. 1991. C. 32–34.

       10.     Haralick R.M. Scene Matching Problems. Digital image processing and analysis: NATO advanced study institute. 1978. P. 184–202.

       11.     Ткачев И.И. Эквивалентные преобразования в одном классе распознающих систем. Кибернетика. 1981. № 1. С. 27–32. http://www.nucpi.nas.gov.ua/images/staff/Tkachev/Kibernetika1981.pdf

       12.     Ткачев И.И. Преобразования реляционных схем и задача «восстановления грамматики». Міжнар. конф. «Сучасна інформатика: проблеми, досягнення та перспективи розвитку». Київ: Інститут кібернетики імені В.М. Глушкова НАН України. 2017. С. 154–157. https://ru.calameo.com/read/0031683724703e37cfd96

       13.     Ткачов І.І. Генеративні можливості реляційних схем. V Міжнар. конф. «Обчислювальний інтелект (Результати, проблеми, перспективи)». Ужгород. 2019. С. 131–132. https://en.calameo.com/read/003168372f07dda801899

       14.     Ткачев И.И. О модели конструктивного порождения множеств сложных объектов на основе реляционных схем. V Міжнародна конференція «Відкриті еволюціонуючі системи». К.: ФООП Маслаков. 2020. С. 203–205. https://ru.calameo.com/read/0031683726ecb6303d80a

       15.     Фу К. Структурные методы в распознавании образов. М.: Мир, 1977. 319 с.

       16.     Шлезингер М.И. Синтаксический анализ двумерных зрительных сигналов в условиях помех. Кибернетика. 1976. № 4. С. 113–130.

       17.     Шлезингер М.И. Математические средства обработки изображений. Киев: Наукова думка, 1989. 200 с.

       18.     Минский М., Пэйперт С. Персептроны. М.: 1971. 262 с.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна

 

 

            Випуски

 

© Вебсайт та оформлення. 2019-2024,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.