Это ограничение имеет место только для задачи подсчета количества тех или иных схем, т.к. при этом надо хотя бы сосчитать до (2**n)**(2**n). А так-то предложенное кодирование схем позволяет проанализировать любую схему при более широком наборе n. То, что при этом рассматриваются все 2**n состояний схемы не сильно усложняет задачу. Но спасибо, своими комментариями вы подсказали мне нему будущей статьи.
Все так, но я не анализирую схемы а считаю их и тут при любой скорости анализа можно сосчитать только до n=3. А признаки отбраковывающие нужные схемы я определил из удобства кодирования схем и их компактности. При этом для полумодулярных и дистрибутивных схем я и рассматриваю только параллельные переключения.
Все именно так, я лишь подчеркиваю, что совместная проверка на дистрибутивность и полумодулярность (детонантность и конфликтность состояния в ваших терминах) имеет более компактное условие, чем отдельные проверки этих факторов.
Я в этом цикле статей неоднократно говорил, что рассматриваю схемы, заданные на всем множестве 2**n состояний, что никак не влияет на локальное определение последовательности, дистрибутивности и полумодулярности.
Предлагаемый алгоритм выявляет состояния, в которых происходит нарушение и дистрибутивности, и полумодулярности схемы, причем используется совокупный признак этих нарушений, который оказывается компактнее из раздельных признаков. Строго говоря, обнаруживается не само состояние-нарушитель, а его предшественник, а отсекается, по вашему меткому выражение не такое состояние, а схема, его содержащая.
mocoment, я вложил интересующий вас код в этот комментарий:
f=True
for i in range (0,8):
if Q[i]==3:
j = i^1
if (Q[j]!=2):
f=False
break
j = i^2
if (Q[j]!=1):
f=False
break
if Q[i]==5:
j = i^1
if (Q[j]!=4):
f=False
break
j = i^4
if (Q[j]!=1):
f=False
break
if Q[i]==6:
j = i^2
if (Q[j]!=4):
f=False
break
j= i^4
if (Q[j]!=2):
f=False
break
if Q[i]==7:
j= i^1
if (Q[j]!=6):
f=False
break
j=i^2
if (Q[j]!=5):
f=False
break
j=i^4
if (Q[j]!=3):
f=False
break
j=i^3
if (Q[j]!=4):
f=False
break
j=i^5
if (Q[j]!=2):
f=False
break
j=i^6
if (Q[j]!=1):
f=False
break
f=True
for i in range (0,8):
if Q[i]==3:
j = i^1
if (Q[j]!=2):
f=False
break
j = i^2
if (Q[j]!=1):
f=False
break
if Q[i]==5:
j = i^1
if (Q[j]!=4):
f=False
break
j = i^4
if (Q[j]!=1):
f=False
break
if Q[i]==6:
j = i^2
if (Q[j]!=4):
f=False
break
j= i^4
if (Q[j]!=2):
f=False
break
if Q[i]==7:
j= i^1
if (Q[j]!=6):
f=False
break
j=i^2
if (Q[j]!=5):
f=False
break
j=i^4
if (Q[j]!=3):
f=False
break
j=i^3
if (Q[j]!=4):
f=False
break
j=i^5
if (Q[j]!=2):
f=False
break
j=i^6
if (Q[j]!=1):
f=False
break
На схемы, не зависящие от скорости, в свое время возлагались большие надежды, как на конкурента традиционных синхронных схем. Я не знаю, как обстоит дело сейчас, но мне кажется надежды не оправдались. Я рассматриваю свои упражнения с этой тематикой, как математические упражнения на хорошо известном материале, ну как игры с простыми числами, например.
В статье рассматриваются только алгоритмы подсчета схем разных подклассов без учета структурных особенностей самих схем. Поднятым вами проблемам уделено некоторое внимание в цикле статей "Последовательные схемы", опубликованном в песочнице.
Это справедливое замечание, но я ограничился подсчетом схем (различных систем уравнений) не исследуя их структуру. Такая попытка исследования была предпринята в серии статей "Последовательные схемы" опубликованных в Песочнице Хабра. Меня больше интересовали статистические характеристики схем, а именно размеры множеств изоморфных к которым они принадлежат. То, что среди перечисляемых схем много "мусора" очевидно, но, как пошутил один математик, - это на Земле это мусор, а может на Альфе Центавра Ab лучшие умы пытаются создать что-то подобное, но не смогут пока не прочитают обсуждаемый материал.
Теория сложности применяется к оценке разных алгоритмов и то, что комментатор знает о ее оценке метода Квайна-МакКласки, свидетельствует о его высокой образованности. Но так совпало, что и алгоритм пересчета схем о котором толкуют мои статьи обладает высокой сложностью. Такова природа вещей и не надо обвинять в этом автора.
Естественно из тупикового (сиречь устойчивого) состояния схема сама не выйдет. Можно ли устойчивые состояния переопределять произвольно с целью минимизации схемы,- вопрос ее(схемы) применения и в данной статье не рассматривается, но как бы эти состояния не определить, полученная схема все равно будет описана системой логических уравнений, а значит и посчитана, если число n элементов не слишком велико.
Рассматриваются все возможные схемы поведение которых можно задать системой логических уравнений, как в известной комментатору Алгебре асинхронных логических схем.
Тупиковые схемы не определяются, определяются тупиковые состояния, т.е. такие, в которых выходы всех элементов устойчивы. Например, генератор из трех, соединенных в кольцо, инверторов можно доопределить так, что состояния 000 и 111 будут устойчивы и схема станет последовательной для всех состояний, хотя, конечно, и усложнится.
Во-первых не правильно противопоставляться полумодулярные и живые схемы. Схема имеющая устойчивые (тупиковые состояния) может быть вполне полумодулярной, например x=x; y=y. Во-вторых поиск изоморфных был осуществлен, как среди всех схем, так и среди таких классов, как полумодулярные и последовательные, что видно из результирующих таблиц (1 и 2). В-третьих понятие нечувствительности к задержке в проводе относится только к полумодулярным схемам и означает, что такая задержка не выводит схему из этого класса. Более того, еще Маллер показал, что все полумодулярные схемы не чувствительны к задержке в проводе исходящем из выхода элемента до первого разветвления - именно этот фокус и проделал комментатор. Скажем, в синхронной схеме он бы не прошел.
И, строго говоря, схема с добавленной задержкой не эквивалентна исходной, т.к. имеет в двое больше состояний и может быть для получения этих дополнительных состояний задержку-то и добавили.
На счет истории предмета комментатор очевидно прав. На счет ограниченности модели - замечание, скорее всего, неактуально в силу вычислительной сложности даже при введенных ограничениях. Десять элементов в схемотехнике ерунда, а различных даже замкнутых схем 2**10240. Вопрос оптимальности схем здесь, как впрочем и у Мюллера, вообще не рассматривается, т.к. он определяется выбранным элементным базисом.
К сожалению автор является (точнее являлся) специалистом именно в узкой области, где занимались созданием полумодулярных схем, обладающих некоторыми преимуществами перед синхронными и вопрос об их подсчете никогда не стоял. Оценка же их количества показала, что эта задача имеет слишком высокую вычислительную сложность, а результаты для малых количеств элементов можно оценивать просто как подарок.
Про программирование вы совершенно правы, что касается предмета исследований, то термины типа схемы не зависящие от скорости, полумодулярные или последовательные хорошо известны специалистам в области асинхронной схемотехники именно на которых и рассчитана эта статья, причем первая, попавшая на Хабр, так-то дальше песочницы меня и не пропускали. Для них, этих специалистов, это букварь и толковать эти термины лишний раз я посчитал излишним. А вот подсчетом таких схем никто не занимался, вот я и заинтересовался этой темой.
Спасибо. Наверное вы правы, но я не специалист по программированию вообще и по Питону в частности. Поэтому пишу программы только для утилитарных целей - не до красоты и лаконичности. Для меня интерес представляют схемы из логических элементов и их статистические свойства.
Это ограничение имеет место только для задачи подсчета количества тех или иных схем, т.к. при этом надо хотя бы сосчитать до (2**n)**(2**n). А так-то предложенное кодирование схем позволяет проанализировать любую схему при более широком наборе n. То, что при этом рассматриваются все 2**n состояний схемы не сильно усложняет задачу. Но спасибо, своими комментариями вы подсказали мне нему будущей статьи.
Все так, но я не анализирую схемы а считаю их и тут при любой скорости анализа можно сосчитать только до n=3. А признаки отбраковывающие нужные схемы я определил из удобства кодирования схем и их компактности. При этом для полумодулярных и дистрибутивных схем я и рассматриваю только параллельные переключения.
Все именно так, я лишь подчеркиваю, что совместная проверка на дистрибутивность и полумодулярность (детонантность и конфликтность состояния в ваших терминах) имеет более компактное условие, чем отдельные проверки этих факторов.
Я в этом цикле статей неоднократно говорил, что рассматриваю схемы, заданные на всем множестве 2**n состояний, что никак не влияет на локальное определение последовательности, дистрибутивности и полумодулярности.
Предлагаемый алгоритм выявляет состояния, в которых происходит нарушение и дистрибутивности, и полумодулярности схемы, причем используется совокупный признак этих нарушений, который оказывается компактнее из раздельных признаков. Строго говоря, обнаруживается не само состояние-нарушитель, а его предшественник, а отсекается, по вашему меткому выражение не такое состояние, а схема, его содержащая.
Спасибо!
Если вы объяснителем называете автора, то он уже нигде не работает - он пенсионер со стажем.
mocoment, я вложил интересующий вас код в этот комментарий:
f=True for i in range (0,8): if Q[i]==3: j = i^1 if (Q[j]!=2): f=False break j = i^2 if (Q[j]!=1): f=False break if Q[i]==5: j = i^1 if (Q[j]!=4): f=False break j = i^4 if (Q[j]!=1): f=False break if Q[i]==6: j = i^2 if (Q[j]!=4): f=False break j= i^4 if (Q[j]!=2): f=False break if Q[i]==7: j= i^1 if (Q[j]!=6): f=False break j=i^2 if (Q[j]!=5): f=False break j=i^4 if (Q[j]!=3): f=False break j=i^3 if (Q[j]!=4): f=False break j=i^5 if (Q[j]!=2): f=False break j=i^6 if (Q[j]!=1): f=False breakmocoment я вложил код в ответ на ваш комментарий.
f=True for i in range (0,8): if Q[i]==3: j = i^1 if (Q[j]!=2): f=False break j = i^2 if (Q[j]!=1): f=False break if Q[i]==5: j = i^1 if (Q[j]!=4): f=False break j = i^4 if (Q[j]!=1): f=False break if Q[i]==6: j = i^2 if (Q[j]!=4): f=False break j= i^4 if (Q[j]!=2): f=False break if Q[i]==7: j= i^1 if (Q[j]!=6): f=False break j=i^2 if (Q[j]!=5): f=False break j=i^4 if (Q[j]!=3): f=False break j=i^3 if (Q[j]!=4): f=False break j=i^5 if (Q[j]!=2): f=False break j=i^6 if (Q[j]!=1): f=False breakНа схемы, не зависящие от скорости, в свое время возлагались большие надежды, как на конкурента традиционных синхронных схем. Я не знаю, как обстоит дело сейчас, но мне кажется надежды не оправдались. Я рассматриваю свои упражнения с этой тематикой, как математические упражнения на хорошо известном материале, ну как игры с простыми числами, например.
В статье рассматриваются только алгоритмы подсчета схем разных подклассов без учета структурных особенностей самих схем. Поднятым вами проблемам уделено некоторое внимание в цикле статей "Последовательные схемы", опубликованном в песочнице.
Это справедливое замечание, но я ограничился подсчетом схем (различных систем уравнений) не исследуя их структуру. Такая попытка исследования была предпринята в серии статей "Последовательные схемы" опубликованных в Песочнице Хабра. Меня больше интересовали статистические характеристики схем, а именно размеры множеств изоморфных к которым они принадлежат. То, что среди перечисляемых схем много "мусора" очевидно, но, как пошутил один математик, - это на Земле это мусор, а может на Альфе Центавра Ab лучшие умы пытаются создать что-то подобное, но не смогут пока не прочитают обсуждаемый материал.
Теория сложности применяется к оценке разных алгоритмов и то, что комментатор знает о ее оценке метода Квайна-МакКласки, свидетельствует о его высокой образованности. Но так совпало, что и алгоритм пересчета схем о котором толкуют мои статьи обладает высокой сложностью. Такова природа вещей и не надо обвинять в этом автора.
Естественно из тупикового (сиречь устойчивого) состояния схема сама не выйдет. Можно ли устойчивые состояния переопределять произвольно с целью минимизации схемы,- вопрос ее(схемы) применения и в данной статье не рассматривается, но как бы эти состояния не определить, полученная схема все равно будет описана системой логических уравнений, а значит и посчитана, если число n элементов не слишком велико.
Рассматриваются все возможные схемы поведение которых можно задать системой логических уравнений, как в известной комментатору Алгебре асинхронных логических схем.
Тупиковые схемы не определяются, определяются тупиковые состояния, т.е. такие, в которых выходы всех элементов устойчивы. Например, генератор из трех, соединенных в кольцо, инверторов можно доопределить так, что состояния 000 и 111 будут устойчивы и схема станет последовательной для всех состояний, хотя, конечно, и усложнится.
Во-первых не правильно противопоставляться полумодулярные и живые схемы. Схема имеющая устойчивые (тупиковые состояния) может быть вполне полумодулярной, например x=x; y=y.
Во-вторых поиск изоморфных был осуществлен, как среди всех схем, так и среди таких классов, как полумодулярные и последовательные, что видно из результирующих таблиц (1 и 2).
В-третьих понятие нечувствительности к задержке в проводе относится только к полумодулярным схемам и означает, что такая задержка не выводит схему из этого класса.
Более того, еще Маллер показал, что все полумодулярные схемы не чувствительны к задержке в проводе исходящем из выхода элемента до первого разветвления - именно этот фокус и проделал комментатор. Скажем, в синхронной схеме он бы не прошел.
И, строго говоря, схема с добавленной задержкой не эквивалентна исходной, т.к. имеет в двое больше состояний и может быть для получения этих дополнительных состояний задержку-то и добавили.
На счет истории предмета комментатор очевидно прав. На счет ограниченности модели - замечание, скорее всего, неактуально в силу вычислительной сложности даже при введенных ограничениях. Десять элементов в схемотехнике ерунда, а различных даже замкнутых схем 2**10240. Вопрос оптимальности схем здесь, как впрочем и у Мюллера, вообще не рассматривается, т.к. он определяется выбранным элементным базисом.
К сожалению автор является (точнее являлся) специалистом именно в узкой области, где занимались созданием полумодулярных схем, обладающих некоторыми преимуществами перед синхронными и вопрос об их подсчете никогда не стоял. Оценка же их количества показала, что эта задача имеет слишком высокую вычислительную сложность, а результаты для малых количеств элементов можно оценивать просто как подарок.
Про программирование вы совершенно правы, что касается предмета исследований, то термины типа схемы не зависящие от скорости, полумодулярные или последовательные хорошо известны специалистам в области асинхронной схемотехники именно на которых и рассчитана эта статья, причем первая, попавшая на Хабр, так-то дальше песочницы меня и не пропускали. Для них, этих специалистов, это букварь и толковать эти термины лишний раз я посчитал излишним. А вот подсчетом таких схем никто не занимался, вот я и заинтересовался этой темой.
Спасибо. Наверное вы правы, но я не специалист по программированию вообще и по Питону в частности. Поэтому пишу программы только для утилитарных целей - не до красоты и лаконичности. Для меня интерес представляют схемы из логических элементов и их статистические свойства.