Устройство для раскрытия определителей матриц и поиска прадеревьев направленного графа

111 474809 О ПИЗОБРЕТЕНИЯ Сааз Советских Соцналнстнческнх Респуолнк(22) Заявлено 31,0 с присоединением заявки Государственный комнте овета Мнннстров ССС(32) ПриоритетОпубликовано 25.06.7 3) УДК 681.142(088.823 оллете по делам нзооретеннм н открытийДата опубликования описания 13.11.75. Блажк ч, Е, Д. Михаилова и Ю. А, Спиридонов изико-механический институт АН Украинской ССР 1) Заявител(54) УСТРОЙСТВО ДЛЯ РАСКРЫТИЯ ОПРЕДЕЛИТЕЛЕЙ ТРИЦ И ПОИСКА ПРАДЕРЕВЬЕВ НАПРАВЛЕННОГО ГРАФтение относится к вычислительной технике.Известные устройства для раскрытия определителей матриц и поиска прадеревьев направленного графа, содержащие гггг магри цу управляемых ключей, в которой управляемые ключи каждой строки и каждого столбца соединены последовательно своими первыми и, соответственно, вторыми выходами и входами, первые выходы управляемых ключей 10 последнего столбца соединены с соответствующими входами первой группы цз гг входов блока управления, соответствующие входы которого подключены к выходу блока сброса, соединенного со сбросовым входом 15 блока памяти, и выходу генератора единичных импульсов, а соответствующий выход соединен с индикатором конца поиска, соответствующие выходы первой группы из гг выходов блока управления соединены с третьими 20 входами управляемых ключей одноименной строки матрицы, которая содержит по числу строк и столбцов горизонтальные и вертикальные шины, среди которых одноименные соединены между собой, элементы ИЛИ и И, 25 распределитель импульсов с подключенным к нему индикатором найденного члена определителя, селектор цикла, искатель несвязностей с подключенным к нему индикатором найденного прадерева, элемент задержки, ин- З 0 дцкатор знака, переключатель вида работы ц переключатель корня.Известные устройства имеют ограниченные функциональные возможности ц требуют использования большого объема оборудования при исследовании определителей различными методами.Цель изобретения - расширение ооласти применения.Для этого в предлагаемом устройстве третьи выходы управляемых ключей каждого столбца, кроме диагонального управляемого ключа, соединены с одноименной вертикальной шиной, а четвертые входы управляемых ключей каждой строки, кроме диагонального урео ключа, одючены к одноигценцой горизонтальной шине, первые входы управляемых ключей первого столбца матрицы подключены к соответствующим выходам первой группы цз и выходов блока памяти, соответствующие выходы второй группы цз и выходов которого соединены с пятыми входамц управляемых ключей одноименной строки, шестые входы всех управляемых ключей подключены к первому выходу переключателя вида работы и одному входу распределителя импульсов, выходы второй группы цз и выходов блока памяти, кроме первого, соединены с соответствующими входамп второй группы цз (гг - 1) входов блока управления, выходы5 1 О 5 20 25 зо 3 аО д 50 г 6 О 65 первой группы из гг выходов которого соединены с соответствующими входами группы из гг входов блока памяти, вертикальные шины соединены с соответствующими входами первой группы из и входов распределителя импульсов и соответствующими входами группы из гг входов селектора цикла, гг выходов которого через искатель несвязностей соединены с соответствующими входами третьей группы из гг входов блока управления, выходы второй группы из (гг - 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, а шестой вход - с первым входом элемента ИЛИ 23 и первым входом элемента ИЛИ в -11 Е 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. Нулевые входы ц 5 то 5 20 25 зо 35 40 45 50 55 60 65 выходы каждого из триггеров 48 являются, соответственно, входами и вьтхоламц селектора циклов 6, принадлежащими к соответствующим строкам,Искатель несвязностей 7 со,чержцт соответствующие кажлой строке блокирутощце ячейки 49 и переключатели 50, перелвижные контакты которого механически сопряжены с подвижным контактом соответствующего этой же строке переключателя 45 в управляющей ячейке 34 блока управления 4. Вхо,чами тлскателя несвязностей, соответствующими отдельным строкам, являются первые неподвижные контакты переключателей 50, вторые их контакты соечцнены вместе ц образуют отдельный вход искателя несвязностей 7, присоединенный к отдельному выхолу селектора циклов 6. Полвижный контакт каждого переключателя 50 прцсоечинен к петтвому вхолу соответствующей блокипутотттей ячейки 49. Ее первый выхоч является выходом искателя несвязностей 7, соответствующим той же стпоке, что и ланная блокипуюшая ячейка 49. Блокттруюттттте ячейки через их втопые входы ц выходы сое,цнены послеловательно, причем втопой вход последней блокирующей ячейки 49 является отлельным входом искателя несвязностец 7, соелиненньтм с выхолом элемента залержки 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 первых слева незаблокированных управляющих ключец строки в единичное55 60 55 состояние продолжается до тех цор, пока не переключится один из триггеров 20 последней задействованной строки управляемых ключей 2 или в какой-то строке не окажутся заблокированными все управляемые ключи.В первом случае импульс поступает через элемент ИЛИ 18 на распределитель импульсов 5, с элементов задержек 47 которого сигнал поступает на триггеры 48 селектора циклов 6, выходные сигналы которых управляют работой индикатора знака 12, О нахождении каждого члена определителя свидетельствует сигнал на выходе распределителя импульсов 5 (индикатор найденного члена определителя 13),Во втором случае сигнал, пройдя через управляющую ячейку 34, соответствующую заблокированной строке, поступает на вход вышестоящей управляющей ячейки 34, Если в соответствующей этой управляющей ячейке строке имеется справа от триггера 20, находящегося в единичном состоянии, незаблокированный управляемый ключ 2, то в этой строке производится перезапись единицы в триггер 20 первого справа незаблокированного управляемого ключа 2, после чего продолжается установка в единичное состояние триггеров 20 в управляемых ключах ниже расположенных строк, Если же таких управляемых ключей не было в этой строке, то импульс поступает в следующую вышестоящую управляющую ячейку 34 ло тех пор, пока не будет найдена такая строка, В случае отсутствия такой строки появляется сигнал на выходе первой сверху управляющей ячейки 34 и срабатывает индикатор конца поиска 15, что свидетельствует оо окончании поиска членов определителя.Для опречеления кажчого следующего члена определителя неоохочимо от генератора единичных импульсов 11 подать сигнал на вход первой снизу управляющей ячейки 34,При поиске прадеревьев направленного графа переключатель корня 9 ставится в положение, соответствующее заданной корневой вершине графа, а переключатель вила работы 8 устанавливается в нижнее положение. при котором сигнал на вхо,чы элементов И 28 не поступает, а следовательно, единичное состояние триггеров 20 не может вызвать блокирования нижестоящих управляемых ключей 2. Также не поступает сигнал на вхо,чы элементов И 46, поэтому сигналы с выхода предыдущего элемента залержки 47 не поступают на вход следующих, и распределитель импульсов 5 перестает выполнять функцию коммутатора.Работа устройства после подачи сигнала от блока сброса 10 при занесении единиц в триггеры 20 всех строк проходит аналогично описанному при раскрытии опрс,челителя, причем из-за отсутствия блокировок всегда в каж,ой стпоке будет по одному триггеру 20, находящемуся в единичном состоянии. После занесения единиц в триггеры 20 сигнал с вы 5 10 15 20 25 30 35 40 45 50 хола элемента ИЛИ 18 проходит через элсмент И 1 и поступает через переключатель корня 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. О конце поиска прадеревьев в графе сви,четельствует появление сигнала на индикаторе конца поиска 15. Предмет изобретенияУстройство для раскрытия определителей матриц и поиска прадеревьев направленного графа, содержащее пКп матрицу управляемых ключей, в которой управляемые ключи каждой строки и каж,чого столбпа соединены последовательно своими первыми и, соответственно, вторыми выходами и входами, первые выхо 1 ы управляемых ключей последнего столбца с оединены с соответствующими вхолами первой группы из п вхолов блока управ. ления, соответствующие входы которого подключены к выходу блока сброса, соединенно 474809 10го со сбросовым входом блока памяти, ц выходу генератора единичных импульсов, а соответствующиц выход соединен с шгдикатором конца поиска, соответствующие выходы первой группы из п выходов блока управления соединены с третьими входами управляемых клочей одноименной строки матрицы, которая содержит по числу строк и столбцов горизонтальные и вертикальные шины, среди которых одноименные соединены между собой, элементы ИЛИ и И, распределитель импульсов с подключенным к нему индикатором найденного члена определителя, селектор цикла, искатель несвязностей с подключенным к нему индикатором найденного прадерева, элемент задержки, индикатор знака, переключатель вида работы и переключатель корня, отличающееся тем, что, с целью расширения области применения, в нем третьи выходы управляемых ключей каждого столбца, кроме диагонального управляемого ключа, соединены с одноименной вертикальной шиной, а четвертые входы управляемых ключей каждой строки, кроме диагонального управляемого ключа, подклгочены к одноименной горизонтальной шине, первые входы управляемых ключей первого столбца матрицы подключены к соответствующим выходам первой группы из гг выходов блока памяти, соответствующие выходы второй группы из гг выходов которого соединены с пятыми входами управляемых ключей одноименной строки, шестые входы всех управляемых ключей подключены к первому выходу переключателя вида работы ц одному входу распределителя импульсов, выходы второй группы из гг выходов блока памяти, кроме первого, соединены с соответствующими входамц второй группы из (гг - 1) входов блока управления, выходы первой группы цз п выходов которого соединены с соответствующими входамц группы цз гг вколов блока памяти, вертикальные шины соединены с соответствующими входами первой группы цз п входов распределителя импульсов ц соответствующими входамц группы цз гг входов селектора цикла, п выходов которого через искатель несвязностей соединены с соответствующими входамц третьей 15 группы из и входов блока управления, выходы второй группы цз (гг - 1) выходов которого через первый элемент ИЛИ соединены с соответствующими входа ми распределителя импульсов, селектора цикла и первыми вхо лами индикатора знака, подключенного вторым входом к соответствующему выходу селектора цикла ц соответствующему входу искателя несвязностей, ц элемента И, подключенного вторым входом ко второму выходу 2 Б переключателя вида работы ц соединенноговыходом со входом второго элемента ИЛИ непосредственно и с входамц второй группы из гг входов распределителя импульсов через переключатель корня, выход второго элемен- ЗО та ИЛИ, (гг - 1) входов которого подключены к соответствующим выходам искателя несвязностей, через элемент задержки соединен с соответствующим входом искателя несвяз цостей.Подписное 739/7ЦН Зака ппография, пр. Сапунова, 2 Изд Ъо 835 И Государственного комнте по делам нзобретенш Москва, Ж, РаушскТираж б 79а Совета Министров СССи открытийя наб., д. 4,5