|
|
ОглавлениеКонтрольная работа 1. Простейшие свойства функций алгебры логики Контрольная работа 2. Специальные представления булевых функций Контрольная работа 3. Полнота систем функций алгебры логики Для бесплатного чтения доступна только часть главы! Для чтения полной версии необходимо приобрести книгуЗаключениеВ пособии приведены задачи для контрольных работ студентов, осваивающих простейшие булевы функции и их свойства. Эти навыки необходимы для дальнейшего освоения теории алгоритмов и теории алгоритмической сложности. В частности, в терминах булевых функций и выполнимости логических формул можно сформулировать основную задачу теории сложности — так называемую SAT-проблему. Это задача о выполнимости булевой формулы, то есть о существовании набора переменных, на которых она истинна. Такая задача относится к так называемым переборным задачам. Она решается методом прямого перебора наборов переменных. Прямой перебор состоит в следующем: один за другим генерируются всевозможные двоичные наборы в произвольном порядке, и для любого набора переменных вычисляется значение функции на нем. Этот алгоритм дает решение вопроса о выполнимости тогда, когда либо будет найден набор, на котором формула истинна (в этом случае формула выполнима), либо ни на каком наборе формула не будет истинной (в этом случае она невыполнима). Такого рода задачи называются NP-задачами. Важно, что вычисление функции на наборе является очень простой процедурой. Вся сложность заключается в том, что нужно перебирать экспоненциально большое число двоичных наборов. Возникает вопрос: возможно ли ускорить этот перебор? Данный вопрос является открытой математической проблемой. Это — так называемая P = NP(?)-проблема. Заметим, что если формула находится в форме ДНФ, то вопрос о ее выполнимости решается очень просто. Если же формула находится в КНФ, то задача становится очень сложной, так как переход от КНФ к ДНФ ведет к экспоненциальному росту длины формулы. Отметим, что вопрос о выполнимости формулы эквивалентен вопросу о поиске решения уравнения f(x) = 1, где f — булева функция. На квантовом компьютере решение этой задачи требует действий, или занимает время порядка . Этот результат был получен Л. К. Гровером (США) в 1994 г. Данный алгоритм особого рода. Его применение основано на построении квантового компьютера, что само по себе является фундаментальной проблемой естествознания. Это обусловливает важность задач дискретной математики для широкого круга специалистов. Внимание! Авторские права на книгу "Дискретная математика. Булевы функции. Сборник контрольных работ" (Викторова Н.Б.) охраняются законодательством! |
||||||||||||||||||||||
