Устройство для решения задач на графах Советский патент 1992 года по МПК G06F15/20 

XJ

CJ О О GJ VI

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

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

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

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

К недостатку указанного устройства относится отсутствие возможности определения вероятности превышения потоком в графе заданного порога.

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

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

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

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

5 разреза.

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

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

Устройство содержит блок 1 синхронизации (БС), первый выход которого подключен к входу опроса многоканального

5 генератора 2 случайных событий (ГСС), выход событий К-го канала первой группы и выход события (К, М)-го канала второй группы которого соответственно соединены с входом опроса К-го канала первой группы и

0 входом опроса (К, М)-го канала второй группы многоканального блока 3 памяти (БП), информационный выход К-го канала первой группы и информационный выход (К, М)-го канала второй группы которого соответст5 венно соединены с входом задания веса К-й вершины и входом задания веса (К, М)-йдуги блока 4 определения значения минимального разреза (БОЗМР), информационный выход которого соединен с первым

0 информационным входом блока 5 сравнения, вход опроса которого соединен с вторым входом БС 1, вход пуска которого соединен с входом 6 пуска устройства, вход 7 задания вероятности существования вер5 шин графа и вход 8 задания вероятности существования дуг графа которого соединены соответственно с входом установки каналов первой группы и входом установки каналов второй группы ГСС 2, вход установки каналов первой группы и вход установки

каналов второй группы БП 3 соединены соответственно с входом 9 задания веса вершин графа и входом 10 задания веса дуг графа устройства, вход 11 задания истоков графа и вход 12 задания стоков графа которого соединены соответственно с входом задания истоков графа и входом задания стоков графа БОЗМР 4, вход 13 задания порога устройства соединен с вторым информационным входом блока 5 сравнения, выход признака больше которого соединен с выходом 14 признака превышения порога устройства.

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

Перед началом работы подается необходимая информация на входы устройства 7 - 13, которая записывается в соответствующие блоки.

На вход 6 устройства пуска подают импульс управления Лог. 1. При этом БС 1 формирует на своих выходах 1 и 2 последовательность сигналов, предусмотренную временной диаграммой его работы. Сигнал управления Лог. 1 на его первом выходе поступает на вход опроса ГСС 2. При этом ГСС 2 формирует на своих выходах набор потенциалов управления - Лог. 1 (наличие элемента графа в розыгрыше) и Лог. О (отсутствие элемента графа в розыгрыше). Наличие Лог. 1 на выходах ГСС 2 разрешает выдачу значения соответствующего элемента графа с выходов БП 3 на входы задания веса БОЗМР 4, определяет минимальный разрез (7) и выдает его значение CQ своего информационного выхода на первый информационный вход блока сравнения.

Через время, достаточное для окончания указанных процессов, БС 1 формирует сигнал Лог. 1 на своем выходе 2, поступающий на вход опроса блока 5 сравнения. При этом блок 5 сравнения сравнивает информацию, поступившую на его информационные входы.

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

На этом работа заканчивается. Формула изобретения

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

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

вероятности превышения потоком в графе заданного порога, в него введены многоканальный блок памяти, блок определения значения минимального разреза и блок сравнения, причем выход события К-ro канала первой группы и выход события (К М)-го канала второй группы многоканального генератора случайных событий (К 1,2

.... В; М 1, 2 В, где В - количество

вершин в графе) подключены к входу опроса

К-го канала первой группы и входу опроса (К, М)-го канала второй группы многоканального блока памяти соответственно, информационные выходы К-го канала первой группы и (К, М)-го канала второй группы

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

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

Изобретение относится к вычислительной технике и может быть использовано для исследования характеристик эффективности (надежности, живучести и т. д.) систем, структуру которых можно представить графами и сетями. Целью изобретения является расширение функциональных возможностей устройства за счет определения вероятности превышения потоком в графе заданного порога. Устройство содержит блок 1 синхронизации, многоканальный генератор 2 случайных событий, многоканальный блок 3 памяти, блок 4 определения значения минимального разреза, блок 5 сравнения, вход 6 пуска, вход 7 задания вероятности существования вершин графа, вход 8 задания вероятности существования дуг графа, вход 9 задания веса вершин графа, вход 10 задания веса дуг графа, вход 11 задания истоков графа, вход 12 задания стоков графа, вход 13 задания порога и выход 14 признака превышения порога. При поступлении на вход 6 пуска устройства импульса уровня логической 1 блок 1 синхронизации формирует на своих выходах последовательность сигналов, под управлением которой на выходе 14 устройства формируется признак отказа сети. 1 ил (Л С