アルゴリズム

33の素敵な数学小景

フィボナッチ数、タイル張り、アルゴリズムを線形代数で眺めてみると…
イジィ・マトウシェク
日本評論社

ミニチュア1 フィボナッチ快速
ミニチュア2 フィボナッチ数の公式
ミニチュア3 オッドタウンのクラブ
ミニチュア4 同じサイズの交わり
ミニチュア5 誤り訂正符号
ミニチュア6 奇数距離
ミニチュア7 ユークリッド距離でその配置を実現できるか?
ミニチュア8 完全二部グラフを詰め込む
ミニチュア9 等角直線
ミニチュア10 三角形はどこ?
ミニチュア11 行列のかけ算を検算する
ミニチュア12 長方形を正方形でタイル張り
ミニチュア13 3個のペテルセンでは足りない
ミニチュア14 ペテルセン,ホフマン・シングルトン,もしかしたら57
ミニチュア15 距離は二種類だけ
ミニチュア16 一点ぬいた立方体を覆う
ミニチュア17 中央値の交差は避け難し
ミニチュア18 直径を縮めることの難しさについて
ミニチュア19 小銭の行方
ミニチュア20 広場を散歩する
ミニチュア21 全域木を数える
ミニチュア22 何通りの方法で人は盤をタイル張りできるのだろうか?
ミニチュア23 もっと煉瓦を――もっと壁を?
ミニチュア24 完全マッチングと行列式
ミニチュア25 有限体上で梯子をひっくり返す
ミニチュア26 合成を数える
ミニチュア27 それは結合律をみたすか?
ミニチュア28 スパイと傘
ミニチュア29 合併のシャノン容量:二体物語
ミニチュア30 等距離集合
ミニチュア31 固有値を使って楽に切る
ミニチュア32 立方体を回転させる
ミニチュア33 集合対と外積

<訳者による付録>の前書き

付録A 本書には何が書いてあるのか
付録B 集合と写像
付録C 代数構造

  • C.1 群
  • C.2 置換,行列式
  • C.3 有限体
  • C.4 多項式

付録 D線形代数

  • D.1 正則行列の性質,ランク
  • D.2 連立方程式の解空間
  • D.3 実対称行列
  • D.4 トレース,三角行列
  • D.5 Q上のベクトル空間R

付録E グラフ

  • E.1 グラフの用語
  • E.2 GottliebからSperner
  • E.3 HoffmanからErdos-Ko-Rado(注:oはロング「"」付き)
  • E.4 Gessel-Viennotの補題

付録F アルゴリズム,計算量

  • F.1 O記法,オーダー
  • F.2 多項式時間,NP困難,NP完全
  • F.3 二つの行列の積を計算するStrassenの方法