Патенты с меткой «графах»

Номер патента: 1675907

Опубликовано: 07.09.1991

Авторы: Кириллов, Умбиталиев

МПК: G06F 15/173

Метки: графах, задач, решения

...изменяющимися данными, вместо коррекции базы знаний в соответствии собстановкой, возможно существующие факты отмечать сигналами В;в, а отсутствующие - сигналами Вв, = О, в соответствии сдинамикой их изменения,Элемент И 22 предназначен для вцработки сигнала записи информации в триггеры 26 и 27 при одновременном появлениисигналов координатной выборки на входах14, Инвертор 23, элемент 24, элемент ИЛИ25 образуют схему управления ячейкой 7при чтении хранимой в ней информации,При появлении сигнала горизонтальной выборки на входах 14 и сигнала "чтения" навходе 17 схема разрешает задачу информации с триггеров 26 и 27 через инвертирующие преобразователи 28 и 8 на шины 16ячейками строки однородной структуры, выбранной сигналом горизснтальной...

Номер патента: 1681311

Опубликовано: 30.09.1991

Автор: Костюк

МПК: G06F 15/173

Метки: графах, задач, решения

...единицы на первом выходе 6 группы и черезвремя, достаточное для его установления, - на своем выходе 7, При этом блок 2 формирует на своих выходах потенциалы уровня логической единицы в соответствии с составом КСС графа (с текущей топологией),включающей первую вершину. Через время, достаточное для определения КСС, блок 1 формирует потенциал уровня логической единицы на своем выходе 8, При этом блок3 стягивания вершин фиксирует на своихвыходах состав дуг, инцидентных первой вершине (текущей точке стягивания) при стягиваниии в нее всех вершин текущей КСС графа. Через время, достаточное для 5 10 15 203040 стягивания вершин, блок 1 снимает потенциалы с первого выхода 6 группы и выходов 7 и 8 и формирует импульс уровня логической единицы...

Номер патента: 1683037

Опубликовано: 07.10.1991

Автор: Лапин

МПК: G06F 15/173

Метки: графах, задач, решения

...временнойдиаграммой его работы. Блок 2 формируетимпульс уровня логической ".1" на своем выходе 11, При этом блок 3 формирует потенциалы уровня логической "1" на тех своихвыходах, номера которых соответствуют номерам дуг (ребер), входящим в состав маршрута из начальной в конечную вершинуграфа, При этом опрошенные каналы блока 504 памяти выдают на свои выходы занесенные в них значения (т.е, значения весов дуг,входящих в состав текущего пути). Черезвремя, достаточное для выполнения указанных операций, блок 2 синхронизации формирует импульс уровня логической "1" навыходе 12. При этом блок 5 суммирует всезначения, поступившие на его входы слагаемых, сравнивает полученную сумму со значением, полученным в предыдущеМ такте работы и при...

Номер патента: 1684795

Опубликовано: 15.10.1991

Авторы: Александров, Парамонов, Фролов

МПК: G06F 15/173

Метки: графах, задач, решения

...т,Кг рвботЫ бЛОК 1 СИНХроИЗацИИ" Уег потенцалы уровня логическойна К-м выходе 11 группы и наск" ":.д"оде 8. Г ри 3) ом блок 2 формирус;г)1 х выходах с)гтав множества вер" .:, г. орце являются концевыми точкамиСх)дяцсх из (В+1-К)-й вершины графа.г:;:г, 1 комутатор 4 подключает к своим. ),"Оцоныи выходам информацион. О входы Г)ородй групы (тем самым воз.у,сг)тся ) с входы блока 5 памяти. ;) ,рые сгоогвстсгвуют составу указанных цышс коце.ых Гочедк), а блок 5 памяти вы- ,Г;вта свои информационные выходы значсиЛаг;ислные в предыдущих тактах РЛГ, гы 1"М СЛМЫМа ВХОДЫ СУММатОРа 6 О, "ЮС ЗНСгОН 1 Я КОЛИЧЕСТВ РаЗЛИЧаО ц, ":", Ггуе из каждой концевой точки теу:.".)гг) акта работы в конечнуо вершину),дг). ЕРЕЗ ВЭЕМЯ, ДОСтаТОЧНОО ДЛЯ ОКОН- "с....

Номер патента: 1684796

Опубликовано: 15.10.1991

Авторы: Глушан, Курейчик, Пришибской

МПК: G06F 15/173

Метки: графах, задач, решения

...включающих зэданую, например К-ю центральную) вершину, перед началол 1 работы разряды блока 2 устанавливают в единицу, в блок 4 регистрации матрицы смежности заносят инфорлацию о топологии графа На К-й вход 5 задания центральной вершиы подм 1 ожестга и вход 6 опроса подают сигнал уровня лсгической единицы. При этом на выходах 7 устройс 1 ва будет сформирован состав вутре;1 е устачивых вершин, включающих К-ю вершину, 1 ил1684796 Формула изобретенияУстройство для решения задач на графах, содержащее блок элементов ИЛИ, блок регистрации вершин внутренне устойчивого подмножества, блок определения смежСоставитель А,Мишин Редактор Н.Каменская Техред М,Моргентал Корректор А.ОсауленкоЗаказ 3508 Тираж Подписное ВНИИПИ Государственного...

Номер патента: 1705840

Опубликовано: 15.01.1992

Авторы: Евстафьев, Зверков, Трояновский, Червяцов

МПК: G06F 15/419

Метки: графах, задач, решения

...)у чайных событий. многоканальныйлок памяти, вход пуска устройства, причем ход пуска устройства соединен с входом пуска блока синхронизации, К-й выход первой группы и (К. М)й выход второй группы многоканального генератора случаиных событий соединены соответственно с входами подключения К-го слагаемого первой группы и(К,М)-го слагаемого второй группы многоканального блока памяти.К недостатку указанного устройства относится отсутствие возможности моделировать отказы типа снижение суммарного веса графа ниже допустимого и учитывать процессы восстановления в исследуемых системах. структуры которых можно предстанить графами,Г., , ; " сч) ген с выходом 10 признака наличия отказа ,ИГ; ЕМЬ УГ, ГсчО)СТВа"сс:Ис вс. рас)осг)е) сс)дую)(им...

Номер патента: 1705841

Опубликовано: 15.01.1992

Авторы: Боровик, Дикий, Ильин, Листровой, Певнев

МПК: G06F 15/419

Метки: графах, задач, решения

...управляющих паботой блоков устройства. Блок 2формирования корневой вершины и синхро 50 ниэирующих сигналов управляет раб.тойблоков 3, 4, 7,1,7,(В - 1), 9.1.,9.(В - 1) ислужит для записи номера корневой вешины. Выход 12 корневой вершины подкл.ченк входу блока 3 задания матрицы восоре 55 бер, входу блока 4 переименования вершини входу корневой вершины каждого 6 ока5.15.(В - 1) формирования путеи, В ыхсд 13синхронизирующих сигналов пересылки путей блока 2 соединен с управляющим входом каждого блока 7.17,(В - 1) фикс;ции1 у гей, а выход 14 синхронизирующих сигналое получения ессое путей - с управляю;ц;м входом каждого блика 9.19.(В - 11 суммироеачия Блок 3 задан л глатрицы весов т)ебер пргз 7( аз гзчг;н,(11 гг хоан нля 1 выдачи...

Номер патента: 1709349

Опубликовано: 30.01.1992

Авторы: Глушан, Курейчик, Макеев

МПК: G06F 15/173

Метки: графах, задач, комбинаторнологических, решения

...ИЛИ 51, а все разряды с пятого по и-й содержат элемент И 66. Кроме того, разряды с третьего по п-й блока 4 содержат элементы И 64 и 65. Второй разряд содержит только элемент И 65. При этом один вход элемента ИЛИ 73 соединен с кнопкой 74 "Пуск", а второй вход через элемент задержки 72 - с выходом переключателя 71 и первыми входами элементов И 63. Один вход переключателя 71 подключен к входу 75 подачи тактовых импульсов, а второй вход через элемент 70 задержки - к кнопке 74 "Пуск", Выход элемента ИЛИ 73 связан с входами синхронизации триггеров 59 и входами установки исходного состояния регистра 71 сдвига. Каждый выход регистра сдвига (третий, четвертый, пятый, шестой) подключен к первому входу элемента И 58. Выходы элементов И 58 (с...

Номер патента: 1711187

Опубликовано: 07.02.1992

Авторы: Глушан, Курейчик, Рябец, Щербаков

МПК: G06F 15/419

Метки: графах, задач, решения

...этом второй блок 5 задания матрицы смежности выдает на свой выход значение элемента матрицы, находящегося на пересечении опрошенных строки и столбца (признак отсутствия или наличия дуги во втором графе). Через время, достаточное для окончания указанных процессов, блок 1синхронизации снимает потенциал уровня 5 10 15 20 25 30 35 40 45 50 55 логической единицы со своего выхода 9 и формирует потенциал уровня логической единицы на выходе 10. При этом блок 4 сравнения сравнивает поступившую на его входы информацию и формирует на своем выходе значение признака неравенства. При единичном значении признака неравенства блок 2 перечисления подмножества пар вершин устанавливается в исходное состояние, а блок 7 перечисления перестановок формирует на...

Номер патента: 1711188

Опубликовано: 07.02.1992

Автор: Лапин

МПК: G06F 15/419

Метки: графах, задач, решения

...логической единицы, младшие (первые) разряды всех остальных регистров 9 устанавливают в единицу(при этом предполагается, что вершины графа перенумерованы таким образом, что существует соответствие между (К)-й (К=1В, где В - количество вершин в графе) и Т(Р)-й вершинами графа (Р=1,Я, где Я - количество ярусов в графе; Т(Р)=1,.ВЯ(Р), где ВЯ(Р) - количество вершин в Р-м ярусе графа),На вход б пуска устройства подают импульс уровня логической единицы. Блок 1 синхронизации формирует на своем первом выходе импульс уровня. логической единицы, Блок 2 перечисления подмножеств вершин формирует на своем выходе очередное (в первом такте - первое) подмножество множества вершин графа (после первого тактового импульса сигнал уровня логической единицы...

Номер патента: 1716538

Опубликовано: 28.02.1992

Авторы: Алексеев, Борисов, Ячкула

МПК: G06F 15/419

Метки: графах, задач, решения

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

Номер патента: 1730637

Опубликовано: 30.04.1992

Авторы: Евстафьев, Червяцов

МПК: G06F 15/20

Метки: графах, задач, решения

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

Номер патента: 1765832

Опубликовано: 30.09.1992

Авторы: Ильин, Листровой, Мариян, Певнев, Сова

МПК: G06F 15/419

Метки: графах, задач, решения

...указанной вершины в составмаршрута не приводит к появлению замкнутого цикла, определяют вес маршрута (каксумму весов входящих в него ребер), запоминают (накапливают) вес и состав полученного маршрута и выдают вес маршрута насвои выходы весов маршрута. В противномслучае (т.е, при отсутствии связностивершин или при появлении циклов) каналывыдают на свой выход веса маршрута максимально возможные значения. При этомканалы блока 3 выбора минимума выдаютсигнал уровня логической единицы на тотсвой выход, позиция которого соответству 10 15 ет позиции информационного входа канала, на которую поступило наименьшее значение и выдают это значение на свои информационные входы (тем самым выбираетсямаршрут наименьшего веса в вершину, совпадающую по...

Номер патента: 1765833

Опубликовано: 30.09.1992

Автор: Лапин

МПК: G06F 15/419

Метки: графах, задач, решения

...минимума и значение суммы, вычисленное в данном такте работы, меньше зарегистрированного значения, блок 4 регистрирует вычисленное значение суммы (заменяет на него значение, зарегистриро- . ванное в предыдущих тактах работы), выдает его на свой выход текущего значения суммы и формирует импульс уровня логической единицы на своем выходе признака наличия экстремума. При этом блок 5 регистрирует по текущему адресу значения, установленные на его информационных входах, и выдает на свой информационный выход значение, поступившее по первому информационному входу (вес длиннейшего, кратчайшего из всех перечисленных ранее путей),Через время, достаточное для выполнения указанных операций, блок 1 синхронизации формирует импульс уровня логической...

Номер патента: 1767503

Опубликовано: 07.10.1992

Авторы: Бороденко, Бындыч, Валерьянов, Верияскин, Подзубанов

МПК: G06F 15/419

Метки: графах, задач, решения

...началом работы в блок 5 задания матрицы смежности заносят информацию о топологии графа, На вход 6 пуска устройства подают импульс уровня логической "1",При этом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, Сигнал уровня логической "1" появляется на первом выходе 7 группы блока 1 синхронизации. При этом блок 2 выдает на свои выходы подмножество вершин, из которых может быть до- стигнуто опрошенная вершина графа (в первом такте работы - первая вершина) Одновременно блок 4 выдает на свои выходы подмножество вершин, которые могут быть опрошены из опрошенной. При этом блок 3 выполняет поразрядно операцию логического умножения (конъюнкцию) операндов,...

Номер патента: 1767506

Опубликовано: 07.10.1992

Авторы: Калмыков, Обломов

МПК: G06F 15/419

Метки: графах, задач, решения

...блок 2 определения достижимых вершин, блок 3 определения соединяющих дуг, входы 4 признаков наличия дуг графа устройства, 15 входы 5 задания начальных вершин пути устройства, входы 6 задания конечных вершин пути устройства, выходы 7 признаков принадлежности вершин множеству вершин экстремального пути устройства и вы ходы 8 признаков принадлежности дуг множеству дуг экстремального пути устройства.Устройство работает следующим образом, 25Пусть необходимо определить состав дуг и вершин экстремального пути из заданной начальной д заданную конечную вершину графа.По входам 4 устройства задают матрицу 30 смежности исходного графа, по входам 5, 6 - его начальную и конечную вершины. При этом блок 1 формирует сигналы уровня логической "1" на...

Номер патента: 1774353

Опубликовано: 07.11.1992

Авторы: Соловьев, Тихонова, Черезова

МПК: G06F 15/419

Метки: графах, задач, решения

...блока 3 подключен к одноименному входу узла 14 определения смежных вершин, выход признака окончания списка узла 12 перечисления вершин является выходом 24 признака выдачи информации блока 3 и подключен к входу останова узла 11 синхронизации, М- ый вход 25 задания центральной вершины блока 3 подключен к М-му разряду первого информационного входа узла логического сложения 13.Устройство работает следующим образом.Перед началом работы обнуляют блок 4 регистрации, устанавливают в исходное состояние блок 2 перечисления вершин, в блок 5 задания матрицы смежности заносят информацию о топологии графа,На вход 7 пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих выходах 8-10...

Номер патента: 1777156

Опубликовано: 23.11.1992

Авторы: Беликов, Жигора

МПК: G06F 15/419

Метки: графах, задач, решения

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

Номер патента: 1837311

Опубликовано: 30.08.1993

Авторы: Александров, Парамонов, Рыбаков, Фролов

МПК: G06F 15/20

Метки: графах, задач, решения

...того, как удут перенумерованы концевые вершины сех исходящих из них дуг. Топологию, полченного таким образом графа заносят в лок 3 задания матрицы смежности. В блокпамяти по адресу В заносят единицу, а стальные ячейки обнуляют, кроме того в локе памяти 5 сформирована матрицавхв - вероятностей перехода по дугам, чейки которой обнуляют, На вход 9 пуска роцесса счета числа путей из каждой верины графа в конечную блока 1 синхрониации подают импульс уровня логической диницы, При этом блок 1 синхронизации ормирует на своих выходах 11, 12, 13, 14 оследовательность сигналов уровня логиеской единицы предусмотренную временой диаграммой его работы. Поскольку абота устройства состоит из В однотипных актов, рассмотрим 1-й. В 1-м такте работы лок 1...

Номер патента: 1837312

Опубликовано: 30.08.1993

Авторы: Ильин, Ковальчук, Листровой, Мариян, Певнев

МПК: G06F 15/20, G06G 7/122

Метки: графах, задач, решения

...ИЛИ 47.Выход сумматора 38 подключен к информационным входам сборок элементов И 49.(В+1) и 51. Выходэлемента ИЛИ 47 соединен с первым входом триггера 48, выход которого 55 подключен к разрешающим входам сборок элементов И 51 и 52, Выходы сборок элементовы И 49,149.(8+1) подключены к входам соответствующих регистров 50,150.(В+1),.в которых хранится информация о кратчайшем пути (номера вершин и вес пути).Выходы регистров 50.2.50.(В+1) подлючены к информационным входам саотетствующих сборок элементов И 7.1.57.В и, кроме того, выход регистра 0.(В+1) подключен к информационным вхоам сборок элементов И 52 и 56, Выходы борок элементов И 51 и 52 соединены со ходами схемы 53 сравнения, выход котоой подключен к разрешающим входам сбоок элементов...

Номер патента: 1837314

Опубликовано: 30.08.1993

Авторы: Додонов, Приймачук, Самков, Чадюк, Щетинин

МПК: G06F 15/20

Метки: графах, задач, решения

...еток о свершении вершин.В многоканальном таймере 5 в вершиы памяти заносится информация о длит льностях моделируемых дуг сети,В блок памяти логической функции верин 7 предварительно для каждой вершины ( амера списка) заносятся информационые слова, соответствующие их логическим ункциям, Первоначально на полюс 8 задася номер начальной вершины моделируеой сети. На полюс 9 задается сигнал ачальной установки. В блоке 4 по этим сигналам для выбранной вершины опредеяется список исходящих дуг, который с выода блока 4 поступает на вход ногоканального таймера 5. В блоке 5 включаются таймер лирования дуг, исходящих из н раины сети. В эти таймеры з ительности моделируемых време рвалов (запускаются выбранные ереэ время, достаточное для...

Номер патента: 1839263

Опубликовано: 30.12.1993

Авторы: Евстафьев, Червяцов

МПК: G06F 15/419

Метки: вероятностных, графах, задач, решения

...чен к входу пуска блока синхронизации, маршрута. Выходпризнакапревышенияпопервый выход которого подключен к такто- рога блока 4 соединен с тактовым входом вому входу регистрирующего блока пере- регистрирующего блока 5 выбора максимучисления множества маршрутов, выход ма, информационный выход которого соеприэнакаисчерпанияспискамаршрутовко- динен с первым информационным входом1839263 5 10 15 20 25 30 35 40 50. блока 6 сравнения. Вход 7 пуска устройства соединен с входом пуска блока 1, второй выход которого соединен с входом опроса блока 4, установочный вход задания порога вероятности которого подключен к одноименному входу 8 устройства. Вход 9 задания порога эффективности устройства подключен к второму информационному входу...