Устройство для исследования вероятностных графов Советский патент 1987 года по МПК G06F15/173 

ройство содержит вход 1 пуска, генератор 2 импульсов, выход 3 окончания испытания, вход 4 начальной установки, элемент И 5, группу элементов И бр пять групп ключей 7 - 11, две группы триггеров 12 и 13, входы 14 розыгрыша вершин, входы 15 розыгрыша ребер, информационные выходы 16 устройства, распределитель 17 -импульсов , вход 18 опроса устройства, две группы блоков 19 и 20 памяти, наборное поле 21, сумматор 22, два массива групп контактов 23 и 24 наборного поля. В исходном состоянии на триггерах 12 и 13 записаны результаты розыгрыша ребер и вершин соответственна. После пуска при помощи ключей 7-10 производится анализ вер

1

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

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

На фиг. 1 представлена функцио

нальная схема предлагаемого устройства j на фиг. 2 - функциональные схемы

-ключей, подключаемых к наборному полю

Устройство содержит вход 1 пуска устройства, генератор 2 импульсов, выход 3 признака окончания испытаний, вход 4 начальной установки, элемент И 5, группу элементов И 6, пять групп ключей 7-11, две группы триггеров 12 и 13, Н входов 14 розыгрыша вершин где Н - количество вершин в графе, Е входов 15 розыгрьш1а ребер, где Е количество ребер в графе, Н информационных выходов 16 устройства, распределитель 17 импульсов, вход 18 опроса устройства, две группы блоков 19 и 20 памяти, наборное поле 21 и сумматор 22 с фиксацией результата.

Наборное поле 21 содержит два массива контактов 23 и 24. Ключи 9 и 10 содержат обмотки 25 реле.

Устройство работает следующим образом.

шин графа на связность. Веса связанных вершин и веса соответствующих ребер поступают с выхода блоков 19 и 20 памяти на вход сумматора 22, где формируется вес первого подграфа Одновременно производится сброс триггера 12 и 13, соответствующих ребрам и вершинам первого подграфа. По следующему импульсу генератора 2 производится обнуление сумматора 22 и при помощи ключей 7 производится выбор первой вершины второго подграфа. Процесс повторяется до тех пор, пока не будут обнулены все триггеры 13. В этом случае сигнал с выхода элемента И 5 формирует сигнал окончания испытания и останавливает генератор 2. 2 ил.

В первом такте импульс начальной установки поступает по входу 4 на первые R-входы триггеров 12 и 13 и устанавливает их в нулевое состояние. Во втором такте на входы 14 и 15 поступают данные розыгрыша вершин и ребер, в результате чего открываются соответствующие ключи 9 и 10 (при этом все выходы ключа 9 соединяются с информационным входом, и между всеми выходами ключа образуется электрический контакт). Единичные сигналы с прямых выходов триггеров 11 открывают соответствующие ключи В. В результате этого образуется электрический контакт между всеми вершинами и ребрами, присутствующими в розыгрьш1е. Если в данном розыгрьш1е не выпало ни одной вершины, то единичные потенциалы с инверсных выход ов триггеров 11 поступают на все входы элемента И 5, который выдает импульс на вьгход. При отсутствии сигнала на выходе 3 в третьем такте на вход 11 устройства поступает сигнал, запускающий генератор 2, первый импульс которого своим передним фронтом обнуляет сумматор 22, а также проходит .через первый открытый ключ 8 и соответствующий ключ 9 на контакты 23 и 24 первого и второго массивов контактов наборного поля, соответствующие связанным между собой ребрам и вершинам в первом подграфе. При этом импульс проходит через соответствующие сработавшие ключи 9 и 10. При появлении импульса на контактах одной из групп контактов 23 он попадает на второй R-вход соответствующего триггера 11 и сбра- .сывает его в ноль, триггер 12, соответствующий одному из ребер, присутствующих в данном розыгрыше, сбрасывается единичным сигналом с выхода соответствующего элемента И 6 лишь в том случае, если в розыгрьш1е присутствуют обе вершины, связанные данным ребром, только в этом случае единичные сигналы поступают на оба входа элемента И 6 с соответствующей пары контактов 23.

При переходе триггеров 11 и 12 в нулевое состояние единичные сигналы с их инверсных выходов поступают на входы считывания соответствующих блоков 19 и 20, которые вьщают веса связанных в первом подграфе вершин и ребер на входы сумматора 22. Последний суммирует вес вершин и ребер подграфа и выдает вес подграфа на информационные входы ключей 11.

В четвертом такте по входу 18 опроса на тактовый вход распределителя 17 поступает сигнал, в результате чего открывается первый ключ 21 и вес первого подграфа поступает на первый выход 16 устройства.

Второй импульс генератора 2 обнуляет сумматор 22 через открытые ключи 7, проходит до первого открытого единичньм потенциалом.с прямого выхода соответствующего триггера 11. ключа 8. Тем самым вьщеляется первая из присутствующих в данном розыгрыше вершин, входящая во второй подгра Далее устройство работает аналогично только вес второго подграфа выдается на второй вьпсод 16 устройства и т.д. После прохождения некоторого количества импульсов с выхода генератора 2 уже не останется вершин, для которых соответствующие триггеры 11 находятс в состоянии 1, единичные сигналы с инверсных выходов .триггеров 11 проходят через элементы И 6 на. все входы элемента И 5, который выдает на выход 3 сигнал окончания данного испытания. Этот же сигнал обнуляет , распределитель 17, который переходит в исходное состояние и останавливает генератор 2. Число подграфов, на кот

торые распадается граф в каждом испытании, равно числу выходов 16, по которым выдается информация, а веса подграфов вьщаются по выходам 16.

Формула изобретения

Устройство для исследования вероQ ятностных графов, содержащее элемент И, четыре группы ключей, две группы триггеров, генератор импульсов,- распределитель импульсов и наборное поле, контакты которого соединены со5 гласно, топологии графа, причем вход пуска генератора импульсов является входом пуска устройства, выход генератора импульсов подключен к информационным входам первых ключей пер0 вой и второй групп: вход установки в 1 k -ro триггера первой группы ( k 1,. .. н , где Н - количество вершин в графе) является К-м входом розыгрыша вершин устройства, прямой

5 вьпсод k-ro триггера первой группы подключен к управляющим входам К-х ключей второй и третьей групп, инверсный вьпсод fc-ro триггера первой группы (К±Н) подключен к управляюще0 му входу К -го ключа первой группы, вькод М-го ключа первой группы (М 1,...,Н- 2) подключен к информационному входу (м+1) ключей первой и второй групп, выход (Н-1)-го ключа первой группы подключен к информа- ; ционному входу н -го ключа, второй группы, выход ключа третьей группы подключен к контактам К-и группы первого массива контактов наборного

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

5

5

0

5

группы блоков памяти, пятая группа ключей и группа элементов И, причем инверсный выход k-ro триггера первой группы подключен к k-му входу элемента Инк входу признака чтения k-ro блока памяти первой группы, выход которого подключен к входу К-го слагаемого сумматора с фиксацией результата, инверсный выход Р-го триггера второй группы подключен к чтения р-го блока памяти второй группы, выход которого подключен к входу (н+р)-го слагаемого сумматора с фиксацией результата, выход которого подключен к информационным входам всех ключей пятой группы, вход опроса устройства подключен к тактовому входу распределителя импульсов.

//

416А66

К-й выход которого подключен к управляющему входу И-го ключа пятой группы, которого является К-м информационным выходом устройства, выход генератора импульсов подключен к входу сумматора с фиксацией результата, выход К-го ключа второй группы подключен к информационному входу Х-го ключа третьей группы, выход которого подключен к входу установки в О К-г.о триггера первой группы, контакты второй пары Р-й группы второго массива контактов наборного поля подключены к первому и второму входу р-го элемента И соответственно, выход которого подключен к входу установки в О Р -го триггера второй группы.

10

15

Г2

25

OrS

о о

23

21

(рцг.2

Редактор М.Дылын

Составитель А.Мишин Техред М.Дидык

Заказ 4438/53 Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная , 4

Корректор Л. Патай

Изобретение относится к вычислительной технике, и может быть использовано для решения задач на вероятностных графах и позволяет определять веса подграфов, на которые распадается вероятностный граф в каждом розыгрыше вершин и ребер. Уст°16 JS IS (Л со О) 4: С5 о