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

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

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

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

Устройство содержит вход 1 пуска устройства, генератор 2 импульсов, выход J признака окончания работы устройства, установочный вход 4 устройства, первый 5 и второй 6 элементы ИЛИ, первую 7, вторую 8, третью 9, четвертую 10, пятую 11, шестую 12 группы ключей, коммутационное поле 13, первую 14, вторую 15, третью 16, четвертую 17 группы триггеров, второй 18, третий 19 и первый 20 элементы И, сумматор 21, седьмую группу 22 ключей, группу 23 элементов И, распределитель 24 импульсов, выходы 25 веса подграфа, выходы 26 управляющих вершин устройства, выХоды 27 исполнительных вершин устройства, выходы 28-30 признаков отсутствия управляющих верщин, исполнительных вершин, ребер и дуг графа, вход 31 опроса устройства, вхбды 32 задания управляющих и исполнительных вершин, ребер и дуг графа, элемент 33 задержки, блок 34 памяти. Как вариант показано исполнение первого ключа 9 в виде реле, обмотка которого соединена с шиной нулевого потенциала и прямым выходом первого триггера 14 разделительного диода и контактов реле.

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

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

Устройство работает по тактам. В первом такте на первые входы установки в О триггеров 14-17 с входа 4 поступает единичный потенциал и обнуляет их. В третьем такте на входы 32 поступают результаты розыгрыша элементов графа, причем присутствующие в розыгрыше элементы графа воспроизв(1дятся единичными состоя488462

ниями соответствующих триггерчл,

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

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

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

2{) входы первых ключей 7 и 8. Пусть в розыгрыше присутствует первая управляющая вершина, тогда первый триггер 14 находится в единичном состоянии, первый ключ 7 закрыт нулевым

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

30 7, проходит через контакты наборного поля и все вершины и ребра первого подграфа в результате срабатывания ключей 9-12, соответствующих присутствующим в розыгрьпде элементам

(- подграфа, связанным с первой управляющей вершиной. При этом импульсы с выходов соответствующих ключей поступают на вторые входы установки в О соответствующих триггеров 144Q 17 и устанавливают их в нулевое состоя- вне. Если в данном подграфе не бьшо ни одной исполнительной вершины, то из блока 34 не будет считан ни один код веса. Если же есть одна или не(- сколько исполнительных вершин, связанных хотя бы с первой управляющей вершиной, то при установке соответствующих триггеров 16 в нулевое состояние единичный сигнал, проходя через элементы ИЛИ 6, откроет элементы И 23, указывающие на присутствие U первом подграфе управляющих вершины. При этом из блока 34 будет считан код веса исполнительных вершин, имеющих в первом подграфе связь хотя бы с одной управляющей вершиной. Единичные потенциалы на соответствующих выходах 27 указывают на наличие исполнительных вершин, связанных в

50

55

первом подграфе хотя бы с одной управляющей вершиной,

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

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

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

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

ключа первой группы (), информационный выход которого подключен к информационному входу (К+1)-го ключа

второй группы и к информационному входу (К+1)--ро ключа первой группы (KfA-1, А), вход задания М-го ребра устройства (М-1,,,., В, где В - количество ребер в графе) подключен

к входу установки в 1 М-го триггера второй группы, прямой выход которого подключен к управляющему входу М-го ключа четвертой группы, исполнительная цепь которого подключена к М-й

паре контактов второго массива наборного поля, контакты наборного поля соединены согласно топологии графа, отличающееся тем.

что, с целью расширения функциональных возможностей устройства за счет определения массы исполнительных вершин в подграфах, имеющих хотя бы одну управляющую и одну исполнительную вершины, в него введены третья и четвертая группы триггеров, пятая, шестая и седьмая группы ключей, группа элементов И, два элемента ИЛИ, три элемента И, блок памяти и сумматор, причем инверсный выход К-го триггера первой группы подключен к первому входу К-го элемента И группы и к К-му входу первого элемента И, выход которого подключен к первому входу первого элемента ИЛИ и является выходом признака отсутствия управляющих вершин устройства, вход задания Р-й исполнительной вершины графа (,,,,, С, где С - количество исполнительных вершин в графе) подключен к входу установки в 1 Р-го триггера третьей группы, прямой выход которого подключен к управляющему входу Р-го ключа пятой группы, исполнительная цепь которого подключена к Р-й группе контактов третьего массива наборного поля и к входу установки в О Р-го триггера третьей группы, инверсный выход которого подключен к Р-му входу считывания блока памяти, к Р-му входу второго элемента ИЛИ, к Р-му выходу исполнительных вершин устройства и к Р-му входу второго элемента И, выход которого подключен к второму входу первого элемента И и является выходом признака отсутствия исполнительных вершин устройства, выход второго элемента ИЛИ подключен к вторым входам всех элементов И группы, выход К-го элемента И группы является К-м выходом управляющих вершин устройства, вход задания Н-й дуги устройства (,..., D, где D - количество дуг в графе) подключен к входу установки в 1 Н-го триггера четвертой группы, прямой выход которого подключен к управляющему входу Н-го ключа щестой группы, исполнительная цепь которого подключена к Н-й паре контактов четвертого массива наборного поля, инверсный выход М-го триггера второй группы подключен к М-му входу третьего элемента И, инверсный выход Н-го триггера четвертой группы подключен к (В+Н)-м входу третьего элемента И, выход ко

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

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

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

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

Подписное