19. Методология логического программирования

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

Методы и концепции:

1. Применение единого механизма логического доказательства ко всей программе.

2. Унификация структур данных при декомпозиции.

Синтаксис и семантика задаются при помощи фактов (аксиом) и правил вывода. Правила вывода имеют вид так называемых «дизъюнктов Хорна» – утверждений вида:

А <= B₁& … &B_n

Аксиомы в программах обычно представляются, как правила с пустой «посылкой»:

А

Известные языки логического программирования:

1. Prolog (1971)

2. LOGLISP (1982)

3. Mercury (1993)

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

20. Методология программирования в ограничениях

Для данной методологии характерно, что в программе определяются:

• тип данных решения;

• предметная область решения;

• ограничения на значение искомого решения.

Синтаксис и семантика. В данном случае постановка задачи – это:

1. Конечный набор переменных V = {v[1], …, v[n]}.

2. Набор соответствующих им конечных множеств значений

D = {d[1], …, d[n]}.

3. Набор ограничений C = {c[1], …, c[m]}.

Ограничения представляются как утверждения, в которые в качестве «параметров» входят переменные из некоторого подмножества V[j], j=1..m набора V.

Решение задачи – это набор значений переменных, удовлетворяющий всем ограничениям C[j].

Исполнение программы – это нахождение значений переменных.

Языки программирования в ограничениях:

1. Sketchpad (1963)

2. УТОПИСТ (1980)

3. Thinglab (1980)

4. IDEAL (1981)

5. OPS5 (1987)

6. Bertrand (1998)

7. OPL (1998)

Пример программы на языке УТОПИСТ (Универсальные Текстовые ОПИСания Терминов):

ПУСТЬ`

СХЕМА: (I1, I2, I3, U1, U2, U3, R1, R2, R3: ВЕЩ`;

УРАВ` U1 = I1 * R1;

УРАВ` U2 = I2 * R2;

УРАВ` U3 = I3 * R3;

УРАВ` I1 + I2 + I3 = 0);

СХЕМА1: СХЕМА

R1 = 16, R2 = 32, R3 = 5,

U1 = 50, U2 = -28;

ДЕЙСТВИЯ`

НА` СХЕМА1 ВЫЧИСЛИТЬ` U3;

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

21. Методология структурного императивного программирования

Подход заключается в задании хорошей топологии императивных программ за счёт следующих приёмов:

1. Отказ от использования глобальных данных.

2. Отказ от оператора безусловного перехода.

3. Разработка модулей с сильной связностью и обеспечение их независимости от других модулей.

Методы и концепции:

1. Метод алгоритмической декомпозиции сверху вниз. Заключается в пошаговой детализации постановки задачи, начиная с наиболее общей задачи.

2. Метод модульной организации частей программы. Заключается в использовании при кодировании трёх основных управляющих конструкций (следование, ветвление, цикл).

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

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