Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

Заметим, что система тестирования, предусматривающая двухбалльную оценку (О или 1) за каждый ответ на задание, может быть описана системой булевых уравнений.

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

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

Рассмотрим псевдобулево неравенство

;

, ; .

Минимальным покрытием этого неравенства называется множество , такое, что

и для любого вышеуказанное неравенство не выполняется.

Из формулы включения-выключения следует, что число решений псевдобулева неравенства определяется как

,

где - множество минимальных покрытий,

.

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

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

Такой подход может быть распространен и на случай системы псевдобулевых неравенств. Для этого достаточно формально заменить систему минимальных покрытий неравенства на объединение систем минимальных покрытий, входящих в систему неравенств.

Пример. Система псевдобулевых неравенств

эквивалентна булевому уравнению

.

Для первого слагаемого формулы, определяющей N , получаем оценку

,

для первого и второго

,

Рекомендуем скачать другие рефераты по теме: реферат мировые войны, курсовые работы бесплатно.





Предыдущая страница реферата | 1  2  3 | Следующая страница реферата