В то время как EE старшекурсник я посетил некоторые лекции, которые представили хорошую характеристику булевых схем с точки зрения, сколько у них вложенных циклов. По своей сложности булевы схемы часто считаются дагами, но в реальных аппаратных циклах это обычное явление. Теперь, по модулю некоторых технических моментов, касающихся того, что представляет собой цикл и что представляет собой вложенный цикл, утверждалось, что для реализации в аппаратном обеспечении автомата нужны два вложенных цикла, а для реализации процессора нужны три вложенных цикла. (Я мог бы быть один на один с этими подсчетами.)
Меня беспокоит две вещи:
- Там не было ничего, как формальное доказательство.
- Я не видел это нигде.
Кто-нибудь расследовал точные заявления такого рода?
В поисках имени профессора я нашел небольшую веб-страницу и книгу (глава 4), в которой обсуждается эта таксономия.
Обоснование : если вам интересно, почему циклы полезны на реальном оборудовании, вот простой пример. Подключите два инвертора в цикле. (Инвертор - это логический элемент, который вычисляет логическую функцию НЕ.) Эта схема имеет два устойчивых равновесия (и неустойчивое). В отсутствие какого-либо вмешательства извне, цепь просто останется в одном из двух состояний. Тем не менее, можно принудительно привести схему в одно конкретное состояние, подав внешний сигнал. Ситуацию можно увидеть так: пока цикл подключен к внешнему сигналу «мы читаем вход», а в остальном мы просто «запоминаем последнее значение, которое мы видели». Так что одна петля помогает нам вспомнить вещи.
Ответы:
Вы должны взглянуть на кандидатскую диссертацию (позже опубликованную в виде монографии) Томаса Федера: Стабильные сети и графики продуктов , где он изучил сложность поиска стабильных конфигураций сетей , которые в точности представляют собой схемы с «петлями», как вы упомянули.
источник