ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.01.2024
Просмотров: 302
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
такие концепции, как инкапсуляция (абстрактные типы данных), наследование и полиморфизм, являются весьма полезным дополнением к традиционному структурному программированию. Возможность их достаточно эффективной реализации привела к созданию широко распространенных в наши дни объектно-ориентированных языков программирования.
Вычислительная модель
«чистого» объектно-ориентированного программирования (ООП) явно поддерживает только одну операцию, которой является посылка объекту сообщения. Такие сообщения могут иметь параметры, являющиеся объектами; само сообщение также является объектом.
Объект имеет набор обработчиков сообщений (методов). У объекта также есть поля — «персональные» переменные для данного объекта, значениями которых являются ссылки на другие объекты. В одном из полей объекта хранится ссылка на объект-предок, которому переадресуются все сообщения, не обрабатываемые данным объектом. Структуры, описывающие обработку и переадресацию сообщений, обычно выделяют в отдельный объект, называемый классом данного объекта, тогда как сам объект называют экземпляром указанного класса.
В синтаксисе «чистых» объектно-ориентированных языков все может быть записано в форме посылки сообщений объектам. Класс в объектно- ориентированных языках описывает структуру и функционирование множества объектов с аналогичными характеристиками, атрибутами и поведением. Объект здесь естественным образом принадлежит к некоторому классу и обладает своим собственным внутренним состоянием. Методы же представляют собой функциональные свойства, которые можно активизировать.
Вычислительная модель
«чистого» объектно-ориентированного программирования (ООП) явно поддерживает только одну операцию, которой является посылка объекту сообщения. Такие сообщения могут иметь параметры, являющиеся объектами; само сообщение также является объектом.
Объект имеет набор обработчиков сообщений (методов). У объекта также есть поля — «персональные» переменные для данного объекта, значениями которых являются ссылки на другие объекты. В одном из полей объекта хранится ссылка на объект-предок, которому переадресуются все сообщения, не обрабатываемые данным объектом. Структуры, описывающие обработку и переадресацию сообщений, обычно выделяют в отдельный объект, называемый классом данного объекта, тогда как сам объект называют экземпляром указанного класса.
В синтаксисе «чистых» объектно-ориентированных языков все может быть записано в форме посылки сообщений объектам. Класс в объектно- ориентированных языках описывает структуру и функционирование множества объектов с аналогичными характеристиками, атрибутами и поведением. Объект здесь естественным образом принадлежит к некоторому классу и обладает своим собственным внутренним состоянием. Методы же представляют собой функциональные свойства, которые можно активизировать.
В объектно-ориентированном программировании определяют три основных свойства:
- инкапсуляция — скрытие информации и комбинирование данных и функций, которые аналогичны абстрактным типам данных;
- наследование — построение иерархии порожденных объектов с возможностью для каждого такого объекта, относящегося к иерархии, доступа к коду и данным всех порождающих объектов;
- полиморфизм (полиморфизм включения) — присваивание действию одного имени, которое затем разделяется вверх и вниз по иерархии объектов, причем каждый объект иерархии выполняет это действие способом, подходящим именно ему.
Объектно-ориентированные языки программирования содержат конструкции, позволяющие определять объекты, принадлежащие классам и обладающие свойствами инкапсуляции, наследования и полиморфизма.
Наиболее распространенные объектно-ориентированные языки — С++,
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 и с. Метод резолюций
В логике теории задаются при помощи аксиом и правил вывода. То же самое мы имеем и в базисном языке логического программирования Prolog,
— только аксиомы здесь принято называть фактами, а правила вывода ограничивать по форме до так называемых «дизъюнктов Хорна» — утверждений вида А <= B1& ... &Bn. В языке Prolog такие утверждения принято записывать следующим образом:
а :- b1, ..., bn
Факты (они же аксиомы) представляются в языке Prolog как правила с пустой «посылкой», например, а.
Обычно Prolog-система работает в форме диалога с пользователем.
Утверждение, которое требуется доказать, вводится с клавиатуры. Однако компилирующие версии трансляторов Prolog могут располагать и специальными синтаксическими средствами для задания утверждений, которые требуется доказать. Такие утверждения в Prolog принято называть целями.
Prolog-система использует для доказательства утверждений метод унификации и метод резолюций. Унификация — это сопоставление двух произвольных термов, содержащих переменные, чтобы определить, можно ли присвоить этим переменным такие значения, чтобы получились два одинаковых терма. Метод резолюций же заключается в последовательном доказательстве отдельных утверждений, входящих в посылку дизъюнкта
Хорна, для доказательства его следствия. Например, применение метода резолюций к правилу а :- b, c. и утверждению а приведет к последовательному доказательству утверждений b и с. Метод резолюций
имеет прямой аналог в обычной логике высказываний, — это правило modus ponens, согласно которому (А & А => В) => В.
Логические языки программирования обычно содержат в себе конструкции, позволяющие выполнить описание проблемы в терминах фактов и логических формул, тогда как собственно решение проблемы выполняет программная система с помощью механизмов логического вывода. Неотъемлемой частью такого языка программирования является и механизм конструктивного вывода целевого утверждения, основанный на строгих математических моделях.
Язык Prolog является родоначальником целого семейства подобных ему языков, в котором можно выделить три ветви:
- модификации языка (использование более мощных логических средств, внесение модульности и т. п.);
- функциональное направление (комбинация с функциональными языками);
- направление, связанное с использованием параллельных вычислений (так как логическое программирование по сути своей параллелизуемо).
Отметим, что класс задач логического программирования практически совпадает с классом задач функционального программирования.
2.1.5 Методология программирования в ограничениях
Рассмотрим теперь другие, менее распространенные методологии, применяемые при решении задач искусственного интеллекта.
Методология программирования в ограничениях — это подход, в котором в программе для искомого решения определяется тип данных, предметная область и ограничения на его значение. Решение же отыскивается системой. Данная методология предполагает двухуровневую архитектуру, интегрирующую компонент ограничений и программный
Логические языки программирования обычно содержат в себе конструкции, позволяющие выполнить описание проблемы в терминах фактов и логических формул, тогда как собственно решение проблемы выполняет программная система с помощью механизмов логического вывода. Неотъемлемой частью такого языка программирования является и механизм конструктивного вывода целевого утверждения, основанный на строгих математических моделях.
Язык 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-х гг.
Язык программирования «УТОПИСТ» («Универсальные Текстовые Описания
Терминов») предназначен для описания понятий и задач. Этот язык является базовым для инструментальной системы программирования «ПРИЗ». Он имеет процедурную часть (поскольку при описании задачи иногда приходится описывать действия), но основная его выразительность достигается за счет описаний.
К классу задач программирования в ограничениях относятся задачи исследования операций и искусственного интеллекта. В них часто используется некоторое пространство решений, сужением которого и
Методология программирования в ограничениях возникла в начале
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 Методология нейросетевого программирования
Методология нейросетевого программирования — это подход, заключающийся в том, что на основе знаний, полученных от экспертов, создается программа на нейронном языке программирования, которая затем компилируется в эквивалентную нейронную сеть из аналоговых нейронов.
2.1.6 Методология нейросетевого программирования
Методология нейросетевого программирования — это подход, заключающийся в том, что на основе знаний, полученных от экспертов, создается программа на нейронном языке программирования, которая затем компилируется в эквивалентную нейронную сеть из аналоговых нейронов.
1 2 3 4 5 6 7 8 9
ТЕМА 2.2 КРАТКОЕ ВВЕДЕНИЕ В ИСЧИСЛЕНИЕ
ПРЕДИКАТОВ И ДОКАЗАТЕЛЬСТВО ТЕОРЕМ
Высказывание — это логическое утверждение, которое может быть истинным или ложным. Оно состоит из объектов и отношений между ними.
Символьную логику (symbolic logic) можно использовать для решения трех основных задач формальной логики: для выражения высказываний, выражения отношений между высказываниями и описания способов вывода новых высказываний из других высказываний, считающихся истинными.
Объекты в высказываниях логического программирования представляются простыми термами, являющимися либо константами, либо переменными. Константа — это символ, представляющий некий объект.
Переменная — это символ, который может представлять разные объекты в разное время, хотя в некотором смысле переменная в этом контексте намного ближе к математическому пониманию переменной, чем к переменным в императивных языках программирования.
Простейшие высказывания, называемые атомарными высказываниями, состоят из составных термов. Составной терм — это элемент математического отношения, формально записанного в виде математической функции.
Составной терм состоит из двух частей: функтора (functor), представляющего собой функциональный символ, называющий отношение, и упорядоченного списка параметров.
Примеры:
человек (Джек) любит (Боб, стейк)
Высказывания можно формулировать двумя способами: в первом случае высказывание считается истинным, а во втором истинность высказывания требуется установить. Иными словами, высказывания можно формулировать либо как факты, либо как запросы. Высказывания в примерах, приведенных выше, могут представлять собой как факты, так и запросы.
Исчисление предикатов дает нам метод для выражения совокупностей высказываний. Использовать совокупности высказываний — это означает определять, можно ли вывести из них какие-нибудь интересные или полезные факты. Последнее аналогично работе математиков, старающихся открыть новые теоремы, которые можно вывести из уже известных аксиом и теорем.
В 1950-х — начале 1960-х гг. процессу автоматического доказательства теорем уделялось большое внимание. Одним из крупных научных достижений в этой области было открытие принципа резолюции (resolution)
Аланом Робинсоном (Alan Robinson) из Сиракузского университета.
Резолюция (resolution) — это правило логического вывода, позволяющее вычислять выводимые высказывания по заданным высказываниям, обеспечивая таким образом метод, имеющий потенциальные приложения в области автоматического доказательства теорем. Резолюция была изобретена для применения к высказываниям в дизъюнктивной форме.
Концепция резолюции заключается в следующем. Предположим, что нам даны два высказывания в следующих формах:
Старше (Джоанна, Джек) => мать (Джоанна, Джек)
мудрее (Джоанна, Джек) => старше (Джоанна, Джек)
По этим высказываниям, используя резолюцию, можно построить новое высказывание: мудрее (Джоанна, Джек) => мать (Джоанна, Джек)
Механизм этой резолюции прост: термы в левых частях этих двух высказываний объединяются с помощью логической операции «И», образуя левую часть нового высказывания. Затем точно так же формируется правая часть нового высказывания:
Старше (Джоанна, Джек) И мудрее (Джоанна, Джек) =>
=> мать (Джоанна, Джек) И старше (Джоанна, Джек)
Далее терм, появляющийся в обеих частях нового высказывания, удаляется из них («сокращается»):