結合則

有限文字列と無限文字列からなるモノイド を で生成された自由モノイドとします。演算子を とします。 の元を文字、 の元を有限の長さの文字列とみなします。 の積は 、 のとき を と包含写像からなる射影系による射影的極限とします。この元を無限の長さの文字列とみまします。 と の積 を定義することができます。、 のとき とおくと はモノイドになります。演算子を とします。、 を と同一視し、 の単位元を の単位元と同一視することによって、 は演算子 に関してモノイドになります。前回の議論のためには がモノイドである必要はなく、有限文字列と無限文字列の積が自然に定義できれば良いのですが、「積が定義さ…

Simple Description 行列演算 スカラー倍 和 積 行列の関係 転置行列 単位行列 逆行列 随伴行列 ベクトル内積 行列式 余因子 余因子展開 2次正方行列の行列式 3次正方行列の行列式 ベクトル外積 逆行列 固有値 固有値方程式 エルミート行列の固有値 エルミート行列の固有ベクトル 固有方程式 対角化 ユニタリ行列 行列の指数関数 回転行列 Basic Problems 行列の指数関数 Standard Problems 行列の指数関数 Simple Description 行列演算 スカラー倍 $$\alpha[a _ {ij}]=[\alpha a _ {ij}]$$ 和…

遅延セグメント木（Lazy Segment Tree）の使い方を解説します。 セグメント木とは セグメント木（以下、セグ木）とは、二分木を作り、各ノード（頂点）に区間の情報を与えることで、区間クエリに で答えることができるデータ構造です。セグ木にはモノイドが乗ります。モノイドとは、以下の性質を満たす「集合Sと二項演算Fの組」です。 1. Fについて閉じている Sの元と元でFをしたとき、その返り値がSの元である。 2. 結合則を満たす 例えば、Sの元s1、s2、s3について、F(F(s1, s2), s3) == F(s1, F(s2, s3))が成り立つ。 つまり、順番はそのままにしてどこから…

Google の NotebookLM に Wikipedia の多元数に関する記事を読ませてみました。

先に結論を書きます。 円を中心が (x, y) 半径 r で軸並行矩形の中心が (cx, cy) 横幅が w 縦幅が h とすると、 bool HitTestCircle2AABB(float x, float y, float r, float cx, float cy, float h, float w) { float dx = std::max(0.f, std::abs(x - cx) - w); float dy = std::max(0.f, std::abs(y - cy) - h); return dx * dx + dy * dy <= r * r; } 導出 アイデア1 …

TL;DR SegmentTreeはモノイドが扱えるデータ構造だという理解をしていたが、モノイドではなく半群を扱えるデータ構造だと理解した方が良いのではないかと考えている。 前提知識 半群とモノイドについて まず半群とモノイドについて整理する。 半群 結合法則を満たす群構造のことを半群と呼ぶ。結合法則とは、任意の群の要素、、について が成立することを言う。 モノイド 結合法則を満たしかつ単位元が存在する群構造のことをモノイドと呼ぶ。ある群の要素とは単位元であるとは、任意の群の要素について が成立することを言う。 すなわち、モノイドと半群の違いは単位元が存在するかどうかである。 SegmentT…