Декларативное программирование

Непроцедурное (декларативное) программирование появилось в начале 70-х годов 20 века, но стремительное его развитие началось в 80-е годы, когда был разработан японский проект создания ЭВМ пятого поколения, целью которого явилась подготовка почвы для создания интеллектуальных машин.

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

Декларативное программирование можно подразделить на два семейства – функциональное (Лисп) и логическое (типичный представитель – Пролог).

Функциональное программирование

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

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

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

Для успешного овладения данным стилем программирования, необходимо весьма глубокое понимание многих разделов математики.

Логическоепрограммирование

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

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

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

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

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

Лекция 13
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ АЛГОРИТМОВ

1 Определение алгоритма и понятие его исполнителя

2 Классы моделей алгоритмов

3 Формы записи алгоритмов