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

@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

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

Новые блоги и статьи Все статьи Все блоги /
std::vector в C++: от основ к оптимизации производительности NullReferenced 05.04.2025 Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .	Реляционная модель и правила Кодда: фундамент современных баз данных Codd 05.04.2025 Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .	Асинхронные операции в Django с Celery py-thonny 05.04.2025 Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .	Использование кэшей CPU: Максимальная производительность в Go golander 05.04.2025 Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .	Создаем Telegram бот на TypeScript с grammY run.dev 05.04.2025 Одна из его самых сильных сторон Telegram — это интеграция ботов прямо в экосистему приложения. В отличие от многих других платформ, он предоставляет разработчикам мощный API, позволяющий создавать. . .
Паттерны распределённых транзакций в Event-Driven микросервисах ArchitectMsa 05.04.2025 Современные программные системы всё чаще проектируются как совокупность взаимодействующих микросервисов. И хотя такой подход даёт множество преимуществ — масштабируемость, гибкость, устойчивость к. . .	Работа с объемным DOM в javascript Htext 04.04.2025 Сегодня прочитал статью тут о расходах памяти в JS, ее утечках и т. п. И вот что вспомнил из своей недавней практики. Может, кому пригодится. Хотя, в той статье об этом тоже есть. Дело в том, что я. . .	Оптимизация производительности Node.js с помощью кластеризации run.dev 04.04.2025 Масштабирование приложений для обработки тысяч и миллионов запросов — обыденная задача для многих команд. Node. js, благодаря своей асинхронной событийно-ориентированной архитектуре, стал популярной. . .	Управление зависимостями в Python с Poetry py-thonny 04.04.2025 Стандартный инструмент для установки пакетов в Python - pip - прекрасно справляется с базовыми сценариями: установил пакет командой pip install и используешь его. Но что произойдёт, когда разные. . .	Мониторинг с Prometheus в PHP Jason-Webb 04.04.2025 Prometheus выделяется среди других систем мониторинга своим подходом к сбору и хранению метрик. В отличие от New Relic, который использует агентный подход и отправляет данные во внешнее хранилище,. . .

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

	Транзитивное замыкание 10.02.2013, 21:00. Показов 9174. Ответов 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 2800 / 1846 / 202 Регистрация: 05.06.2011 Сообщений: 5,360
	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
	Спасибо большое! Буду ждать!