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

Сколько этапов имеет алгоритм обнаружения состязаний Эйхельбергера?

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

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

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

изготовление ЦУ;

проверка логики функционирования;

размещение логических элементов;

трассировка соединений;

поиск неисправностей;

анализ состязаний сигналов;

определение временных характеристик;

выборочный контроль

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

Какие алфавиты используются для анализа состязаний?

Оценивается вероятность обнаружения неисправности const0 на линии n?

Оценивается вероятность обнаружения неисправности const1 на линии n?

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

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