よりも小さい時間計算量 で行列積を計算するシュトラッセンのアルゴリズムとその導出方法を紹介します。 シュトラッセンのアルゴリズム の行列積 を考えます。 まず を $$ \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \begin{pmatrix…

ケイリーの公式の証明たちの紹介です。 ケイリーの公式とは ケイリーの公式とは 頂点のラベル付きの木の総数 が であるという公式のことです。 ここで、ラベル付きであるとは、それぞれの頂点を区別するということです。 たとえば のとき、頂点を区別しない…

時間計算量 <O(n), O(1)> の LCA(Lowest Common Ancestor) と RMQ(Range Minimum Query) を C++ で実装しました。 アルゴリズムの解説はDさんのスライド [1] LCA and RMQ ~簡潔もあるよ！~ がとても分かりやすいのでそちらを参照してください。 概要だけ説明します。 LCA</o(n),>…

IOI2017（イラン大会）に副団長として参加してきました。 ioi2017.org IOIの参加記は選手・役員の感想（まだ公開されていないようなのであとでリンクを張ります）に書いたのでそちらを参照してください。 第29回国際情報オリンピック イラン大会 速報 も面白…

ミラーラビン素数判定法について ミラーラビン素数判定法はフェルマーテストを拡張した感じです。 フェルマーテストでは が素数のとき、フェルマーの小定理より と が互いに素なとき となることを利用して、 と互いに素な整数 を取って であれば合成数と判断…

言語処理系で講義でクリーネの不動点定理をやった時にベルマンフォードの証明にも使えるなぁと思ったので紹介します。 クリーネの不動点定理 を完備半順序集合とし、 をその上のスコット連続写像とする。このとき、 は最小不動点を持つ。 ここで、完備半順序…

HashedNets [1] を chainer で実装しました。 HashedNets の説明 ニューラルネットワークのパラメータ数は非常に多く、パラメータは冗長な表現になっていることが多いです。 そこで、自由なパラメータの数を減らして、正則化と軽量化を達成するための手法の…