代数系とデータ構造 part1　～代数系のおさらい～

<注意>
本記事の内容はプログラミングの基礎知識を前提としたものです。一応代数系に関しては記事内にて解説をしますが、難易度については保証できません(なるべく簡単な説明を試みてみます)。また、各代数構造の解説は厳密なものではなく、誤りがある可能性もあるので注意してください。

いきなり注意書きから始まってしまい大変申し訳無いのですが、こんにちは、サイキです。

今回は代数系とデータ構造というタイトルの通り、各代数構造とプログラミングにおけるデータ構造との絡み合いについての解説記事となっています。連載記事なので、何部かにわけて投稿する予定ですが、もしかすると最終的には一つの記事にまとめるかもしれません。

読者の想定レベルとしましては、

ある程度プログラミングの知識がある(プログラミングの入門書一冊を読んだ程度、あるいはそれに準ずる授業を受けた程度で十分です)

これだけ満たしていれば、内容を理解できるように書いたつもりですが、最後の解説だけ行列の知識が必要となってくる部分があるので注意してください(他に良い案が思い浮かばなかったのです。本当にすみません……)

わかりやすく大阪市立大学電気情報工学科のカリキュラムに沿った説明を行うと、一回生前期の授業であるプログラミング言語を履修し終えたあたりの学生であれば理解できる内容だと考えています。もちろんこれは授業の理解が前提となっているので、理解度が浅い場合は読解が困難な箇所も考えられます。

また、同じく一回生前期の情報数学内で教わる代数系の範囲も理解していると、より一層読みやすくなるかと思います。

他の学部や学科がどのような授業を受けているのか知識がないので具体的なことは言えませんが、とにかく代数系の基礎知識(群とか環)があれば読むのが楽になると言うことです。

代数系のおさらい
終わりに

代数系のおさらい

今回の記事では今後のデータ構造の話をするにあたって大切な代数系のおさらい(あるいは、紹介)をします。初見の人には難しい内容かと思いますし、実際私も学習時には苦しみましたが、実は言っていることは単純なことばかりなので、落ち着いて学んでいきましょう。

マグマ

ある集合 $A$ とその上で定義された二項演算 $*$ の組 $(A,*)$ について、演算結果が常に閉じている時、この組はマグマであると言えます。

ここで、演算結果が閉じているとは、 $A$ のある二要素 $x,y$ について、その演算結果 $z=x*y$ が常に $z \in A$ であることを指します。

例えば、マグマの例としては $(\mathbb{R},+)$ や $(\mathbb{R}, \times)$ などがあげられます( $\mathbb{R}$ は実数全体の集合)

いずれの場合にしても、演算の結果は常に指定された集合の要素に含まれていることが直感的にわかると思うので、厳密な証明はここでは避けます。

逆にマグマでない例としては、 $(\mathbb{N},\div)$ があります( $\mathbb{N}$ は自然数全体の集合)。適当に2,3と言う数を取ってくると、これら2つは自然数に含まれていますが、 $\frac{2}{3}$ は自然数ではありません。これは閉じていないと言えるでしょう。

半群

$(A,*)$ がマグマであり、かつ

結合則： $x*(y*z)=(x*y)*z \ |\ x,y,z \in A$

が成り立つならば、それは半群であると言えます。もっと簡単に言うと、式中のどこから計算をはじめても結果は変わらないと言うことです。

これからはこのようにどんどんと条件が付け足されていきますが、制約の多い代数構造ほど使い勝手は良くなっていきます。

半群の例としては、先程も登場した $(\mathbb{R},+)$ があります。実際、足し算はどこから計算し始めても問題ないと小中学校で教わったと思います。

逆に半群でない例としては、 $(\mathbb{R},-)$ があります。例えば $5-3-2$ と言う計算を行う時に $3-2$ を先に計算してしまうと答えと合わなくなりますよね？これは結合則が成り立っていないからです。

モノイド(単位半群)

$(A,*)$ が半群であり、かつ $x \in A$ について

$e*x=x*e=x$

であるような元 $e \in A$ が存在する時、モノイドと言い、この元 $e$ を単位元と呼びます。

情報数学の授業では単位半群と習ったと思いますが、世間ではモノイドと言う呼び方の方が一般的なのでこちらを使います。

モノイドの例としては、 $(\mathbb{R},\times)$ があります。この場合、単位元 $e$ は1になりますね。実際、 $1 \times x=x \times 1=x$ であることがすぐにわかります。

逆にモノイドでない例としては、 $(\mathbb{R},min)$ があります。 $min$ は与えられた2要素のうち、小さい方を返却する演算です( $min(5,2)$ ならば2になります)。これに単位元を設定しようとすると、 $\mathbb{R}$ の中で最も大きな値をとってくる必要がありますが、そのような値は存在しないので単位元はありません。

群

$(A,*)$ がモノイドであり、かつ各 $x \in A$ に対して

$\overline{x}*x= x* \overline{x}=e$

となる $\overline{x} \in A$ が存在する時、群と言い、 $\overline{x}$ を $x$ の逆元と言います。ちなみに、この時 $\overline{x}$ の逆元は $x$ です。

群の例としては、 $(\mathbb{R},+)$ があります。なんか同じやつばっかり出してしまってすみません……

それはさておき、この時の逆元は、 $x \in \mathbb{R}$ に対して $-x$ と設定できます。これらの演算結果はいついかなる時でも0になりますよね？(ちなみにですが、ご察しの通りこの時の単位元は0です)

逆に群でないもの例としては、 $(\mathbb{R},\times)$ があります。 $x \in \mathbb{R}$ に対して $\frac{1}{x}$ を設定すれば良いのでは？と思う方もいるかも知れませんが、それだと $x=0$ の時にうれしくないことが起こります。なのでこれは群であるとは言えません。