Устройство для раскрытия определителей матриц и поиска прадеревьев направленного графа Советский патент 1975 года по МПК G06F17/16 

1

Изобретение относится к вычислительной технике.

Известные устройства для раскрытия определителей матриц и поиска прадеревьев направленного графа, содержандие «Х/г матрицу управляемых ключей, в которой управляемые ключи каждой строки и каждого столбца соединены последовательно своими первыми и, соответственно, вторыми выходами и входами, первые выходы управляемых ключей последнего столбца соединены с соответствующими входами первой группы из п входов блока управления, соответствующие входы которого подключены к выходу блока сброса, соединенного со сбросовым входом блока памяти, и выходу генератора единичных ил{пульсов, а соответствующий выход соединен с индикатором конца поиска, соответствующие выходы первой группы из я выходов блока управления соединены с третьими входами управляемых ключей одноименной строки матрицы, которая содержит по числу строк и столбцов горизонтальные и вертикальные шипы, среди которых одноименные соединены между собой, элементы ИЛИ и И, распределитель импульсов с подключенным к нему индикатором найденного члена определителя, селектор цикла, искатель несвязностей с подключенным к нему индикатором найденного прадерева, элемент задержки, индикатор знака, иереключатель вида работы и переключатель корня.

Известные устройства имеют ограниченные функциональные возможности и требуют использования большого объема оборудования при исследовании определителей различными методами.

Цель изобретения - расширение области применения.

Для этого в предлагаемом устройстве третьи выходы управляемых ключей каждого столбца, кроме диагонального управляемого ключа, соединены с одноименно верт кальной щиной, а четвертые входы управляемых ключей каждой строки, кроме диагонального управляемого ключа, подключены к одноименной горизонтальной шине, первые входы управляемых ключей первого столбца подключены к соответствующим выходам первой груипы з п выходов блока памяти, соответствующие выходы второй группы из п выходов которого соединены с пятыл входаЛ 1 управляемых ключей одноименной строк, шестые входы всех управляемых ключей нодкл очены к первому выходу переключателя вида работы и одному входу расиредел гтеля импульсов, выходы второй группы 3 п выходов блока памяти, кроме первого, соединены с соответствующим входам второй группы из (п-1) входов блока управлен 1я, выходы

«-«.jrr.

, w f«l«l

первой группы из n выходов которого соединены с соответствующими входами группы из п входов блока памяти, вертикальные шины соединены с соответствующими входами первой группы из п входов распределителя импульсов и соответствующими входами группы из п входов селектора цикла, п выходов которого через искатель несвязностей соединены с соответствующими входами третьей группы из п входов блока управления, выходы второй группы из (п-1) выходов которого через первый элемент ИЛИ соединены с соответствующими входами распределителя импульсов, селектора цикла и первыми входами индикатора знака, подключенного вторым входам к 1соответствующему выходу селектора цикла и соответствующему входу искателя несвязностей, и элемента И, подключенного вторым входом ко второму выходу переключателя вида работы и соединенного выходом с входом второго элемента ИЛИ непосредственно и со входами второй группы из п входов распределителя импульсов через переключатель корня, выход второго элемента ИЛИ, (п-1) входов которого подключены к соответствующим выходам искателя несвязностей, через элемент задержки соединен с соответствующим входом искателя несвязностей.

На фиг. 1 изображена блок-схема предлагаемого устройства для раскрытия определителей матриц и поиска прадеревьев направленного графа; на фиг. 2 - его функциональная схема; на фиг. 3 - функциональная схема управляемого ключа; на фиг. 4 - функциоиальная схема управляющей ячейки.

Устройство содержит вертикальные и горизонтальные щины 1, управляемые ключи 2, образующие матрицу управляемых ключей, блок памяти 3, блок управления 4, распределитель импульсов 5, селектор циклов 6, искатель несвязностей 7, переключатель вида работы 8, переключатель корня 9, блок сброса 10, генератор единичных импульсов 11, индикаторы знака 12, найденного члена определителя 13, найденного нрадерева 14, конца поиска 15, элемент задержки 16, элементы И 17, ИЛИ 18 и 19.

В блоке памяти 3, блоке управления 4, распределителе импульсов 5, селекторе циклов 6 и искателе несвязностей 7 имеются группы выходов и входов, соответствующие отдельным строкам (горизонтальным щинам) матрицы управляемых ключей.

Управляемый ключ 2 (см. фиг. 3) содержит триггер 20, элементы ИЛИ 21, 22, 23, элементы И 24-28, элементы ИЛИ-НЕ 29, НЕ 30 и программирующий выключатель 31, причем первый вход управляемого ключа соединен с отдельными входами элементов И 25 и 27, второй вход-с входом элемента ИЛИ 21, третий ВХОД - со вторым входом элемента И 25 и первым входом элемента И 26, четвертый вход - с входом элемента И 28, пятый вход-с первым входом элемента И 24, а ще474809

стой вход - с первым входом элемента ИЛИ 23 и первым входом элемента ИЛИ-НЕ 29, второй вход элемепта ИЛИ-НЕ 29 через программирующий выключатель 31 присоединяется к источнику питания Е, а его выход подключен к третьему входу элемента И 25 и через элемент НЕ 30 ко второму входу элемента И 27, выход которого присоединен к первому входу элемента ИЛИ 22, выход которого является первым выходом управляемого ключа 2. Выход элемента И 25 присоединен к единичному входу триггера 20. Нулевой вход последнего присоединен к выходу элемента ИЛИ 21, второй вход которого соединен с выходом элемента И 26. Единичный выход триггера 20 присоединен ко вторым входам элементов И 26, 28, 24 и элемента ИЛИ 22. Выход элемента И 24 является вторым выходом управляемого ключа 2. Второй вход элемента ИЛИ 23 присоединен к выходу элемента И 28, а его выход является третьим выходом управляемого ключа 2.

Блок памяти 3 содержит триггеры 32 и разделительные диоды 33 по числу строк матрицы управляемых ключей, причем все разделительные диоды соединены вместе и подключены к отдельному входу блока памяти. Второй зажим каждого из разделительных диодов соединен с единичным входом соответствующего триггера 32 и образует второй выход в группе выходов, соответствующей отдельной строке. Единичный выход триггера 32 является первым выходом блока памяти 3 в такой группе. Входы блока памяти 3, соответствующие отдельным строкам, совпадают с нулевыми входами триггера 32.

Блок управления 4 содержит по числу строк матрицы управляемых ключей 2 управляющие ячейки 34 и элементы ИЛИ 35. Управляющая ячейка 34 содержит элемент задержки 36, элементы ИЛИ 37, 38, элементы И 39- 42, элементы НЕ 43 и 44 переключатель 45, причем первый вход управляющей ячейки соединен непосредственно с первым входом элемента И 41, а через элемент НЕ 43 -с первыми входами элементов И 40 и 42. Второй вход управляющей ячейки 34 через элемент задержки 36 присоединен ко второму входу элемента И 40 и первому входу элемента И 39. Третий вход управляющей ячейки 34 присоединен ко вторым входам элемента И 41 и элемента И 42, выход которого подключен к первому входу элемента ИЛИ 38. Выход элемента И 40 через элемент НЕ 44 присоединен ко второму входу элемента И 39, а непосредственно - ко второму входу элемента ИЛИ 38, выход которого является нервым выходом управляющей ячейки 34. Второй ее выход совпадает с выходом элемента ИЛИ 37, первый вход которого присоединен к выходу элемента И 41, а второй вход-к первому неподвижпому контакту переключателя 45. Второй его неподвижный контакт образует третий выход управляющей ячейки 34. Подвижный

контакт переключателя 45 соединен с выходом элемента И 39.

Управляющие ячейки 34, соответствующие отдельным строкам, в блоке управления 4, соединены цепочкой, причем первый выход и третий вход предыдущей управляющей ячейки соединены соответственно со вторым входом и вторым выходом последующей управляющей ячейки. Первый вход каждой управляющей ячейки и ее третий выход являются, соответственно, первым входом и вторым выходом блока управления 4, соответствующими данным строкам. Второй выход первой управляющей ячейки 34 является отдельным выходом блока управления 4, соединяемым с индикатором конца поиска 15, а ее второй вход - отдельным входом этого блока, соединяемым с блоком сброса 10. Третий вход последней управляющей ячейки 34 является отдельным входом блока управления 4, подключенным к генератору единичных импульсов 11, а ее первый выход - отдельным выходом этого же блока, соединенным с входом элемента ИЛИ 18. Элемент ИЛИ 35, соответствующий отдельной строке, первым своим входом присоединен к первому выходу управляющей ячейки 34, соответствующей этой же строке. Второй ее вход является третьим входом, а выход - первым выходом блока управления 4, соответствующими той же строке.

Распределитель импульсов 5 содержит соответствующие каждой строке элементы И 46 и присоединенные к их выходам элементы задержки 47, причем первые входы всех элементов И 46 образуют отдельный вход распределителя импульсов 5, присоединенный к первому неподвижному контакту переключателя вида работы 8. Второй вход элемента И 46, соответствующий первой строке, является вторым отдельным входом распределителя имнульсов 5, соединенным с выходом элемента ИЛИ 18. Вторые входы элементов И 46, соответствующих последующим строкам, через элементы задержки 47, соответствующие предыдущим строкам, присоединены к выходам элементов И 46, соответствующими этим же строкам. Точка соединения выхода элемента И 46 с элементом задержки 47, соответствующей отдельной строке, представляет собой второй вход распределителя ИМПУЛЬСОВ 5, соответствующий этой же строке. Выход элемента задержки 47, соответствующий последней строке, является выходом распределителя импульсов 5, присоединенным к индикатору найденного члена определителя 13.

Селектор циклов 6 содержит соответствующие отдельным строкам триггеры 48. Единичные выходы всех триггеров 48 соединены вместе и образуют отдельный вход селектора циклов 6, присоединенный к выходу элемента ИЛИ 18, а соединенные вместе единичные выходы этих триггеров образуют отдельный выход селектора циклов, присоединенный к входу индикатора знака 12 и отдельному входу искателя несвязностей 7. Нулевые входы и

выходы каждого из триггеров 48 являются, соответственно, входами и выходами селектора циклов 6, принадлежащими к соответствующим строкам.

Искатель несвязностей 7 содержит соответствующие каждой строке блокирующие ячейки 49 и переключатели 50, передвижные контакты которого механически сопряжены с подвижным контактом соответствующего этой

же строке переключателя 45 в управляющей ячейке 34 блока управления 4. Входами искателя несвязностей. соответствующими отдельным строкам, являются первые неподвижные контакты переключателей 50, вторые их контакты соединены вместе и образуют отдельный вход искателя несвязностей 7, присоединенный к отдельному выходу селектора циклов 6. Подвижный контакт каждого переключателя 50 присоединен к перво„ ...„

му входу соответствующей блокиоуюн1еи ячейки 49. Ее первый выход является выходом искателя несвязностей 7. соответствующим той же строке, что и данная блокирующая ячейка 49. Блокирующие ячейки через их вторые входы и выходы соетинены последовательно, причем второй вход последней блокирующей ячейки 49 является отдельным входом искателя несвязностей 7, соединенНЫЛ5 с выходом элемента задержки 16, а второй ВЫХОД первой блокирующей ячейки 49 - отдельным выходом искателя несвязностей, присоединенным к индикатору найденного прадерева 14.

До начала работы переключатели вида работы 8 и корня 9 ставят в соответствующе положение. Устанавливают в рабочее положение программирующие выключатели 31 в управляемых ключах 2, соответствующих ненулевым элементам матрицы или наличным

дугам графа. Сдвоенные переключатели 45 к 50, соответствующие строкам заданной матрицы или вершинам графа, переключаются в первое положение. Работа устройства начинается с посылки сигнала от блока сброса

10.

При раскрытии определителя матриц через переключатель вида работы 8 «а соответствующие входы элементов И 24 и 46 от источника питания 51 поступает сигнал. При

этом вырабатывается импульс, устанавливающий триггер 32 в единичное, а триггеры 20 в нулевое положение. Этот же импульс, проходя последовательно через управляющие ячейки 34, переключает первый слева незаблокированный триггер 20 в соответствующей строке в единичное состояние. Одновременно сбрасываются триггеры 20 последующей строки в нулевое состояние. Выходной сигнал триггера 20, находящегося в единичном состоянии, поступает «а вход элемента И 24 и через элементы И 28 и ИЛИ 23 блокирует все нижестоящие в данном столбце управляемые ключи 2. Последовательная установка триггеров 20 первых слева незаблокированпых управляющих ключей строки в едт ничное состояние продолжается до тех пор, пока не переключится один из триггеров 20 последней задействованной строки управляемых ключей 2 или в какой-то строке не окажутся заблокированными все управляемые ключи. В первом случае импульс поступает через элемент ИЛИ 18 на распределитель нмпульсов 5, с элементов задержек 47 которого сигнал поступает на триггеры 48 селектора циклов 6, выходные сигналы которых управляют работой индикатора знака 12. О нахождении каждого члена определителя свидетельствует сигнал на выходе распределителя импульсов 5 (индикатор найденного члена определителя 13). Во втором случае сигнал, пройдя через управляющую ячейку 34, соответствующую заблокированной строке, поступает на вход вьппестоящей управляющей ячейки 34. Если в соответствующей этой управляющей ячейке строке имеется справа от триггера 20, находящегося в единичном состоянии, незаблокированный управляемый ключ 2, то в этой строке производится перезапись единицы в триггер 20 первого справа незаблокированного управляемого ключа 2, после чего продолжается установка в единичное состояние триггеров 20 в управляемых ключах ниже расположенных строк. Если же таких управляемых ключей не было в этой строке, то импульс поступает в следующую выщестоящую управляющую ячейку 34 до тех пор, пока не будет найдена такая строка. В случае отсутствия такой строки появляется сигнал на выходе первой сверху управляющей ячейки 34 и срабатывает индикатор конца поиска 15, что свидетельствует об окончании поиска членов определителя. Для определения каждого следующего члена онределителя необходимо от генератора единичных импульсов 1I подать сигнал на вход первой снизу управляющей ячейки 34. При поиске прадеревьев направленного графа переключатель корня 9 ставится в положение, соответствующее заданной корневой верщине графа, а переключатель вида работы 8 устанавливается в нижнее положение, при которол сигнал на входы элементов И 28 не поступает, а следовательно, единичное состояние триггеров 20 не может вызвать блокирования нижестоящих управляемых ключей 2. Также не поступает сигнал на входы элементов И 46, поэтому сигналы с выхода предыдущего элемента задержки 47 не поступают на вход следующих, и распределитель импульсов 5 перестает выполнять функцию коммутатора. Работа устройства после подачи сигнала от блока сброса 10 при занесении единиц в триггеры 20 всех строк проходит аналогично онисанному при раскрытии определителя, причем из-за отсутствия блокировок всегда в каждой строке будет по одному триггеру 20, находящемуся в единичном состоянии. После занесения единиц в триггеры 20 сигнал с выхода элемента ИЛИ 18 проходит через элемент И 17 и поступает через переключатель корня 9 на вход элемента задержки 47, соответствующей строке корневой вершины графа, и кроме того, через элемент ИЛИ 19 и элемент задержки 16 - на вход первой снизу блокирующей ячейки 49 искателя несвязиостей 7. Импульс с выхода элемента задержки 47, соответствующей корневой верщине графа, через вертикальные н горизонтальные щины 1 и элементы И 24 поступает на единичные входы триггеров 48 селектора циклов 6, соответствующих лишь связанным корие.м вершинам графа. С выходов триггеров 48 селектора циклов 6 сигналы через нереключатели 50 поступают на первые входы блокирующих ячеек 49. Паличие сигналов на этих входах разрещает прохождение импульса со второго входа на второй выход соответствующей блокирующей ячейки 49 и занреи ает появление его на первом ее выходе. На втором выходе появляется импульс только у блокирующей ячейки 49, соответствующей первой снизу из несвязанных с корнем верщины графа, а вследствие отсутствия сигнала на ее втором выходе не произойдет прохождения сигналов по остальным блокирующим ячейкам 49. Импульс с первого выхода указанной блокирующей ячейки 49 иоступает через элемент ИЛИ 35 на управляемые ключи 2 соответствующей строки и вызывает в ней перезапись единицы в триггер 20 следующего справа управляемого ключа. Кроме того, этот же имцульс на один из входов элемента ИЛИ 19. После перезаписи единиц в триггерах 20 строки, соответствующей верщине, ранее не связанной с корневой вершиной графа, появляется импульс на выходах элементов ИЛИ 18 и 19. Если дуги графа, соответствующие управляемым ключам 2 с находящимися в единичном состоянии триггерами 20, образуют прадерево, то сигнал с выхода элемента ИЛИ 19 проходит через все блокирующие ячейки 49, а на индикаторе найденного прадерева 14 появляется сигнал. Переход к определению следуюндего прадерева происходит как и. при поиске члена определителя путем посылки единичиого импульса от генератора единичных импульсов 11. О конце поиска прадеревьев в графе свидетельствует появление сигнала на и 1дикаторе конца поиска 15. Предмет изобретения Устройство для раскрытия определителей матриц и поиска прадеревьев направленного графа, содержангее матрицу управляемых ключей, в которой управляемые ключи каждой строки и каждого столбца соединены последовательно своими первыми и, соответственно, вторыми выходами и входами, первые выходы управляемых ключей последнего столбца соединены с соответствующими входами первой группы из п входов блока управления, соответствующие входы которого подключены к выходу блока сброса, соединенно9го со соросовым входом олока памяти, н выходу генератора единичных импульсов, а соответствующий выход соединен с индикатором конца иоиска, соответствующие выходы первой группы нз п выходов блока управления соединены с третьими входами управляемых ключей одноименной строки матрицы, которая содержит по числу строк и столбцов горизонтальные и вертикальные шины, среди которых одноименные соединены между собой, элементы ИЛИ и И, распределитель импульсов с подключенным к нему индикатором найденного члена определителя, селектор цикла, искатель несвязностей с подключенным к нему индикатором найденного прадерева, элемент задержки, индикатор знака, переключатель вида работы и переключатель корня, отличающееся тем, что, с целью расширения области применения, в нем третьи выходы управляемых ключей каждого столбца, кроме диагонального управляемого ключа, соединены с одноименной вертикальной шиной, а четвертые входы управляемых ключей каждой строки, кроме диагонального управляемого ключа, подключены к одноименной горизонтальной шине, первые входы управляемых ключей первого столбца матрицы подключены к соответствующим выходам первой группы из п выходов блока памяти, соответствующие выходы второй группы из п выходов которого соединены с пятыми входами управляемых ключей одноименной строки, шестые входы всех управляемых ключей подключены к первому выходу переключате10ля вида работы и одному входу распределителя импульсов, выходы второй группы из п выходов блока памяти, кроме первого, Соединены с соответствующими входами второй группы из (п-1) входов блока управления, выходы первой группы из п выходов которого соединены с соответствуюцдими входами группы нз я входов блока памяти, вертикальные шииы соединены с соответствующими входами первой группы пз п входов распределителя импульсов и соответствующими входами группы из п входов селектора цикла, п выходов которого через искатель несвязностей соединены с соответствующими входами третьей группы из п входов блока управления, выходы второй группы из (п-1) выходов которого через первый элемент ИЛИ соединены с соответствующими входами распределителя импульсов, селектора цикла и первыми входами индикатора знака, подключенного вторым входом к соответствующему выходу селектора цикла и соответствующему входу искателя несвязиостей, и элемента И, подключенного вторым входом ко второму выходу переключателя вида работы и соединенного выходом со входом второго элемента ИЛИ непосредственно и с входамн второй группы из п входов распределителя импзльсов через переключатель корня, выход второго элемента ИЛИ, (п-1) входов которого подключены к соответствующим выходам искателя несвязностей, через элемент задержки соединен с соответствующим входом искателя несвязностей.

r-v//

Фг/г 7 .иг 2

22

,J

1риг J J4 о 1 50 11, 77 72