Устройство для исследования вероятностных графов

 

Изобретение относится к вычислительной технике, может быть использовано для исследования сетей отображения вероятностными графами и позволяет определять веса подграфов, имеющих хотя бы одну управляющую и исполнительную вершины. Устройство работает по тактам, В первом такте производят начальную установку устройства. Во втором такте задают результаты розыгрыша исполнительных и управляющих вершин, ребер и дуг графа. Кроме зтого, во втором такте проверяется наличие исполнительных и управляющих вершин. Если по результатам розыгрьш а исполнительные или управляющие вершины отсутствуют, работа устройства прекращается в данном такте . В третьем такте находят первую управляющую вершину и определяют вес подграфа, которому она принадлежит . В четвертом такте опрашивают устройство, при этом на соответствующий выход веса подграфа устройства выдается значение веса. Далее работа устройства продолжается чередованием третьего и четвертого тактов до полного перебора всех управляющих вершин графа. 1 ил. i СЛ со 4 оо 00 4 О5

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (50 4 С 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4018737/24-24 (22) 07.02.86 (46) 30.10.87. Вюл. к 40 (72) M.М. Овчинников, Ю.М. Копте! и В.Г. Петриенко (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 896630, кл. С 06 F 15/20, 1982.

Авторское свидетельство СССР

1! 656073, кл. G 06 F 15/36, 1976. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ВЕРОЯТНОСТНЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике, может быть использовано для исследования сетей отображения вероятностными графами и позволяет определять веса подграфов, имеющих хотя бы одну управляющую и исполнительную вершины. Устройство работает по тактам. В первом такте произÄÄSUÄÄ 1348846 A 1 водят начальную установку устройства.

Во втором такте задают результаты розыгрыша исполнительных и управляющих вершин, ребер и дуг графа. Кроме этого, во втором такте проверяется наличие исполнительных и управляющих вершин. Если по результатам розыгрыша исполнительные или управляющие вершины отсутствуют, работа устройства прекращается в данном такте. В третьем такте находят первую управляющую вершину и определяют вес подграфа, которому она принадлежит, В четвертом такте опрашивают устройство, при этом на соответствующий выход веса подграфа устройства выдается значение веса. Далее работа устройства продолжается чередованием третьего и четвертого тактов до полного перебора всех управляющих вершин графа. 1 ил.

1348846

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

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

На чертеже изображена функциональная схема предлагаемого устройства, Устройство содержит вход 1 пуска устройства, генератор 2 импульсов, 1 выход 3 признака окончания работы устройства, установочный вход 4 устройства, первый 5 и второй 6 элементы ИЛИ, первую 7, вторую 8, третью

9, четвертую 10, пятую 11, шестую 12 группы ключей, коммутационное поле

l3, первую 14, вторую 15, третью 16, четвертую 17 группы триггеров, второй 18, третий 19 и первый 20 элементы И, сумматор 2 1, седьмую группу

22 ключей, группу 23 элементов И, распределитель 24 импульсов, выходы

25 веса подграфа, выходы 26 управляющих вершин устройства, выходы 27 исполнительных вершин устройства, выходы 28-30 признаков отсутствия управляющих верщин, исполнительных вершин, ребер и дуг графа, вход 31 опроса устройства, вхбды 32 задания управляющих и исполнительных вершин, ребер и дуг графа, элемент 33 задержки, блок 34 памяти, Как вариант показано исполнение первого ключа 9 в ниде реле, обмотка которого соединена с шиной нуленого потенциала и прямым выходом первого триггера 14, разделительного диода и контактов реле.

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

Перед началом работы в блок 34 заносят носа исполнительных вершин при помощ;I наборного поля вершины, ребра и дуги графа соединяют согласно его топо Iогии.

Устройство работает по тактам.

В первом такте на первые входы установки н "0" триггеров 14 — 17 с входа

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

35 ниями соответствующих триггер >н, которые единичными сигналами со своих прямых выходов замыкают одноименные ключи 9-12. Информационному входу ключа 12 соответствует начало дуги.

Если в розыгрыше нет управляющих или исполнительных вершин, ребер и дуг, то единичные потенциалы с инверсных выходов соответствующих триггеров проходят через элементы

18 (19,20) И и элемент 5 ИЛИ на выход 3 окончания испытания. В против«ом случае в третьем такте сигнал по входу 1 запускает генератор 2, первый импульс которого обнуляет сумматор 21, а через элемент 33 задержки проходит на информационные входы первых ключей 7 и 8. Пусть в

1 розыгрыше присутствует первая управляющая вершина, тогда первый триггер 14 находится в единичном состоянии, первый ключ 7 закрыт нулевым потенциалом на его управляющем входе, а первый ключ 8 открыт единичным потенциалом с прямого выхода первого триггера 14. Импульс, поступив на информационный вход первого ключа

7, проходит через контакты наборного поля и все вершины и ребра первого подграфа в результате срабатывания ключей 9-12, соответствующих присутствующим в розыгрыше элементам подграфа, связанным с первой управляющей вершиной. При этом импульсы с выходов соответствующих ключей поступают на вторые входы установки в "0" соответствующих триггеров 1417 и устанавливают их в нулевое состояние. Если в данном подграфе не было ни одной исполнительной вершины, то из блока 34 не будет считан ни один код веса. Если же есть одна или несколько исполнительных вершин, связанных хотя бы с первой управляющей вершиной, то при установке соответстнующих триггеров 16 в нулевое состояние единичный сигнал, проходя через элементы ИЛИ 6, откроет элементы И 23, указывающие на присутствие н первом подграфе управляющих вершины. При этом из блока 34 будет считан код веса исполнительных вершин, имеющих н первом подграфе связь хотя бы с одной управляющей вершиной.

Единичные потенциалы на соответствующих выходах 27 указывают на наличие исполнительных вершин, связанных в

1348846 первом подграфе хотя бы с одной управляющей вершиной, В четвертом такте с входа 31 на тактовый вход распределителя 24 поступает сигнал опроса, по которому распределитель 24 выдает сигнал на своей первый выход при этом открывается первый ключ 22, с выхода которого вес первого подграфа поступает на первый выход 25.

Второй импульс генератора 2 обнуляет сумматор 21 и проходит через все открытые ключи 7 до первого открытого ключа 8, соответствующего очередной присутствующей в данном розыгрыше управляющей вершине. Аналогично определяются характеристики второго подграфа в данном розыгрыше.

После того, как в единичном состоянии не останется ни одного триггера

14-16, или 15, останавливается генератор 2, обнуляется распределитель

24 и появляется сигнал на выходе 3.

Устройство готово к следующему розыгрышу.

15

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

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

35 делитель импульсов, тактовый вход которого является входом опроса устройства, вход пуска устройства подключен к входу пуска генератора импульсов выход которого подключен к Вхо 4С ду элемента задержки, выход которого подключен к информационным входам первых ключей первой и второй групп, информационный выход К-го ключа второй группы (К=1,..., А, где А — ко- 45 личество управляющих вершин в графе) подключен к информационному входу

К-ro ключа третьей группы, выход которого подключен к К-й группе контактов первого массива наборного поля и к входу установки в "0" К-го триггера первой группы, прямой выход которого подключен к управляющим входам К-х ключей второй и третьей групп, вход задания К-й управляющей вершины устройства подключен к входу установки в "1" К-го триггера первой группы, инверсный выход которого подключен к управляющему входу К-ro ключа первой группы (КФА), информационный выход которого подключен к информационному входу (К+1)-го ключа второй группы и к информационному входу (К+1)-го ключа первой группы (К А-1, A), вход задания M-го ребра устройства (M-1,..., В, где  — количество ребер в графе) подключен к входу установки в "1" M-го триггера второй группы, прямой выход которого подключен к управляющему входу М-ro ключа четвертой группы, исполнительная цепь которого подключена к М-й паре контактов второго массива наборного поля, контакты наборного поля соединены согласно топологии графа, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения массы исполнительных вершин в подграфах, имеющих хотя бы одну управляющую и одну исполнительную вершины, в него введены третья и четвертая группы триггеров, пятая, шестая и седьмая группы ключей, группа элементов И, два элемента

ИЛИ, три элемента И, блок памяти и сумматор, причем инверсный выход

К-го триггера первой группы подключен к первому входу К-го элемента И группы и к К-му входу первого элемента

И, выход которого подключен к первому входу первого элемента ИЛИ и является выходом признака отсутствия управляющих вершин устройства, вход задания P-й исполнительной вершины графа (P=1,..., С, где С вЂ” количество исполнительных вершин в графе) подключен к входу установки в " 1"

P-го триггера третьей группы, прямой выход которого подключен к управляющему входу P-го ключа пятой группы, исполнительная цепь которого подключена к P-й группе контактов третьего массива наборного поля и к входу установки в 0" P-ro триггера третьей группы, инверсный выход которого подключен к P-му входу считывания блока памяти, к P-му входу второго элемента ИЛИ, к P-му выходу исполнительных вершин устройства и к P-му входу второго элемента И, выход которого подключен к второму входу первого элемента И и является выходом признака отсутствия исполнительных вершин устройства, выход второго элемента ИЛИ подключен к вторым входам всех элементов И группы, вы1348846

15

28 2Е

ВНИИПИ Заказ 4803/49 Тираж 670

Подписное

Произв.-полигр. пр-тие, г. Ужгород, ул. Проектная, 4 ход К-го элемента И группы является

К-м выходом управляющих вершин устройства, вход задания Н-й дуги устройства (Н=1,..., D, где D — количество дуг в графе) подключен к входу установки в "1" Н-го триггера четвертой группы, прямой выход которого подключен к управляюшему входу

Н-го ключа шестой группы, исполнительная цепь которого подключена к

Н-й паре контактов четвертого массива наборного поля, инверсный выход

M-го триггера второй группы подключен к M-му входу третьего элемента

И, инверсный выход Н-го триггера четвертой группы подключен к (В+Н)-му входу третьего элемента И, выход которого является выходом признака отсутствия ребер и дуг ус тройства и подключен к третьему входу первого элемента ИГ!И, выход которого является выходом признака окончания работы устройства и подключен к входу останова генератора импульсов, выход которого подключен к. входу установки в 0" сумматора, вход P-го слагаемого которого подключен к P-му выходу блока памяти, а выход подключен к информационным входам всех ключей седьмой группы, P-й выход распределителя импульсов подключен к управляющему входу P-ro ключа седьмой группы, выход которого является выходом массы P-го подграфа устройства.