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

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

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

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

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

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

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. Метод модульной организации частей программы. Заключается в использовании при кодировании трёх основных управляющих конструкций (следование, ветвление, цикл).

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

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

22. Методология параллельного
императивного программирования

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

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

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

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

- параллелизм на уровне микрокоманд;

- параллелизм на уровне операторов;

- параллелизм на уровне циклов и итераций;

- параллелизм на уровне подпрограмм;

- параллелизм на уровне потоков управления;

- параллелизм на уровне процессов;

- параллелизм на уровне приложений.

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

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

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

1. Программирование на параллельном языке программирования. Причем такие языки могут быть:

- универсальными (например, язык Ada);

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

2. Программирование на широко распространенном языке программирования (например, C, C++, Pascal), который расширен языковыми (на уровне языка) распараллеливающими конструкциями.

3. Программирование с использованием дополнительных указаний компилятору на уровне языка прагм (например, по стандарту OpenMP).

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

5. Применение средств автоматического распараллеливания последовательных программ такими инструментами, как компиляторы.

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

1. Algol-68 (1968)

2. Concurrent Pascal (1972)

3. Modula-2 (1978)

4. CSP (1978)

5. Edison (1980)

6. Ada (1979, 1983)

7. Occam (1982)

8. Concurrent Prolog (1983)

9. Linda (1985)

10. Oblig (1993)

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