2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Об алгоритмах умножения матриц
Сообщение31.07.2014, 10:20 
Заслуженный участник
Аватара пользователя


06/10/08
6313
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 делить нельзя. Чем меньше операций используется - тем лучше.
Буду рад каким-нибудь нестандартным мыслям по задаче :)

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение31.07.2014, 10:40 
Аватара пользователя


01/09/13

711
Xaositect в сообщении #892028 писал(а):
Давайте проведем эксперимент.


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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение31.07.2014, 11:05 
Заслуженный участник


08/04/08
8505
Linkey в сообщении #892030 писал(а):
Если я правильно понял, эта задача на оптимизацию, как свести к минимуму вычислительные ресурсы. Я подумаю и напишу ответ в ЛС, чтобы другим тоже осталось.
Это слишком известная задача, чтобы ее оставлять другим.
Пишите здесь, не стесняйтесь. (может тогда дойдет быстрее)

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение31.07.2014, 13:53 
Заслуженный участник
Аватара пользователя


30/01/06
72408
Linkey в сообщении #892000 писал(а):
Я в прошлом здесь цитировал одного современного публициста, который пишет, что он любит философию и ненавидит псевдофилософию. Так и с этими форумами: меня интересует научное творчество, но его крайне сложно найти из-за нагромождения псевдонаучного псевдотворчества.

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

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

Linkey в сообщении #892009 писал(а):
Может вы оговорились? По-моему наоборот, образование снижает способность мыслить нестандартно.

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

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

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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение31.07.2014, 14:25 
Заслуженный участник


14/03/10
867
Munin в сообщении #892060 писал(а):
С этими уточнениями, это становится той самой известной задачей, о которой говорит Sonic86,
и перестает быть задачей,
Xaositect в сообщении #892028 писал(а):
для понимания которой образования 7 класса хватит

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение31.07.2014, 14:46 
Заслуженный участник
Аватара пользователя


30/01/06
72408
patzer2097 в сообщении #892068 писал(а):
и перестает быть задачей,
Xaositect в сообщении #892028 писал(а):
для понимания которой образования 7 класса хватит

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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение31.07.2014, 15:17 
Заслуженный участник


14/03/10
867
Munin в сообщении #892079 писал(а):
Нет, условия-то вполне понятны и 7-класснику
Если $n$ и элементы обеих матриц фиксированы, то я еще готов согласиться с Xaoscitect; но имеет ли эта задача смысл при фиксированном $n$? Но у Вас данные произвольны, и Вы говорите о "способе вычисления" для всех $n$ - т.е., надо думать, об алгоритме, понятие сложности которого выходит далеко за рамки школьной программы

Munin в сообщении #892079 писал(а):
Вот решение - нет
ну, решение пока никому не понятно; вся надежда на Linkey! :D

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 09:42 
Аватара пользователя


01/09/13

711
Извините, не осилил, да и лень разбираться.
У меня только есть общая идея. Предположим, нам надо сосчитать два числа:
$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 писал(а):
Это распространённый миф. Распространён он среди людей необразованных. Им приятно думать, что раз они не получили образования, то взамен получили какую-то другую выгоду: не лишились "способности мыслить нестандартно".


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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 09:59 
Заслуженный участник
Аватара пользователя


06/10/08
6313
Linkey в сообщении #892281 писал(а):
Я пробовал повторить этот же приём для вашей задачи при $n=2$, выписал все члены матрицы, которую нужно сосчитать, и не смог найти линейную комбинацию этих членов, для которой можно обойтись одной операцией умножение. Но, может быть, если $n=3$ или больше, такую комбинацию можно найти (хотя бы вместо трёх умножений обойтись двумя)?
Там таких нет. Для любого $n$ любая нетривиальная линейная комбинация $c_{ij}$ как билинейная форма от $a, b$ имеет ранг, кратный $n$, и поэтому не вычисляется меньше, чем за $n$ умножений.
Если бы Вы знали линейную алгебру, Вы могли бы до этого додуматься. Любое знание - это не ограничение, а полезный в каких-то случаях инструмент.

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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 10:02 
Заслуженный участник
Аватара пользователя


30/01/06
72408
Linkey в сообщении #892281 писал(а):
Я считаю, что образование способствует догматизму.

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 10:04 
Заслуженный участник
Аватара пользователя


06/10/08
6313
patzer2097 в сообщении #892086 писал(а):
но имеет ли эта задача смысл при фиксированном $n$?
Если говорить про количество умножений, то эта задача имеет смысл даже при $n=3$. Известная верхняя оценка - $\leqslant 22$, нижняя - $\geqslant 19$.

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 10:06 
Заслуженный участник
Аватара пользователя


30/01/06
72408
Xaositect в сообщении #892284 писал(а):
Любое знание - это не ограничение, а полезный в каких-то случаях инструмент.

+1.

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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 10:19 
Аватара пользователя


01/09/13

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


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

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 10:26 
Заслуженный участник
Аватара пользователя


06/10/08
6313
Linkey в сообщении #892293 писал(а):
Я полагаю для многих здесь не секрет, что атеисты гораздо чаще читают библию, чем верующие.
Лично я в этом сильно не уверен.

 Профиль  
                  
 
 Re: Форумы математиков
Сообщение01.08.2014, 10:27 
Аватара пользователя


01/09/13

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 38 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group