Автореферат (1150568)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

На правах рукописиПетухова Нина ДмитриевнаРазработка и оценка числа шагов работыалгоритмоврешения задач логико-предметного распознаванияобразов с использованием тактик обратного метода Маслова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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации