Транзитивное замыкание

@PinkPink · Регистрация: 10.05.2012

Author24 — интернет-сервис помощи студентам

Добрый вечер!
Разбираю транзитивное замыкание и насколько я поняла, выполняется перемножение матриц. Однако пример, который находится на изображении иллюстрирует результат возведения матрицы в 2 и 3 степень. При умножении матрицы самой на себя, т.е. при возведении в степень, я получила совсем другой результат, а именно
(0.8•0.8)+(1•0)+(0.1•0.3) (0.8•1)+(1•0.4)+(0.1•0) (0.8•0.1)+(1•0)+(0.1•0.2)
(0•0.8)+(0.4•0)+(0•0.3) (0•1)+(0.4•0.4)+(0•0) (0•0.1)+(0.4•0)+(0•0.2)
(0.3•0.8)+(0•0)+(0.2•0.3) (0.3•1)+(0•0.4)+(0.2•0) (0.3•0.1)+(0•0)+(0.2•0.2)
=
0.67 1.2 0.1
0 0.16 0
0.3 0.3 0.07

Скажите пожалуйста, каким методом там выполняется умножение и почему получается такой разный результат?

iifat · 11.02.2013, 05:56

Смотря что за матрицы, от этого зависит, что за сложение и что за умножение используются в формулах.

@Mysterious Light · 11.02.2013, 12:09

В данном случае ТС имеет в виду (хоть и не написала) следующее: http://www.sernam.ru/book_smn.php?id=24
$https://www.cyberforum.ru/cgi-bin/latex.cgi?R^2 \; :\; (x,z)\; \mapsto\; \max\limits_y \quad \min (\mu(x,y), \mu(y,z))$
То есть под (+) подразумевается взятие наибольшего числа, под (•) подразумевается взятие меншего числа.
С помощью Wolfram Math я подсчитал выписанное ТС выражение и оно сошлось с тем, что в ответе указано.
Действетильно, например, (0.8•0.8)+(1•0)+(0.1•0.3)=0.8+0+0.1=0.8

@PinkPink · 11.02.2013, 19:06 **[ТС]**

Спасибо большое за ответ!
Возможно, вы сможете развеять мои сомнения ещё по одному вопросу. Как видите вычисление матриц в степени k производится до R^k-1 = R^k, но существуют ситуации, когда такого равенства просто нет. Я не очень поняла как поступать в таком случае. Как мне известно, транзитивное замыкание используется для когнитивных карт, которые необходимы для прогнозирования систем. Может ли k быть выбрано вручную в зависимости от степени прогнозирования? т.е. насколько далеко мы хотим спрогнозировать результат? Или существует какое-то k, которое используется всегда в случае если последовательность вычислений не сходится?

@Mysterious Light · 12.02.2013, 10:22

Я больше привык работать с бинарными отношениями

Там транзитивное замыкание определяется как наименшее транзитивное множество, содержащее (как подмножество) рассматриваемое бин. отношение. Поэтому в матричном виде выполняется
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\tilde{R} = \bigcup\limits_{k=0}^\infty R^k$
Логика проста: R^k выражает бин. отношение между элементами (x,y), между которыми существует цепочка R-переходов длины ровно k, то есть если существует последовательность {a0,a1,a2,...,ak} такая, что a0=x, ak=y и любые два соседа входят в отношение R.
На моей памяти явно это понятие встречалось один раз, когда нужно было перейти от понятия одношаговой редукции к многошаговой, где количество шагов может быть любым. Поэтому если мы наперёд знаем, что можно ограничиться K шагами, то объединение в формуле становится конечным.

Здесь:
В статье указана подобная формула.

Можно не читать, это мысли вслух

Если логика та же, то можно ограничиться достаточно большим числом первых членов последовательности. Но это может не сработать в особо специфичиских вариантах (которые мы не рассматриваем) определения (+) и (*), потому что нет гарантии, что сумма
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\bigcup\limits_{k=0}^K R^k$
быстро сходится с ростом K. Но это нас не должно волновать, думаю.
Что всё-таки подразумевается под формулой (17.8), которая написана первой в посте, если сумма бесконечная?
Для «чётких» бин.отношений она означает сумму по счётной коллекции множеств {I,R,R²,...}. Иными словами, что ожидаемо, это означает, что xRy т.и т.т., когда найдётся k, что xR^ky, что эквивалентно рассуждениям выше по последовательность.
Для нечётких множеств это может означать по (12.25) и (12.26)
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{\tilde{R}}(x,y) = \max_k \; \mu_{R^k}(x,y)$
здесь ищется максимум или наибольшее число среди счётной последовательности, или
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{\tilde{R}}(x,y) = \sup_k \; \mu_{R^k}(x,y)$
здесь ищется супремум.
Как трактовать это я не знаю. В случае конечных (в частности, двучлена) сумм наибольший элемент/максимум и супремум совпадает, потому что (0,1) линейно упорядочена, т.е. любые два числа сравнимы. А вот для бесконечных множеств они разнятся, что выражается в таком примере:
Пусть случилось так, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{R^k}(x,y)$ — строго возрастающая последовательность по k для каких-то (x,y) и пусть R не содержала 1 в себе. Но она к тому же ограничена 1, которая не может быть достигнута (ведь постоянно идёт min-max, единице неоткуда взяться). Тогда эта последовательность имеет супремум, но не имеет максимума, потому что супремум не достигается, то есть нет его в последовательности.
Ну так как будем трактовать формулу (17.8)?

(17.16) утверждает, что для конечного носителя E сумма всегда конечна.
В остальных случаях либо читать в литературе, что нужно делать строго, либо ограничиться очень большим K. ИМХО, Вы правильно говорите по поводу дальновидности прогноза.

@PinkPink · 17.02.2013, 23:37 **[ТС]**

Возникли сложно с составлением матрицы взаимовлияния.
Вкратце:
есть граф, вес на рёбрах между вершинами это влияние. Соответственно можно составить матрицу этих весов. Но! Влияние может быть не прямое т.е. ребро от одной вершины к другой, а просто, если существует путь от одной вершины к другой. А влияет на Б, Б влияет на В, а В влияет на Г. Соответственно необходимо найти как А влияет на Г.

Все вычисления этих значений происходят на основе каузальной алгебры. На картинках, которые я прикрепила видно, какие операции, что в ней значат.
Для определения влияния всех вершин друг на друга используется транзитивное замыкание. Но вместо операции умножения (при возведении в степень) используется операция макстриангулярной композиции, которую мы разобрали выше. И к полученным степеням матриц применяется операция max как указано в книге. Напрашивается вывод, что если у нас везде только операции min и max новых значений мы не получим. Однако, в примере, приведённом в этой же книге чотко видна изначальная матрица, а потом результирующая матрица, со значениями, которые по моему мнению могли быть получены только благодаря умножению (вопрос тогда каким образом).
Вообщем, не могу придти к такому же результату как в примере в книге, даже чисто логически.

26.05.2013, 20:04

Здравствуйте!
Подскажите, пожалуйста, источник, фотографии из которого здесь вывешены.

Правильно ли я понимаю по примеру, что транзитивное влияние А на Г рассчитывается, как произведение сил влияния и выбора наибольшего из них (в случае положительных влияний)?

@PinkPink · 27.05.2013, 11:09 **[ТС]**

Сообщение от Igor_Gercog

Здравствуйте!
Подскажите, пожалуйста, источник, фотографии из которого здесь вывешены.

Правильно ли я понимаю по примеру, что транзитивное влияние А на Г рассчитывается, как произведение сил влияния и выбора наибольшего из них (в случае положительных влияний)?

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

27.05.2013, 12:42

Спасибо большое! Буду ждать!

Новые блоги и статьи Все статьи Все блоги /
Контейнеризация React приложений с Docker Reangularity 03.04.2025 Контейнеризация позволяет упаковать приложение со всеми его зависимостями в автономный контейнер, который можно запустить на любой платформе с установленным Docker. Это существенно упрощает процессы. . .	Свой попап в SwiftUI mobDevWorks 03.04.2025 SwiftUI, как декларативный фреймворк от Apple, предоставляет множество инструментов для создания пользовательских интерфейсов. В нашем распоряжении есть такие API как alerts, popovers, action sheets. . .	Антипаттерны микросервисной архитектуры ArchitectMsa 03.04.2025 Хорошо спроектированная микросервисная система может выдержать испытание временем, оставаясь гибкой, масштабируемой и устойчивой к большинству проблем. Такая архитектура обладает высоким уровнем. . .	std::mutex в C++: Советы и примеры использования bytestream 03.04.2025 std::mutex - это механизм взаимного исключения, который гарантирует, что критический участок кода выполняется только одним потоком в каждый момент времени. Это простое, но могущественное средство. . .	Не удержался от оценки концепции двигателя Стирлинга. Hrethgir 03.04.2025 Сколько не пытался - она выдавала правильные схемы, причём случайно рисовала горячие области в середине, холодные по краям, трубки с краёв в низ и магнит в соединяющей, но при этой выдавала описание. . .
Метод с двумя буферами (или double buffering) или ping-pong buffering Hrethgir 02.04.2025 Из ответов LM модели. Метод, который предполагает использование двух массивов для хранения промежуточных результатов сложения векторов, обычно применяется в сценариях, где необходимо минимизировать. . .	На любовном киберфронте Alexander-7 01.04.2025 Недавно на одном малоизвестном сайте знакомств мною заинтересовалась девушка: «Текст немного странный. Но, судя по адресу почты, иностранка», – подумал я. Поколебавшись пару суток, я ответил ей:. . .	Как работает Node.js изнутри run.dev 29.03.2025 Node. js изменил подход к разработке веб-приложений, позволив использовать JavaScript не только на стороне клиента, но и на сервере. Созданный в 2009 году Райаном Далем, этот открытый,. . .	Моки в Python: Mock Object Library py-thonny 29.03.2025 Тестирование кода требует особого подхода, когда речь идёт о компонентах, взаимодействующих с внешним миром. Мы часто сталкиваемся с непредсказуемостью HTTP-запросов, чтением данных из базы или. . .	JavaScript: Управление памятью и улучшение производительности run.dev 29.03.2025 В отличие от низкоуровневых языков программирования, JavaScript не требует ручного выделения и освобождения памяти. Здесь работает автоматический сборщик мусора, который определяет, какие объекты. . .

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292

	Транзитивное замыкание 10.02.2013, 21:00. Показов 9160. Ответов 8 Метки нет (Все метки) Добрый вечер! Разбираю транзитивное замыкание и насколько я поняла, выполняется перемножение матриц. Однако пример, который находится на изображении иллюстрирует результат возведения матрицы в 2 и 3 степень. При умножении матрицы самой на себя, т.е. при возведении в степень, я получила совсем другой результат, а именно (0.8•0.8)+(1•0)+(0.1•0.3) (0.8•1)+(1•0.4)+(0.1•0) (0.8•0.1)+(1•0)+(0.1•0.2) (0•0.8)+(0.4•0)+(0•0.3) (0•1)+(0.4•0.4)+(0•0) (0•0.1)+(0.4•0)+(0•0.2) (0.3•0.8)+(0•0)+(0.2•0.3) (0.3•1)+(0•0.4)+(0.2•0) (0.3•0.1)+(0•0)+(0.2•0.2) = 0.67 1.2 0.1 0 0.16 0 0.3 0.3 0.07 Скажите пожалуйста, каким методом там выполняется умножение и почему получается такой разный результат? Миниатюры 0

iifat 2799 / 1845 / 202 Регистрация: 05.06.2011 Сообщений: 5,357
	11.02.2013, 05:56
	Смотря что за матрицы, от этого зависит, что за сложение и что за умножение используются в формулах. 0

@Mysterious Light $Эксперт по математике/физике$ 4302 / 2093 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	11.02.2013, 12:09
	В данном случае ТС имеет в виду (хоть и не написала) следующее: http://www.sernam.ru/book_smn.php?id=24 $https://www.cyberforum.ru/cgi-bin/latex.cgi?R^2 \; :\; (x,z)\; \mapsto\; \max\limits_y \quad \min (\mu(x,y), \mu(y,z))$ То есть под (+) подразумевается взятие наибольшего числа, под (•) подразумевается взятие меншего числа. С помощью Wolfram Math я подсчитал выписанное ТС выражение и оно сошлось с тем, что в ответе указано. Действетильно, например, (0.8•0.8)+(1•0)+(0.1•0.3)=0.8+0+0.1=0.8 Миниатюры 1

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292
	11.02.2013, 19:06 [ТС]
	Спасибо большое за ответ! Возможно, вы сможете развеять мои сомнения ещё по одному вопросу. Как видите вычисление матриц в степени k производится до R^k-1 = R^k, но существуют ситуации, когда такого равенства просто нет. Я не очень поняла как поступать в таком случае. Как мне известно, транзитивное замыкание используется для когнитивных карт, которые необходимы для прогнозирования систем. Может ли k быть выбрано вручную в зависимости от степени прогнозирования? т.е. насколько далеко мы хотим спрогнозировать результат? Или существует какое-то k, которое используется всегда в случае если последовательность вычислений не сходится? 0

@Mysterious Light $Эксперт по математике/физике$ 4302 / 2093 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	12.02.2013, 10:22
	Я больше привык работать с бинарными отношениями Там транзитивное замыкание определяется как наименшее транзитивное множество, содержащее (как подмножество) рассматриваемое бин. отношение. Поэтому в матричном виде выполняется $https://www.cyberforum.ru/cgi-bin/latex.cgi?\tilde{R} = \bigcup\limits_{k=0}^\infty R^k$ Логика проста: R^k выражает бин. отношение между элементами (x,y), между которыми существует цепочка R-переходов длины ровно k, то есть если существует последовательность {a0,a1,a2,...,ak} такая, что a0=x, ak=y и любые два соседа входят в отношение R. На моей памяти явно это понятие встречалось один раз, когда нужно было перейти от понятия одношаговой редукции к многошаговой, где количество шагов может быть любым. Поэтому если мы наперёд знаем, что можно ограничиться K шагами, то объединение в формуле становится конечным. Здесь: В статье указана подобная формула. Можно не читать, это мысли вслух Если логика та же, то можно ограничиться достаточно большим числом первых членов последовательности. Но это может не сработать в особо специфичиских вариантах (которые мы не рассматриваем) определения (+) и (), потому что нет гарантии, что сумма $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bigcup\limits_{k=0}^K R^k$ быстро сходится с ростом K. Но это нас не должно волновать, думаю. Что всё-таки подразумевается под формулой (17.8), которая написана первой в посте, если сумма бесконечная? Для «чётких» бин.отношений она означает сумму по счётной коллекции множеств {I,R,R²,...}. Иными словами, что ожидаемо, это означает, что xRy т.и т.т., когда найдётся k, что xR^ky, что эквивалентно рассуждениям выше по последовательность. Для нечётких множеств это может означать по (12.25) и (12.26) $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{\tilde{R}}(x,y) = \max_k \; \mu_{R^k}(x,y)$ здесь ищется максимум или наибольшее число среди счётной последовательности, или $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{\tilde{R}}(x,y) = \sup_k \; \mu_{R^k}(x,y)$ здесь ищется супремум. Как трактовать это я не знаю. В случае конечных (в частности, двучлена) сумм наибольший элемент/максимум и супремум совпадает, потому что (0,1) линейно* упорядочена, т.е. любые два числа сравнимы. А вот для бесконечных множеств они разнятся, что выражается в таком примере: Пусть случилось так, что $https://www.cyberforum.ru/cgi-bin/latex.cgi?\mu_{R^k}(x,y)$ — строго возрастающая последовательность по k для каких-то (x,y) и пусть R не содержала 1 в себе. Но она к тому же ограничена 1, которая не может быть достигнута (ведь постоянно идёт min-max, единице неоткуда взяться). Тогда эта последовательность имеет супремум, но не имеет максимума, потому что супремум не достигается, то есть нет его в последовательности. Ну так как будем трактовать формулу (17.8)? (17.16) утверждает, что для конечного носителя E сумма всегда конечна. В остальных случаях либо читать в литературе, что нужно делать строго, либо ограничиться очень большим K. ИМХО, Вы правильно говорите по поводу дальновидности прогноза. 0

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292
	17.02.2013, 23:37 [ТС]
	Возникли сложно с составлением матрицы взаимовлияния. Вкратце: есть граф, вес на рёбрах между вершинами это влияние. Соответственно можно составить матрицу этих весов. Но! Влияние может быть не прямое т.е. ребро от одной вершины к другой, а просто, если существует путь от одной вершины к другой. А влияет на Б, Б влияет на В, а В влияет на Г. Соответственно необходимо найти как А влияет на Г. Все вычисления этих значений происходят на основе каузальной алгебры. На картинках, которые я прикрепила видно, какие операции, что в ней значат. Для определения влияния всех вершин друг на друга используется транзитивное замыкание. Но вместо операции умножения (при возведении в степень) используется операция макстриангулярной композиции, которую мы разобрали выше. И к полученным степеням матриц применяется операция max как указано в книге. Напрашивается вывод, что если у нас везде только операции min и max новых значений мы не получим. Однако, в примере, приведённом в этой же книге чотко видна изначальная матрица, а потом результирующая матрица, со значениями, которые по моему мнению могли быть получены только благодаря умножению (вопрос тогда каким образом). Вообщем, не могу придти к такому же результату как в примере в книге, даже чисто логически. Миниатюры 0

Igor_Gercog
	26.05.2013, 20:04
	Здравствуйте! Подскажите, пожалуйста, источник, фотографии из которого здесь вывешены. Правильно ли я понимаю по примеру, что транзитивное влияние А на Г рассчитывается, как произведение сил влияния и выбора наибольшего из них (в случае положительных влияний)?

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292
	27.05.2013, 11:09 [ТС]
	Сообщение от Igor_Gercog Здравствуйте! Подскажите, пожалуйста, источник, фотографии из которого здесь вывешены. Правильно ли я понимаю по примеру, что транзитивное влияние А на Г рассчитывается, как произведение сил влияния и выбора наибольшего из них (в случае положительных влияний)? Да, вы правильно понимаете. На данный момент не могу вам точно сказать всех авторов, один из них как мне помнится Круглов. Возможно позже я смогу сказать более точно 1

Igor_Gercog
	27.05.2013, 12:42
	Спасибо большое! Буду ждать!