November 2016

S M T W T F S
  1 2345
6789101112
13141516171819
20212223 242526
27282930   

Style Credit

Expand Cut Tags

No cut tags
avysk: (Default)
Friday, September 12th, 2014 10:44 am
tl;dr опять про математику

А знаете ли вы, что неизвестно, какое минимальное количество умножений нужно совершить для того, чтобы умножить две матрицы 3x3? В 1976 году был придуман алгоритм с 23 умножениями. Позволю себе процитировать часть статьи:

The algorithm in this paper was produced by finding an integer solution to the following system of 729 nonlinear algebraic equations involving 621 unknowns

[...]

No use of computers was made in solving this system of equations.
Через 35 лет был придуман другой алгоритм с 23 умножениями. Алгоритма с 22 умножениями (как и доказательства того, что его не существует), насколько мне известно, нет.

Для матриц 2x2 нужно 7 умножений; есть и алгоритм, и доказательство.
avysk: (Default)
Friday, September 12th, 2014 10:29 am
tl;dr про математику

Знаете ли вы, что такое Frankl's conjecture, оно же Union-closed sets conjecture? Я тут узнал и впечатлен.

Удивительная гипотеза: для любого конечного набора конечных множеств (за исключением набора, состоящего только из пустого множества), замкнутого относительно объединения, есть элемент, принадлежащий как минимум половине множеств набора.

Ещё более удивительный факт: эта гипотеза была сформулирована в 1979 году, и до сих пор нет ни доказательства, ни контрпримера.

Согласно википедии, прогресс более чем скромный: доказана верность гипотезы в одном из следующих случаев:
  • В наборе не более 46 множеств
  • Объединение всех множеств набора содержит не более 11 элементов
  • В наборе есть наименьшее множество из одного или двух элементов.
Я придумал штук десять почти доказательств, каждое из которых упиралось в какую-то маленькую "очевидную" деталь.

avysk: (dwarf)
Saturday, February 1st, 2014 09:52 am
“Physicists do not always clearly distinguish between a matrix Lie group and its (real) Lie algebra, or between a real Lie algebra and its complexification. Thus, for example, some references in the physics literature to SU(2) actually refer to the complexified Lie algebra, sl(2;C).”

Да, действительно, какая разница -- унитарные матрицы с определителем 1, или что угодно, лишь бы след был 0.

Хорошо, что я не физик. “I'm really awfully glad I'm a Beta, because I don't work so hard.”
avysk: (Default)
Wednesday, January 23rd, 2013 09:02 am
Нашёл чудесное в книжке, которую собирался прочитать уже много лет, и, наконец, вчера начал.


И всероссийский обыватель, попадая в Финляндию, чувствует себя не дома, здесь он - всегда в гостях. Он старается идти по улице не толкаясь, он приобретает неожиданно вежливый тон и даже извозчику говорит "вы". Он торопливо опускает пять пенни в кружку, висящую в входной двери в трамвай, опасаясь презрительно безмолвного напоминания кондуктора - встряхивания кружкой перед забывчивым пассажиром. Чистота уличных уборных его ошеломляет, и он входит в их матовые стеклянные двери, как в часовню, - молча и благоговейно. Он деликатно оставляет недоеденный бутерброд за столом вокзального буфета, где за марку можно нажрать на все пять марок. Всероссийский обыватель ходит по улицам Гельсингфорса, умиляясь сам себе и восторгаясь заграничной культурой, тихий, как на похоронах, и радостный, как именинник...

Но истинно-русский человек не может быть долго трезвым на собственных именинах: он робко напивается в ресторане, и вино разжигает в нем патриотическое самолюбие. Чья страна? Финская? Что это за финская страна? Чухляндия! Провинция матушки России! Кто здесь хозяин?.. Российский обыватель вспоминает фельетоны Меньшикова в "Новом времени", где ясно доказывается, что Россия погибнет от финнов, поляков и жидов. Тогда он хлопает кулаком по столу. Шведы и финны брезгливо оглядываются. Потом появляются полицейские в черных сюртуках и молча выводят его в автомобиль, - даже не дерутся. В полицейском управлении точно и быстро называют сумму штрафа; она крупна так, что веселье и удаль спадают. С этого дня российский обыватель начинает отвечать чухнам их же ненавистью, перестает умиляться порядком и теряет всякий вкус к газовым плитам, дешевым прокатным автомобилям и автоматическим выключателям на лестницах, включающим свет ровно на столько времени, сколько нужно трезвому человеку, чтобы подняться на самый верхний этаж. Он живет в Гельсингфорсе напуганно, скучно, без размаха. Скучная страна Финляндия!