Диссертация (Разработка и оценка числа шагов работы алгоритмов решения задач логико-предметного распознавания образов с использованием тактик обратного метода Маслова), страница 12

4.3.1.76Рис. 4.3.1. Предикаты V и L.Задан класс объектов Ω1 – класс контурных изображений «девять».Схематическое изображение эталонного объекта имеет вид, представлены нарисунке 4.3.2 (а).Рис. 4.3.2 (а). Контурное изображениеРис. 4.3.2 (б). Контурное изображение«девять».«четыре».Описание класса задается следующей формулой:A1 x1,..., x5   V  x1, x2 , x3  & V  x2 , x4 , x1  & V  x2 , x5 , x1  && V  x3 , x1, x4  & V  x4 , x3 , x2  & V  x4 , x5 , x3  & L x4 , x2 , x5 .Задан класс объектов Ω2 – класс контурных изображений «четыре».Схематическое изображение эталонного объекта имеет вид, представлено нарисунке 4.3.2 (б).Это изображение имеет описание:A2  y1,, y4   V  y1, y3 , y2  & V  y1, y4 , y2  & V  y2 , y1, y3  && V  y3 , y2 , y1  & V  y3 , y4 , y2  & L y3 , y1, y4 Требуется найти максимальную общую подформулу этих двух классов.Так как при выделении максимальной общей подформулы двух заданныхэлементарных конъюнкцийA x  и A y  требуется найти такую подформулу~~~A y  формулы A y , что имеет место следствие~Ax   y A'  y  , то первое,что необходимо сделать, чтобы решить поставленную задачу, это выбрать какую77из двух формул A1  x1 ,..., x5  или A2  y1,, y4  взять заA x , а какую за A~ y .

Таккак в полученных оценках числа шагов работы алгоритмов, основанных наобратном методе, в показателе степени стоят параметры правой части, то вкачествеA x  возьмем формулу, в которой больше атомарных формул. В нашемслучае это A1  x1,..., x5  .Таким образом, требуется проверить частичную выводимостьA1x   p yA2  y .Тогда δ = 6, s1  6 , s2  1 ,l = 3, следовательно, верхняя оценка числа шагов6решения этой задачи имеет порядок   l   max sk   6  3  6  839 808 шагов. kПосредством алгоритма PHIAPTA получена наибольшая длина фрагментаравнаятрем,которойL x4 , x2 , x5  & V  x2 , x4 , x1  & V  x2 , x5 , x1 соответствуютдвафрагментаиV  x4 , x3 , x2  & V  x4 , x5 , x3  & L x4 , x2 , x5  ,представленные на рисунке 4.3.3, и следующие два общих унификаторафрагмент 1 фрагмент 2y1  x2y2  x1y1  x2y2  x3y3  x 4y4  x5y3  x4y4  x5На решение этой задачи потребовалось 1345 шагов.Рис.

4.3.3. Наибольшие общие фрагменты объектов «девять» и «четыре».78ЗАКЛЮЧЕНИЕВ работе получены следующие результаты:1. Сформулирована и обоснована адаптация обратного метода Маслова длядоказательства выводимости формул вида x1,..., xn   & Di a1,..., ak , x1,..., xn  , к i 1доказательству выводимости которых сводятся многие задачи ИскусственногоИнтеллекта, объекты исследования в которых характеризуются свойствами своихэлементовиотношениямимеждуэтимиэлементами,аследовательно,допускающие формализацию средствами языка исчисления предикатов.2.Разработаналгоритмx1,..., xn   & Di a1,..., ak , x1,..., xn  , i 1IMAвыводимостиоснованныйнаформулвидаразработаннойадаптацииобратного метода.

Доказаны асимптотические оценки числа шаговработы этого алгоритма.3. Разработана модификацияIAPTA алгоритма IMA, использующая тактикимуравьиных алгоритмов и параллельных вычислений. Доказаны асимптотическиеоценки числа шагов работы этого алгоритма.4. Обоснована возможность применения обратного метода Маслова длярешения задачи выведения максимальной общей подформулы. Сформулированалгоритм PHIAPTA выделения максимальной общей с точностью до именаргументовподформулыдвухэлементарныхконъюнкций.Доказаныасимптотические оценки числа шагов работы этого алгоритма.Крометого,можносформулироватьследующиерекомендациипоприменению результатов работы в научных исследованиях:1.

Сформулированная конкретизация обратного метода Маслова являетсяпростым и понятным средством доказательства выводимости формул вида79x1,..., xn   & Di a1,..., ak , x1,..., xn  , i 1поэтомуеѐможноприменятьдляпервоначального знакомства с обратным методом.2. Построенные алгоритмы полностью готовы к программной реализации имогут быть применены для решения различных задач Искусственного Интеллектав рамках логико-предметного подхода.В качестве основных перспектив дальнейшей разработки тематики можноуказать построение модификаций предложенных алгоритмов для решенияразличныхзадачискусственногоинтеллекта,программнуюреализациюпостроенных алгоритмов, а также качественноесравнение полученного метода ссуществующими методами решения задач логико-предметного распознаванияобразов и теории выводимости, например, с методом резолюций.В результате диссертационного исследования были выполнены всепоставленные задачи и достигнута цель работы.80ЛИТЕРАТУРААнисимов, Д.Н.

Диагностика динамических объектов методами нечеткойлогики с использованием параметров имитационных моделей / Д.Н.Анисимов, О.С. Колосов, Д.В. Вершинин, М.В. Зуева, И.В. Цапенко //Мехатроника, автоматизация, управление – 2010, №10, – С. 45–50, – ISSN1684-6427[2] Ахо, А. Структуры данных и алгоритмы / А. Ахо, Д. Хопкрофт, Д. Ульман// Москва: Вильямс, 2009, – 400 с.

– ISBN: 978-5-8459-1610-5[3] Бурлуцкий, В.В. Как сократить пространство поиска для разрешающейпроцедуры, основанной на обратном методе / В. В. Бурлуцкий //НациональныйисследовательскийТомскийгосударственныйуниверситет, – Томск, 2001, – Деп. в ВИНИТИ РАН 21.09.2001 № 2017В2001[4] Бурлуцкий, В.В. Логический вывод в дедуктивных системах. / В.В.Бурлуцкий, В.Б. Новосельцев // Вторая сибирская школа молодогоученого: том 3, Томск: изд-во ТГУ, 2001, – с.

27-41[5] Бурлуцкий, В.В. Логический вывод в модальных системах на основеобратного метода. / В.В. Бурлуцкий, В.Б. Новосельцев // Трудырегиональной научно-практическолй конференции студентов, аспирантоми молодых ученых "Вторая сибирская школа молодого ученого" Том 3,Физика, математика, информационные технологии, – Томск: изд-во ТГПУ,2000, – с. 24[6] Бурлуцкий, В.В. Применение обратного метода Маслова к системемодальной логики S5. / В.В. Бурлуцкий // Материалы XXXVIIМеждународной научной студенческой конференции "Студент и научнотехнический прогресс". Секция математики, – Новосибирск: изд-во НГУ,1999, – с 18[7] Бурлуцкий, В.В. Реализация обратного метода для модальной логикизнания / В.В. Бурлуцкий // Труды XXIII Конференции молодых ученыхмеханико-математического факультета МГУ, – Москва: изд-во Мех.-мат.Ф-та МГУ, – 2001, – с 66-70.[8] Бурлуцкий, В.В.

Реализация обратного метода для модальной логики КТ /В.В. Бурлуцкий // Исследования по математическому анализу и алгебре:Сборник статей, Томский университет [ТГУ] им. В.В. Куйбышева. –Томск: изд-во ТГУ, 2001, – том 3, – с. 26-32, ISBN 5-946210-10-6[9] Бурлуцкий, В.В. Стратегия обратного метода вывода для модальнойлогики КТ, основанная на Ф-упорядочении / В. В. Бурлуцкий //НациональныйисследовательскийТомскийгосударственныйуниверситет, – Томск, 2001, – Деп. в ВИНИТИ РАН 21.09.2001 № 2018В2001[10] Вагин, В.Н. Достоверный и правдоподобный вывод в интеллектуальныхсистемах.

Монография. / В.Н. Вагин, Е.Ю. Головина // Москва: Физматлит[1]81– 2008, – 714 с. – ISBN 978-5-9221-0962-8[11] Вагин, В.Н. Решение задач диагностики с использованием системподдержки истинности / В.Н. Вагин, Д.С. Зарецкий Известия южногофедерального университета. Технические науки, – № 12, том 113, 2010, –с. 63-70, – ISSN 1999-9429[12] Вагин, В.Н. Эвристические и вероятностные методы снятия эффективныхпоказаний в системах диагностики. / В.Н. Вагин, П.В. Оськин // ИзвестияРАН. Теория и системы управления, – 2006, № 4, – с.

78-93, – ISSN 00023388[13] Ватутин, Э.И. Анализ результатов применения алгоритма муравьинойколонии в задаче поиска пути в графе при наличии ограничений / Э.И.Ватутин, В.С. Титов // Известия Южного федерального университета.Технические науки. 2014. № 12 (161). c. 111–120 – ISSN 1999-9429[14] Введение в контурный анализ. Приложения к обработке изображений исигналов / под ред.

Я. А. Фурман //, Москва: ФИЗМАТЛИТ, 2003. – 592 с.– ISBN 978-5-9221-0374-9[15] Верещагин, Н. К. Колмогоровская сложность и алгоритмическаяслучайность / Н. К. Верещагин, В. А. Успенский, А. Шень, // Москва:МЦНМО 2013. – 576 с. – ISBN 978-5-4439-0212-8[16] Воеводин, В. В.

Параллельные вычисления / Воеводин, В. В., Воеводин,Вл. В.//, Санкт-Петербург: БХВ, 2002. – 608 с. – ISBN 5-94157-160-7[17] Вопросы кибернетики. Вып.131 (проблемы сокращения перебора).Москва, 1987. – ISSN 0134-6388[18] Воронков, А.А. Метод поиска доказательства / А.А. Воронков //Вычислительные системы. Новосибирск. 1985.

– том 107, – ISSN 0568661X[19] Генкин, В.Л. Системы распознавания автоматизированных производств /В.Л. Генкин, И.Л. Ерош, Э.С. Москалев //. Москва: Машиностроение, –1988, – 242 с., – ISBN 5-217-00162-3[20] Гергель, В.П. Высокопроизводительные вычисления для многоядерныхмногопроцессорных систем / В.П. Гергель // Нижний Новгород: Изд-воННГУ им. Н.И.Лобачевского, 2010. – 421 c. – ISBN 5-85746-602-4[21] Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. //Москва: Техносфера, 2005.

– 1072 c. – ISBN 5-94836-028-8[22] Гонсалес, Р. Цифровая обработка изображений в среде MATLAB: пер. сангл / Р. Гонсалес, Р. Вудс, С. Эддинс // Москва: Техносфера, – 2006, 616с. – ISBN: 5-94836-092-Х.[23] Громкович, Ю. Теоретическая информатика. Введение в теориюавтоматов, теорию вычислимости, теорию сложности, теорию алгоритмов,рандомизацию, теорию связи и криптографию: учебное пособие / Ю.Громкович, пер.

с нем. под ред. Б. Ф. Мельникова. – 3-е изд. // СПб: БХВПетербург, 2010. – 336 с. – ISBN 978-5-9775-0406-582[24] Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри,Д. Джонсон // Москва: Мир, 1982. – 416 с.[25] Давыдов, Г.В. Машинный алгоритм установления выводимости на основеобратного метода / Г.В. Давыдов, С.Ю. Маслов и др.// Зап. научн. сем.ЛОМИ АН СССР. – 1969, том 16, – С. 8–20[26] Давыдов, Г.В.

Синтез метода резолюций с обратным методом / Г.В.Давыдов //Записки научных семинаров ЛОМИ АН СССР, Т.20, 1971. –ISSN 0373-2703[27] Джонс, М. Т. Программирование искусственного интеллекта вприложениях / М. Т. Джонс, пер. с англ. Осипов А.И. // Москва: ДМК Пресс, 2011. – 312 с. – ISBN 5-94074-275-0[28] Дуда, Р.