Системы искусственного интеллекта. Тематический план
 Скачать 1.4 Mb.
|
|
ТЕМА 2.1 МЕТОДОЛОГИИ ПРОГРАММИРОВАНИЯ План лекции: 2.1.1 Методология императивного программирования 2.1.2 Методология объектно-ориентированного программирования 2.1.3 Методология функционального программирования 2.1.4 Методология логического программирования 2.1.5 Методология программирования в ограничениях 2.1.6 Методология нейросетевого программирования 2.1.1 Методология императивного программирования На сегодня существует не так много методологий, особенно полных, т. е. учитывающих все стадии жизненного цикла программного обеспечения. Именно методология определяет, какие языки и системы будут применяться для разработки программного обеспечения и какой технологический подход будет при этом использован. Подход к методологиям заключается в том, что существует некоторое ядро методологии со своими методами, которое уточняется некоторыми дополнительными особенностями. Ядра же методологий определяются способом описания алгоритмов. Перечислим основные ядра методологий и посвятим следующие разделы книги их подробному анализу: - методология императивного программирования; - методология объектно-ориентированного программирования; - методология функционального программирования; - методология логического программирования. Некоторые методологии имеют алгоритмическое происхождение. Четыре главных модели алгоритма математически эквивалентны, но на практике они породили разные направления в программировании, в том числе некоторые основные методологии: - абстрактные вычислительные машины Тьюринга и Поста — определяют методологию императивного программирования; - рекурсивные функции Гильберта и Аккермана — от них унаследовала свои идеи и конструкции методология структурного программирования; - лямбда-исчисление Черча, Шейнфинкеля и Карри — эти идеи активно развиваются в методологии функционального программирования; - нормальные алгоритмы Маркова — эта модель послужила основой логического программирования и обработки символьной информации. Данный подход характеризуется принципом последовательного изменения состояния вычислителя пошаговым образом. При этом управление изменениями полностью определено и полностью контролируемо. Императивное программирование — это исторически первая аппаратно поддерживаемая методология программирования. Она ориентирована на классическую фон Неймановскую модель, остававшуюся долгое время единственной аппаратной архитектурой, получившей широкое практическое применение. Императивное программирование основано на описании последовательного изменения состояний вычислителя. Если под вычислителем понимать современный компьютер, то его состоянием будут значения всех его ячеек памяти, состояние процессора (в том числе значение указателя текущей команды) и всех сопряженных устройств. Единственная структура данных здесь — это последовательность ячеек (пар «адрес — значение») с линейно упорядоченными адресами. Языки, поддерживающие данную вычислительную модель, являются компактным средством описания функции переходов между состояниями вычислителя. В качестве математической модели императивное программирование использует машину Тьюринга—Поста — абстрактное вычислительное устройство, предложенное на заре компьютерной эры для описания алгоритмов. Основным синтаксическим понятием здесь является оператор, причем возможно несколько разновидностей (групп) таких операторов. Первая группа — это атомарные операторы, у которых никакая часть не является самостоятельным оператором (например, операторы присваивания, безусловного перехода, вызова процедуры и т. п.). Вторая группа — структурные операторы, объединяющие другие операторы в новый, более крупный оператор (например, составной оператор, оператор выбора, цикла и т. д.). Операторы исполняются в порядке, предписанном объемлющим их структурным оператором. Если это составной оператор, то входящие в него операторы исполняются в том порядке, в котором они записаны. Традиционное средство структурирования — подпрограмма (процедура или функция). Подпрограммы имеют параметры и локальные определения и могут быть вызваны рекурсивно. Функции же возвращают значения как результат своей работы. Императивные языки программирования манипулируют данными в пошаговом режиме, используя последовательные инструкции и применяя их к тем или иным данным. Наиболее известные и распространенные императивные языки программирования — Fortran, Algol, Pascal, C. Императивное программирование наиболее пригодно для решения задач, в которых последовательное исполнение каких-либо команд является естественным. Примером может служить управление современными аппаратными средствами: поскольку практически все современные компьютеры императивны, эта методология позволяет получать достаточно эффективный исполняемый код. Однако с ростом сложности задачи императивные программы становятся все менее читабельными. Важнейшим развитием императивной методологии является методология структурного императивного программирования — подход, заключающийся в отказе от использования глобальных данных и оператора безусловного перехода, в разработке модулей с сильной связностью и обеспечении их независимости от других модулей. Этот подход базируется на двух основных принципах: - последовательная декомпозиция алгоритма решения задачи сверху вниз; - использование структурного кодирования. Создателем структурного подхода считается Эдсгер Дейкстра. Ему также принадлежит попытка (к сожалению, совершенно неприменимая для массового программирования) соединить структурное программирование с методами доказательства правильности программ. 2.1.2 Методология объектно-ориентированного программирования Этот подход использует объектную декомпозицию, при которой статическая структура системы описывается в терминах объектов и связей между ними, а поведение системы описывается в терминах обмена сообщениями между объектами. На возникновение объектного мышления оказали влияние моделирование и представление данных, графические пользовательские интерфейсы и системное программирование (с понятием «процесс»). Исследования в области моделирования реальных систем привели к необходимости создания средств естественного описания сущностей, которые в них встречаются, — объектов и событий. Позже оказалось, что такие концепции, как инкапсуляция (абстрактные типы данных), наследование и полиморфизм, являются весьма полезным дополнением к традиционному структурному программированию. Возможность их достаточно эффективной реализации привела к созданию широко распространенных в наши дни объектно-ориентированных языков программирования. Вычислительная модель «чистого» объектно-ориентированного программирования (ООП) явно поддерживает только одну операцию, которой является посылка объекту сообщения. Такие сообщения могут иметь параметры, являющиеся объектами; само сообщение также является объектом. Объект имеет набор обработчиков сообщений (методов). У объекта также есть поля — «персональные» переменные для данного объекта, значениями которых являются ссылки на другие объекты. В одном из полей объекта хранится ссылка на объект-предок, которому переадресуются все сообщения, не обрабатываемые данным объектом. Структуры, описывающие обработку и переадресацию сообщений, обычно выделяют в отдельный объект, называемый классом данного объекта, тогда как сам объект называют экземпляром указанного класса. В синтаксисе «чистых» объектно-ориентированных языков все может быть записано в форме посылки сообщений объектам. Класс в объектно- ориентированных языках описывает структуру и функционирование множества объектов с аналогичными характеристиками, атрибутами и поведением. Объект здесь естественным образом принадлежит к некоторому классу и обладает своим собственным внутренним состоянием. Методы же представляют собой функциональные свойства, которые можно активизировать. В объектно-ориентированном программировании определяют три основных свойства: - инкапсуляция — скрытие информации и комбинирование данных и функций, которые аналогичны абстрактным типам данных; - наследование — построение иерархии порожденных объектов с возможностью для каждого такого объекта, относящегося к иерархии, доступа к коду и данным всех порождающих объектов; - полиморфизм (полиморфизм включения) — присваивание действию одного имени, которое затем разделяется вверх и вниз по иерархии объектов, причем каждый объект иерархии выполняет это действие способом, подходящим именно ему. Объектно-ориентированные языки программирования содержат конструкции, позволяющие определять объекты, принадлежащие классам и обладающие свойствами инкапсуляции, наследования и полиморфизма. Наиболее распространенные объектно-ориентированные языки — С++, Object Pascal, Java, Visual Basic и др. Данная методология является мощным средством для моделирования отношений между объектами практически в любой предметной области. Особенно удобно и легко в форме объектов выражать взаимодействие между различными элементами графического интерфейса пользователя. 2.1.3 Методология функционального программирования Данная методология представляет собой способ составления программ, в которых единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени для функции и задание для этого имени выражения, вычисляющего значения функции, а единственным правилом композиции является оператор суперпозиции функции. Функциональная методология — одна из старейших. По происхождению она тесно связана с лямбда-исчислением, изобретенным еще в начале 1930-х гг. логиком Алонзо Черчем (Alonzo Church). Для многих людей функциональная методология стала ассоциироваться с языком Lisp, созданным Джоном Маккарти (John McCarthy) в конце 1950-х гг. В то же время эта методология в основном используется теоретиками программирования и является средством лабораторных исследований искусственного интеллекта. Метод аппликативности заключается в том, что программа есть выражение, составленное из применений функций к их аргументам. Программа при этом состоит из совокупности определений функций, представляющих собой вызовы других функций и предложений, управляющих последовательностью вызовов. Данный метод поддерживается концепцией функции. Метод рекурсивного поведения заключается в самоповторяющемся поведении, возвращающемся к самому себе. Данный метод поддерживается концепцией рекурсии. Метод настраиваемости заключается в том, что можно легко порождать новые программные объекты по образцу как значения соответствующих выражений (применяя порождающую функцию к параметрам образца). Этому способствует то, что в идеале не только программа, но и любой программный объект является выражением. Функциональное программирование представляет собой одну из альтернатив императивному подходу. В функциональном программировании отсутствует понятие времени, программы являются выражениями, а исполнение программ заключается в вычислении этих выражений. В качестве математической модели функциональное программирование использует лямбда-исчисление Черча. Функциональные языки программирования — это языки, в которых, как уже говорилось, единственным действием является вызов функции, единственным способом расчленения программы на части является введение имени для функции и задание для этого имени выражения, вычисляющего значения функции, а единственным правилом композиции — оператор суперпозиции функции. Основная специфика функциональных языков программирования заключается в том, что функции обмениваются между собой данными непосредственно, т. е. без использования промежуточных переменных и присваиваний, а переменные, однажды получив значение, никогда его не изменяют. (Присваивание же, например, в императивной методологии, — это конструкция, «вносящая время» в процесс вычисления: правая часть присваивания должна быть вычислена, и только после этого ее значение будет связано с левой частью.) В результате в функциональных языках циклы заменяются аппаратом рекурсивных функций. Функциональное программирование обычно применяется для решения задач, которые трудно сформулировать в терминах последовательных операций. В эту категорию попадают и практически все задачи, связанные с искусственным интеллектом, — такие как обработка естественного языка, экспертные (консультирующие) системы, проблемы зрительного восприятия и многие другие. 2.1.4 Методология логического программирования Согласно данному подходу, программа содержит описание проблемы в терминах фактов и логических формул, а решение проблемы система находит с помощью механизмов логического вывода. Логическое программирование появилось в конце 1960-х гг., когда Корделл Грин (Cordell Green) предложил использовать резолюцию как основу логического программирования. Позже, в 1970-х гг., Алан Колмероэ (Alain Colmerauer) создал язык логического программирования Prolog. В основе логических языков лежит теория хорновских дизъюнктов. Логическое программирование пережило пик популярности в середине 1980-х гг., когда оно было положено в основу проекта разработки программного и аппаратного обеспечения вычислительных систем пятого поколения [7]. В логике теории задаются при помощи аксиом и правил вывода. То же самое мы имеем и в базисном языке логического программирования Prolog, — только аксиомы здесь принято называть фактами, а правила вывода ограничивать по форме до так называемых «дизъюнктов Хорна» — утверждений вида А <= B1& ... &Bn. В языке Prolog такие утверждения принято записывать следующим образом: а :- b1, ..., bn Факты (они же аксиомы) представляются в языке Prolog как правила с пустой «посылкой», например, а. Обычно Prolog-система работает в форме диалога с пользователем. Утверждение, которое требуется доказать, вводится с клавиатуры. Однако компилирующие версии трансляторов Prolog могут располагать и специальными синтаксическими средствами для задания утверждений, которые требуется доказать. Такие утверждения в Prolog принято называть целями. Prolog-система использует для доказательства утверждений метод унификации и метод резолюций. Унификация — это сопоставление двух произвольных термов, содержащих переменные, чтобы определить, можно ли присвоить этим переменным такие значения, чтобы получились два одинаковых терма. Метод резолюций же заключается в последовательном доказательстве отдельных утверждений, входящих в посылку дизъюнкта Хорна, для доказательства его следствия. Например, применение метода резолюций к правилу а :- b, c. и утверждению а приведет к последовательному доказательству утверждений b и с. Метод резолюций имеет прямой аналог в обычной логике высказываний, — это правило modus ponens, согласно которому (А & А => В) => В. Логические языки программирования обычно содержат в себе конструкции, позволяющие выполнить описание проблемы в терминах фактов и логических формул, тогда как собственно решение проблемы выполняет программная система с помощью механизмов логического вывода. Неотъемлемой частью такого языка программирования является и механизм конструктивного вывода целевого утверждения, основанный на строгих математических моделях. Язык Prolog является родоначальником целого семейства подобных ему языков, в котором можно выделить три ветви: - модификации языка (использование более мощных логических средств, внесение модульности и т. п.); - функциональное направление (комбинация с функциональными языками); - направление, связанное с использованием параллельных вычислений (так как логическое программирование по сути своей параллелизуемо). Отметим, что класс задач логического программирования практически совпадает с классом задач функционального программирования. 2.1.5 Методология программирования в ограничениях Рассмотрим теперь другие, менее распространенные методологии, применяемые при решении задач искусственного интеллекта. Методология программирования в ограничениях — это подход, в котором в программе для искомого решения определяется тип данных, предметная область и ограничения на его значение. Решение же отыскивается системой. Данная методология предполагает двухуровневую архитектуру, интегрирующую компонент ограничений и программный компонент. Компонент ограничений при этом обеспечивает основные операции и состоит из системы выводов на фундаментальных свойствах системы ограничений. Операции, окружающие компонент ограничений, реализуются программно-языковым компонентом. Методология программирования в ограничениях возникла в начале 1980-х гг. как перспективная область исследований на пересечении символьных вычислений, искусственного интеллекта, исследования операций и интервальной арифметики. Программирование в ограничениях — это программирование в терминах постановок задач. Постановка задачи представляет собой конечный набор переменных V = {v[1], ..., v[n]}, соответствующих им конечных (перечислимых) множеств значений D = {D[1], ..., D[n]} и набор ограничений C = {С[1], ..., C[m]}. При этом ограничения представлены как утверждения, в которые в качестве «параметров» входят переменные из некоторого подмножества v[j], j = 1 ... m заданного набора V. Решение такой задачи есть набор значений переменных, удовлетворяющий всем ограничениям C[j]. Семантически исполнение программы здесь рассматривается как нахождение значений переменных. Языки программирования в ограничениях также получили наибольшую известность в 1980-х гг. Язык программирования «УТОПИСТ» («Универсальные Текстовые Описания Терминов») предназначен для описания понятий и задач. Этот язык является базовым для инструментальной системы программирования «ПРИЗ». Он имеет процедурную часть (поскольку при описании задачи иногда приходится описывать действия), но основная его выразительность достигается за счет описаний. К классу задач программирования в ограничениях относятся задачи исследования операций и искусственного интеллекта. В них часто используется некоторое пространство решений, сужением которого и достигается необходимый результат. Такое сужение исходного пространства решений можно естественным образом представить как ограничения. 2.1.6 Методология нейросетевого программирования Методология нейросетевого программирования — это подход, заключающийся в том, что на основе знаний, полученных от экспертов, создается программа на нейронном языке программирования, которая затем компилируется в эквивалентную нейронную сеть из аналоговых нейронов. |