メモ 環 環 単位元をもつ環 斜体 単位元をもつ環で0以外のすべての元が単元であるもの 体 斜体で可換なもの 整域 単位元をもつ環で可換で0以外に零因子をもたないもの 体は整域である。 部分環 可換環の部分環に有限部分集合を添加して得られる部分環 部分体…

メモ 3.1節 2-連結グラフと部分グラフ 「k-連結」の2通りの見方 グラフを非連結にするのに少なくともk個の頂点を除去する必要がある。 任意の2頂点に対して、それを結ぶ独立な道がk本存在する。 2-連結グラフとその構成

2.3節 道被覆 定理2.3.1 (Gallai & Milgram 1960) 系2.3.2 (Dilworth 1950) 任意の有限な半順序集合(P, ≦)において、Pを被覆する鎖の最小個数は、Pが含む反鎖の要素の最大個数と一致する。

2.2節 一般のグラフにおけるマッチング 定理2.2.3 条件(ii) |T'| + q(C'-T') * (奇数) = |C'| 右辺は偶数だから、 |T'| と q(C'-T') の偶奇は一致する。

2.2節 一般のグラフにおけるマッチング 系2.2.2 (Petersen 1891) 橋をもたない任意の3-正則グラフは1-因子をもつ。 Gに奇数本のS-C辺がある。 ∵ (S-C辺の本数) = 第一項は奇数、第二項は偶数だから、S-C辺の本数は奇数。

2.2節 一般のグラフにおけるマッチング 定理2.2.1 (Tutte 1947) グラフが1-因子をもつための必要十分条件は、すべてのS⊆V(G)に対して q(G-S) |S| が成り立つことである。 十分性 対偶を考える。 1-因子をもたないならば、q(G-S) > |S| となるS⊆V(G)が存在す…

メモ 2.7節 凸関数 凸関数から凸関数を構成する例 微分可能な凸関数の勾配による特徴付け 2回連続的微分可能な凸関数のHesse行列による特徴付け 2回連続的微分可能な狭義凸関数のHesse行列による十分条件 2回連続的微分可能な強凸関数のHesse行列による特徴…

メモ 2.6節 関数の連続性と微分可能性 拡張実数値関数の定義 値としてを許す 上半連続、下半連続、連続の定義 Brouwerの不動点定理 レベル集合の定義 拡張実数値関数の下半連続性のレベル集合による特徴付け 微分可能性の定義 平均値の定理 Taylorの定理 陰…

メモ 第1章 導入 ラスベガスアルゴリズム 乱数によらず正しい結果を与える乱択アルゴリズム モンテカルロアルゴリズム 乱数によって誤った結果を与えることがある乱択アルゴリズム 確率・期待値 2項分布・幾何分布 末端確率

まあ、簡単なメモ 第1章 正規言語 決定性有限オートマトン(DFA)の定義 正規言語をDFAで認識される言語として定義 正規演算の定義 和集合演算、連結演算、スター演算 非決定性有限オートマトン(NFA)の定義 DFAとNFAは等価 正規言語をNFAで認識される言語とし…

http://projecteuler.net/problem=91 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2091O(0,0), P(x1,y1), Q(x2,y2) 0 三角形OPQで異なる直角三角形は何個作れるか? 次のコードは自分で書いたもの。原点Oが直角になる場合とそうで…

1.4 不等式制約問題の最適性条件 不等式制約問題 min: s.t.: 実行可能解xに対し不等式条件で等号が成り立つとき、この制約条件はxにおいて有効であるという。 有効制約条件の添え字集合を次のように記す。 実行可能解xに対し有効である不等式制約条件の勾配…

1.3 等式制約問題の最適性条件 等式制約問題 min: s.t.: ラグランジュ関数 このはラグランジュ乗数ベクトルと呼ばれる。 ペナルティ関数 等式制約問題の最適性必要条件 1次の最適性必要条件の幾何学的解釈 制約が1つ g(x)=0 だけのときは、この範囲内で微小…

I.3 有限マルコフ連鎖 同値類の要素数が有限なとき、同値類が再帰的なことと閉じていることは同値 既約な有限マルコフ連鎖は再帰的

まあ、簡単なメモ 12章 連結性と中間値の定理 12.1 連結空間と連結集合 位相空間が連結性の開集合を使った定義 閉集合によっても特徴付けられる 位相空間の部分空間の連結性の開集合を使った特徴付け 位相空間の連結性は連続写像に対し不変 連結性は位相的性…

まあ、簡単なメモ 第11章 コンパクト性と最大値・最小値の定理 11.1 コンパクト空間とコンパクト集合 位相空間の被覆の定義 開被覆 有限被覆 有限部分被覆 位相空間のコンパクト性の定義 位相空間のコンパクト性は連続写像に対し不変 コンパクト性は位相的性…

まあ、簡単なメモ 第10章 位相空間 前節まででは 距離関数 → 開集合 → 位相同型写像を開集合により特徴付け と話が進んだ。この章では与えられた集合に距離関数を定めずに直接、開集合を定めて位相同型の概念を定義する。 10.1 位相空間 集合Xの位相構造の定…

まあ、簡単なメモ 第9章 距離空間の開集合系 9.1. 開集合・閉集合と連続写像 距離空間の間の連続写像の開集合・閉集合による特徴付け 位相同型写像の開集合による特徴付け 閉集合によっても特徴付けられる。 位相同型写像とは、全単射な連続写像で逆写像もま…

まあ、簡単なメモ 第8章 距離空間の開集合と閉集合 境界の定義 境界とは相対的な概念で、どの空間における境界であるかに注意。 開集合、閉集合の境界による定義 距離空間 (X,d) の部分集合 A が ならばAは閉集合であり開集合でもある。 特に、Xとφはいつで…