Диссертация (Разработка и оценка числа шагов работы алгоритмов решения задач логико-предметного распознавания образов с использованием тактик обратного метода Маслова)
Описание файла
Файл "Диссертация" внутри архива находится в папке "Разработка и оценка числа шагов работы алгоритмов решения задач логико-предметного распознавания образов с использованием тактик обратного метода Маслова". PDF-файл из архива "Разработка и оценка числа шагов работы алгоритмов решения задач логико-предметного распознавания образов с использованием тактик обратного метода Маслова", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст из PDF
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ МОРСКОЙ ТЕХНИЧЕСКИЙУНИВЕРСИТЕТНа правах рукописиПетуховаНина ДмитриевнаРАЗРАБОТКА И ОЦЕНКА ЧИСЛА ШАГОВ РАБОТЫ АЛГОРИТМОВРЕШЕНИЯ ЗАДАЧ ЛОГИКО-ПРЕДМЕТНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ СИСПОЛЬЗОВАНИЕМ ТАКТИК ОБРАТНОГО МЕТОДА МАСЛОВА05.13.17 – Теоретические основы информатикидиссертация на соискание ученой степеникандидата физико-математических наукНаучный руководитель – докторфизико-математическихнаук,доцент, КОСОВСКАЯ ТатьянаМатвеевнаСанкт-Петербург20162ОглавлениеВВЕДЕНИЕ ...................................................................................................................... 4Степень достоверности и апробация результатов ................................................
8Публикации результатов ......................................................................................... 9Положения, выносимые на защиту ........................................................................ 9Структура и объем диссертации ........................................................................... 10Содержание работы ................................................................................................ 10ГЛАВА 1. ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ ПРЕДМЕТНОЙ ОБЛАСТИ......................................................................................................................................... 231.1.
Постановка задач Искусственного Интеллекта при логико-предметномподходе........................................................................................................................ 231.2. Обратный метод С.Ю. Маслова для решения задач логико-предметногораспознавания образов ..............................................................................................
27Общая схема обратного метода ............................................................................ 281.3. Алгоритмы Муравья ........................................................................................... 361.4. Параллельные вычисления ................................................................................ 381.5. Совместное применение идей муравьиных алгоритмов и параллельныхвычислений ................................................................................................................. 401.6.
Понятие неполной выводимости предикатных формул ................................. 41ГЛАВА 2. АДАПТАЦИЯ ОБРАТНОГО МЕТОДА МАСЛОВА РЕШЕНИЯЗАДАЧ ЛОГИКО-ПРЕДМЕТНОГО РАСПОЗНАВАНИЯ ОБРАЗОВ .................... 422.1. Формулировка обратного метода для решения задач логико-предметногораспознавания образов .............................................................................................. 422.2. Алгоритм IMA (InverseMethodAlgorithm), использующий тактику обратногометода ..........................................................................................................................
47Алгоритм IMA (Inverse Method Algorithm).......................................................... 502.3. Оценка числа шагов работы алгоритма IMA ................................................... 53ГЛАВА 3. АЛГОРИТМ, ОСНОВАННЫЙ НА ПРИМЕНЕНИИ ОБРАТНОГОМЕТОДА, МУРАВЬИНЫХ ТАКТИК И ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ..... 583.1. Применение идей муравьиных алгоритмов и параллельных вычислений длярешения задач логико-предметного распознавания образов ................................ 58Алгоритм IAPTA .................................................................................................... 593.2. Оценка числа шагов работы алгоритма IAPTA ...............................................
63ГЛАВА 4. ВЫДЕЛЕНИЕ МАКСИМАЛЬНОЙ ОБЩЕЙ ПРЕДИКАТНОЙПОДФОРМУЛЫ С ПОМОЩЬЮ ОБРАТНОГО МЕТОДА МАСЛОВА ................ 694.1. Использование обратного метода для решения задачи выделениямаксимальной общей подформулы .......................................................................... 694.2.
Алгоритм PHIAPTA (PartialHatchabilityInverseAntParallelTacticAlgorithm)выделения максимальной общей подформулы ...................................................... 6934.3. Оценка числа шагов работы алгоритма PHIAPTA. ......................................... 74ЗАКЛЮЧЕНИЕ .............................................................................................................
78ЛИТЕРАТУРА ............................................................................................................... 80ПРИЛОЖЕНИЕ А. Пример решения задачи с помощью алгоритма IMA.............. 89ПРИЛОЖЕНИЕ B. Пример решения задачи с помощью алгоритма IAPTA ........ 100ПРИЛОЖЕНИЕ C. Пример решения задачи выделения наибольшей общейподформулы с помощью алгоритма PHIAPTA. ....................................................... 1114ВВЕДЕНИЕАктуальность темы исследования.Во многих задачах искусственногоинтеллекта исследуемый объект характеризуется не только своими глобальнымипризнаками, задающими его свойства как единого целого, но и свойствами егочастей и отношений между ними.
При распознавании контурного изображенияобъект может быть представлен как множество его вершин и вида соединенийэтих вершин[19], [72], [76], [78], [83], [93]. В задачах диагностики объект задаѐтсянабором своих составляющих, а также зависимостями между этими элементами,позволяющими объекту функционировать[1],[10], [11], [12], [31], [32], [63].Такой подход ещѐ в 70-ые годы XX века был сформулирован в литературе(см., например,[29], [60], [64], [70], [94]). Однако практического применения онпочти не получил в силу высокой вычислительной сложности возникающих приэтом задач, которые являются NP-трудными [2], [17], [90].При изучении алгоритмов одно из ключевых мест занимает анализ времениих работы[36], [50], [71],[89],[92].
Первым шагом является нахождениеасимптотических оценок: верхней и нижней границ работы алгоритмов [15], [23],[43], [44].В настоящее время для множества задач найдены только такие алгоритмы,которые перебирают экспоненциально зависящее от длины записи исходныхданных количество вариантов. Такие задачи, как правило, являются NP-трудными[24]. Ясно, что при больших размерах решаемых задач применение алгоритмов сэкспоненциальной оценкой иррационально, хотя для задач небольшого объемаэкспоненциальные решения могут оказаться лучше полиномиальных (например,при n≥100 экспоненциальная оценка 1.1n лучше, чем 10n3)[73].В данной работе построены и доказаны оценки числа шагов алгоритмоврешения задач логико-предметного распознавания образов, использующихтактики обратного метода, который был предложен в середине 60ых годовсоветским логиком С.Ю.
Масловым (1932 – 1983).5Обратный метод С.Ю. Маслова не является менее эффективным методомавтоматического доказательства теорем, чем, например, метод резолюций [26],[33], [35],[52]. При практическом применении, как показано в диссертации, онявляется даже более эффективным, но не получил широкого распространения впрограммировании. Одной из причин этого является сложность реализацииобратного метода в оригинальном изложении С.Ю. Маслова[34].В диссертации предложена конкретизация обратного метода для частногослучая формул исчисления предикатов, к которым сводится доказательствонекоторых задач искусственного интеллекта.
А также разработаны алгоритмырешения задач логико-предметного распознавания образов, использующиетактики обратного метода Маслова, и доказаны оценки числа их шагов.Эффективностьэтихалгоритмовпроиллюстрировананапримерах.Представленные алгоритмы пригодны для программной реализации.Степень разработанности темы исследования. Термин «обратный метод»впервые введен С.Ю. Масловым в 1964 году в работе [55].
В этой работе авторомбыл разработан метод установления выводимости для формул классическогоисчисления предикатов без равенства и функциональных символов.Интерес к обратному методу установления выводимости появился в связи ссерией работ С.Ю. Маслова и группы математической логики ЛОМИ АН СССР:[25], [52], [53], [54], [56], [57] и [58].В 1973 году Н. Нильсон написал книгу, посвященную методам поискарешений в пространстве состояний[60]. В 1976 году Р.
Дуда и П. Харт изложили исистематизировалиметодыраспознаванияобразовидалианализпространственных сцен по их плоскому изображению [28]. В 1981 году Г.Е.Минц, назвав обратный метод «резолютивными исчислениями», применил его кнеклассическим пропозициональным логическим исчислениям. В 1982 году М.Гэри и Д. Джонсон написали книгу, посвященную вопросам сложности решениязадач [24].В работе [59] обратный метод, хоть и названный «резолютивнымиисчислениями» впервые применяется к неклассическим пропозициональнымлогическимисчислениям.В[18]обратныйметодрассматриваетсядля6классической логики без равенства на основе обратного исчисления свободныхпеременных. В 1989 году выходит работа В. Лифшица в которой представленыосновные идеи обратного метода в форме, подчеркивающей его связь с методомрезолюций [99].
