群論ワード
「このデータ構造にはこれが乗る!」で出る群論ワードを、メモ程度にまとめてみる
下に行くほど条件が厳しい
モノイド : かなり最小限なやつ。min, maxあたりがこれ。たぶんAND, ORもここ
結合法則 : $ a * (b * c) = (a * b) * c
単位元 : $ \exist 1\colon a*1 = 1*a = a
アーベル群 : いわゆる 和&差 もしくは 積&商 ができるやつ。たぶんXORはここ
結合法則・単位元
逆元 : $ \forall a, \exist a^{-1} \colon a * a^{-1} = a^{-1} * a = 0
交換法則 : $ a * b = b * a
半環 : 和&積 ができるやつ。行列のかけ算ができるような中身の条件 問題例1 問題例2 加法はモノイド+可換、乗法はモノイド
引き算・わり算はできなくてもいい
かけ算は交換できなかくてもいい
分配法則 : $ a*(b+c) = (a*b) + (a*c), \quad (a+b)*c = (a*c) + (b*c)
「加法の単位元」で乗算するとみんな「加法の単位元」になる
整数周りだと$ (+,*) : (\min, \max), (\min, +), (\text{OR}, \text{AND}), (\text{XOR}, \text{AND}) など
環 : 和&差&積 ができるやつ。任意modとか正方行列とか整数とか
加法はアーベル群、乗法はモノイド
つまり、かけ算が交換できなかったり、わり算ができなかったりしてもいい
分配法則 : $ a*(b+c) = (a*b) + (a*c), \quad (a+b)*c = (a*c) + (b*c)
※半環の最後の条件は自動的に満たされる
体 : 和&差&積&商 ができるやつ。有理数とか素数modとか
環の条件に加えて、乗法の交換法則と、加法の単位元以外なら乗法の逆元が存在する
あとは見かけたら加筆する