『「異様に難しいドラクエの謎解き」をモデル検査器で解く』代わりに数学で解く

前置き

タイトルは本歌取りもいい加減にしろ, という長さですが. こんなつぶやきをしたので, 予告どおり記事を書きます.

酒井さんの続きの記事 → http://msakai.jp/d/?date=20130402#p01

解説

まず方針としては酒井さんと同じく連立方程式を解きます. 酒井さんはモデル検査を用いて解いていますが, 私は数学で解きます. 一応, 数学を学んできた身としては, 数学で解けるものは数学で解きたいものです. (酒井さんも同じようなお考えなのかもしれません) 数学を使って厳密に解いてしまえば, この解が最適解かどうか考えるのも楽になります. 手法による違いを楽しんでいただけたら, と思います.

まず最初に立式する連立方程式は同じです.

$$ \begin{aligned} x_1 + x_2 + x_3 + a_1 &\equiv b_1\ (\bmod 4) \\ x_2 + x_3 + x_4 + a_2 &\equiv b_2\ (\bmod 4) \\ x_1 + x_3 + x_4 + a_3 &\equiv b_3\ (\bmod 4) \\ x_1 + x_2 + x_4 + a_4 &\equiv b_4\ (\bmod 4) \end{aligned} $$

4 次元の縦ベクトル \(\mathbf{a}\) は 4 つの銅像の初期状態, \(\mathbf{b}\) は終了状態を表します. 各要素は内側を向いている状態を 0 として, 右回りに 90 度回るごとに 1 増えるとします.

与えられた \(\mathbf{a}\) に対し \(\mathbf{b} \equiv 0\) の条件で \(\mathbf{x}\) について解くのですが, ここでおもむろに行列を持ち出します.

$$ \begin{aligned} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} + \begin{pmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{pmatrix} \equiv \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{aligned} $$

こうして

$$ \begin{aligned} \begin{pmatrix} 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} \equiv \begin{pmatrix} - a_1 \\ - a_2 \\ - a_3 \\ - a_4 \end{pmatrix} \end{aligned} $$

こうして

$$ \begin{aligned} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} \equiv \begin{pmatrix} 1 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 1 & 2 \\ 2 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{pmatrix} \end{aligned ...

Python で書く代数 - pytest で test class 編

前回 は pytest を使ってパラメータ化されたテストを実行しました.

実際に使ったテスト対象コードは, 群を Python で実装したコードでした. ABC モジュールと pytest によるテストを使って, 代数の公理的な定義を擬似的に表現しました.

ただし前回のテストコードではテスト関数が多く, 分類したい気持ちになってきます.

pytest のドキュメント を眺めると, 2.4.5 Parametrizing test methods through per-class configuration にクラスを使ってテスト関数をまとめる方法が書いてあります. 早速これを使います.

test hook

ここで使用するのはテストの前に実行される pytest_generate_tests 関数です. この関数でテスト実行前に, モジュールの中にあるクラスとそのメソッドからパラメータ化されたテストを生成しています.

def pytest_generate_tests(metafunc):
    """Collect and parameterize classes in this module as test cases.

    This test-case collecting function ignores module level functions.

    c.f. 2.4.5 Parametrizing test methods through per-class configuration
    """

    if metafunc.cls is None: # ignore module level functions
        return
    funcarglist = metafunc.cls.params[metafunc.function.__name__]
    argnames = list(funcarglist[0])
    metafunc.parametrize(argnames, [[funcargs[name] for name in argnames]
                                    for funcargs in funcarglist])

テストクラスには, テストコードを記述した関数をメソッドとして記述します.

class TestEquality:
    params = {
        'test_equals_reflexive_law': single_params,
        'test_equals_symmetric_law': double_params,
        'test_equals_transitive_law': triple_params
        }

    def test_equals_reflexive_law(self, a):
        assert a == a

    def test_equals_symmetric_law(self, a, b):
        if a == b:
            assert b == a

    def test_equals_transitive_law(self, a, b, c):
        if a == b and b == c:
            assert a == c

パラメータ化されたテストを実装するためにテストクラスには仕掛けが施されています. その仕掛けは params というクラスフィールドで, テストメソッドとそれが使用するパラメータの対応付けが辞書で設定されています. params 辞書の値は辞書のリストになっていて, 個々のテストケースが列挙されています.

single_params = [{'a': a} for a
                 in integer_values +
                 rational_values +
                 intint_values]

(ここでは single_params の書き方だけを載せましたが, モジュール全体は BitBucket のレポジトリ を参照してください)

前回の pytest.mark.parametrize デコレータとはパラメータ値の指定の方法が異るので注意してください.

pytest_generate_tests やその引数 metafunc の裏側については, また調べてブログに書くことにします.

それでは.

スタート代数 #3

報告

数学の勉強会をしてきました.

http://partake.in/events/1009ce0b-a3ca-448e-bd83-8819bc6b1326

テキストは↓これです.

今回はテキストの「1.3 分解体」のところを扱いました.

ガロア理論はこの分解体の感覚が付くとだいぶ後が楽になるので, 丁寧に解説や指摘を入れました.

準備のポイント

数学のゼミの準備をするときは,

  • その命題, 定理が何を言っているかを, 自分の言葉で説明できるまで考える
  • 具体例を挙げる
  • 仮定の条件を1つ外したり, 別のものに変えたりして, 結論が成り立つか調べる
  • 成り立たない場合は反例を作る (それが条件が必要である根拠となる)

というあたりに気を付けて, 準備すると良いです. これをやっておくと単なるテキストの朗読ではなく自分の言葉で説明できますし, 講師役の人に突っ込まれてもすぐ答えられるようになっているはずです.

メモ

質問や議論ができる場所を作った方が良いかも, という話が出ました. LaTeX で数式が書けることが条件となると思うので, 色々調べないといけないですね. Wiki 感覚で LaTeX が書けると嬉しいのですが.

次回

次回は 7/23, 24 の 19:00--21:00 に「1.4 代数的閉体」「1.5 分離拡大体、非分離拡大体」を取り扱います. まだ日程は仮ですが2日間の集中勉強会の形式で行う予定です.

興味があれば是非参加してみてください.

それでは.

スタート代数 第2回

今日はスタート代数の第2回でした.

スタート代数 #2

さて今回もガチにゼミをやってたわけで, 丁寧にゼミをやった結果, 今日の発表者は @mr_konn さん1人になってしまいました.

随所で参加者の方々から質問などが出てきて, 活発な議論ができて良かったと (主催者として) 感じています.

内容

今日の内容としては §1.1 を終え, やっと用語の定義などが終わりました. これでやっと本論に入っていけます. この先, 部分体全体とガロア群の部分群の対応を扱っていき, その美しさに心打たれる (予定) です.

定義ばっかりで面白くない部分だったのですが, 現代数学は定義のちょっとしたところに仕掛けがあったりするので気が抜けません. 「仕掛け」とは後々出てくる定理で必要な条件だったり, 他の概念と組み合わせるときに必要な条件だったりします. なので, 定義ばっかりでつまらないところは飛ばして, 命題や定理からまた定義に戻る, という本の読み方も良いです.

(と数学本の読み方の紹介など.)

ゼミの発表

発表者にツッコム係は主に主催者がやっているのですが, 私がゼミ発表するときに気を付けていることを書いていってみます.

状況としては, 教授の前で自分の勉強したことを話したり, 同じくらいのレベルの友達どうしで集まって発表し合うなど色んな場面が考えられますが, どの場面でも共通して大切に思っていることを書いていきます.

楽しくさせる

時間を割いて発表を聞いてもらうので, このゼミの時間の中で何かを得てもらいたい, と思っています. 「この時間を過ごして良かったな」と思ってもらうために「楽しくさせる」ということに気を遣っています.

「楽しく」というのは, 新しい知識を得たり, 上手な例を聞いて関心するなどの学問的な楽しさのことを言います.

そして, その時間を有意義にするには, 単にテキストを読めば分かることを喋るだけではだめなのです. それでは自習となんら変わりません. 自分の言葉での説明, 自分なりの解釈, そして自分で考えた話の構成で喋る必要があります. 決してテキストに喋らされてはいけません. そうやってテキストの内容を自分の色に変えて発表することで, 聞き手は2つの視点で内容を眺めることができ理解が深まります. 何より発表準備をした本人が理解が最も深まっているはずです.

「楽しくさせる」をゼミ準備の指標にすることで,「発表者の理解が深まる」「聞き手が新たな視点での物の見方が得られ刺激になる」というメリットを引き出すことができるのです.

キモを押さえる

これは, 結論を固定してから発表の構成を考えなさい, ということです. これ自体は色んなところで言われているので, 数学の場合について話したいと思います. もしかしたら, 別の分野での理論的なお話にも通じるのかも知れませんが, ほとんど知らないのでそこは想定に入れません.

数学ではたいていのテキストが, 定義 (Definition), 補題 (Lemma), 命題 (Proposition), 定理 (Theorem) とその証明 (Proof), 系 (Corollary) というパーツの集まりで, 依存関係を持ちつつ配置されています. この中でも「定理」が最も華々しい数学理論の成果なわけですが, その定理が成立するための最も重要なパーツがどこかにあるはずです. それがこの定理, ひいては理論のキモになります. 定義や定理の羅列の中に理論の流れを読んで, このキモを見付けるのが重要なのです.

どんな数学理論でも, その発端となる発想があるはずで, そこさえ押さえてしまえば後は芋づる式に示すべき命題や補題が出てくるものです. 例えば, 今回扱っているガロア理論では「多項式の根の取り替えを考えると, 体についての情報が分かる」という感覚がキモになっています. この感覚を正確に述べようとすると, 色んな用語の定義が必要になって, 定理を示すまでのステップを刻むために補題や命題が必要になってきます. これをまとめれば1つの数学理論になるはずです.

ゼミ発表においては発表する部分だけで構わないので, 話のキモを考え, それが良く伝わるような例えを出したり, 比喩の話をしたりすると良い発表になると思います.

まとめ

今回はガロア理論で必要な前提知識や用語の定義とその意味を押さえました. 次回からは体の拡大の種類を具体的に見ていきます.

またこの記事の後半では, 数学のゼミ発表について大事にしていることを書きました. もちろん私が常にできているかと言えば No なのですが, 常にこれを目指していることは確かです.

それでは.

スタート代数 第1回

今日はスタート代数という勉強会を開催してきました. http://partake.in/events/989bf10a-d5f0-4fcc-ba1f-f152fe2f7072

「スタート」と頭に付いていますが, 懇切丁寧に教えるのではなく懇切丁寧にツッコミを入れる大学のゼミ形式でやってきました. 初めてこの形式に触れた人は驚いたかもしれませんが, ゼミ形式では発表者が理解を深めるのが目的となっています. ソースコードレビューを思い浮かべてもらえると感覚は理解できると思います.

なぜ体論からか?

通常, 代数を学ぶ際には「群」→「環」→「体」と進むのが普通です. でもそこで敢えて体論から始めるのには訳があります.

まず, 体が代数的対象の中で一番身近なこと. もちろん自然数や整数も使っていますが, 割り算が許されない数を扱う場面は少ないと思います.

第2に具体例が分かりやすいこと. 群の例として剰余群が出てきたり, 環の例として多項式環が出てきたりしますが,「これ使ってすごいことができるぜ」感が足りないのです. それに比べてガロア理論での「方程式の根の様子が分かっちまうぜ」の方が印象が強いと考えました.

もちろん群や環のことも少しは知らないと体の話ができないので, その部分については全力でバックアップしていってます.

結果報告

今回は3ページまで進み, 多項式とその根について語り始めるあたりで時間切れとなりました. 遅いように感じると思いますが, 確実な理解を得るためにはこれくらいのスピードになってしまうものです.

「抽象代数を理解するとは?」や「数学のゼミってどんなふうにやるの?」という, あまり知られていない (と思われる) ところが, 体験できたのではないでしょうか?

こちらに参加者の方の板書ノートが公開されています. http://lockerz.com/s/135335969

宿題

今日は宿題がいくつか出ていました.

  • 1のある可換環 R に対し, ∀a ∈ R, a0 = 0
  • 四元数体の逆元を計算せよ
  • ある可換とは限らない群において, ある元の逆元が1つしか存在しないことを示せ

どれもそう難しくないので挑戦してみてください. 1つ目の問題などは「R が可換で無かったらどうなるか?」「R に1が無かったらどうなるか?」「0の公理を削ってみたらどうなるか?」と色々といじってみると, 公理の必要性が分かると思います. (自分はこんなふうにして数学の抽象概念を理解していました.)

まとめ

内容はけっこうガチでやってしまったので, 次回何人参加するのか不安ではあります. また, 元々数学ができる人しか参加しないんじゃないか? という指摘もあると思います. しかし,「数学の抽象的な思考を知った上でプログラミングをする方が幸せになれる」と確信しているので, 今後も様々な方法で数学について知ってもらえるよう活動をしていきます.

  • Java 使いのための数学入門
  • Coq を使って知る数学

などなどできたら良いな, と思っています. だいぶ先の話ですが :P

Licenses