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

 

rlr1 474809

О П

ИЗОБРЕТЕНИЯ

Са1оз Советских

Социалистических

Респу5лик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Зависимое от авт. свидетельства (22) Заявлено 31.03.71 (21) 1641625/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 25.06.75. Бюллетень ¹ 23

Дата опубликования описания 13.11.75 (51) М. Кл. G 06f 15/32

Госудврствеинык комитет

Совета Мииистров СССР по делам изооретеиий и открытий (53) УДК 681.142(088.8) (72) Авторы изобретения

Б. И. Блажкевич, E. Д. Михайлова и Ю. А. Спиридонов

Физико-механический институт АН Украинской ССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РАСКРЫТИЯ ОПРЕДЕЛИТЕЛЕЙ

МАТРИЦ И ПОИСКА ПРАДЕРЕВЬЕВ НАПРАВЛЕННОГО ГРАФА

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

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

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

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

10 Для этого в предлагаемом устройстве третьи выходы управляемых ключей каждого столбца, кроме диагонального управляемого ключа, соединены с одноименной вертикальной шиной, а четвертые входы управляемых

15 ключей каждой строки, кроме диагонального управляемого ключа, подключены к Одноименной горизонтальной шине, первые входы управляемых ключей первого столбца матрицы подключены к соответствующим выходам

20 первой группы пз и выходов блока памяти, соответствующие выходы второй группы из и выходов которого соединены с пятыми входамп управляемых ключей одноименной строки, шестые входы всех управляемых ключей no;I,25 ключены к первому выходу переключателя вида работы и одному входу распределителя импульсов, выходы второй группы пз и выходов блока памяти, кроме первого, соединены с соответствующими входамп второй группы

30 из (n — 1) входов блока управления, выходы

="- . Ф,фе „ у. 1У " --а.- м.Рвф

474809

10 !

Зо

50 г

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

ИЛИ, (n — 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, а ше4 стой вход — с первым входом элемента ИЛИ

23 и первым входом элемента ИЛИ вЂ” -I IE 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, а через элемент HE 43 — с первыми входами элементов И 40 и 42. Второй вход управляющей ячейки 34 через элемент задержки 36 присоединен ко второму входу элемента И 40 и первому входу элемента И

39. Третий вход управляющей ячейки 34 присоединен ко вторым входам элемента И 41 и элемента И 42, выход которого подключен к первому входу элемента ИЛИ 38. Выход элемента И 40 через элемент НЕ 44 присоединен ко второму входу элемента И 39, а непосредственно — ко второму входу элемента ИЛИ

38, выход которого является первым выходом управляющей ячейки 34. Второй ее выход совпадает с выходом элемента ИЛИ 37, первый вход которого присоединен к выходу элемента И 41, а второй вход — к первому неподвижному контакту переключателя 45. Второй его неподвижный контакт образует третий выход управляющей ячейки 34. Подвижный

474809 контакт переключателя 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. Нулевые входы и

10 !

G5 выходы каждого из триггеров 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 в ечиничное, а триггеры ?0 в нулевое положение. Этот же импульс, проходя последовательно через управляющие ячейки 34, переключает первый слева незаблокнрованный триггер 20 в соответствующей строке в единичное состояние. Одновременно сбрасываются триггеры 20 последующей строки в нулевое состояние. Выходной сигнал триггера 20, находящегося в единичном состоянии, поступает на вход элемента И 24 и через элементы И 28 и ИЛИ 23 блокирует все нижестоящие в данном столбце управляемые ключи 2. Последовательная установка триггеров 20 первых слева незаблокированных управляющих ключей строки в единичное

474809

55 состояние продолжается до тех цор, пока не переключится один из триггеров 20 последней задействованной строки управляемых ключей 2 или в какой-то строке не окажутся заблокированными все управляемые ключи.

В первом случае импульс поступает через элемент NEIN 18 на распределитель импульсов 5, с элементов задержек 47 которого сигнал поступает на триггеры 48 селектора циклов 6, выходные сигналы которых управляют работой индикатора знака 12. 0 нахождении каждого члена определителя свидетельствует сигнал на выходе распределителя импульсов

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

4О

50 хода элемента ИЛИ 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. О конце поиска прадеревьев в графе сви,четельствует появление сигнала на индикаторе конца поиска 15.

Предмет изобретения

Устройство для раскрытия определителей матриц и поиска прадеревьев направленного графа, содержащее nQn матрицу управляемых ключей, в которой управляемые ключи каждой строки и каж,чого столбца соединены последовательно своими первыми и, соответственно, вторыми выходами и входами, первые выхо1ы управляемых ключей последнего столбца с оедицены с соответствующими входами первой группы из п входов блока управления, соответствующие входы которого подключены к выходу блока сброса, соединенно474809

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

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

Редактор Т. Иванова

Составитель Г. Сорокин

Техред Т. Курилко

Корректор А. Галахова

Заказ 2739/7 Изд. ¹ 835 Тираж 679 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, К-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2