2025-07-08

ライツアウトの数学的解法

数学

動機

ipotazero.github.io

このゲームを作ったとき、自力で解くのは面倒だから自動で解くアルゴリズムを作れないか考えた。

ipotazero.github.io

そして完成したので仕組みを解説する。

解法

m×n盤面について考える。

クリックした時ひっくり返る様は、 $\mathbb{F}_2$ 上の行列が足されているみたいに見える。

そこで盤面を、セルをクリックした時どこがひっくり返るかを表す行列の線形結合で表すことを考える。

何もない盤面から同じ盤面を作れれば、1+1=0だから何もない盤面に解決できる。

例：3×3盤面で左上と右下をクリックした時

$\begin{pmatrix}1&1&0\\1&1&0\\0&0&0\end{pmatrix}+\begin{pmatrix}0&0&0\\0&1&1\\0&1&1\end{pmatrix} =\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix}$

このままでは計算しづらいから、行列の代わりに盤面のセルに左上から右下まで0からmn-1まで連番を振りベクトルとしてみる。

例：

$\begin{pmatrix}1&1&0\\1&0&1\\0&1&1\end{pmatrix} \rightarrow \begin{pmatrix}1\\1\\0\\1\\0\\1\\0\\1\\1\end{pmatrix}$

盤面のどこがひっくり返っているかを表す $\mathbb{F}_2$ 上のベクトルを $b$ とする。（ひっくり返っているインデックスだけ1、他は0）

どこをクリックしたかを表す $\mathbb{F}_2$ 上のベクトルを $x$ とする。（クリックしたインデックスだけ1、他は0）

$i$ 番目のセルをクリックした時どこがひっくり返るかを表す $\mathbb{F}_2$ 上のベクトルを $a_i$ とする。

$A = \begin{pmatrix} a_0&\dots&a_{mn-1} \end{pmatrix}$ とする。

$Ax=b$

この方程式を満たすことが解である必要十分条件だ！

内部ではPA=LU分解をして特殊解と $\mathrm{Ker}A$ の基底を求めている。

余談

正方形にひっくり返すときはmとnが3k+2でない時にAが正則となる。

普通のライツアウトではひっくり返し方がグラフの隣接関係として表せる。

でも、別に「ひっくり返し方」であればなんでもいいので、クリックするということを忘れて、 $A$ をmn×k行列（k個のひっくり返し方）とすればなんでも解ける。（盤面が矩形やグラフである必要もない）

今回はひっくり返っているかいないかの2値で、周期的（1+1=0）だったけど、 $b$ の各成分が $\mathbb{Z}_n$ の時とか、周期的でない時とかはどうなるんだろう？

2025-03-17

新歓情報 2025

お知らせ

こんにちは、マイコン研究会の部長のうめぼしです。

入学式も近づいてきたので、今年の新歓情報についてまとめようと思います。

と、その前に……

このサークルについて

大阪公立大学杉本キャンパスのサークル、マイコン研究会、通称：MCRの活動内容について軽く説明します。

このサークルでは、主にゲーム制作をしています。そのほかにも、

プログラミング学習
ウェブサイト制作
DTM
イラスト
etc

に取り組んでいる人もいます。自分は作ったBGMをゲームに使って、それをウェブで公開したりしています。

なんにも知識がない、パソコンを初めて触る、という方でも大歓迎です。

割とゆるいサークルなので兼部、兼サーも可能です。

オープンチャットについて

マイコン研究会の今年の新歓用オープンチャットを作ったので、興味がある人はぜひ参加してください。匿名で入れます。

招待URL：オープンチャット「マイコン研究会　2025新歓」
https://line.me/ti/g2/OFrc2lxXMuC0VaWcgmDmlzktGzBRGMQvQM6PgQ?utm_source=invitation&utm_medium=link_copy&utm_campaign=default

新歓日程

新歓は複数回にわたって行う予定なので、興味がある人はどれかに来てください。

その1

3/26（水）　Zoom新歓

15:00にオープンチャットにZoomのリンクを貼るので、そこから入ってください。

内容はサークルの説明、履修登録について、大学生活についてなどを考えていますが、要望に応じて柔軟に色々できたらと思います。

1、2時間を予定しております。

その2

4/2（水）　対面新歓

カリキュラムオリエンテーションがあるので、その終了後に部室に来てください。

（学部ごとに終了時間がちがうため、いつ来てもらっても大丈夫です）

部室は第一合同部室二階、B16にあります。

場所がわからない人向けにオープンチャットで道筋を紹介しようと思います。

その3

4/7（月）　対面新歓

学生証交付と健康診断があり、その帰り道には新歓ロードがあります。

そこにマイコン研究会（MCR）の人たちが看板をもって勧誘しているので、その勧誘に乗ってください。

もしいなかった場合は部室まで来てください。

その4

4/12（土）、4/13（日）　第20回ふたば祭

848教室にて出展を行っていますので、ぜひ来てください。基本的にずっと開いてます。

内容としては今までマイコン研究会が制作したゲームを体験できます。

MCRゲームセンターという名前でやってます。

余裕があったらビラ配りも行っています。

その5

ふたば祭後の火曜と金曜　対面新歓

サークル活動日ですので、基本的に誰かいると思います。

放課後に部室まで来てください。（おそらく3限終了後ぐらいから居ると思います）

それ以外

オープンチャットやX（旧Twitter）のDM等であらかじめ連絡していただけると、上記以外の日程でも対応できる場合があります。

入部方法

基本的にはサークルのだれかに入部したい旨を直接伝えてください。

オープンチャット、X（旧Twitter）のDM等で連絡してもらっても構いません。

最後に

マイコン研究会のHPやX（旧Twitter）もぜひチェックしてください。

HP：https://ocumcr.github.io/mcr-homepage/#top

X：https://x.com/ocu_mcr

それではまた。

2025-02-08

ホームページ移転と最近のゲームたち

活動記録ＨＰ更新履歴ゲーム制作

どうも、こんにちは。

現在マイコン研究会の部長をしているうめぼしです。

はてなブログの更新が滞っていたので再開させようと思います。

前回の更新がほぼ一年前らしいですね。自分の下の代にはブログ更新の引継ぎをしっかりしようと思います。

ということで、最近の活動報告を書こうと思います。

まず、マイコンのホームページを移転しました：

ocumcr.github.io

もともと無料サーバーを借りてやっていたのですが更新の手間もあり、いろいろあってgithubPagesを使ったものとなりました。

ホームページはいくつか機能が増えたりしているのでついでに紹介します。

たとえばこれ：

ocumcr.github.io

最近MCRが作ったゲームにはメンバーが作った曲が使われていたりします。そんなわけで、MCRの人たちが作ったゲーム音楽が聴けるサイトを作りました。ぜひ鬼リピしてください。

次に、ホームページが新しくなってから出たゲームをどんどん紹介していこうと思います。

今から紹介するものはすべてURLから、PCのブラウザで遊ぶことができます。

その1

作品名：Pentamond

作者：うめぼし

URL：Pentamond

はい、ということで僕が作ったやつです。ペンタモンドと読みます。

見た目テトリスのような落ちものパズルですが、一列揃うと消えるわけではなく、頑張って特定の形を作り、その列をEnterで消去するゲームです。うまくいくと時間制限が増えたりスコアが増えたりします。

（地味にコントローラーでも遊べます）

上の画像は通常モードではなく別モードなのですが、友人にはこちらのほうが人気です。

そのうちローカル対戦ができるPentamond2（仮）が出るという噂もあります。

その2

作品名：20歳になる前に

作者：いぽた

URL：20歳になる前に

20歳ははたちと読むらしいです。いぽたさんが20歳になる前後に作られたやつですが本人曰くあまり関係ないとのこと。

選択肢はあるが基本的に一本道なノベルゲーです。いぽたさんの世界観が詰まった独特な雰囲気をもつ作品です。

全画面から戻るにはEscを押しましょう。

その3

作品名：Vector Space

作者：いぽた、うめぼし

URL：Vector Space

ベクタースペースと読みます。直訳は「ベクトル空間」（数学用語）ですが、ゲーム内容は誰でも遊べるのでご安心ください。

真ん中にある丸みたいなものを動かしたり、ジャンプさせたり、弾を撃ったりしてゴールまで進んでいく、2Dアクションゲームです。

慣性があるので、操作には少しクセがあります。

ゲームはいぽたさんが、音楽はうめぼしが作りました。

その4

作品名：まいんどすいーぱー

作者：いぽた、うめぼし

URL：Mind Sweeper

ノベル部分とマインスイーパー部分を交互に繰り返すゲームです。

ストーリー（？）はいぽたさんの世界観が反映されたものです。内容は暗めなのでプレイする際は注意してください。

（作者にうめぼしが載ってますが1曲作っただけです）

その5

作品名：もこたたき::NEO!

作者：いぽた

URL：もこたたき::NEO!

MCRの11年前のゲームをいぽたさんが勝手にリメイクしたものです。

内容としてはとてもシンプルで、MCRのマスコットである「もこた」を20秒間のうちにたくさんクリックするゲームです。

リメイク前とはそもそも内容が変わっているのはご愛嬌。

スマホ対応しているので、ぜひプレイしてみてください。

ここで紹介した作品はすべてホームページのWorksに載っていますので、他の作品も覗いて行ってください。（ダウンロードが必要なものもあります）

4月12日（土）、13日（日）にはふたば祭（大阪公立大学の文化祭）があります。マイコン研究会も出展予定です。

内容としては、作ったゲームの体験会、VRゲーム（有料）となっています。

先ほど紹介したゲーム以外にもたくさんあります。なかにはブログにもホームページにも載っていないものあり、ここでしか遊べないものもありますので、ぜひご来場ください。

ちなみに、大きめの新作ゲームが出るという噂もあります。

とりあえずのお知らせはこんなところでしょうか。

2025年も始まったので、今年もたくさん活動していきたいですね。

もうすぐ新歓ですので、それについての記事もそのうち書こうと思います。

それでは。

2024-04-24

MineCraft Educationでプログラミングで作品を作る

*これは2024年新歓イベントの資料です。

こんにちは。今回は、「MineCraft Education」というソフトを使い、マイクラの世界をプログラミングで改造していきたいと思います。今回作るのは以下の二つです。

・巨大レール

・ビル

ブロックを繋げていく形でプログラミングしていきます。日本語なので、初心者でも全然大丈夫だと思います。それではやっていきましょう！

①MineCraft Educationのインストール

Microsoft Storeで「MineCraft Education」をインストールして開いてください。

少なくとも現在は無料で使えるので、マイクラを購入していなくてもできます。

②Makecodeの使用

プログラミングはMineCraft Educationの中に入っている「MakeCode」というソフトを使ってしていきます。

ワールドを開いたら「C」キーを押した後、下のようなボタンをクリックしてみましょう。

そのあと、新しいプロジェクトをクリックしてプロジェクトを作成してください。

右のような画面が出てきたら成功です。

③ビルダーの使用

MakeCodeでブロックを置く方法は色々ありますが、個人的にビルダーが一番使いやすいので、ビルダーを使っていきます。

ビルダーは左のエリアの下の方にある高度なブロックをクリックすると出てきます。

左下の画像の「ビルダー」と書かれているピンク色のボタンをクリックしてください。

クリックすると右下の画像のようなものが出てくると思います。

見て大体察しが着くかもしれませんが、ビルダーは位置をもっていて、その位置を移動させてブロックを置くことで、建物を作っていきます。

また、これ以外にも繰り返しや条件分岐、変数、関数などを使っていきます。ビルダー以外にも、ほかにどんなブロックがあるかをしっかり確認しておいてください。その機能については、その都度理解していく感じで大丈夫です。

④レールをたくさん敷いていく

早速ですが、巨大レールを作っていきます。こんな感じでブロックを組んでいきましょう。くりかえしのブロックはくりかえしの所にあります。出来たら右下の画像のようなボタンをクリックして、実行できるようにしておきましょう。

出来たら、「Enter」キーを押して、下の画像のようにrunとクリックして、実行してみましょう。

こんな感じになるはずです。ざっくり説明いたしますと、

レッドストーンブロックを置く、レールを置くを繰り返しているだけですね。ここまでは難しくないと思います。

⑤関数を使って、もっとレールを敷く

関数を使って、もっと色々な方向にレールを敷いていきましょう。

関数→関数を作成を押すと、下のような画面が出てくると思います。

下と同じように、名前をレールにして、パラメーターとして数値とpositionを追加しましょう。これは、プログラミングにおいて引数と呼ばれます。

これができたら、下のようにブロックを組んで見てください。

関数はプログラムの箱であり、関数に入れたプログラムは何度でも実行できます。また、引数を追加することで、違う動作をさせることができます。

この例だと10回繰り返して、1, 0, -1ブロックだけ上に上がっています。

こんな感じになったでしょうか？

このように手で作るのが大変なものでもプログラムを使えば簡単に作れてしまいます

ここまで出来たら、もっといろいろ挑戦してみましょう。

チャレンジ

もっとたくさんレールを敷いてみる

こんな感じでレールを曲げたり、回転させたり遊んでみましょう！参考にプログラムを載せておきます。こんな感じで関数の引数を効率的に使えたらいいですね

また余裕があればこんな感じのビルなども簡単に作れてしまいます。

ぜひ作ってみてください！

このビルを作る際は、下のようなブロックで埋める機能を使えば便利ですよ！

まとめ

ここまで出来ましたでしょうか？

このようにプログラムを使えば大きなものでも一瞬で作れてしまうというメリットがあります。

このようにプログラムで形状を作成することは、プロシージャル生成と呼ばれ、良く使われているので調べてみてください！

2022-04-07

Github Copilotの挑戦

はじめに

新4回生の済木です。今回、個人的に使用申請を出していたGithub Copilotがいつの間にか使えるようになっていたので、これだけでどの程度プログラムが書けるのか簡単に試していこうと思います。本当は去年の11月ごろに使用許可が出ていたけど、つい最近まで気づかなかった。

Github Copilot って？

Github CopilotはGithubとOpenAIの提供するシステムで、人間の書いたコメントや関数名等に応じてその続きのプログラムを提案してくれるものです。例えば、「入力された数値が素数かどうか判定する」といったコメントを記述すると、以下のようにその続きに予想されるプログラムが出力されます。(Github Copilotの予想部分は灰色っぽい文字になっている)

f:id:ocumcr:20220407175502p:plain

上図ではboolまで入力していますが、この程度のプログラムであればほとんど人間が頭を使うこと無く記述できるようになっています。

注意として、結局のところGithub Copilotの予想が正しいのかどうかを確認できるのは人間なので、これを使えば誰でもプログラミングができるようになる！といったものではありません。あくまでCopilot(副操縦士)というわけです。

実践

条件

人間は、関数やクラスの内容をコメントとして日本語及び英語で記述できる。
人間は、関数の返り値の型を記述できる。
人間は、関数の引数を記述できる。
人間は、関数やクラスの名前を記述できる。
人間は、状況に応じて(グローバル、ローカル、メンバ)変数を追加することができる。
人間は、状況に応じて(通常の、あるいはメンバ)関数を追加することができる。ただし、その内容を直接書くことはできない。
人間は、状況に応じてクラスを追加することができる。ただし、その内容を直接書くことはできない。
人間は、状況に応じて適切に開き括弧、閉じ括弧を記述できる。
人間は、状況に応じてヘッダファイルをincludeできる。
using namespace std; は記述されているものとする。

①2次元のベクトルを扱うクラスを作る

まず、2次元のベクトルを扱うクラスを作成してみます。

コメント、クラス名、波括弧を入力すると以下のように予想が出力されました。

f:id:ocumcr:20220407181017j:plain

f:id:ocumcr:20220407181020j:plain

お気づきの方もいられるかと思いますが、メンバ変数が宣言されていないためこのままだとプログラムは動きません(おっちょこちょいかな？かわいいね)。privateにメンバ変数を追加してあげましょう。

f:id:ocumcr:20220407181447p:plain

？？？？？？？？？？？？？？？？

メンバ関数で利用している変数名はx_, y_なのに、こっちだとアンダーバーの抜けた変数名が提案されています。いきなりやらかしの多いCopilot君ですが、まぁこのくらいであれば人間の手で簡単に修正できるので問題なしとしましょう。

②AtCoder Beginner ContestのA問題を解いてみる

次に、AtCoder Beginer Contest(ABC)のA問題を解かせてみます。ABCはAtCoder社の開催する競技プログラミングのコンテストの中でもっとも初心者向けであり、その中でもA問題は(保証はされていませんが)1番簡単な問題という位置付けになっています。

今回は、ABC 246のA問題Four Pointsの問題文をコメントとして入力することで、どの程度正解に近いコードが出力されるのかを検証してみます。

入力はコメント、main関数の名前です。

f:id:ocumcr:20220407191353p:plain

一見きちんとプログラムが書けているように見えますが、おそらく間違った出力をしてしまいます。とりあえず、iostreamを用意していなかったのでincludeしてから提出してみましたが、結果は案の定WAでした。

上の問題では出力の内容こそ間違っていたものの、入出力の形式を指定していないにも関わらずうまく予想できていたことには可能性を感じます。何かもう1つ問題を解かせてみましょう。

次に試してみるのは、ABC 245のA問題Good morningです。前と同様に問題文をコメントとして入力して、それに対する反応を見ます。結果は以下のようになりました。

f:id:ocumcr:20220407192339p:plain

今回も入出力の形式は守られていましたが、提出してみた結果はWAでした。よく見てみると、プログラム中の条件文が若干間違っています。正しくは、 $b\lt d$ ではなく $b \leq d$ になるはずです。実際、そのように修正してから提出してみるとACが取れました。

今回は2つの問題についてGithub Copilotを用いて解答を作成していましたが、いずれも正解にはなりませんでした。ただ、両方入出力の部分は正しく書けており、2問目に関してはほとんど正解のプログラムを出力することに成功していました。

不正解のプログラムを出力してしまった原因としては、コメントが日本語であったこと、コメントによる説明が不足していたこと、そもそもGithub Copilotの学習がまだ十分でないことが考えられます。

③何かゲームを作ってみる

最後に、Github Copilotを用いて何かしらのゲームを作成してみます。

ひとまず、ライフゲームでも出力させてみましょう。クラス名を定義すると、以下のように予想を吐き出しました。

f:id:ocumcr:20220407194228p:plain

相変わらずメンバ変数を用意してくれないみたいです。とりあえずここで用意されたメンバ関数の定義を続けて予測させます。

f:id:ocumcr:20220407194401p:plain

f:id:ocumcr:20220407194553p:plain

f:id:ocumcr:20220407194500p:plain

f:id:ocumcr:20220407194622p:plain

f:id:ocumcr:20220407194717p:plain

f:id:ocumcr:20220407194743p:plain

f:id:ocumcr:20220407194809p:plain

f:id:ocumcr:20220407194842p:plain

f:id:ocumcr:20220407194858p:plain

f:id:ocumcr:20220407194928p:plain

ひとまず、メンバ関数とメイン関数については以上です。

ところで、private領域にメンバ変数を用意しようとすると以下のように地獄みたいなことになってしまいました。

f:id:ocumcr:20220407195309p:plain

仕方がないので変数は手入力しました。このくらいであれば人間が頭を使っているとは言えないので大丈夫でしょう。

f:id:ocumcr:20220407200522p:plain

さて、最後にコンパイルして実行してみます。コンパイラはg++(GCC)のversion10.2.0です。

適当に入力を入れた結果、以下のようになりました。

f:id:ocumcr:20220407200940p:plain

見辛い！！！！！

まったく改行やステップ数が書かれていないため、どこが区切りなのかわかりません。さすがにわかりにくいので、手入力で改行を追加しました。また、入力が単純すぎてつまらなかったので、少し複雑にしてやり直してみました。その結果が以下の画像です。

f:id:ocumcr:20220407201413p:plain

ライフゲームのルールはいくつかありますが、update関数の条件を見るとこのプログラムにおいては以下の3つのルールで動作しているようです。

生きているセルの周囲9マス(自身を含める)に生きているセルが2つか3つあれば生存
死んでいるセルの周囲9マスに生きているセルが3つあれば誕生
それ以外は死滅

確かに、プログラムで出力された結果はその通りになっているのではないでしょうか？これはGithub Copilotの勝利と言っても過言ではないでしょう。

総評

Github Copilotにいくつかの挑戦をしてもらいましたが。頻繁に記述されるような小プログラムに関してはある程度任せられるかな、といった感想です。

例えば2次元ベクトルの例でも、メンバ変数の名前がおかしいといった不満点はあるものの、その程度であれば人間が必要なものを追記できるはずです。ある程度人間の側がサポートすることを踏まえれば、すでにお遊びを超えて実用的なツールと化していると言えるでしょう。

また、適当なタイミングで予測をさせることで、「なるほど！たしかにこんな関数があればよさそうだな」とプログラマを刺激させる効果も期待できそうです。

まだまだ進化の余地はありますが、活用次第ではプログラミングの質を上げるツールとして十分期待できるでしょう。

ただし最初の方にも書きましたが、これはあくまで補助的なツールであり、完全に任せることはできません。また、予想されたプログラムが本当に正しく動作するのかどうかは、結局人間が判断しなくてはいけません。Github Copilotを活用するためには、最低限同レベルのプログラムを人間が記述できる必要がありそうです。

2021-09-11

市大の成績発表は遅すぎる！少しだけはやく成績を知る方法

　毎度毎度他大と比べて成績発表が異常に遅い当大学ですが、この時期になると各方面から今期の成績はどうかと心配する声が聞こえてきます。そんな成績ですが、実は正式な発表以前に知る方法があるのです。

　ただし、ここで紹介する方法は正式な成績を確認する方法ではないので、その信憑性は保証されたものではありませんためあしからず。

OCU指標って何？

　いきなりですが、市大にはいわゆる評定平均的なGPAの他に、6つの分野における学習具合を示したOCU指標と呼ばれるものがあり、UNIPAで確認することができます。6つの分野とは具体的に以下の通りです。

論理的思考
情報活用
外国言語・文化
表現
社会貢献
各学部独自

　これらの分野の学習具合がレーダーチャートで表され、今までに受けた授業のバランスがどのようになっているのかを確認することができます。次の履修で何を取るとバランスの良い教養が得られるか、と言ったことがわかるようになっているわけです。

　さて、このOCU指標ですが、その値の計算にはなんと各授業の成績が使われています。また、OCU指標は成績発表の数日前にしれっと公開されるので、これから逆算することで自分の成績を発表の前に割り出すことができるのです！(2021/9/11現在の情報です)

OCU指標の計算方法

　さて、OCU指標の計算方法ですが、実は公表されています。*1

　おおざっぱに説明すると、以下のとおりです。

授業ごとに12のポイントが与えられ、これを各分野に振り分けている。(このポイントがその授業における分野ごとの重みになる)
成績が決まると、 $(重み\times \mathrm{GP}) / 12$ で各分野の指標が計算される。

　例えば、ある授業において社会貢献に3ポイント割り振られていた場合、その指標は成績がAAの時1、Aの時0.75(表示は0.8)、Bの時0.5……といった感じになります。

　よって、成績がAAの場合、その授業のOCU指標の和が4になることがわかります。

OCU指標の確認方法、すなわち成績確認

　すでに書いたように、OCU指標はUNIPAより確認できます。UNIPAの上の方にある一覧からOCU指標をクリックして確認画面に遷移しましょう。

f:id:ocumcr:20210911013229p:plain

　さらに、表示単位、年度学期を適切に変更し、以下のように科目ナンバーの上7桁を指定します。

f:id:ocumcr:20210911013312j:plain

　科目ナンバーはUNIPAのシラバス参照から確認することができます。実際には8桁以上あるものが大半(と言うか全部？)ですが、OCU指標の確認画面で指定できるのは7桁までです。そのため、上7桁が被っている授業があった場合はそれらの指標が加算されて表示されるため注意してください。(解消方法は模索中)

　入力項目が大量にありますが、それぞれの行で独立しているため、異なる行に8桁目以降を入力してもうまく動作しません。

　さて、科目ナンバーの入力を終えて表示ボタンを押すと、いよいよOCU指標を確認することができます。

f:id:ocumcr:20210911014243p:plain

　各項目の頂点(チョボになっている部分)にマウスを持っていくとその分野の値が表示されるので、それらを合計することで成績を確認することができます。

　ちなみに、表示される値はおそらく小数2桁目を四捨五入したものなので若干の誤差がありますが、おおよそGPに近い値になるはずです。

おわりに

　改めて書きますが、当記事で紹介した方法は成績を確認するための正式な手順を踏んでいないため、都市伝説に毛が生えた程度のものです。あくまで気休めとして参考程度に利用してください。(あと内容が間違っている可能性もあるので注意してね)

*1:https://www.econ.osaka-cu.ac.jp/wp-content/uploads/2019/08/econ_ocu.pdf (2021/09/11 確認)

2020-05-17

代数系とデータ構造 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$ の時にうれしくないことが起こります。なのでこれは群であるとは言えません。