Введение. 
Интеллектуальные системы

Суть понятия управляющей системы составляют следующие компоненты: элементы, схемы элементов, их функционирование и среда, с которой взаимодействует схема.

Элементы имеют входные и выходные каналы, через которые осуществляется связь с ними. Из элементов соединением входов одних из них с выходами других строятся схемы. Они также имеют входы и выходы. Такая схема реализует во времени (для определенности — дискретном) некоторый рекуррентный процесс ее взаимодействия со средой. Он определяется рядом допущений.

Элемент имеет состояния, которые меняются во времени за счет влияния текущего значения его входов и состояний в предыдущий момент. Эти значения и состояния определяют значения входов элементов. Заданность состояний элементов схемы и значения ее выходов, таким образом, могут определять текущие значения выходов ее элементов, а, значит, и состояния элементов в следующий момент. Таким образом, среда, формируя значения входов схемы, определяет при заданных начальных состояниях элементов значения выходов элементов и схемы в текущий момент и значения состояний элементов в последующий момент. Цикл взаимодействия схемы со средой повторяется и т. д. Этот процесс называют функционированием схемы.

Под управляющей системой может пониматься описанная схема, функционирующая в среде при взаимодействии с последней.

Функционирование схемы называют также поведением управляющей системы в среде.

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

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

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

Изучение свойств автоматов стало основным направлением в работе коллектива ученых факультета, которую образовали первый из авторов и его ученики. Были выделены и изучены основные среды, типы автоматов и виды поведения автоматов в средах, исследованы проблемы выразимости и полноты для автоматов, созданы методы оптимального синтеза помехоустойчивых автоматов, исследованы моделирующие возможности бесконечных автоматов, называемых клеточными автоматами и др.

Эти результаты вместе с достижениями Э. Мура, С. Клини, Д. Мак-Ноттона и др. сегодня составляют классическое содержание теории автоматов.

Одним из главных направлений этой теории является изучение поведения автоматов в средах. Идеология этого направления смыкается с тем, что изучается в теории интеллектуальных систем.

Так, автоматный анализ геометрических сред связан с распознаванием образов; анализ языковых сред — с языками, логическим выводом и решением задач; анализ смешанных языковогеометрических сред — с коллективным поведением и приняти;

Рис. 1: Интеллектуальная система.

ем решений; вопросы синтеза автоматов с заданным поведением сопряжены с разработкой внутренних для автоматов архитектур баз данных и знаний, быстрого поиска информации и т. д.

При разработке теории автоматов первый из авторов и его ученики постоянно расширяли сферу интерпретаций автоматов, используя модели и соответствующие задачи из разных областей таких, как математика, физика, биология, психология, социология, техника и др. Это обогащало теорию автоматов и расширяло сферу ее применимости.

Как сопряженная с моделью автомата рассматривается и интеллектуальная система.

Очертим в достаточно общем виде распространенный вариант интеллектуальной системы, которую считаем системой типа Тьюринга, и изображаем, как на рисунке 1.

Имеется объект О, помещенный в среду С, с которой у него имеется двусторонняя связь. Он может воспринимать информацию, поступающую из среды, и влиять на нее, что изображено соответствующим направлением стрелок.

Входная информация из С поступает в О на блок распознавания Р, оттуда она направляется в блок оперативной памяти П, где подвергается анализу. При этом анализе используется блок ДЗ базы данных и знаний, играющий роль долгосрочной памяти, а сам процесс анализа регулируется управляющим блоком У, который учитывает группу параметров, описывающих как внутренние характеристики объекта, так и состояние среды.

Базы данных и знаний вместе с блоком управления образуют «мозговой центр» системы. От достаточности заложенной в них информации и эффективности внутренних операторов зависят ее имитационные возможности.

Функционирование объекта в среде осуществляется во времени пошагово и оценивается серией внутренних и в общем случае внешних функционалов.

Последовательность значений этих функционалов считается характеризацией взаимодействия объекта и среды. По ней осуществляется оценка «разумности» поведения объекта, включая, в частности, заключение о том, сумел ли объект решить заданную задачу.

Конкретные интерпретации компонент, составляющих систему, приводят к конкретным видам интеллектуальных систем.

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

Его базы данных и знаний включают список стандартных приемов тождественных преобразований выражений алгебры и тригонометрии, основных теорем из этих разделов, а также логических операций вывода.

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

В этом блоке реализуется новая идея, позволившая обойти неэффективные попытки использовать для подобных целей логико-аксиоматический подход; упомяним в этой связи «General Problem Solver», «Mathematika» и др.

Эта интеллектуальная система, созданная третьим из авторов, показала высокую эффективность, справляясь за секунды с большинством задач из известных учебников.

Решатель демонстрировался на международной выставке компьютеров и программных продуктов в г. Ганновере (ФРГ), на российских и международных конференциях и семинарах.

Список же конкретных интеллектуальных систем сегодня очень широк.

В соответствии со схемой интеллектуальной системы, изображенной на рисунке 1, в курсе будут рассмотрены 3 основные составляющие интеллектуальной системы. Первая глава, посвященная распознаванию образов, связана с блоком распознавания Р. Вторая глава посвящена теории хранения и поиска информации и связана в блоком ДЗ — баз данных и знаний. И наконец, последняя глава курса, связанная с блоком управления У, посвящена математической логике.

Предлагаемое изложение осуществлено авторами на основе курса лекций, читаемых ими на протяжении ряда лет студентам, специализирующимся по кафедре математической теории интеллектуальных систем (МаТИС) механико-математического факультета МГУ им. М. В. Ломоносова. При курсе работают спецсеминары, рассчитанные на студентов третьего курса кафедры МаТИС. Руководство этими спецсеминарами в разные годы осуществляли сотрудники кафедры МаТИС Алексеев Д. В., Алисейчик П. А., Мазуренко И. Л., Пантелеев П. А., Холоденко А.Б.

Нам приятно поблагодарить весь коллектив кафедры МаТИС, чье постоянное внимание, доброжелательная критика и советы способствовали появлению этой книги. Авторы выражают особую благодарность В. А. Носову, А. С. Строганову и А. А. Часовских, которые принимали активное участие в разработке курса, и Алексееву Д. В., Алисейчику П. А., Мазуренко И. Л., Пантелееву П. А. и Холоденко А. Б. за помощь в составлении упражнений.

Рассматриваемая в книге область знаний активно развивается, и за время, прошедшее после предыдущего издания, было получено множество новых результатов, по которым было защищено 14 кандидатских работ, подготовлено к защите еще две работы и опубликованы сотни статей.

Прежде чем перейти рассмотрению отдельных разделов теории интеллектуальных систем приведем ссылки на обзорную статью акад. В. Б. Кудрявцева по этой тематике [83].

Академик В. Б. Кудрявцев и его ученики ведут активные исследования в области распознавания образов. Ими разработан новый комбинаторно-логический метод распознавания образов, исследованы его метрические свойства и эффективность; с его помощью решены задачи поиска нефти, олова и др. полезных ископаемых. В 2007 г. в была издана монография В. Б. Кудрявцева, А. Е. Андреева, Э. Э. Гасанова «Теория тестового распознавания» [84]. В ней построена теория распознавания дискретно характеризуемых объектов в конечном поле признаков. Теория основана на понятии теста и его вариаций. Введено несколько функционалов принятия решения для задачи распознавания, главным из которых является «голосующая» процедура. На основе нахождения тонких характеристик комбинаторных свойств тестов получены условия, когда «голосующая» процедура является эффективной как с точки зрения скорости, так и качества. В монографии систематизированы и подытожены исследования авторов и их учеников за последние 30 лет.

Профессором Э. Э. Гасановым и его учениками активно развивается теория хранения и поиска информации, являющаяся частью теории интеллектуальных систем [85]. В 2002 г. вышла монография Э. Э. Гасанова и В. Б. Кудрявцева «Теория хранения и поиска информации» [86]. В ней изучается раздел теории баз данных, связанный с физической организацией данных на носителях информации. Рассматриваются основные типы задач поиска информации в базах данных и предложены новые быстрые в среднем алгоритмы решения этих задач, и доказано, что они близки к оптимальным.

Т. Д. Уварова (Блайвас) занималась исследованиями сложности интервального поиска на булевом кубе [87]. В этом направлении достигнуты существенные продвижения. Получены точные значения сложности для сбалансированных деревьев и асимптотические оценки функции Шеннона в классе древовидных схем. По этим результатам в 2005 г. Т. Д. Уваровой под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «О сложности интервального поиска на булевом кубе».

В 2005 г. Т. А. Беляевой под руководством доц. А. С. Строгалова защищена кандидатская диссертация «Интерактивная компьютерная модель информационно-познавательной среды» [88].

Создана компьютерная обучающая система китайской письменности. По этим результатам Лю Юном в 2006 г. под руководством доц. А. С. Строгалова защищена кандидатская диссертация [89].

Последние две диссертации относятся к направлению обучающих систем, являющемуся частью теории интеллектуальных систем. Среди работ по обучающим системам можно также выделить работу В. Б. Кудрявцева, П. А. Алисейчика и А. С. Строгалова [90].

Профессором В. Н. Козловым и его учениками активно развивается теория зрительного восприятия [91]. В 2007 г. в издательстве МГУ вышел учебник В. Н. Козлова «Введение в математическую теорию зрительного восприятия» [92], содержание которого составили исследования, выполненные на кафедре МаТИС. В нем введено центральное понятие внутреннего кода конечно точечного изображения, которое позволило решить задачу распознавания с точностью до аффинных преобразований плоских и объемных изображений, а также восстановить объемное изображение через стереопару его плоских проекций.

Профессор А. С. Подколзин разработал и постоянно развивает новый подход к созданию технологий моделирования логических процессов, на основе которого создан компьютерный решатель математических задач (элементарная алгебра, геометрия, математический анализ, аналитическая геометрия и дифференциальные уравнения и т. д.) аналога которому нет в мире [93]. В 2008 г. была издана монография А. С. Подколзина «Компьютерное моделирование логических процессов. Архитектура и языки компьютерного решателя задач» [94] объемом 1024 страницы. Она содержит только оригинальные фундаментальные результаты по технологии синтеза компьютерных решателей математических задач. В 2015 г. вышел второй том, посвященный решателю математических задач, состоящий из двух книг «Компьютерное моделирование логических процессов. Опыт обучения компьютерного решателя задач: логические приемы, алгебра множеств, комбинаторика» [95] и «Компьютерное моделирование логических процессов. Опыт обучения компьютерного решателя задач: математический анализ, дифференциальные уравнения и элементарная геометрия» [96] объемом 1153 и 1320 страниц соответственно.

Рассмотрены варианты обобщений нейронных сетей с памятью, образующих алгебры относительно операций суперпозиции и обратной связи [97]. Эти алгебры введены как замыкание специальных порождающих множеств. Для них решены задачи описания функций, реализуемых соответствующими нейронными сетями, а также «экономного» канонического задания таких функций. На основе этих результатов В. С. Половниковым в 2008 г. под руководством доц. А. А. Часовских защищена кандидатская диссертация «Об оптимизации структурной реализации нейронных сетей».

Г. А. Майлыбаевой [98] построена математическая модель протоколов конфиденциального доступа к данным (РШ-протоколов), на основе которой получены рекордные нижние оценки коммуникационной сложности, доказывающие оптимальность по порядку разработанных PIR-протоколов. На основе этих результатов Г. А. Майлыбаевой в 2008 г. под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «Коммуникационная сложность протоколов доступа к данным без раскрытия запросов».

Исследованы свойства регулярных марковских языков и построены алгоритмы аппроксимации произвольных марковских языков языками из специального класса [99]. На основе этих результатов А. Б. Холоденко в 2008 г. под руководством проф. Д. Н. Бабина защищена кандидатская диссертация «Об автоматной аппроксимации реальных языков».

Построена математическая модель явления самоочищения легких живых систем [100]. Поставлены и решены ключевые проблемы, характеризующие это явление. Эта работа была выполнена как результат многолетнего и плотного сотрудничества кафедры МаТИС и института пульмонологии (ИП) РАМН. По этим результатам в 2009 г. Ю. Г. Черновой (Гераськиной) под руководством акад. В. Б. Кудрявцева защищена кандидатская диссертация «Автоматная модель одной транспортной системы в биологии» [101]. В 2015 г. в издательстве филиала МГУ в г. Ташкенте вышла монография Ю. Г. Черновой «Автоматное моделирование функционирования лёгких». Эта работа относится к направлению моделирования биологических систем, которым руководит акад. В. Б. Кудрявцев. Среди последних работ этого направления можно выделить [102—104].

В 2010 г. Н. С. Кучеренко под руководством проф. Э. Э. Гасанова защитила кандидатскую диссертацию «Сложность поиска в случайных базах данных». Ею построены серии функций роста сложности поиска информации в случайных базах данных в зависимости от функций распределения элементов баз данных и запросов, порождающие бесконечную возрастающую шкалу функций роста, которая начинается с ограниченных функций и заканчивается двоичным логарифмом [105].

В 2011 г. Ю. С. Шуткиным под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «Сложность реализации булевых функций информационными графами». Эта работа стала победителем конкурса «Ломоносов-2010». Ю. С. Шуткиным получена асимптотика сложности реализации булевых функций информационными графами и разработан метод синтеза контактных схем, асимптотически оптимальный и по мощности, и по объему [106].

В иностранной литературе распознавание образов является разделом такой области знаний как машинное обучение (Machine Learning). Другим разделом машинного обучения является расшифровка функций. В 2011 г. В. В. Осокиным под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «О расшифровке логических функций». Им получен порядок параллельной и параметро-эффективной сложности расшифровки некоторых классов логических функций [107]. Эта работа стала победителем конкурса «Ломоносов-2011». К области расшифровки функций также относятся работы С. И. Хегая [108], А. В. Быстрыговой [109].

В 2012 г. А. П. Пивоваровым под руководством проф. Э. Э. Гасанова защищена кандидатская диссертация «Неперечислительные задачи информационного поиска». Им разработаны математические модели для неперечислительных задач информационного поиска. Получены оценки сложности некоторых вычислительных задач информационного поиска и задач поиска представителя.

[110].

Одно из направлений исследований теории интеллектуальных систем — явление прогнозирования. В работах Э. Э. Гасанова и А. А. Мастихиной [111] предлагается использовать автоматный подход к моделированию явления прогнозирования. По этим результатам в 2012 г. А. А. Мастихина под руководством проф. Э. Э. Гасанова защитила кандидатскую диссертацию «Частичное предвосхищение сверхсобытий автоматами». Ею получены критерии частичной прогнозируемости автоматами общерегулярных множеств, сверхитераций языков, порожденных простыми LL (1) — грамматиками, сверхитераций детерминированных контекстносвободных языков.

В 2012 г. Е. А. Снегова (Скиба) под руководством проф. Э. Э. Гасанова защитила кандидатскую диссертацию «Сложность задачи о предотвращении столкновений». Ею получены критерии сводимости задачи о предотвращении столкновений к некоторым простым геометрическим задачам поиска, и на основе этого сведения получены сверхбыстрые алгоритмы поиска движущихся объектов [112].

В 2013 г. А. П. Соколовым под руководством проф. В. Б. Кудрявцева защищена кандидатская диссертация «О сложности перестройки формальных нейронов». Им получены оценки сложности взаимной перестройки (обучаемости) пар пороговых функций в самом сложном случае, в большинстве случаев и внутри классов пороговых функций, инвариантных относительно групп перестановок [113].

А. А. Плетневым разработана математическая модель динамических баз данных [114]. Эта модель основывается на двух основных понятиях: понятии информационного графа, который отражает структуру хранения данных, и понятии конечного автомата, который отвечает за перестройку структуры базы данных в соответствии запросами на вставку и удаление данных. Эта конструкция названа динамическим информационным графом. Исследуется вопрос обслуживания динамическим информационным графом произвольных потоков запросов. Здесь идет речь о одновременной бесконфликтной работе сколь угодно большого количества автоматов на одной структуре данных. Фактически предлагаемый подход позволяет строить бесконечно распараллеливаемые алгоритмы обработки данных. На основе этих результатов А. А. Плетневым под руководством проф. Э. Э. Гасанова подготовлена кандидатская диссертация «Моделирование динамических баз данных».

Е. М. Перпер исследовал задачи поиска, возникающие при семантическом анализе текстов, в частности задача поиска подслова в базе данных слов [115—116]. Им получены нижние оценки временной и объёмной сложности задачи поиска подслова и предложен оптимальный по порядку алгоритм поиска в множестве слов вхождений подслова. На основе разработанных алгоритмов Е. М. Перпером предложен подход, который позволяет по тексту нормативного акта автоматически строить компьютерную программу, которая выполняет действия, предписанные нормативным актом. На основе этих результатов Е. М. Перпером под руководством проф. Э. Э. Гасанова подготовлена кандидатская диссертация «Семантический анализ текстов и связанные с ним задачи поиска».

Сейчас подготавливается к публикации монография В. Б. Кудрявцева, Э. Э. Гасанова, А. С. Подколзина «Основы теории интеллектуальных систем», которая будет включать в себя многие из выше перечисленных результатов, а также будет содержать главу по теории автоматов, отражающую как классические, так и самые последние результаты в этом направлении.

Для облегчения изучения данной книги могут оказаться полезными следующие учебники, вышедшие в издательстве «» [117−122].