Python で書く代数 - pyarith よ, 私は帰ってきた

1年ぶりの pyarith の記事です. 実は Python で書く代数 を書いてから, 追加した実装があるのでそれについて書きます.

書いてあること

  • pyarith のおさらい
  • 環について
  • 環の公理とテストケースの対応

おさらい

pyarith とは Python でどこまで代数的対象が表現できるかの実験ライブラリです. Python コードは読めるけど代数学のことは知らない人に, 代数的概念を説明することを目的としています. 今のところライブラリとしての実用性は目指していません. おそらくパフォーマンスも出ません.

前々回の記事 で「群」の解説をし, 前回の記事 で群であることを確かめるテストについて解説しました. このテストでは pytest というライブラリを使用し, パラメータ化されたテストを行いました.

この記事を書いたおかげで pytest に興味を持ってくれた人もいたようで, ちょっと嬉しいです.

前回扱ったのは「群」という概念でしたが, 今回は「環」を取り上げます.

群はある規則を満たす集合でした. 環は, 群にさらに満たすべき規則を追加した集合です.

群と環にどんな差分があるかは環を実装した Ring クラスの実装を見てみましょう. https://bitbucket.org/cocoatomo/pyarith/src/dfbb010c50390e5dece00b92558a5c3461199507/tests/test_ring.py ここから分かるのは「環は群に無い __mul__ というメソッドを持つ」ということです.

この Ring クラスと __mul__ というメソッドに課せられた制限はテストケースで表すのでした.

テストケースとその意味
test_mul_welldefined_right 右からの乗算が well-defined であること
test_mul_welldefined_left 左からの乗算が well-defined であること
test_ONE (乗法に関する) 単位元の存在
test_mul_ONE 単位元の性質
test_mul_associative_law 乗法の結合律

乗法は可換とは限らない演算なので, 可換性に関するテストはありません.

また加算と乗算が両方登場する性質を表すテストケースとして以下のものがあります.

テストケースとその意味 (2)
test_distributing_law 分配法則

小学生の頃に分配法則という言葉が出てきましたが, 当時はここまで重要な性質だとは思いませんでした.

環の公理一覧については http://ja.wikipedia.org/wiki/%E7%92%B0_(%E6%95%B0%E5%AD%A6) を参照してください.

ライツアウトを代数的に見る (1)

みなさん, ライツアウトというゲームは知ってますか? 少し前に流行ったので知ってる人も多いでしょう. 4×4のマス目にボタンが配置されていて, ゲームの初期状態ではいくつかは光っています.

光ってるボタン:

光っていないボタン:

初期状態:

■ □ □ ■
■ ■ □ □
□ ■ ■ ■
□ □ □ □

ここで真ん中のボタンを1つ押すと次のように光り方が変化します.

□ □ □
□ □ □
□ □ □
↓
□ ■ □
■ ■ ■
□ ■ □

■ ■ □
■ ■ □
□ □ □
↓
■ □ □
□ □ ■
□ ■ □

このゲームのゴールは全てのボタンを光らせることです. (全てのボタンの光を消す, というのも考えられますが, 問題としては同じなので光る方を選びました.)

問題になるのは,

  • 初期状態だけを見てこのゲームはクリアできるのか?
  • 任意の初期状態に対してクリアする方法があるのか?

といったところです. これを数学的に扱っていきます.

Licenses