Об алгоритмах умножения матриц

[Xaositect]

Linkey в сообщении #892009 писал(а):

Может вы оговорились? По-моему наоборот, образование снижает способность мыслить нестандартно.
Я слышал такую историю, не знаю насколько это достоверно: однажды Форд пытался сделать хорошее стекло для автомобилей, и его специалисты не могли ничего придумать, говорили — это невозможно. Тогда Форд пригласил людей с улицы, не разбиравшихся в этих вещах, и те быстро нашли решение (потому что могли посмотреть на проблему незашоренным взглядом).

Давайте проведем эксперимент.
Есть задача, для понимания которой образования 7 класса хватит: У нас есть $2n^2$ чисел $a_{11},a_{12},\dots,a_{1n},a_{21},a_{22},\dots,a_{2n},\dots,a_{n1},a_{n2},\dots,a_{nn}, b_{11},b_{12},\dots,b_{1n},b_{21},b_{22},\dots,b_{2n},\dots,b_{n1},b_{n2},\dots,b_{nn}$. Число $n$ большое. Надо вычислить $n^2$ чисел $c_{11},\dots,c_{nn}$, где $c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + \dots + a_{in} b_{nj}$. Для вычисления можно использовать разные арифметические операции - сложение умножение, вычитание. Деление тоже можно, но надо помнить, что на 0 делить нельзя. Чем меньше операций используется - тем лучше.
Буду рад каким-нибудь нестандартным мыслям по задаче :)

[Linkey]

Xaositect в сообщении #892028 писал(а):

Давайте проведем эксперимент.

Если я правильно понял, эта задача на оптимизацию, как свести к минимуму вычислительные ресурсы. Я подумаю и напишу ответ в ЛС, чтобы другим тоже осталось.

[Sonic86]

Linkey в сообщении #892030 писал(а):

Если я правильно понял, эта задача на оптимизацию, как свести к минимуму вычислительные ресурсы. Я подумаю и напишу ответ в ЛС, чтобы другим тоже осталось.

Это слишком известная задача, чтобы ее оставлять другим.
Пишите здесь, не стесняйтесь. (может тогда дойдет быстрее)

[Munin]

Linkey в сообщении #892000 писал(а):

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

Научное творчество найти легко. Как всегда, надо просто знать, где искать. Главный секрет: научное творчество лежит не на форумах.

Научное творчество можно найти в статьях, на конференциях, семинарах (научных). Например, в физико-математических науках - есть огромный сайт arXiv.org, через который проходят, по сути, все публикации, ещё даже перед тем, как быть напечатанными в журналах. (Некоторые так и остаются в виде "публикации на arXiv-е".) В био-медицинских науках схожую роль играет сайт PubMed. Есть поисковик по научным публикациям Google Scholar.

Linkey в сообщении #892009 писал(а):

Может вы оговорились? По-моему наоборот, образование снижает способность мыслить нестандартно.

Это распространённый миф. Распространён он среди людей необразованных. Им приятно думать, что раз они не получили образования, то взамен получили какую-то другую выгоду: не лишились "способности мыслить нестандартно".

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

Кстати, к слову о примере Xaositect: ещё образование позволяет не только больше фантазировать, но и оценивать результаты своей фантазии, взвешивать их объективно и беспристрастно. Например, возможны такие уточнения к названной постановке задачи:
1. Операция умножения считается самой "дорогостоящей" (не считая деления, которого можно не использовать вообще), и ценным является уменьшение количества именно умножений, даже если оно происходит за счёт увеличения количества сложений и вычитаний.
2. Поскольку число $n$ не оговорено (просто сказано, что оно большое), то более ценным является способ вычислений, который при бо́льших $n$ становится эффективней, хотя при ме́ньших $n$ может уступать другим способам. (Например, для $n=1$ есть один очевидный способ, и все остальные либо совпадают с ним по эффективности, либо уступают.)
С этими уточнениями, это становится той самой известной задачей, о которой говорит Sonic86, и решение которой до конца не доведено, но потребовало именно нестандартного мышления и образованных людей.

[patzer2097]

Munin в сообщении #892060 писал(а):

С этими уточнениями, это становится той самой известной задачей, о которой говорит Sonic86,

и перестает быть задачей,

Xaositect в сообщении #892028 писал(а):

для понимания которой образования 7 класса хватит

[Munin]

patzer2097 в сообщении #892068 писал(а):

и перестает быть задачей,

Xaositect в сообщении #892028 писал(а):

для понимания которой образования 7 класса хватит

Нет, условия-то вполне понятны и 7-класснику. Вот решение - нет. Точнее, даже решение может быть понятно, непонятно будет другое: почему это - решение.

[patzer2097]

Munin в сообщении #892079 писал(а):

Нет, условия-то вполне понятны и 7-класснику

Если $n$ и элементы обеих матриц фиксированы, то я еще готов согласиться с Xaoscitect; но имеет ли эта задача смысл при фиксированном $n$? Но у Вас данные произвольны, и Вы говорите о "способе вычисления" для всех $n$ - т.е., надо думать, об алгоритме, понятие сложности которого выходит далеко за рамки школьной программы

Munin в сообщении #892079 писал(а):

Вот решение - нет

ну, решение пока никому не понятно; вся надежда на Linkey!

[Linkey]

Извините, не осилил, да и лень разбираться.
У меня только есть общая идея. Предположим, нам надо сосчитать два числа:
$N_1=a_1b_1+a_2b_2$
$N_2=a_1b_2+a_2b_1$
Если решать задачу в лоб, здесь нужно четыре операции умножения. Но можно сосчитать сумму и разность $N_1$ и $N_2$:
$N_1+N_2=(a_1+a_2)(b_1+b_2)$
$N_2-N_1=(a_1-a_2)(b_1-b_2)$
В данном случае достаточно выполнить две операции умножения, а потом пересчитать $N_1$ и $N_2$ как линейную комбинацию этих сумм.
Я пробовал повторить этот же приём для вашей задачи при $n=2$, выписал все члены матрицы, которую нужно сосчитать, и не смог найти линейную комбинацию этих членов, для которой можно обойтись одной операцией умножение. Но, может быть, если $n=3$ или больше, такую комбинацию можно найти (хотя бы вместо трёх умножений обойтись двумя)?

-- 01.08.2014, 09:44 --

Munin в сообщении #892060 писал(а):

Это распространённый миф. Распространён он среди людей необразованных. Им приятно думать, что раз они не получили образования, то взамен получили какую-то другую выгоду: не лишились "способности мыслить нестандартно".

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

[Xaositect]

Linkey в сообщении #892281 писал(а):

Я пробовал повторить этот же приём для вашей задачи при $n=2$, выписал все члены матрицы, которую нужно сосчитать, и не смог найти линейную комбинацию этих членов, для которой можно обойтись одной операцией умножение. Но, может быть, если $n=3$ или больше, такую комбинацию можно найти (хотя бы вместо трёх умножений обойтись двумя)?

Там таких нет. Для любого $n$ любая нетривиальная линейная комбинация $c_{ij}$ как билинейная форма от $a, b$ имеет ранг, кратный $n$, и поэтому не вычисляется меньше, чем за $n$ умножений.
Если бы Вы знали линейную алгебру, Вы могли бы до этого додуматься. Любое знание - это не ограничение, а полезный в каких-то случаях инструмент.

Если интересно, то для $n=2$ существует алгоритм с 7 умножениями вместо 8, а вот если мы вместо всех четырех $c_{ij}$ будем вычислять любые три из них, то улучшить тривиальный алгоритм с 6 умножениями нельзя.

[Munin]

Linkey в сообщении #892281 писал(а):

Я считаю, что образование способствует догматизму.

Да, это ещё один распространённый среди невежд миф. Тоже очень приятный, и абсолютно ошибочный.

Linkey в сообщении #892281 писал(а):

Наша система образования построена так, что людям подаются только знания, вписывающиеся в какое-то мировоззрение, общую парадигму

Это может заявлять только человек, не получивший образования, потому что тот, кто получил, - прекрасно знает, что это не так.

Linkey в сообщении #892281 писал(а):

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

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

Не всякое "одна баба сказала" - это факт. Не всё, что вы мне имеете сказать, я готов доверчиво слушать. У меня есть собственные мысли, отличающиеся от ваших, и я имею право и смелость их высказывать и на них настаивать. Более того, я их аргументирую (в отличие от вас). Если вы не готовы к столкновению с такой реальностью (а это норма жизни, а не лично моя вредность) - вы инфантильны. Если вы называете это агрессией - вы просто не знаете, что такое настоящая агрессия.

[Xaositect]

patzer2097 в сообщении #892086 писал(а):

но имеет ли эта задача смысл при фиксированном $n$?

Если говорить про количество умножений, то эта задача имеет смысл даже при $n=3$. Известная верхняя оценка - $\leqslant 22$, нижняя - $\geqslant 19$.

[Munin]

Xaositect в сообщении #892284 писал(а):

Любое знание - это не ограничение, а полезный в каких-то случаях инструмент.

+1.

От того, что человек идёт в магазин, и покупает молоток, он не становится "приверженцем веры (церкви) молоткистов". Он не отказывается навсегда в жизни пользоваться пилой, или рубанком, или отвёрткой. Зато он становится способным забивать гвозди. А без молотка он не имел такой способности. Рукой, или подручной табуреткой, гвозди особо не позабиваешь.

[Linkey]

Munin в сообщении #892285 писал(а):

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

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

[Xaositect]

Linkey в сообщении #892293 писал(а):

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

Лично я в этом сильно не уверен.

[Linkey]

Xaositect в сообщении #892284 писал(а):

Если интересно, то для $n=2$ существует алгоритм с 7 умножениями вместо 8, а вот если мы вместо всех четырех $c_{ij}$ будем вычислять любые три из них, то улучшить тривиальный алгоритм с 6 умножениями нельзя.

А числа целые, рациональные или действительные?