math / Drkcore

代数的構造

Sat, 01 Sep 2012 09:10:20 +0919

何度も読みなおす必要がある。

代数的構造

集合Eがあって、その2つの要素a,bから、一定の方法で第3の要素c=φ(a,b)を作り出す、φ(a,b)という2変数の関数が定義されているとき、このEを代数的構造という

群

群とは操作の集まりである

代数的構造 (ちくま学芸文庫)
遠山啓
筑摩書房 / 1365円 ( 2011-12-07 )

「数学ガール／乱択アルゴリズム」を予約した

Wed, 16 Feb 2011 04:12:08 +0919

早速予約

数学ガール／乱択アルゴリズム
結城浩
ソフトバンククリエイティブ / 1995円 ( 2011-03-02 )

楽しみですな。

「なわばりの数理モデル」を読んだ

Thu, 16 Dec 2010 19:15:47 +0919

ボロノイ図おもしろい。IBIS行ったときに、最近傍探索はボロノイ図を使えば効率的に求めることができると聞いて興味をもった(Blogopolisから学ぶ計算幾何にも載ってた)

本書は、実装が載っていないのが残念だけど、実例を交えて進んでいくので非常に分かりやすかった。

なわばりの数理モデル -ボロノイ図からの数理工学入門-
杉原厚吉
共立出版 / ￥ 2,730 ()
通常2～5週間以内に発送

局所ドロネー性
ドロネー辺は与えられた点集合に隣同士という関係を定義するものだと解釈できる
最大空円
ロイド法
最遠点ボロノイ図と最小包含円
最小全域木の辺は相対近傍グラフの辺

ケミカルスペース(PCA)に対してボロノイ図描かせてPCRすれば、ケミストにとって分かりやすい(既存のどの化合物に近いか一目でわかる)表現方法にならないだろうか？

「食える数学」を読んだ

Sat, 11 Dec 2010 17:26:57 +0919

読み物として面白い。数学が実際の生活の中でどう使われているのか？とかを子供に説明する時に使えるネタが色々書いてあった。

chemoinformatics(とかbioinformatics)の世界に入って10年くらい経つけど、最近は数学的な部分を押さえてないと先に進めないなぁと。テクニシャンとかオペレーターからサイエンティフィックな方面に進みたい時には数学力がないと辛いなぁ（今まさになくて辛い）と感じる。

食える数学
神永正博
ディスカヴァー・トゥエンティワン / ￥ 1,575 ()
在庫あり。

ソリトン
プログラミングが出来るようになるにはプログラミングの訓練を重ねるしかない
現代はタスクフォース型のシステムが有効に働くという状況ではない
ウェーブレット

本書でオススメされてたので読んでみよう。

これなら分かる応用数学教室―最小二乗法からウェーブレットまで
金谷健一
共立出版 / ￥ 3,045 ()
通常2～4週間以内に発送

「データ構造とアルゴリズム」を読んだ

Wed, 08 Dec 2010 21:13:43 +0919

実装が載っていないけど、これはわかりやすい。大学の1,2年向けらしい。情報系って1,2回でこんなことやってたのか。うらやましい。囲み記事のカーペンターズアルゴリズムの解説が良かった、というか読むべし。

データ構造とアルゴリズム
杉原厚吉
共立出版 / ￥ 2,415 ()
在庫あり。

第1章アルゴリズムと計算量
第2章リスト構造
第3章ヒープ
第4章ハッシュ法とバケット法
第5章　再帰呼出しと分割統治
第6章グラフ探索
第7章最短路問題
第8章動的計画法
第9章縮小法
第10章最大流と割当て問題
第11章ボロノイ図とドロネー図
第12章 3次元凸包とドロネー図
第13章　平面走査法
第14章問題の難しさの測り方
第15章難問対策
第16章難問を利用した情報保護

以下メモ

ヒープソートの良さはメモリを効率的に扱えるところ
分割統治は問題が比で小さくなるか差で小さくなるかを考えることが重要
縮小法の中央値を早く見つける方法
空円性
最近点対
最小全域木に属する全ての辺はドロネー辺
平面走査法は次元を下げることにより問題を効率よく扱う
分枝限定法

14章から先はちょっと端折っている感があるが、ここらへんが気になるのであれば「メタヒューリスティクスの数理」でも読めばいいのではと。Pythonの実装も載ってるし。

メタヒューリスティクスの数理
久保幹雄,J. P. ペドロソ
共立出版 / ￥ 3,675 ()
在庫あり。

「計算論」を(中途半端に)読んだ

Sat, 20 Nov 2010 09:14:23 +0919

離散数学への招待(上)を読んだら、関数のイメージがわいたので、この勢いで以前読んですぐに挫折->放置という運命を辿っていた計算論を読み返してみた。

計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座)
高橋正子
近代科学社 / ￥ 3,570 ()
在庫あり。

計算可能な関数
ラムダ計算の基礎
ラムダ計算のモデル

3はよくわからなかったけど、2はそこそこ理解できた。1章はラムダ計算とは関係ないのだけど、チューリング機械を数学的に表現する話なのでそこそこ楽しかった。

λ式

変数xはλ式
Mがλ式でxが変数のとき(λx.M)はλ式 # 関数抽象
MとNがλ式のとき(MN)はλ式 # 関数適用

数式だけだと理解が進まないので、grassを動かしたり中を覗いてみたりしたのが良かった。

あとメモ

Curryの不動点演算子: Y = λy.(λx.y(xx))(λx.y(xx))
β正規形
正規化定理

離散数学への招待〈下〉

Thu, 18 Nov 2010 20:59:11 +0919

6章のシュペルナーの定理とブラウワーの不動点定理は、おおーとなるような内容だった。

8章のファノ平面も面白かったけど、それがどう役に立つのかまではイメージできなかった（最終章のブロックデザインに絡んでたけど）

確率的証明の章は読んでて勉強になったけど、自分の仕事には役立つのかなぁ？と疑問符。

母関数は途中からついていけなくなったし、ブロックデザインは難しい。

離散数学への招待〈下〉
J. マトウシェク,J. ネシェトリル
シュプリンガー・フェアラーク東京 / ￥ 2,520 ()
在庫あり。

第6章 2通りに数える　　
第7章全域木の総数　　
第8章有限射影平面　　
第9章確率と確率的証明　　
第10章母関数　　
第11章線形代数の応用

時間が出来たら演習問題解きながらもう一度読んでみたい。

「離散数学への招待」がおもしろい

Sat, 13 Nov 2010 09:06:11 +0919

上巻読み終えたけど、この本はグラフ理論のさわりをおさえるのにちょうどいい難易度だ（難しすぎず、かといって平易すぎもしない）

離散数学への招待〈上〉
J. マトウシェク,J. ネシェトリル
シュプリンガー・フェアラーク東京 / ￥ 2,835 ()
在庫あり。

第2章組合せ的数え上げ
- 2.1 関数と部分集合
- 2.2 置換と階乗
- 2.3 二項係数
- 2.4 評価 ―― 入門編
- 2.5 評価 ―― 階乗関数
- 2.6 評価 ―― 二項係数
- 2.7 包除原理
- 2.8 クローク係嬢の問題
第3章グラフ理論入門
- 3.1 グラフの概念 ―― 同型
- 3.2 部分グラフ，連結成分，隣接行列
- 3.3 次数列
- 3.4 オイラー・グラフ
- 3.5 オイラー回路を求めるアルゴリズム
- 3.6 オイラー有向グラフ
- 3.7 2-連結性
第4章木
- 4.1 木の定義と特徴づけ
- 4.2 木の同型
- 4.3 グラフの全域木
- 4.4 最小全域木問題
- 4.5 ヤルニークとボルーフカのアルゴリズム
第5章グラフを平面に描く
- 5.1 平面や曲面の上の描画
- 5.2 平面的グラフの中の閉路
- 5.3 オイラーの公式
- 5.4 地図の色分け ―― 四色定理

1.4

X Yを任意の集合とする。直感的には、関数fとはXの各元にYの元を一つだけ割り当てる何かである

という記述とその次のページからの関数合成とp.36の関数合成の集合のイメージでHaskellの関数合成のイメージがかなり強く沸いた。

3.3

次数列定理って面白いなと調べたら、Havel-Hakimiアルゴリズムというらしい。perlで書いてあったので、pythonでかいてみた。

def hakimi(deg):
    deg.sort()

    n = len(deg)
    m = deg[-1]

    if m == 0:           return True
    if m < 0:            return False
    if m > 0 and n == 1: return False

    new_deg = []
    for i,v in enumerate(deg[:-1]):
        if i+1 < n-v:
            new_deg.append(v)
        else:
            new_deg.append(v-1)
    return hakimi(new_deg)


if __name__ == "__main__":
    print [1,1,1,2,2,3,4,5,5]
    print hakimi([1,1,1,2,2,3,4,5,5]) # True
    print [2,2,2]
    print hakimi([2,2,2]) # True
    print [3,3,3]
    print hakimi([3,3,3]) # False

4

木の章もおもしろかった(符号化アルゴリズムとか)。

クラスカルのアルゴリズムやヤルニークとボルーフカのアルゴリズム（プリムのアルゴリズム）は読みなおした。そっちに興味がわくようだったら、最短経路の本がより深いのでよいかも。

5

4色定理はいわんとしていることは分かるが証明の過程をきちんと理解しているとは言いがたい。確か図書館に四色定理の本が置いてあったので今度借りてみるかな

四色問題
ロビン・ウィルソン
新潮社 / ￥ 2,310 ()
在庫あり。

mimetex入れた

Thu, 21 May 2009 20:34:49 +0919

数式を書く時にめんどいので、はてなにならってmimetexを入れてみた。

慣れれば楽なのかな。