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

На правах рукописиПетухова Нина ДмитриевнаРазработка и оценка числа шагов работыалгоритмоврешения задач логико-предметного распознаванияобразов с использованием тактик обратного метода Маслова05.13.17 – Теоретические основы информатикиАВТОРЕФЕРАТдиссертации на соискание ученой степеникандидата физико-математических наукСанкт-Петербург2016Работа выполнена на кафедре «Математики» Федерального государственногобюджетного образовательного учреждении высшего профессиональногообразования «Санкт-Петербургский государственный морской техническийуниверситет»Научный руководитель:Косовская Татьяна Матвеевна,докторфизико-математических,доцент,профессор кафедры «Информатики» федеральногогосударственного бюджетного образовательногоучреждения высшегообразования«СанктПетербургский государственный университет»(СПб ГУ).Официальные оппоненты:Бельтюков Анатолий Петрович,доктор физико-математических наук, профессор,профессорфедеральногогосударственногобюджетногообразовательногоучреждениявысшегопрофессиональногообразования«Удмуртский государственный университет».Пак Вадим Геннадьевич,кандидат физико-математических наук, доцент,научныйсотрудникфедеральногогосударственного автономного образовательногоучреждения высшегообразования«СанктПетербургский политехнический университетПетра Великого».Ведущая организация:Защита состоится «___» _______ 2016 года в ___:___ на заседаниидиссертационного совета Д 212.232.51 на базе Санкт-Петербургскогоуниверситета по адресу: __________________________________________.

Сдиссертациейможноознакомитьсяпоадресу________________________________________________________________ и насайте _______________________________________________________Автореферат разослан «___» _______ 2016 года.Ученый секретарь диссертационного советаД 212.232.51 д.ф.-м.н., профессорДемьянович Юрий КазимировичОбщая характеристика работыАктуальность темы.Во многих задачах искусственного интеллектаисследуемый объект характеризуется не только своими глобальными признаками,задающими его свойства как единого целого, но и свойствами его частей иотношений между ними. При распознавании контурного изображения объектможет быть представлен как множество его вершин и вида соединений этихвершин. В задачах диагностики объект задаѐтся набором своих составляющих, атакже зависимостями между этими элементами, позволяющими объектуфункционировать.Такой подход ещѐ в 70-ые годы XX века был сформулирован в литературе.Однако, в те годы, практического применения он практически не получил в силувысокой вычислительной сложности возникающих при этом задач, которыеявляются NP-трудными.

Тем не менее, ввиду постоянно возрастающейпроизводительности вычислительной техники, в последние 15 лет интерес к этомувопросу возрос.При изучении алгоритмов одно из ключевых мест занимает анализ времениих работы. Первым шагом является нахождение асимптотических оценок:верхней и нижней границ работы алгоритмов.В настоящее время для множества задач найдены только такие алгоритмы,которые перебирают экспоненциально зависящее от длины записи исходныхданных количество вариантов.

Такие задачи, как правило,являются NP-трудными.Ясно, что при больших размерах решаемых задач применение алгоритмов сэкспоненциальной оценкой иррационально, хотя для задач небольшого объемаэкспоненциальные решения могут оказаться лучше полиномиальных (например,при n≥100 экспоненциальная оценка 1.1n лучше, чем 10n3).В данной работе построены и доказаны оценки числа шагов работыалгоритмов решения задач логико-предметного распознавания образов,использующих тактики обратного метода, который был предложен в середине60ых годов советским логиком С.Ю.

Масловым (1932 – 1983).Обратный метод С.Ю. Маслова не является менее эффективным методомавтоматического доказательства теорем, чем, например, метод резолюций.Припрактическом применении, как показано вдиссертации, он является даже болееэффективным, но не получил широкого распространения в программировании.Одной из причин этого является сложность обратного метода в оригинальномизложении С.Ю. Маслова.В диссертации предложена конкретизация обратного метода для частногослучая формул исчисления предикатов, к которым сводится решение некоторыхзадач искусственного интеллекта.

А также разработаны алгоритмы решения задачлогико-предметного распознавания образов, использующие тактики обратногометода Маслова, и доказаны оценки числа их шагов. Эффективность этихалгоритмов проиллюстрирована на примерах. Представленные алгоритмыпригодны для программной реализации.3Степень разработанности темы исследования. Термин «обратный метод»впервые введен С.Ю. Масловым в 1964 году. Автором был разработан методустановления выводимости для формул классического исчисления предикатов безравенства и функциональных символов.Интерес к обратному методу установления выводимости появился в связи ссерией работ С.Ю.

Маслова и группы математической логики ЛОМИ АН СССР,опубликованных в период с 1694 по 1972 годы. В 1973 году Н. Нильсон написалкнигу,посвященную методам поиска решений в пространстве состояний. В 1976году Р. Дуда и П. Харт изложили исистематизировали методы распознаванияобразов и дали анализ пространственных сцен по их плоскому изображению.

В1981 году Г.Е. Минц, назвав обратный метод «резолютивными исчислениями»,применил его к неклассическим пропозициональным логическим исчислениям. В1982 году М. Гэри и Д. Джонсон написали книгу, посвященную вопросамсложности решения задач.В 1985 году А.А. Воронков рассмотрел обратный методдля классической логики без равенства. В 1989 году выходит работа В.Лифшица в которой представлены основные идеи обратного метода вформе, подчеркивающей его связь с методом резолюций.

В 1992 году А.А.Воронковым и А.Н. Дегтяревым были предложены метод свободных переменныхдля классической логики с равенством, а также ряд критериев избыточности. В1996 году А.А. Воронковприводит описание обратных исчислений свободныхпеременных для неклассических предикатных логик. А в 1996 году Т. Тамметпредложил реализацию обратного метода для предикатной интуиционистскойлогики.

В 2001 году В.В. Бурлуцким была предложена реализация обратногометода для модальной логики КТ. В 2004 году В.П. Оревков применил обратныйметод и доказал разрешимость нового хорновскогофрагмента исчисленияпредикатов. В 2005 году Д.С. Ларионов разработал конкретизацию обратногометода для автоэпистемической логики, которая применялась при построенииэкспертных систем. Г.Е. Минц в 2010 году доказал разрешимость класса Е,используя обратный метод. Кроме того, в 2010 году была предложенареализация обратного метода с применением оператора полученияблагоприятного набора.

А в 2015 году В.А. Филипповским была предложена иреализована система автоматического поиска доказательств теорем, основаннаяна обратном методе, а также проведено сравнение обратного метода и методарезолюций.Целью диссертационной работы является научное обоснованиеиразработкаалгоритмов решения задач логико-предметного распознаванияобразов на основе обратного метода Маслова, а также доказательствоасимптотических оценок числа шагов работы этих алгоритмов.

Для выполненияпоставленной цели необходимо было решить следующие задачи:1. Провести исследование обратного метода, муравьиных алгоритмов,параллельных вычислений и задачи нахождения наибольшей общей подформулы.42. Сформулировать конкретизацию обратного метода для решения задачлогико-предметного распознавания образов, допускающих формулировкусредствами языка исчисления предикатов.3. На основе сформулированного метода разработать алгоритм решениязадач логико-предметного распознавания образов.4. Модифицировать этот алгоритм, используя тактики муравьиныхалгоритмов и параллельных вычислений.5.

Использовать последний алгоритм для решения задачи нахождениянаибольшей общей подформулы.6. Получить асимптотические оценки всех построенных алгоритмов.Цели и задачи диссертационной работы соответствуют области исследованийпаспорта специальности 05.13.17 – «Теоретические основы информатики»:пунктам 2 (Исследование информационных структур, разработка и анализмоделей информационных процессов и структур), 5 (Разработка и исследованиемоделей и алгоритмов анализа данных, обнаружения закономерностей в данных иих извлечениях разработка и исследование методов и алгоритмов анализа текста,устной речи и изображений) и 7(Разработка методов распознавания образов,фильтрации, распознавания и синтеза изображений, решающих правил.Моделирование формирования эмпирического знания).Объектами исследования диссертационной работы являются формулыисчисления предикатов, к которым сводятся многие задачи искусственногоинтеллекта, и обратный метод Маслова.

Предметом исследования являютсяразработка и реализация алгоритмов решения задач искусственного интеллекта.Методология работы основана на методах математического моделирования,анализа и синтеза теоретического и практического материала. Для решения задач,поставленных в работе, использовались методы следующие теоретическиеметоды: построения математических моделей сложных систем, теории сложностиалгоритмов, теории распознавания образов. В практической части работыприменялись методы построения и анализа алгоритмов.Научная новизна данной работы заключается в следующем.1. Сформулирована конкретизация обратного метода для решения задачлогико-предметного распознавания образов, допускающих формулировкусредствами языка исчисления предикатов.2.