カテゴリー: データ構造

2-factor theorem と言われる定理を証明します。

Reinhard Diestelのグラフ理論を読み…

永続セグメント木・永続遅延セグメント木のアルゴリズムを解説する。

原始根についてアルゴリズムの観点から解説する。

この記事では部分永続配列（fat nodes）と全永続配列（永続 m 分木を流用）を解説する。永続配列を使うと、いくつものデータ構造が機械的に永続化できる。

理論的に最良な最悪計算量 \(O(\log(n)/\log(\log(n)))\) を実現する Union Find を紹介する。

全永続 Queue の一種である銀行家の Queue（Banker’s queue）を解説する。

最大独立集合問題を解くアルゴリズムを解説する。この問題は NP困難であることが知られており、多項式の計算量で解くことはできない。しかし、指数の底を改善することで速度を大幅に向上することができる。

この記事では辺空間の部分空間であるサイクル空間、カット空間の基底について解説する。

形式的冪級数を \(\sum a_n\frac{x^n}{n!}\) の形で取ると意味のある畳込みが計算できてなぜか上手くいくことがある。この指数型母関数と呼ばれる形で上手くいくのはどんな場合か、またその性質を積極的に利用して考察に生かせないのか。解説しよう。