Расскажите мне

СЯУ, что алгоритмы разбора контекстно-свободных языков глубоко связаны с алгоритмами перемножения матриц. В частности, существует следующее взаимно-однозначное соответствие:
- Из любого алгоритма разбора контекстно-свободных с ассимптотической сложностью O(f(n)·|G|) можно сделать алгоритм умножения матриц с асимптотической сложностью O(f(n)).
- Существует CYK-алгоритм (разбора контекстно-свободных языков), пользующийся в своих недрах перемножением битовых матриц. Если использовать алгоритм умножения сложности O(f(n)), получится алгоритм разбора сложности O(f(n)·|G|).

(* |G| "размер" грамматики, n = размер стороны матрицы/длина разбираемого текста.)

У самого обычного алгоритма перемножения матриц сложность O(n³), у самого обычного CYK-разбора O(n³·|G|). Однако в последине годы существует активная движуха вокруг степени 3: ещё в 1987-1990 году был предложен (абсолютно не пригодный на практике, но тем не менее чрезвычайно остроумный и интересный теоретически) алгоритм Копперсмита—Винограда, уменьшающий 3 до 2.3755. В последние четыре года новые работы последовательно снизили показатель степени сперва до 2.3727, а затем до 2.373, а в 2014 году до 2.3728642. Существуют две распространённые гипотезы, по поводу оптимального алгоритма: одна о том, что существуют алгоритмы с показателем сколь угодно близким к двойке, одна о том что существует алгоритм ровно O(n²) сложности. Статья "Group-theoretic Algorithms for Matrix Multiplication" (Cohn, Kleinberg, Szegedy, Umans) связывает последнюю гипотезу с двумя другими разумными гипотезами в комбинаторике и теории групп соответственно.

Может мне кто-нибудь рассказать какова глубинная связь между линейной алгеброй и контекстно-свободными языками, и можно ли подковёрную связь с теорией групп как-то понять на уровне контекстно-свободных языков?

Знаменательный день

Сегодня кажется починили баг в Пульсаудио, на который я подписался в 2009 году, когда ещё пользовался десктопным убунту. Всего-то пять лет. ;-)

Мы в будущем

В прошлую субботу я щупал планшеты. И в том числе планшет 12.2" (как раз книжка Medium octavo влезает), к которому опционально коннектится добротная клавиатура, в которую он крепко и хорошо ставится. Так вот, этот планшет при соответствующем софте ничем не будет уступать моему Макбуку. Ну разве что только на коленях не так удобно стоит, но это дело наживное. И стило там есть удобное, которым можно на экране писать как ручкой, причём оно ещё и нажим отлично контроллирует, можно каллиграфией заниматься. И задник у того планшета из приятной на ощупь кожи молодого дермантина. Мы в будущем. Конвертиблы таки не нужны, достаточно планшетов с такой вот штукой для наколенной/настольной работы. Ноутбуки вымрут как динозавры, рабочие станции останутся только для профессионального использования, десктопы-то уже и так почти вымерли в пользу внешних мониторов к ноутбукам.

Это нормально, но я боюсь, что при этой трансформации пользователей могут успеть отучить от концепции файлов и вообще подконтрольных пользователю данных. Крупный бизнес и власти об этом только и мечтают, т.к. хранение в клауде и отстутсвие экспорта в открытые форматы это для бизнеса идеальный vendor lock-in, а для властей идеальный механизм контроля, а власти-то на то и власти, чтобы желать контроллировать и управлять. См. sorhed/594784.

И, да, наконец-то есть часы в качестве приблуды к мобильнику, именно такие как я писал ещё в 2004 году. Десять лет.