Решение теоретико-множественных задач
Основное преимущество Н-моделей состоит в том, что они способны решить задачи, которые не могут быть решены никаким другим способом (кроме, возможно, полного перебора). Это относится в первую очередь к так называемым смешанным задачам: когда в модели присутствуют переменные и ограничения самой различной природы (численные, дискретные, множественные, таблицы и т. п.). Одним из основных нечисловых… Читать ещё >
Решение теоретико-множественных задач (реферат, курсовая, диплом, контрольная)
Одним из основных нечисловых типов данных, используемых в Н-моделях являются множества. Впервые понятие недоопределенного множества было предложено А. С. Нариньяни в работе [10]. Существует несколько различных способов представления недоопределенного множества (см. [10], [15], [18]). Ниже мы используем способ, предложенный в [10].
Недоопределенное множество A представляется тремя компонентами (слотами):
A = < A+, A-, M>,.
где A+ — множество элементов, которые точно принадлежат А;
A— - множество элементов, которые точно не принадлежат А;
М — кардинал А, представленный недоопределенным целым числом.
Естественно, что количество элементов в A+ и A— может только возрастать. Если обозначить через X — универсум множества А, а через card — кардинал множества, то справедливы следующие ограничения:
М card (A+); М card (X) — card (A-);
A+ X; A— X; A+ A— = ;
Рассмотрим один простой пример. Предположим, что в универсуме, состоящем из 20 букв (от а до t), имеются 4 множества (A, B, C и D) со следующими значениями:
имя. | элементы, принадлежащие множеству. | элементы, не принадлежащие множеству. | кардинал. |
A | { a, b, c, d, e, f, k, l, p} | { h, i } | |
B | { k, l} | {g, h, i, j } | |
C | {c, d, e, f } | { a, b, g } | |
D | { o, p, q, r, s, t } | {} | |
Также предположим, что модель состоит из следующих ограничений:
C = A B; D C; card (A) 14; card (B) > 5;
После применения к данной Н-модели процесса удовлетворения ограничений, получаем следующий результат.
имя. | элементы, принадлежащие множеству. | элементы, не принадлежащие множеству. | кардинал. |
A | {a, b, c, d, e, f, k, l, o, p, q, r, s, t} | {g, h, i, j, m, n} | [14,14] |
B | {a, b, k, l, m, n} | {c, d, e, f, g, h, i, j, o, p, q, r, s, t} | [6,6] |
C | {c, d, e, f, o, p, q, r, s, t} | {a, b, g, h, i, j, k, l, m, n} | [10,10] |
D | {o, p, q, r, s, t} | {a, b, g, h, i, j, k, l, m, n} | [6,10] |
Таким образом значения множеств A, B и C полностью уточнились. Значение множества D уточнилось, но не полностью: при текущих ограничениях осталось неясным принадлежат ли множеству D элементы c, d, e и f.
Решение смешанных задач
Основное преимущество Н-моделей состоит в том, что они способны решить задачи, которые не могут быть решены никаким другим способом (кроме, возможно, полного перебора). Это относится в первую очередь к так называемым смешанным задачам: когда в модели присутствуют переменные и ограничения самой различной природы (численные, дискретные, множественные, таблицы и т. п.).
Предположим, что к Н-модели из предыдущего раздела добавляются следующие два уравнения, неравенство и логическая импликация над вещественными (x, y), целым (k) и множествами (D, A, C):
x2 + 6*x = y — 2k;
k*x + 7.7*y = 2.4;
k < 3;
(x y + 1) & (C D).
В такой модели результат будет следующим:
имя. | элементы, принадлежащие множеству. | элементы, не принадлежащие множеству. | кардинал. |
A | {a, b, c, d, e, f, k, l, o, p, q, r, s, t} | {g, h, i, j, m, n} | [14,14] |
B | {a, b, k, l, m, n} | {c, d, e, f, g, h, i, j, o, p, q, r, s, t} | [6,6] |
C | {c, d, e, f, o, p, q, r, s, t} | {a, b, g, h, i, j, k, l, m, n} | [10,10] |
D | {c, d, e, f, o, p, q, r, s, t | {a, b, g, h, i, j, k, l, m, n} | [10,10] |
k = 2; x = -0.6586; y = 0.48 261.