Какую сложность решения в общем случае имеет задача выполнимости КНФ?

При каком числе термов в дизъюнктах задача выполнимости КНФ имеет полиномиальную сложность?

От чего зависит в первую очередь сложность решения задачи выполнимости КНФ?

Какую сложность имеет алгоритм обнаружения состязаний в зависимости от числа элементов?

Какую сложность имеет метод STAFAN? В зависимости от числа линий схемы

Жадный алгоритм поиска масок, описанный в лекции 31,базируется на применении конструкции дерева решений. Проиллюстрируйте конструкцию классического дерева решений для решения следующей задачи: имеется 8 одинаковых монет, среди которых одна фальшивая (она легче, чем стандартная). Монеты пронумерованы числами 1,2,…,8. Требуется найти фальшивую монету, используя равновесные весы с двумя чашками (пусть левая чашка имеет №1, правая - №2).

В какой области раньше была решена задача автоматизация синтеза?

Что необходимо определить для решения задачи с помощью генетического алгоритма?

Какую алгебраическую структуру образуют основные многозначные алфавиты?

Какую булеву функцию представляет приведенная таблица истинности?

Какую булеву функцию представляет приведенная таблица истинности?