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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Сайт компании Red-Star-Soft переехал на новый хостинг! Etyuhibosecyu 06.03.2025 Как и советовал Rius, я покинул хостинг от "Ru-Center" и перенес сайт red-star-soft. com на хостинг с более позитивными отзывами (спойлер: найти его было далеко не просто) (чтобы прочитать текст,. . .	Альтернативная сериализация в Java: сравнение Kryo, Protobuf и Avro Jamaican 06.03.2025 Сериализация — один из краеугольных процессов в Java-разработке. Превращение объектов в поток байтов для хранения или передачи по сети с последующим восстановлением звучит просто, но реализация этого. . .	Битва Java-кешей: Сравниваем Ehcache, Caffeine и Hazelcast Jamaican 06.03.2025 Производительность — вечный Святой Грааль для Java-разработчиков. Мы оптимизируем алгоритмы, настраиваем JVM, распараллеливаем процессы, но неизменно приходим к одному и тому же средству ускорения —. . .	Параметры подтверждения сообщения Kafka Jamaican 06.03.2025 Среди распределённых систем и высоконагруженных приложений Apache Kafka занимает особое место. Эта платформа потоковой обработки данных давно стала стандартом де-факто для организаций, которым. . .	Оптимизация времени запуска Spring Boot Jamaican 06.03.2025 Вы когда-нибудь сидели, барабаня пальцами по столу, пока ваше Spring Boot приложение медленно поднимается? Этот момент, когда вы успеваете сходить за кофе, пообщаться с коллегами и вернуться, а. . .
Деплой Kubernetes в Java: масштабирование Spring Boot приложений Jamaican 06.03.2025 Когда ваше Spring Boot приложение внезапно получает всплеск трафика или требует плавного обновления без простоя — традиционные методы деплоя часто пасуют. Именно здесь на сцену выходит Kubernetes —. . .	Бессерверные приложения Java: сравнение AWS Lambda и Azure Functions Jamaican 06.03.2025 Что такое "бессерверные приложения" и почему они так привлекательны? Вопреки названию, серверы никуда не исчезли — просто теперь управление инфраструктурой перекладывается на плечи облачного. . .	Безопасность микросервисов с OAuth2 и OpenID Connect Jamaican 06.03.2025 С ростом популярности микросервисов растут и проблемы, связанные с их безопасностью. В отличие от монолитных приложений, где безопасность можно было обеспечить централизованно, микросервисная. . .	Структурное логирование в Spring Boot Jamaican 06.03.2025 Представьте, что вы управляете сотней микросервисов в продакшн-среде. Внезапно один из сервисов начинает давать сбои, и вам нужно срочно выяснить причину. Вы открываете логи и видите бесконечные. . .	Предотвращение XSS, CSRF и SQL-инъекций в JavaScript bytestream 05.03.2025 В эпоху цифровизации безопасность веб-приложений становится не просто рекомендацией, а жизненной необходимостью. Если вы разрабатываете приложения на JavaScript, вам наверняка знакома эта. . .

@PinkPink 9 / 9 / 5 Регистрация: 10.05.2012 Сообщений: 292
		1
	Транзитивное замыкание 10.02.2013, 21:00. Показов 9125. Ответов 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 2786 / 1833 / 201 Регистрация: 05.06.2011 Сообщений: 5,334
	11.02.2013, 05:56	2
	Смотря что за матрицы, от этого зависит, что за сложение и что за умножение используются в формулах. 0

@Mysterious Light $Эксперт по математике/физике$ 4302 / 2093 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	11.02.2013, 12:09	3
	В данном случае ТС имеет в виду (хоть и не написала) следующее: 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 [ТС]	4
	Спасибо большое за ответ! Возможно, вы сможете развеять мои сомнения ещё по одному вопросу. Как видите вычисление матриц в степени 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	5
	Я больше привык работать с бинарными отношениями Там транзитивное замыкание определяется как наименшее транзитивное множество, содержащее (как подмножество) рассматриваемое бин. отношение. Поэтому в матричном виде выполняется $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 [ТС]	6
	Возникли сложно с составлением матрицы взаимовлияния. Вкратце: есть граф, вес на рёбрах между вершинами это влияние. Соответственно можно составить матрицу этих весов. Но! Влияние может быть не прямое т.е. ребро от одной вершины к другой, а просто, если существует путь от одной вершины к другой. А влияет на Б, Б влияет на В, а В влияет на Г. Соответственно необходимо найти как А влияет на Г. Все вычисления этих значений происходят на основе каузальной алгебры. На картинках, которые я прикрепила видно, какие операции, что в ней значат. Для определения влияния всех вершин друг на друга используется транзитивное замыкание. Но вместо операции умножения (при возведении в степень) используется операция макстриангулярной композиции, которую мы разобрали выше. И к полученным степеням матриц применяется операция max как указано в книге. Напрашивается вывод, что если у нас везде только операции min и max новых значений мы не получим. Однако, в примере, приведённом в этой же книге чотко видна изначальная матрица, а потом результирующая матрица, со значениями, которые по моему мнению могли быть получены только благодаря умножению (вопрос тогда каким образом). Вообщем, не могу придти к такому же результату как в примере в книге, даже чисто логически. Миниатюры 0

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

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

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