Некоторые задачи искусственного интеллекта, допускающие формализацию на языке исчисления предикатов, и оценки числа шагов их решения
Ключевые слова:
искусственный интеллект, исчисление предикатов, сложность алгоритмов, NP-полнотаАннотация
Ряд задач искусственного интеллекта, включающих в себя такие задачи как распознавание образов, медицинская диагностика, анализ рынка, сведены к доказательству выполнимости формул исчисления предикатов, имеющих простую структуру. Рассмотрены некоторые алгоритмы решения этих задач и доказаны верхние оценки числа шагов этих алгоритмов.Литература
Гэри М., Джонсон Д.} Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с
Журавлёв Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. Математические методы и их применение. 1989. Вып. 1. С.9--16.
ЗакревскийА.Д. Выявление импликативных закономерностей в булевом пространстве признаков и распознавание образов // Кибернетика. 1982. №1. С.1--6
Клини С. Математическая логика. М.: Мир, 1973. 480с.
Косовская Т.М., Тимофеев А.В. Об одном новом подходе к формированию логических решающих правил // Вестник ЛГУ. 1985. №8. С.22–-27.
Косовская Т.М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вестник Санкт-Петербургского университета. Сер.1. 2007. Вып.4. С.82--90.
Косовский Н.К. Элементы математической логики и её приложения к теории субрекурсивных алгоритмов. Л.: Изд-во ЛГУ, 1981. 192с.
Маслов С.Ю. Связь между тактиками обратного метода и метода резолюций // Записки научных семинаров ЛОМИ АН СССР. 1969. Т.16. С.137--146.
Нильсон Н. Искусственный интеллект. М.: Мир, 1973. 270с.
Рассел С., Норвиг П. Искусственный интеллект: современный подход, 2-е изд.: Пер. с англ. М.: Издательский дом <<Вильямс>>, 2006. 1408с.
Оревков В.П. Обратный метод поиска вывода [Приложение 4] // В кн. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. СПб: БХВ-Петербург, 2003. 992 с.
Робинсон Дж. Машинно ориентированная логика, основанная на методе резолюций // Кибернетический сборник, новая серия. 1970. Вып.7. С.194--218.
Журавлёв Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. Математические методы и их применение. 1989. Вып. 1. С.9--16.
ЗакревскийА.Д. Выявление импликативных закономерностей в булевом пространстве признаков и распознавание образов // Кибернетика. 1982. №1. С.1--6
Клини С. Математическая логика. М.: Мир, 1973. 480с.
Косовская Т.М., Тимофеев А.В. Об одном новом подходе к формированию логических решающих правил // Вестник ЛГУ. 1985. №8. С.22–-27.
Косовская Т.М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вестник Санкт-Петербургского университета. Сер.1. 2007. Вып.4. С.82--90.
Косовский Н.К. Элементы математической логики и её приложения к теории субрекурсивных алгоритмов. Л.: Изд-во ЛГУ, 1981. 192с.
Маслов С.Ю. Связь между тактиками обратного метода и метода резолюций // Записки научных семинаров ЛОМИ АН СССР. 1969. Т.16. С.137--146.
Нильсон Н. Искусственный интеллект. М.: Мир, 1973. 270с.
Рассел С., Норвиг П. Искусственный интеллект: современный подход, 2-е изд.: Пер. с англ. М.: Издательский дом <<Вильямс>>, 2006. 1408с.
Оревков В.П. Обратный метод поиска вывода [Приложение 4] // В кн. Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. СПб: БХВ-Петербург, 2003. 992 с.
Робинсон Дж. Машинно ориентированная логика, основанная на методе резолюций // Кибернетический сборник, новая серия. 1970. Вып.7. С.194--218.
Some artificial intelligence problems permitting formalization by means of predicate calculus language and upper bounds of their solution steps
Abstract
Some artificial intelligence problems including such ones as pattern recognition, medical diagnostics, market analysis is reduced to the proof of satisfi\-abi\-li\-ty of predicate calculus formulas with a symple structure. Some algorithms solving such problems are regarded and the upper bounds of their steps are proved.Опубликован
2010-09-01
Как цитировать
Косовская, Т. М. (2010). Некоторые задачи искусственного интеллекта, допускающие формализацию на языке исчисления предикатов, и оценки числа шагов их решения. Труды СПИИРАН, 3(14), 58-75. https://doi.org/10.15622/sp.14.4
Раздел
Статьи
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
