Comments 10
Ни в одной статье цикла ничего не сказано про начальные условия, это специально? Или для схем, заданных на всех 2^n состояниях, начальные условия могут быть произвольными?
Вот наконец-то вопрос, свидетельствующий о понимании сути. Действительно, если схема задана на всех возможных состояниях, то выбор начального состояния - прихоть пользователя. Хотя если диаграмма имеет тупиковые состояния, то их выбор в качестве начального не может показаться неоправданным. Но возвращаясь к смыслу статей - они посвящены подсчету схем того или иного класса, а не их семантике, которая-то и определяет выбор начального состояния.
Вы привели пример неоживляемых схем, поэтому уточню вопрос. Может ли неудачный выбор начальных состояний перевести схему из класса полумодулярных в класс дистрибутивных?
В статьях оговорено, что указанные свойства (полумодулярнойсть, дистрибутивность, etc) проверяется для всех 2^n состояний схемы, поэтому, какое состояние не назови начальным, схема свой класс не поменяет. Кроме того в вашем вопрос закралась неточность - дистрибутивные схемы полумодулярны по определению - имеет место иерархия вложенности классов.
Еще раз напомню, что в статье рассматривается не синтез или композиция схем из логических элементов, а пересчет все существующих схем содержащих ровно n таких элементов. Этот процесс детализирован для схем различных классов, которые приняты в этой области знаний, а не придуманы автором.
Пересчёт подразумевает, что на вход анализатора поступают схемы от первой до последней (с астрономическим номером при n>3). Насколько я понял, поступают они последовательно. Здесь напрашивается конвейер. Возможно, JIT-компилятор Numba и сделает подобие конвейера, но это будет жалкое подобие. Нужно изначально писать под конвейер. Но это требует досконального знания архитектуры процессора. А в случае, если будет принято правильное решение, - то архитектуры GPU. Можно, конечно, написать на Verilog, но для этого нужно иметь отладочную плату с мощной FPGA. Насколько мне известно, бесплатного online доступа к таким платам нет, в отличии от GPU.
Что же касается композиции и декомпозиции, то в качестве легкого утреннего упражнения можно взять n=2 и синтезировать из последовательных схем дистрибутивные или наоборот разложить каждую дистрибутивную на последовательные. Благо, инструмент для этого у Вас (да и у всего прогрессивного человечества) уже есть, называется "Алгебра асинхронных схем". Она изложена в той Книге 1986, на которую Вы ссылаесь.
Вы демонстрируете недюжинные познания в программировании - я даже использованные вами термины не понимаю, но для n=3 поставленная задача на домашнем компьютере решается за несколько секунд, без сложных приемов, а при n=4 и предложенные вами ухищрения, думаю, бесполезны. Хотя никому не возбраняется попробовать. Что касается предлагаемой вами композиции, то в статьях "Последовательные схемы" из песочницы этот прием уже использован и проиллюстрирован. Ничего, кроме понимания устройства конкретных схем он не дает и для расчётов бесполезен. В обсуждаемых же статьях, автора интересовал только подсчет схем и поставленная задача, признайте, решена.
И маленькое замечание - Алгебра асинхронных схем тоже оперирует со схемами одной размерности, т. ч. ваш совет выдает ваше незнание предмета вашего суждения.
На уровне философии Ваш подход страдает тем же недостатком, что и асимпотические оценки в дискретной математике, только наоборот. В том смысле, что математики любят устремить n к бесконечности и показать, что в таком то базисе (например 2И-НЕ плюс 2ИЛИ-НЕ) такая-то схема (например n-разрядный сумматор) имеет такую-то сложность, которая меньше предыдущей. Инженера интересует n в диапазоне от 4 до 1024. Вы фактически устремили n не к бесконечности, а к нулю и получили такой же бесполезный результат. Именно эта задача была поставлена и поэтому признаю - она решена. Композицию в статье "Последовательные схемы" я не видел, поэтому повторю вопрос - можно ли взять несколько последовательных схем одной размерности, выполнить их композицию и получить дистрибутивную схему той же размерности?
В статье Последовательные схемы ч.3 рассматривается схемы для n=2, как композиция двух схем n=1. В Алгебре асинхронных схем рассматриваются операции объединения и пересечения, которые условно можно считать композиционными, но они не гарантируют что результат будет обладать заданными свойствами (дистрибутивность, например). Да и для поставленной задачи подсчета схем это (в смысле, композиция) бесполезно.
Дистрибутивные схемы, ч.2