2-1 / 語問題 項書換え系 4.0. 準備 (3.1. 項 代入 等価性 ) 定義 3.1.1: - シグネチャ (signature): 関数記号の集合 (Σ と書く ) - それぞれの関数記号は アリティ (arity) と呼ばれる自然数が定められている - Σ (n) : アリ

Size: px
Start display at page:

Download "2-1 / 語問題 項書換え系 4.0. 準備 (3.1. 項 代入 等価性 ) 定義 3.1.1: - シグネチャ (signature): 関数記号の集合 (Σ と書く ) - それぞれの関数記号は アリティ (arity) と呼ばれる自然数が定められている - Σ (n) : アリ"

Transcription

1 2-1 / 語問題 項書換え系 4.0. 準備 (3.1. 項 代入 等価性 ) 定義 3.1.1: - シグネチャ (signature): 関数記号の集合 (Σ と書く ) - それぞれの関数記号は アリティ (arity) と呼ばれる自然数が定められている - Σ (n) : アリティ n を持つ関数記号からなる Σ の部分集合 例 : 群 Σ G = {e, i, } (e Σ (0) G, i Σ(1) G, Σ(2) G )

2 2-2 / 32 X: 変数の集合 (Σ X = ) 定義 3.1.2: (Σ-) 項の集合 T (Σ, X) の再帰的定義 - X T (Σ, X) - f Σ (n) かつ t 1,..., t n T (Σ, X) ならば f (t 1,..., t n ) T (Σ, X) 基礎項 : 変数を持たない項 ( その集合を T (Σ, ) や T (Σ) で書く )

3 項の例 : - (e, (x, i(x))) は項 (e は e() の略記 ) - +(+(x, y), z) の代わりに (x + y) + z と書いたりする - g(g( g(t) )) を g n (t) と書く (n は g のネストの数 ) 2-3 / 32

4 2-4 / 32 例による項の木表現の説明 t = (e, (x, i(x))) を木で表現すると - 位置の集合 Pos(t) = {ε, 1, 2, 21, 22, 221} - ε: 根位置 (root position) - 根記号 (root symbol) は 位置 ε の関数記号

5 2-5 / 32 項 s の位置の集合 Pos(s): - Pos(x) = {ε} - Pos(f (s 1,..., s n )) = {ε} 接頭順序 (prefix order) - p q iff p pp = q p q iff (p q) (q p) 項の大きさ - s = Pos(s) n {ip p Pos(s i )} i=1 例 : (e, (x, i(x))) = 6 以降は位置を表すとき i, j N, p, q N と記号を用いる

6 項 s の位置 p の部分項 s p - s ε = s - f (s 1,..., s n ) iq = s i q ( ただし,1 i n) 項 s の位置 p を t で置き換えて得られる項 s[t] p - s[t] ε = t - f (s 1,..., s n )[t] iq = f (s 1,..., s i [t] q,..., s n ) 変数の集合 Var(s) 例 : (e, (x, i(x))) 22 = i(x) (e, (x, i(x)))[ (e, e)] 22 = (e, (x, (e, e))) Var( (e, (x, i(x)))) = {x} 2-6 / 32

7 2-7 / 32 問 : 次の性質を p の長さに関する帰納法で証明せよ - pq Pos(s) ならば s pq = (s p ) q このような性質として以下の性質がある ( 補題 3.1.4) - p Pos(s) q Pos(t) ならば (s[t] p ) pq = t q (s[t] p )[r] pq = s[t[r] q ] p - pq Pos(s) ならば (s[t] pq ) p = (s p )[t] q (s[t] pq )[r] p = s[r] p - p, q Pos(s) p q ならば (s[t] p ) q = s q (s[t] p )[r] q = (s[r] q )[t] p

8 例による代入の説明代入 σ = {x (e, y), y i(e)} とするとき (x, i(y))σ = ( (e, y), i(i(e))) 2-8 / 32

9 代入 σ : V T (Σ, V ) ただし Dom(σ) は有限集合 Dom(σ) = {x V σ(x) x} Dom(σ) = {x 1,..., x n } のとき σ を次のように書く {x 1 σ(x 1 ),..., x n σ(x n )} σ の項上への自然な拡張 ˆσ : T (Σ, V ) T (Σ, V ) - x ˆσ = σ(x) - f (s 1,..., s n )ˆσ = f (s 1ˆσ,..., s 1ˆσ) σ と ˆσ を同一視する 2-9 / 32

10 2-10 / 32 代入 σ と σ を合成して得られる代入 τ = σσ は任意の変数 x について以下を満たす代入 - xτ = (xσ)σ 例 :σ = {x (e, y), y i(e)} σ = {y e, z w} のとき σσ = {x (e, e), y i(e), z w}

11 2-11 / 32 Σ 等式 : T (Σ, V ) 項の対 - 等式 (s, t) を s t と書く - 例 : ( (x, y), z) (x, (y, z)) - 項の順序を意識するときは s t と書く 例による書換えの説明等式 ( (x, y), z) (x, (y, z)) E によって i( ( (i(e), e), e)) E i( (i(e), (e, e)))

12 定義 等式集合 E による書換え E T (Σ, V ) T (Σ, V ) - s E t iff (l, r) E, p Pos(s), σ s p = lσ t = s[rσ] p 2-12 / 32

13 2-13 / 32 補題 : s E t とするとき 次が成り立つ (a) 任意の代入 σ について sσ E tσ (b) f ( s ) E f ( t ) 問 : 上の補題を証明せよ

14 2-14 / 32 定理 : E は 以下を満たす最小の同値関係 1. s 1 t 1,..., s n t n ならば f (s 1,..., s n ) f (t 1,..., t n ) 2. s t ならば σ. sσ tσ 3. E 証明 : E が同値関係であること をみたすことは容易に示せる最小性を示す を を満たす同値関係とする これより E が示せる この両辺の対称閉包と反射的推移的閉包をとることにより E が得られる

15 4.1. E 上の語問題の決定性 E 上の語問題 :s, t T (Σ, X) が与えられて s E t を満たすかを答える問題 定理 4.1.1: E が SN( 停止性 ) と CR( 合流性 ) をもつとき E 上の語問題は決定可能 証明 : 定理 より s E t iff s E = t E 2-15 / 32

16 例 4.1.3: コンビネータ論理 Σ = {, S, K} E = { ((S x) y) z (x z) (y z) (K x) y x } - いかなるプログラムも ( コーディングにより ) 基礎項で表現可能 例えば I x x を満たす I は I = (S K) K で表せる - 語問題は決定不能 2-16 / 32

17 4.5. 単一化 s と t が E 単一化可能 : σ. sσ E tσ - このような σ を E 単一化子とよぶ - E 単一化は一般に決定不能 そうでなければ 語問題が決定可能になるため ( 構文的 ) 単一化 : 単一化 単一化可能な例 : f (x) =? f (a) x =? f (y) h(x, y) = h(a, x) 単一化不可能な例 :f (x) =? g(y) x =? f (x) 2-17 / 32

18 定義 4.5.1: 代入 σ が σ より一般的 (σ σ と書く ): δ. σδ = σ 例 :σ σ ここで σ = {x f (y)} σ = {x f (a), y a} 名前替えの例 :{x y, y z, z x} 補題 4.5.3:σ σ かつ σ σ(σ σ と書く ) iff σδ = σ を満たす名前替え δ が存在する 2-18 / 32

19 定義 4.5.4: - 単一化問題 S = {s 1 =? t 1,..., s n =? t n } - S の解は 次を満たす代入 σ s 1 σ = t 1 σ,..., s n σ = t n σ - S のすべての解の集合 U(S) = {σ (s =? t) S. sσ = tσ} 2-19 / 32

20 σ が S の最汎単一化子 (mgu): σ U(S) σ U(S). σ σ 例 4.5.5:S = {x =? y} とする - σ = {x y} は S の最汎単一化子 - σ = {x z, y z} は S の単一化子だが 最汎単一化子でない - σ = {x y, z 1 z 2, z 2 z 1 } は S の最汎単一化子 例えば σ {z 1 z 2, z 2 z 1 } = σ 2-20 / 32

21 2-21 / 32 代入 σ が巾等 :σσ = σ 定理 4.5.8: 単一化問題 S が解を持つならば 巾等な最汎単一化子が存在する 証明 : 次章に

22 2-22 / 変換に基づく単一化の解法 ( 時間の関係で省略の可能性あり ) 定義 4.6.1: 次の条件を満たす単一化問題を解形式という - S = {x 1 =? t 1,..., x n =? t n } の形式 - x 1,..., x n は相異なる変数 - x 1,..., x n は t 1 から t n には出現しない 解形式の例 : S = {x =? f (z, z), y =? f (f (z, z), f (z, z))}

23 2-23 / 32 解形式 S = {x 1 =? t 1,..., x n =? t n } から代入 S = {x1 t 1,..., x n t n } が定められる 補題 4.6.2: 解形式 S について σ U(S). Sσ = σ 証明 :S = {x 1 =? t 1,..., x n =? t n } とする - x i Dom( S) について x i Sσ = ti σ = x i σ - x Dom( S) について x Sσ = xσ 補題 4.6.3: 解形式 S について S は巾等な最汎単一化子である 証明 : 巾等性については省略 S U(S) は明らか まら 補題 より σ U(S). S σ であり 最汎性が導かれる

24 最汎単一化子を得るための変換系 Unify(S): S に可能な限り変換 を繰り返し適用する その結果 S が解形式なら解 S を返す さもなければ 解なし ( 削除 ) {t =? t} S S ( 分解 ) {f (t 1,..., t n ) =? f (u 1,..., u n )} S {t 1 =? u 1,..., t n =? u n } S ( 方向 ) t が変数でないとき {t =? x} S {x =? t} S ( 消去 ) x Var(S) かつ x Var(t) のとき {x =? t} S {x =? t} S{x t} ここで Sσ = {tσ =? uσ t =? u S} 2-24 / 32

25 2-25 / 32 例 : {x =? f (a), g(x, x) =? g(x, y)} 消去 {x =? f (a), g(f (a), f (a)) =? g(f (a), y)} 分解 {x =? f (a), f (a) =? f (a), f (a) =? y} 削除 {x =? f (a), f (a) =? y} 方向 {x =? f (a), y =? f (a)} 問 : 上の例で 最初に = 分解を適用した変換を試みよ

26 2-26 / 32 x が既解 :x は x =? t の形式で S 中に一ヶ所だけ出現 補題 4.6.5: 手続き Unify(S) は 入力の単一化問題 S によらず停止する証明 : 変換 の停止性を S から (N N N, > 3 lex ) への測度関数 φ(s) = (n 1, n 2, n 3 ) を使って示す - n 1 :S の既解でない変数の数 - n 2 = ( s + t ) s=? t S - n 3 :S 中にある t =? x の形式の数

27 2-27 / 32 証明 ( 続き ) φ の単調性は以下のように示される n 1 n 2 n 3 削除 > 分解 > 方向 = > 消去 >

28 2-28 / 32 補題 4.6.6:S T ならば U(S) = U(T ) 証明 : 消去については以下の通り {x =? t} S {x =? t} S {x t} とする σ U({x =? t} S ) iff xσ = tσ σ U(S ) iff xσ = tσ ({x t}σ) U(S ) by 補 iff xσ = tσ σ U(S {x t}) iff σ U({x =? t} S {x t}) 他の変換規則については明らか

29 2-29 / 32 補題 4.6.7:Unify(S) は健全 ( 得られる代入 S は巾等な S の解 ) 証明 : 補題 から U(S) = U(S ) が導ける また 補題 より S は巾等である

30 2-30 / 32 補題 4.6.8:S が次の形式の要素を含むとき S は解を持たない f (s 1,..., s m ) =? g(t 1,..., t n ) ここで f g 補題 4.6.9:S が次の形式の要素を含むとき S は解を持たない x =? t ここで x Var(t) かつ x t

31 補題 :S が解を持てば Unify(S) は解を返す証明 : 1. 解形式でない S が解を持てば 変換規則が適用できることが 補題 と補題 から示せる これは 変換の正規形は 解形式であるか あるいは 解を持たないことを意味する 2. 変換は停止性を持つ ( 補題 4.6.5) ので その正規形のひとつ S を必ず求めることが出来る S は解を持つという前提と 1. より S は解形式である 補題 より S は S の解である 2-31 / 32

32 解を持たないことを早く発見するために Unify に次の規則を追加してもよい ( 衝突 ) f g のとき {f (s 1,..., s m ) =? g(t 1,..., t n )} S ( 消去 ) x Var(t) かつ x t のとき {x =? t} S ここで は解を持たない特別な単一化問題とする 2-32 / 32

オートマトン 形式言語及び演習 3. 正規表現 酒井正彦 正規表現とは 正規表現 ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械正規表現 : 言語

オートマトン 形式言語及び演習 3. 正規表現 酒井正彦   正規表現とは 正規表現 ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械正規表現 : 言語 オートマトン 形式言語及び演習 3. 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ とは ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械 : 言語を記号列で定義 - 記述しやすい ( ユーザフレンドリ ) 例 :01 + 10 - UNIX の grep コマンド - UNIX の

More information

オートマトン 形式言語及び演習 1. 有限オートマトンとは 酒井正彦 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,

オートマトン 形式言語及び演習 1. 有限オートマトンとは 酒井正彦   形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, オートマトン 形式言語及び演習 1 有限オートマトンとは 酒井正彦 wwwtrscssinagoya-uacjp/~sakai/lecture/automata/ 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, } 形式言語 : 数学モデルに基づいて定義された言語 認識機械 : 文字列が該当言語に属するか? 文字列 機械 受理

More information

オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 正規言語の性質 反復補題正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると

オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦   正規言語の性質 反復補題正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ 正規言語の性質 正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると仮定してを使い 矛盾を導く 閉包性正規言語を演算により組み合わせて得られる言語が正規言語となる演算について調べる

More information

() ): (1) f(x) g(x) x = x 0 f(x) + g(x) x = x 0 lim f(x) = f(x 0 ), lim g(x) = g(x 0 ) x x 0 x x0 lim {f(x) + g(x)} = f(x 0 ) + g(x 0 ) x x0 lim x x 0

() ): (1) f(x) g(x) x = x 0 f(x) + g(x) x = x 0 lim f(x) = f(x 0 ), lim g(x) = g(x 0 ) x x 0 x x0 lim {f(x) + g(x)} = f(x 0 ) + g(x 0 ) x x0 lim x x 0 (1) 3 連続関数と逆関数 定義 3.1 y = f (x) のグラフが x = a でつながっているとき f (x) は x = a において連続と いう. 直感的にはこれが わかりやすい x = a では連続 x = b ではグラフがちぎれているので 不連続 定義 3. f (x) が x = a の近くで定義され lim f (x) = f (a) をみたす時 x a f (x) は x =

More information

Microsoft PowerPoint - 09re.ppt [互換モード]

Microsoft PowerPoint - 09re.ppt [互換モード] 3.1. 正則表現 3. 正則表現 : 正則表現 ( または正規表現 ) とは 文字列の集合 (= 言語 ) を有限個の記号列で表現する方法の 1 つ 例 : (01)* 01 を繰り返す文字列 つまり 0(0+1)* 0 の後に 0 か 1 が繰り返す文字列 (01)* = {,01,0101,010101,01010101, } 0(0+1)*={0,00,01,000,001,010,011,0000,

More information

Microsoft Word - thesis.doc

Microsoft Word - thesis.doc 剛体の基礎理論 -. 剛体の基礎理論初めに本論文で大域的に使用する記号を定義する. 使用する記号トルク撃力力角運動量角速度姿勢対角化された慣性テンソル慣性テンソル運動量速度位置質量時間 J W f F P p .. 質点の並進運動 質点は位置 と速度 P を用いる. ニュートンの運動方程式 という状態を持つ. 但し ここでは速度ではなく運動量 F P F.... より質点の運動は既に明らかであり 質点の状態ベクトル

More information

構造化プログラミングと データ抽象

構造化プログラミングと データ抽象 計算の理論 後半第 3 回 λ 計算と型システム 本日の内容 λ 計算の表現力 ( 前回の復習 ) データの表現 不動点演算子と再帰 λ 計算の重要な性質 チャーチ ロッサー性 簡約戦略 型付き λ 計算 ブール値 組 ブール値と組の表現 true, false を受け取り 対応する要素を返す関数 として表現 T = λt.λf.t F = λt.λf.f if e 1 then e 2 else

More information

Microsoft PowerPoint - 3.ppt [互換モード]

Microsoft PowerPoint - 3.ppt [互換モード] 3. プッシュダウンオートマトンと文脈自由文法 1 3-1. プッシュダウンオートマトン オートマトンはメモリがほとんど無かった この制限を除いた機械を考える 理想的なスタックを利用できるようなオートマトンをプッシュダウンオートマトン (Push Down Automaton,PDA) という 0 1 入力テープ 1 a 1 1 0 1 スタッb 入力テープを一度走査したあと ク2 入力テプを度走査したあと

More information

An Automated Proof of Equivalence on Quantum Cryptographic Protocols

An Automated Proof of Equivalence on Quantum Cryptographic Protocols 量子暗号のための プロトコル等価性検証ツール 久保田貴大 *, 角谷良彦 *, 加藤豪, 河野泰人, 櫻田英樹 * 東京大学情報理工学系研究科, NTT コミュニケーション科学基礎研究所 背景 暗号安全性証明の検証は難しい 量子暗号でもそうである 検証のための形式体系が提案されているが, 実際には, 形式体系の適用は手作業では非常に煩雑である 形式検証のためには, 検証ツールが開発されることが望ましい

More information

<4D F736F F D F2095A F795AA B B A815B837D839382CC95FB92F68EAE2E646F63>

<4D F736F F D F2095A F795AA B B A815B837D839382CC95FB92F68EAE2E646F63> 1/8 平成 3 年 3 月 4 日午後 6 時 11 分 10 複素微分 : コーシー リーマンの方程式 10 複素微分 : コーシー リーマンの方程式 9 複素微分 : 正則関数 で 正則性は複素数 z の関数 f ( z) の性質として導き出しまし た 複素数 z は つの実数, で表され z i 数 u, v で表され f ( z) u i 複素数 z と つの実数, : z + i + です

More information

Microsoft PowerPoint - 第3回2.ppt

Microsoft PowerPoint - 第3回2.ppt 講義内容 講義内容 次元ベクトル 関数の直交性フーリエ級数 次元代表的な対の諸性質コンボリューション たたみこみ積分 サンプリング定理 次元離散 次元空間周波数の概念 次元代表的な 次元対 次元離散 次元ベクトル 関数の直交性フーリエ級数 次元代表的な対の諸性質コンボリューション たたみこみ積分 サンプリング定理 次元離散 次元空間周波数の概念 次元代表的な 次元対 次元離散 ベクトルの直交性 3

More information

構造化プログラミングと データ抽象

構造化プログラミングと データ抽象 計算の理論 後半第 3 回 λ 計算と型システム 本日の内容 λ 計算の表現力 ( 前回のつづき ) 前回の復習 不動点演算子と再帰 λ 計算の重要な性質 チャーチ ロッサー性 簡約戦略 型付き λ 計算 ブール値 組 ブール値と組の表現 ( 復習 ) true, false を受け取り 対応する要素を返す関数 として表現 T = λt.λf.t F = λt.λf.f if e 1 then e

More information

Microsoft PowerPoint - 10.pptx

Microsoft PowerPoint - 10.pptx m u. 固有値とその応用 8/7/( 水 ). 固有値とその応用 固有値と固有ベクトル 行列による写像から固有ベクトルへ m m 行列 によって線形写像 f : R R が表せることを見てきた ここでは 次元平面の行列による写像を調べる とし 写像 f : を考える R R まず 単位ベクトルの像 u y y f : R R u u, u この事から 線形写像の性質を用いると 次の格子上の点全ての写像先が求まる

More information

PowerPoint Presentation

PowerPoint Presentation 付録 2 2 次元アフィン変換 直交変換 たたみ込み 1.2 次元のアフィン変換 座標 (x,y ) を (x,y) に移すことを 2 次元での変換. 特に, 変換が と書けるとき, アフィン変換, アフィン変換は, その 1 次の項による変換 と 0 次の項による変換 アフィン変換 0 次の項は平行移動 1 次の項は座標 (x, y ) をベクトルと考えて とすれば このようなもの 2 次元ベクトルの線形写像

More information

Microsoft PowerPoint - 9.pptx

Microsoft PowerPoint - 9.pptx 9. 線形写像 ここでは 行列の積によって 写像を定義できることをみていく また 行列の積によって定義される写像の性質を調べていく 行列演算と写像 ( 次変換 3 拡大とスカラー倍 p ' = ( ', ' = ( k, kk p = (, k 倍 k 倍 拡大後 k 倍拡大の関係は スカラー倍を用いて次のように表現できる ' = k ' 拡大前 拡大 4 拡大と行列の積 p ' = ( ', '

More information

Microsoft PowerPoint - 9.pptx

Microsoft PowerPoint - 9.pptx 9/7/8( 水 9. 線形写像 ここでは 行列の積によって 写像を定義できることをみていく また 行列の積によって定義される写像の性質を調べていく 拡大とスカラー倍 行列演算と写像 ( 次変換 拡大後 k 倍 k 倍 k 倍拡大の関係は スカラー倍を用いて次のように表現できる p = (, ' = k ' 拡大前 p ' = ( ', ' = ( k, k 拡大 4 拡大と行列の積 拡大後 k 倍

More information

様々なミクロ計量モデル†

様々なミクロ計量モデル† 担当 : 長倉大輔 ( ながくらだいすけ ) この資料は私の講義において使用するために作成した資料です WEB ページ上で公開しており 自由に参照して頂いて構いません ただし 内容について 一応検証してありますが もし間違いがあった場合でもそれによって生じるいかなる損害 不利益について責任を負いかねますのでご了承ください 間違いは発見次第 継続的に直していますが まだ存在する可能性があります 1 カウントデータモデル

More information

PowerPoint Presentation

PowerPoint Presentation 言語モデル論 (4) ー λ 計算その 1 ー 米澤明憲 始めに 関数について 持つ個々の数学的領域 ( 型等 ) に依存しない 関数の一般的な性質を調べる目的 1940 年代にA. Churchが始めた計算の理論体系 作用型プログラミングの基礎 式はλ 式 (λexpression, λterm) と呼ばれ 関数を表す (denoteする) 基本的に文字列の書き換え ( 簡約 ) が計算とみなされる体系であるが

More information

DVIOUT

DVIOUT 最適レギュレータ 松尾研究室資料 第 最適レギュレータ 節時不変型無限時間最適レギュレータ 状態フィードバックの可能な場合の無限時間問題における最適レギュレータについて確定系について説明する. ここで, レギュレータとは状態量をゼロにするようなコントローラのことである. なぜ, 無限時間問題のみを述べるかという理由は以下のとおりである. 有限時間の最適レギュレータ問題の場合の最適フィードバックゲインは微分方程式の解から構成される時間関数として表現される.

More information

4STEP 数学 Ⅲ( 新課程 ) を解いてみた関数 1 微分法 1 微分係数と導関数微分法 2 導関数の計算 272 ポイント微分法の公式を利用 (1) ( )( )( ) { } ( ) ( )( ) ( )( ) ( ) ( )( )

4STEP 数学 Ⅲ( 新課程 ) を解いてみた関数   1 微分法 1 微分係数と導関数微分法 2 導関数の計算 272 ポイント微分法の公式を利用 (1) ( )( )( ) { } ( ) ( )( ) ( )( ) ( ) ( )( ) 微分法 微分係数と導関数微分法 導関数の計算 7 ポイント微分法の公式を利用 () 7 8 別解 [ ] [ ] [ ] 7 8 など () 6 6 など 7 ポイント微分法の公式を利用 () 6 6 6 など () 9 など () þ î ì など () þ î ì þ î ì þ î ì など 7 () () 左辺を で微分すると, 右辺を で微分すると, ( ) ( ) ( ) よって, (

More information

DVIOUT-SS_Ma

DVIOUT-SS_Ma 第 章 微分方程式 ニュートンはリンゴが落ちるのを見て万有引力を発見した という有名な逸話があります 無重力の宇宙船の中ではリンゴは落ちないで静止していることを考えると 重力が働くと始め静止しているものが動き出して そのスピードはどんどん大きくなる つまり速度の変化が現れることがわかります 速度は一般に時間と共に変化します 速度の瞬間的変化の割合を加速度といい で定義しましょう 速度が変化する, つまり加速度がでなくなるためにはその原因があり

More information

オートマトンと言語

オートマトンと言語 オートマトンと言語 回目 4 月 8 日 ( 水 ) 章 ( 数式の記法, スタック,BNF 記法 ) 授業資料 http://ir.cs.yamanashi.ac.jp/~ysuzuki/public/automaton/ 授業の予定 ( 中間試験まで ) 回数月日 内容 4 月 日オートマトンとは, オリエンテーション 4 月 8 日 章 ( 数式の記法, スタック,BNF) 3 4 月 5 日

More information

融合規則 ( もっとも簡単な形, 選言的三段論法 ) ll mm ll mm これについては (ll mm) mmが推論の前提部になり mmであるから mmは常に偽となることがわかり ll mmはllと等しくなることがわかる 機械的には 分配則より (ll mm) mm (ll mm) 0 ll m

融合規則 ( もっとも簡単な形, 選言的三段論法 ) ll mm ll mm これについては (ll mm) mmが推論の前提部になり mmであるから mmは常に偽となることがわかり ll mmはllと等しくなることがわかる 機械的には 分配則より (ll mm) mm (ll mm) 0 ll m 知識工学 ( 第 5 回 ) 二宮崇 ( ninomiya@cs.ehime-u.ac.jp ) 論理的エージェント (7 章のつづき ) 証明の戦略その 3 ( 融合法 ) 証明の戦略その 1 やその 2 で証明できたときは たしかにKKKK ααとなることがわかるが なかなか証明できないときや 証明が本当にできないときには KKKK ααが成り立つのか成り立たないのかわからない また どのような証明手続きを踏めば証明できるのか定かではない

More information

航空機の運動方程式

航空機の運動方程式 可制御性 可観測性. 可制御性システムの状態を, 適切な操作によって, 有限時間内に, 任意の状態から別の任意の状態に移動させることができるか否かという特性を可制御性という. 可制御性を有するシステムに対し, システムは可制御である, 可制御なシステム という言い方をする. 状態方程式, 出力方程式が以下で表されるn 次元 m 入力 r 出力線形時不変システム x Ax u y x Du () に対し,

More information

情報数理学

情報数理学 2007 年度 情報数理学 履修にあたって 2007 年度大学院奇数セメスター ( 前期 ) 開講 教室 : K336 大学院棟 D46( 次回から ) 時限 : 火曜日 3 時限 (2:50-4:20) 担当 草苅良至 2 講義予定 計算機のいろいろな理論モデル 言語理論 計算の限界 問題の難しさ 現実問題と計算 計算量理論 アルゴリズム論 3 参考書 M. Sipser 著 計算理論の基礎 共立出版

More information

スライド 1

スライド 1 ブール代数 ブール代数 集合 { 0, 1 } の上で演算 AND, OR, NOT からなる数学的体系 何のため? ある演算をどのような回路で実現すればよいのか? どうすれば回路が小さくなるのか? どうすれば回路が速く動くのか? 3 復習 : 真理値表とゲート記号 真理値表 A B A B 0 0 0 0 1 0 1 0 0 1 1 1 A B A+B 0 0 0 0 1 1 1 0 1 1 1

More information

<4D F736F F D208C51985F82CD82B682DF82CC88EA95E A>

<4D F736F F D208C51985F82CD82B682DF82CC88EA95E A> 群論はじめの一歩 (6) 6. 指数 2の定理と2 面体群 命題 H を群 G の部分群とする そして 左剰余類全体 G/ H 右剰 余類全体 \ H G ともに指数 G: H 2 と仮定する このとき H は群 G の正規部分群である すなわち H 注意 ) 集合 A と B があるとき A から B を引いた差集合は A \ B と書かれるが ここで書いた H \ Gは差集合ではなく右剰余類の集合の意味である

More information

チェビシェフ多項式の2変数への拡張と公開鍵暗号(ElGamal暗号)への応用

チェビシェフ多項式の2変数への拡張と公開鍵暗号(ElGamal暗号)への応用 チェビシェフ多項式の 変数への拡張と公開鍵暗号 Ell 暗号 への応用 Ⅰ. チェビシェフ Chbhv Chbhv の多項式 より であるから よって ここで とおくと coθ iθ coθ iθ iθ coθcoθ 4 4 iθ iθ iθ iθ iθ i θ i θ i θ i θ co θ co θ} co θ coθcoθ co θ coθ coθ したがって が成り立つ この漸化式と であることより

More information

Microsoft Word ã‡»ã…«ã‡ªã…¼ã…‹ã…žã…‹ã…³ã†¨åłºæœ›å•¤(佒芤喋çfl�)

Microsoft Word ã‡»ã…«ã‡ªã…¼ã…‹ã…žã…‹ã…³ã†¨åłºæœ›å•¤(佒芤喋çfl�) Cellulr uo nd heir eigenlues 東洋大学総合情報学部 佐藤忠一 Tdzu So Depren o Inorion Siene nd rs Toyo Uniersiy. まえがき 一次元セルオ-トマトンは数学的には記号列上の行列の固有値問題である 固有値問題の行列はふつう複素数体上の行列である 量子力学における固有値問題も無限次元ではあるが関数環上の行列でその成分は可換環である

More information

2011年度 大阪大・理系数学

2011年度 大阪大・理系数学 0 大阪大学 ( 理系 ) 前期日程問題 解答解説のページへ a a を自然数とする O を原点とする座標平面上で行列 A= a の表す 次変換 を f とする cosθ siθ () >0 および0θ

More information

Microsoft PowerPoint - lectureNote13.ppt

Microsoft PowerPoint - lectureNote13.ppt i217 関数プログラミング第 13 回プログラム検証 2 二木厚吉 緒方和博 計算機による検証支援 SML のプログラム ( 関数 ) の性質を帰納法等により明らかにすることは可能である. つまり プログラムを検証 ( プログラムが望ましい性質を満たすことを証明 ) することは可能である. ただし SML の処理系は 検証 ( あるいは証明 ) を支援しない. 検証を支援するための計算機言語やツールがある.

More information

パソコンシミュレータの現状

パソコンシミュレータの現状 第 2 章微分 偏微分, 写像 豊橋技術科学大学森謙一郎 2. 連続関数と微分 工学において物理現象を支配する方程式は微分方程式で表されていることが多く, 有限要素法も微分方程式を解く数値解析法であり, 定式化においては微分 積分が一般的に用いられており. 数学の基礎知識が必要になる. 図 2. に示すように, 微分は連続な関数 f() の傾きを求めることであり, 微小な に対して傾きを表し, を無限に

More information

Microsoft PowerPoint - fol.ppt

Microsoft PowerPoint - fol.ppt 認知システム論知識と推論 (4) 知識と論理でを組み合わせて問題を解決する 一階述語論理 (first-order predicate logic) 一階述語論理入門 構文論 ( 論理式の文法 ) 意味論 ( 論理式の解釈 ) 前回までは, 命題論理 の構文と意味, および推論規則について学んだ. 今回からは, 命題論理よりも表現力の高い を学ぶ. 今回はその導入部分であり, 最初に, 命題論理では表現力が不十分であることを理解した後,

More information

Microsoft PowerPoint - H21生物計算化学2.ppt

Microsoft PowerPoint - H21生物計算化学2.ppt 演算子の行列表現 > L いま 次元ベクトル空間の基底をケットと書くことにする この基底は完全系を成すとすると 空間内の任意のケットベクトルは > > > これより 一度基底を与えてしまえば 任意のベクトルはその基底についての成分で完全に記述することができる これらの成分を列行列の形に書くと M これをベクトル の基底 { >} による行列表現という ところで 行列 A の共役 dont 行列は A

More information

1/30 平成 29 年 3 月 24 日 ( 金 ) 午前 11 時 25 分第三章フェルミ量子場 : スピノール場 ( 次元あり ) 第三章フェルミ量子場 : スピノール場 フェルミ型 ボーズ量子場のエネルギーは 第二章ボーズ量子場 : スカラー場 の (2.18) より ˆ dp 1 1 =

1/30 平成 29 年 3 月 24 日 ( 金 ) 午前 11 時 25 分第三章フェルミ量子場 : スピノール場 ( 次元あり ) 第三章フェルミ量子場 : スピノール場 フェルミ型 ボーズ量子場のエネルギーは 第二章ボーズ量子場 : スカラー場 の (2.18) より ˆ dp 1 1 = / 平成 9 年 月 日 ( 金 午前 時 5 分第三章フェルミ量子場 : スピノール場 ( 次元あり 第三章フェルミ量子場 : スピノール場 フェルミ型 ボーズ量子場のエネルギーは 第二章ボーズ量子場 : スカラー場 の (.8 より ˆ ( ( ( q -, ( ( c ( H c c ë é ù û - Ü + c ( ( - に限る (. である 一方 フェルミ型は 成分をもち その成分を,,,,

More information

DVIOUT-17syoze

DVIOUT-17syoze 平面の合同変換と相似変換 岩瀬順一 要約 : 平面の合同変換と相似変換を論じる いま大学で行列を学び始めている大学一年生を念頭に置いている 高等学校で行列や一次変換を学んでいなくてもよい 1. 写像 定義 1.1 X, Y を集合とする X の各元 x に対し Y のただ一つの元 y を対応させる規則 f を写像とよび,f : X! Y のように書く f によって x に対応する Y の元を f(x)

More information

20~22.prt

20~22.prt [ 三クリア W] 辺が等しいことの証明 ( 円周角と弦の関係利用 ) の の二等分線がこの三角形の外接円と交わる点をそれぞれ とするとき 60 ならば であることを証明せよ 60 + + 0 + 0 80-60 60 から ゆえに 等しい長さの弧に対する弦の長さは等しいから [ 三クリア ] 方べきの定理 接線と弦のなす角と円周角を利用 線分 を直径とする円 があり 右の図のように の延長上の点

More information

不偏推定量

不偏推定量 不偏推定量 情報科学の補足資料 018 年 6 月 7 日藤本祥二 統計的推定 (statistical estimatio) 確率分布が理論的に分かっている標本統計量を利用する 確率分布の期待値の値をそのまま推定値とするのが点推定 ( 信頼度 0%) 点推定に ± で幅を持たせて信頼度を上げたものが区間推定 持たせた幅のことを誤差 (error) と呼ぶ 信頼度 (cofidece level)

More information

Microsoft PowerPoint - 10.pptx

Microsoft PowerPoint - 10.pptx 0. 固有値とその応用 固有値と固有ベクトル 2 行列による写像から固有ベクトルへ m n A : m n n m 行列によって線形写像 f R R A が表せることを見てきた ここでは 2 次元平面の行列による写像を調べる 2 = 2 A 2 2 とし 写像 まず 単位ベクトルの像を求める u 2 x = v 2 y f : R A R を考える u 2 2 u, 2 2 0 = = v 2 0

More information

Microsoft PowerPoint - 1.ppt [互換モード]

Microsoft PowerPoint - 1.ppt [互換モード] 第 回オートマトンと正規表現 8//5( 火 ) 履修にあたって 8 年度情報数理学 8 年度大学院奇数セメスター ( 前期 ) 開講教室 : K6 大学院棟 D6( 次回から ) 担当 時限 : 火曜日 時限 (:5-:) 草苅良至 講義予定 計算機のいろいろな理論モデル言語理論 計算の限界計算量理論 問題の難しさ 現実問題と計算アルゴリズム論 参考書. Sipser 著 計算理論の基礎 共立出版

More information

離散数学

離散数学 離散数学 ブール代数 落合秀也 前回の復習 : 命題計算 キーワード 文 複合文 結合子 命題 恒真 矛盾 論理同値 条件文 重条件文 論法 論理含意 記号 P(p,q,r, ),,,,,,, 2 今日のテーマ : ブール代数 ブール代数 ブール代数と束 そして 順序 加法標準形とカルノー図 3 今日のテーマ : ブール代数 ブール代数 ブール代数と束 そして 順序 加法標準形とカルノー図 4 ブール代数の法則

More information

Microsoft PowerPoint - logic ppt [互換モード]

Microsoft PowerPoint - logic ppt [互換モード] 述語論理と ( 全称 ) ( 存在 ) 回の講義の概観 : 命題論理 ( 真理値 ) 2 述語論理 ( モデルと解釈 ) 意味論 semantics 命題論理 ( 公理と推論規則 ) 述語論理 ( 公理と推論規則 ) syntax 構文論 preview 述語論理は命題論理よりも複雑 例題 : 次の文は真か偽か? ( 曖昧な文です ) すべての自然数 x に対して x < y を満たすような自然数

More information

行列、ベクトル

行列、ベクトル 行列 (Mtri) と行列式 (Determinnt). 行列 (Mtri) の演算. 和 差 積.. 行列とは.. 行列の和差 ( 加減算 ).. 行列の積 ( 乗算 ). 転置行列 対称行列 正方行列. 単位行列. 行列式 (Determinnt) と逆行列. 行列式. 逆行列. 多元一次連立方程式のコンピュータによる解法. コンピュータによる逆行列の計算.. 定数項の異なる複数の方程式.. 逆行列の計算

More information

Matrix and summation convention Kronecker delta δ ij 1 = 0 ( i = j) ( i j) permutation symbol e ijk = (even permutation) (odd permutation) (othe

Matrix and summation convention Kronecker delta δ ij 1 = 0 ( i = j) ( i j) permutation symbol e ijk = (even permutation) (odd permutation) (othe Matr ad summato covto Krockr dlta δ ( ) ( ) prmutato symbol k (v prmutato) (odd prmutato) (othrs) gvalu dtrmat dt 6 k rst r s kt opyrght s rsrvd. No part of ths documt may b rproducd for proft. 行列 行 正方行列

More information

Microsoft PowerPoint - 13approx.pptx

Microsoft PowerPoint - 13approx.pptx I482F 実践的アルゴリズム特論 13,14 回目 : 近似アルゴリズム 上原隆平 (uehara@jaist.ac.jp) ソートの下界の話 比較に基づく任意のソートアルゴリズムはΩ(n log n) 時間の計算時間が必要である 証明 ( 概略 ) k 回の比較で区別できる場合の数は高々 2 k 種類しかない n 個の要素の異なる並べ方は n! 通りある したがって少なくとも k n 2 n!

More information

<4D F736F F D A788EA8E9F95FB92F68EAE>

<4D F736F F D A788EA8E9F95FB92F68EAE> 行列を用いた連立一次方程式の解法 概要私たちは数学 C で一次連立方程式の正方行列を用いた解法を学んだ 今回はこれをベースとし 元一次連立方程式の解法への拡張を目標とした まず 行列の性質から解をもつ条件 不定解の処理を考えた また 逆行列を求める手法は一般的に煩雑である そこでそれ以外に Crmer の定理 掃き出し法などの解法も検証した 今回の研究は発展的で難しかったが 研究を通してより多角的で数学的な思考の一端を学べた.

More information

Microsoft Word - 1B2011.doc

Microsoft Word - 1B2011.doc 第 14 回モールの定理 ( 単純梁の場合 ) ( モールの定理とは何か?p.11) 例題 下記に示す単純梁の C 点のたわみ角 θ C と, たわみ δ C を求めよ ただし, 部材の曲げ 剛性は材軸に沿って一様で とする C D kn B 1.5m 0.5m 1.0m 解答 1 曲げモーメント図を描く,B 点の反力を求める kn kn 4 kn 曲げモーメント図を描く knm 先に得られた曲げモーメントの値を

More information

Information Theory

Information Theory 前回の復習 情報をコンパクトに表現するための符号化方式を考える 情報源符号化における基礎的な性質 一意復号可能性 瞬時復号可能性 クラフトの不等式 2 l 1 + + 2 l M 1 ハフマン符号の構成法 (2 元符号の場合 ) D. Huffman 1 前回の練習問題 : ハフマン符号 符号木を再帰的に構成し, 符号を作る A B C D E F 確率 0.3 0.2 0.2 0.1 0.1 0.1

More information

Math-Aquarium 例題 図形と計量 図形と計量 1 直角三角形と三角比 P 木の先端を P, 根元を Q とする A 地点の目の位置 A' から 木の先端への仰角が 30,A から 7m 離れた AQB=90 と なる B 地点の目の位置 B' から木の先端への仰角が 45 であ るとき,

Math-Aquarium 例題 図形と計量 図形と計量 1 直角三角形と三角比 P 木の先端を P, 根元を Q とする A 地点の目の位置 A' から 木の先端への仰角が 30,A から 7m 離れた AQB=90 と なる B 地点の目の位置 B' から木の先端への仰角が 45 であ るとき, 図形と計量 直角三角形と三角比 P 木の先端を P, 根元を Q とする 地点の目の位置 ' から 木の先端への仰角が 0, から 7m 離れた Q=90 と なる 地点の目の位置 ' から木の先端への仰角が であ るとき, 木の高さを求めよ ただし, 目の高さを.m とし, Q' を右の図のように定める ' 0 Q' '.m Q 7m 要点 PQ PQ PQ' =x とおき,' Q',' Q' を

More information

Microsoft PowerPoint - sakurada3.pptx

Microsoft PowerPoint - sakurada3.pptx チュートリアル :ProVerif による結合可能安全性の形式検証 櫻田英樹日本電信電話株式会社 NTT コミュニケーション科学基礎研究所 アウトライン 前半 :ProVerif の紹介 後半 :ProVerifを用いた結合可能安全性証明 [Dahl Damgård, EuroCrypt2014, eprint2013/296] の記号検証パート 2 ProVerif フランス国立情報学自動制御研究所

More information

. 角の二等分線と調和平均 平面上に点 を端点とする線分 と を重ならないようにとる, とし とする の二等分線が線分 と交わる点を とし 点 から に垂直に引いた直線が線分 と交わる点 とする 線分 の長さを求めてみよう 点 から に垂直な直線と および との交点をそれぞれ, Dとする つの直角三

. 角の二等分線と調和平均 平面上に点 を端点とする線分 と を重ならないようにとる, とし とする の二等分線が線分 と交わる点を とし 点 から に垂直に引いた直線が線分 と交わる点 とする 線分 の長さを求めてみよう 点 から に垂直な直線と および との交点をそれぞれ, Dとする つの直角三 角の二等分線で開くいろいろな平均 札幌旭丘高校中村文則 0. 数直線上に現れるいろいろな平均下図は 数 (, ) の調和平均 相乗平均 相加平均 二乗平均を数直線上に置いたものである, とし 直径 中心 である円を用いていろいろな平均の大小関係を表現するもっとも美しい配置方法であり その証明も容易である Q D E F < 相加平均 > (0), ( ), ( とすると 線分 ) の中点 の座標はである

More information

DVIOUT-OCTbook201

DVIOUT-OCTbook201 第 3 章 ヒルベルト空間 本節では, 量子系の理解のために必要な無限次元線形空間の理論であるヒルベルト空間の基本的事柄を概説する. 0.1 基本定理数体 K ( 実数体 R または複素数体 C; これらをスカラー体ともいう ) 上の線形空間の任意の元 x, y, z X と任意の λ K に対して, 1. hx, xi 0, = 0 x =0, 2. hx, yi = hy, xi, 3. hx,

More information

2011年度 筑波大・理系数学

2011年度 筑波大・理系数学 0 筑波大学 ( 理系 ) 前期日程問題 解答解説のページへ O を原点とするy 平面において, 直線 y= の を満たす部分をC とする () C 上に点 A( t, ) をとるとき, 線分 OA の垂直二等分線の方程式を求めよ () 点 A が C 全体を動くとき, 線分 OA の垂直二等分線が通過する範囲を求め, それ を図示せよ -- 0 筑波大学 ( 理系 ) 前期日程問題 解答解説のページへ

More information

Microsoft PowerPoint - ProD0107.ppt

Microsoft PowerPoint - ProD0107.ppt プログラミング D M 講義資料 教科書 :6 章 中田明夫 nakata@ist.osaka-u.ac.jp 2005/1/7 プログラミング D -M- 1 2005/1/7 プログラミング D -M- 2 リスト 1 リスト : 同じ型の値の並び val h=[10,6,7,8,~8,5,9]; val h = [10,6,7,8,~8,5,9]: int list val g=[1.0,4.5,

More information

2018年度 2次数学セレクション(微分と積分)

2018年度 2次数学セレクション(微分と積分) 08 次数学セレクション問題 [ 東京大 ] > 0 とし, f = x - x とおく () x で f ( x ) が単調に増加するための, についての条件を求めよ () 次の 条件を満たす点 (, b) の動きうる範囲を求め, 座標平面上に図示せよ 条件 : 方程式 f = bは相異なる 実数解をもつ 条件 : さらに, 方程式 f = bの解を < < とすると > である -- 08 次数学セレクション問題

More information

2015年度 信州大・医系数学

2015年度 信州大・医系数学 05 信州大学 ( 医系 ) 前期日程問題 解答解説のページへ 放物線 y = a + b + c ( a > 0) を C とし, 直線 y = -を l とする () 放物線 C が点 (, ) で直線 l と接し, かつ 軸と共有点をもつための a, b, c が満 たす必要十分条件を求めよ () a = 8 のとき, () の条件のもとで, 放物線 C と直線 l および 軸とで囲まれた部

More information

Microsoft Word - NumericalComputation.docx

Microsoft Word - NumericalComputation.docx 数値計算入門 武尾英哉. 離散数学と数値計算 数学的解法の中には理論計算では求められないものもある. 例えば, 定積分は, まずは積分 ( 被積分関数の原始関数をみつけること できなければ値を得ることはできない. また, ある関数の所定の値における微分値を得るには, まずその関数の微分ができなければならない. さらに代数方程式の解を得るためには, 解析的に代数方程式を解く必要がある. ところが, これらは必ずしも解析的に導けるとは限らない.

More information

Microsoft Word - 201hyouka-tangen-1.doc

Microsoft Word - 201hyouka-tangen-1.doc 数学 Ⅰ 評価規準の作成 ( 単元ごと ) 数学 Ⅰ の目標及び図形と計量について理解させ 基礎的な知識の習得と技能の習熟を図り それらを的確に活用する機能を伸ばすとともに 数学的な見方や考え方のよさを認識できるようにする 評価の観点の趣旨 式と不等式 二次関数及び図形と計量における考え方に関 心をもつとともに 数学的な見方や考え方のよさを認識し それらを事象の考察に活用しようとする 式と不等式 二次関数及び図形と計量における数学的な見

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション コンパイラとプログラミング言語 第 3 4 週 プログラミング言語の形式的な記述 2014 年 4 月 23 日 金岡晃 授業計画 第 1 週 (4/9) コンパイラの概要 第 8 週 (5/28) 下向き構文解析 / 構文解析プログラム 第 2 週 (4/16) コンパイラの構成 第 9 週 (6/4) 中間表現と意味解析 第 3 週 (4/23) プログラミング言語の形式的な記述 第 10 週

More information

曲線 = f () は を媒介変数とする自然な媒介変数表示 =,= f () をもつので, これを利用して説明する 以下,f () は定義域で連続であると仮定する 例えば, 直線 =c が曲線 = f () の漸近線になるとする 曲線 = f () 上の点 P(,f ()) が直線 =c に近づくこ

曲線 = f () は を媒介変数とする自然な媒介変数表示 =,= f () をもつので, これを利用して説明する 以下,f () は定義域で連続であると仮定する 例えば, 直線 =c が曲線 = f () の漸近線になるとする 曲線 = f () 上の点 P(,f ()) が直線 =c に近づくこ 伊伊伊伊伊伊伊伊伊伊 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 漸近線の求め方に関する考察 たまい玉井 かつき克樹 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 伊伊伊伊伊伊伊伊伊伊. 漸近線についての生徒からの質問 数学において図を使って直感的な説明を与えることは, 理解を深めるのに大いに役立つ

More information

景気指標の新しい動向

景気指標の新しい動向 内閣府経済社会総合研究所 経済分析 22 年第 166 号 4 時系列因子分析モデル 4.1 時系列因子分析モデル (Stock-Watson モデル の理論的解説 4.1.1 景気循環の状態空間表現 Stock and Watson (1989,1991 は観測される景気指標を状態空間表現と呼ば れるモデルで表し, 景気の状態を示す指標を開発した. 状態空間表現とは, わ れわれの目に見える実際に観測される変数は,

More information

Microsoft Word - 微分入門.doc

Microsoft Word - 微分入門.doc 基本公式 例題 0 定義式 f( ) 数 Ⅲ 微分入門 = の導関数を定義式にもとづいて計算しなさい 基本事項 ( f( ), g( ) が微分可能ならば ) y= f( ) g( ) のとき, y = y= f( ) g( ) h( ) のとき, y = ( f( ), g( ) が微分可能で, g( ) 0 ならば ) f( ) y = のとき, y = g ( ) とくに, y = のとき,

More information

Microsoft PowerPoint - DA2_2019.pptx

Microsoft PowerPoint - DA2_2019.pptx Johnon のアルゴリズム データ構造とアルゴリズム IⅠ 第 回最大フロー 疎なグラフ, 例えば E O( V lg V ) が仮定できる場合に向いている 隣接リスト表現を仮定する. 実行時間は O( V lg V + V E ). 上記の仮定の下で,Floyd-Warhall アルゴリズムよりも漸近的に高速 Johnon のアルゴリズム : アイデア (I) 辺重みが全部非負なら,Dikra

More information

Microsoft Word - 町田・全 H30学力スタ 別紙1 1年 数学Ⅰ.doc

Microsoft Word - 町田・全 H30学力スタ 別紙1 1年 数学Ⅰ.doc (1) 数と式 学習指導要領 都立町田高校 学力スタンダード ア 数と集合 ( ア ) 実数 根号を含む式の計算 数を実数まで拡張する意義を理解し 簡単な 循環小数を表す記号を用いて, 分数を循環小数で表 無理数の四則計算をすること すことができる 今まで学習してきた数の体系について整理し, 考察 しようとする 絶対値の意味と記号表示を理解している 根号を含む式の加法, 減法, 乗法の計算ができる

More information

Microsoft PowerPoint - 5.ppt [互換モード]

Microsoft PowerPoint - 5.ppt [互換モード] 5. チューリングマシンと計算 1 5-1. チューリングマシンとその計算 これまでのモデルでは テープに直接書き込むことができなかった また 入力テープヘッドの操作は右方向だけしか移動できなかった これらの制限を取り除いた機械を考える このような機械をチューリングマシン (Turing Machine,TM) と呼ぶ ( 実は TMは 現実のコンピュータの能力を持つ ) TM の特徴 (DFA との比較

More information

< BD96CA E B816989A B A>

< BD96CA E B816989A B A> 数 Ⅱ 平面ベクトル ( 黄色チャート ) () () ~ () " 図 # () () () - - () - () - - () % から %- から - -,- 略 () 求めるベクトルを とする S であるから,k となる実数 k がある このとき k k, であるから k すなわち k$, 求めるベクトルは --,- - -7- - -, から また ',' 7 (),,-,, -, -,

More information

vecrot

vecrot 1. ベクトル ベクトル : 方向を持つ量 ベクトルには 1 方向 2 大きさ ( 長さ ) という 2 つの属性がある ベクトルの例 : 物体の移動速度 移動量電場 磁場の強さ風速力トルクなど 2. ベクトルの表現 2.1 矢印で表現される 矢印の長さ : ベクトルの大きさ 矢印の向き : ベクトルの方向 2.2 2 個の点を用いて表現する 始点 () と終点 () を結ぶ半直線の向き : ベクトルの方向

More information

Information Theory

Information Theory 前回の復習 講義の概要 chapter 1: 情報を測る... エントロピーの定義 確率変数 X の ( 一次 ) エントロピー M H 1 (X) = p i log 2 p i (bit) i=1 M は実現値の個数,p i は i 番目の実現値が取られる確率 実現値 確率 表 裏 0.5 0.5 H 1 X = 0.5 log 2 0.5 0.5log 2 0.5 = 1bit 1 練習問題の解答

More information

混沌系工学特論 #5

混沌系工学特論 #5 混沌系工学特論 #5 情報科学研究科井上純一 URL : htt://chaosweb.comlex.eng.hokudai.ac.j/~j_inoue/ Mirror : htt://www5.u.so-net.ne.j/j_inoue/index.html 平成 17 年 11 月 14 日第 5 回講義 デジタルデータの転送と復元再考 P ({ σ} ) = ex σ ( σσ ) < ij>

More information

情報量と符号化

情報量と符号化 I. ここでの目的情報量の単位はビットで 2 種の文字を持つ記号の情報量が 1 ビットです ここでは 一般に n 種の文字を持つ記号の情報量を定義します 次に 出現する文字に偏りがある場合の平均情報量を定義します この平均情報量は 記号を適当に 0,1 で符号化する場合の平均符号長にほぼ等しくなることがわかります II. 情報量とは A. bit 情報量の単位としてbitが利用されます 1bitは0か1の情報を運びます

More information

PowerPoint Presentation

PowerPoint Presentation 最適化手法 第 回 工学部計数工学科 定兼邦彦 http://researchmap.jp/sada/resources/ 前回の補足 グラフのある点の隣接点をリストで表現すると説明したが, 単に隣接点の集合を持っていると思ってよい. 互いに素な集合のデータ構造でも, 単なる集合と思ってよい. 8 3 4 3 3 4 3 4 E v 重み 3 8 3 4 4 3 {{,},{3,8}} {{3,},{4,}}

More information

(Microsoft Word - 10ta320a_\220U\223\256\212w\223\301\230__6\217\315\221O\224\274\203\214\203W\203\201.docx)

(Microsoft Word - 10ta320a_\220U\223\256\212w\223\301\230__6\217\315\221O\224\274\203\214\203W\203\201.docx) 6 章スペクトルの平滑化 スペクトルの平滑化とはフーリエスペクトルやパワ スペクトルのギザギザを取り除き 滑らかにする操作のことをいう ただし 波のもっている本質的なものをゆがめてはいけない 図 6-7 パワ スペクトルの平滑化 6. 合積のフーリエ変換スペクトルの平滑化を学ぶ前に 合積とそのフーリエ変換について説明する 6. データ ウィンドウデータ ウィンドウの定義と特徴について説明する 6.3

More information

高ゼミサポSelectⅢ数学Ⅰ_解答.indd

高ゼミサポSelectⅢ数学Ⅰ_解答.indd 数と式 ⑴ 氏点00 次の式を展開せよ ( 各 6 点 ) ⑴ (a-)(a -a+) ⑵ (x+y+)(x+y-5) 次の式を因数分解せよ (⑴⑵ 各 6 点, ⑶⑷ 各 8 点 ) ⑴ x y+x -x-6y ⑵ x -x - ⑶ a +5b ⑷ (x+y+z+)(x+)+yz 数と式 ⑵ 氏点00 次の問いに答えよ ( 各 6 点 ) ⑴ 次の循環小数を分数で表せ. a-5 = ⑵ 次の等式を満たす実数

More information

Microsoft PowerPoint - H22制御工学I-10回.ppt

Microsoft PowerPoint - H22制御工学I-10回.ppt 制御工学 I 第 回 安定性 ラウス, フルビッツの安定判別 平成 年 6 月 日 /6/ 授業の予定 制御工学概論 ( 回 ) 制御技術は現在様々な工学分野において重要な基本技術となっている 工学における制御工学の位置づけと歴史について説明する さらに 制御システムの基本構成と種類を紹介する ラプラス変換 ( 回 ) 制御工学 特に古典制御ではラプラス変換が重要な役割を果たしている ラプラス変換と逆ラプラス変換の定義を紹介し

More information

<4D F736F F D E4F8E9F82C982A882AF82E98D7397F1>

<4D F736F F D E4F8E9F82C982A882AF82E98D7397F1> 3 三次における行列 要旨高校では ほとんど 2 2 の正方行列しか扱ってなく 三次の正方行列について考えてみたかったため 数 C で学んだ定理を三次の正方行列に応用して 自分たちで仮説を立てて求めていったら 空間における回転移動を表す行列 三次のケーリー ハミルトンの定理 三次における逆行列を求めたり 仮説をたてることができた. 目的 数 C で学んだ定理を三次の正方行列に応用する 2. 概要目的の到達点として

More information

文法と言語 ー文脈自由文法とLR構文解析2ー

文法と言語 ー文脈自由文法とLR構文解析2ー 文法と言語ー文脈自由文法とLR 構文解析 2 ー 和田俊和資料保存場所 http://vrl.sys.wakayama-u.ac.jp/~twada/syspro/ 前回までの復習 最右導出と上昇型構文解析 最右導出を前提とした場合, 上昇型の構文解析がしばしば用いられる. 上昇型構文解析では生成規則の右辺にマッチする部分を見つけ, それを左辺の非終端記号に置き換える 還元 (reduction)

More information

学習指導要領

学習指導要領 (1) 数と式 学習指導要領 数と式 (1) 式の計算二次の乗法公式及び因数分解の公式の理解を深め 式を多面的にみたり目的に応じて式を適切に変形したりすること 東京都立町田高等学校学力スタンダード 整式の加法 減法 乗法展開の公式を利用できる 式を1 つの文字におき換えることによって, 式の計算を簡略化することができる 式の形の特徴に着目して変形し, 展開の公式が適用できるようにすることができる 因数分解因数分解の公式を利用できる

More information

Probit , Mixed logit

Probit , Mixed logit Probit, Mixed logit 2016/5/16 スタートアップゼミ #5 B4 後藤祥孝 1 0. 目次 Probit モデルについて 1. モデル概要 2. 定式化と理解 3. 推定 Mixed logit モデルについて 4. モデル概要 5. 定式化と理解 6. 推定 2 1.Probit 概要 プロビットモデルとは. 効用関数の誤差項に多変量正規分布を仮定したもの. 誤差項には様々な要因が存在するため,

More information

2-category

2-category 2-ctegory lg-d http://lg-d.com/mth/kn_extension/ 2019 年 1 月 1 日 この PDF では g のように, 一部の記号で色を使用していますが, 色が分から なくても問題無いようにはなっています. 定義はここやここを参照. 圏の圏 Ct では, 対象 C, D Ct に対して Hom Ct (C, D) も圏になるのであった ( 関手が対象, 自然変換が射

More information

ソフトウェア基礎 Ⅰ Report#2 提出日 : 2009 年 8 月 11 日 所属 : 工学部情報工学科 学籍番号 : K 氏名 : 當銘孔太

ソフトウェア基礎 Ⅰ Report#2 提出日 : 2009 年 8 月 11 日 所属 : 工学部情報工学科 学籍番号 : K 氏名 : 當銘孔太 ソフトウェア基礎 Ⅰ Report#2 提出日 : 2009 年 8 月 11 日 所属 : 工学部情報工学科 学籍番号 : 095739 K 氏名 : 當銘孔太 1. UNIX における正規表現とは何か, 使い方の例を挙げて説明しなさい. 1.1 正規表現とは? 正規表現 ( 正則表現ともいう ) とは ある規則に基づいて文字列 ( 記号列 ) の集合を表す方法の 1 つです ファイル名表示で使うワイルドカードも正規表現の兄弟みたいなもの

More information

2019 年 6 月 4 日演習問題 I α, β > 0, A > 0 を定数として Cobb-Douglas 型関数 Y = F (K, L) = AK α L β (5) と定義します. (1) F KK, F KL, F LK, F LL を求めましょう. (2) 第 1 象限のすべての点

2019 年 6 月 4 日演習問題 I α, β > 0, A > 0 を定数として Cobb-Douglas 型関数 Y = F (K, L) = AK α L β (5) と定義します. (1) F KK, F KL, F LK, F LL を求めましょう. (2) 第 1 象限のすべての点 09 年 6 月 4 日演習問題 I α, β > 0, A > 0 を定数として Cobb-Douglas 型関数 Y = F K, L) = AK α L β 5) と定義します. ) F KK, F KL, F LK, F LL を求めましょう. ) 第 象限のすべての点 K, L) R ++ に対して F KK K, L) < 0, かつ dethf )K, L) > 0 6) を満たす α,

More information

Microsoft PowerPoint - mp11-02.pptx

Microsoft PowerPoint - mp11-02.pptx 数理計画法第 2 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 前回の復習 数理計画とは? 数理計画 ( 復習 ) 数理計画問題とは? 狭義には : 数理 ( 数学 ) を使って計画を立てるための問題 広義には : 与えられた評価尺度に関して最も良い解を求める問題

More information

調和系工学 ゲーム理論編

調和系工学 ゲーム理論編 ゲーム理論第三部 知的都市基盤工学 5 月 30 日 ( 水 5 限 (6:30~8:0 再掲 : 囚人のジレンマ 囚人のジレンマの利得行列 協調 (Cooperte:C プレイヤー 裏切 (Deect:D ( 協調 = 黙秘 裏切 = 自白 プレイヤー C 3,3 4, D,4, 右がプレイヤー の利得左がプレイヤー の利得 ナッシュ均衡点 プレイヤーの合理的な意思決定の結果 (C,C はナッシュ均衡ではない

More information

<8D828D5A838A817C A77425F91E6318FCD2E6D6364>

<8D828D5A838A817C A77425F91E6318FCD2E6D6364> 4 1 平面上のベクトル 1 ベクトルとその演算 例題 1 ベクトルの相等 次の問いに答えよ. ⑴ 右の図 1 は平行四辺形 である., と等しいベクトルをいえ. ⑵ 右の図 2 の中で互いに等しいベクトルをいえ. ただし, すべてのマス目は正方形である. 解 ⑴,= より, =,= より, = ⑵ 大きさと向きの等しいものを調べる. a =d, c = f d e f 1 右の図の長方形 において,

More information

1/17 平成 29 年 3 月 25 日 ( 土 ) 午前 11 時 1 分量子力学とクライン ゴルドン方程式 ( 学部 3 年次秋学期向 ) 量子力学とクライン ゴルドン方程式 素粒子の満たす場 y ( x,t) の運動方程式 : クライン ゴルドン方程式 : æ 3 ö ç å è m= 0

1/17 平成 29 年 3 月 25 日 ( 土 ) 午前 11 時 1 分量子力学とクライン ゴルドン方程式 ( 学部 3 年次秋学期向 ) 量子力学とクライン ゴルドン方程式 素粒子の満たす場 y ( x,t) の運動方程式 : クライン ゴルドン方程式 : æ 3 ö ç å è m= 0 /7 平成 9 年 月 5 日 ( 土 午前 時 分量子力学とクライン ゴルドン方程式 ( 学部 年次秋学期向 量子力学とクライン ゴルドン方程式 素粒子の満たす場 (,t の運動方程式 : クライン ゴルドン方程式 : æ ö ç å è = 0 c + ( t =, 0 (. = 0 ì æ = = = ö æ ö æ ö ç ì =,,,,,,, ç 0 = ç Ñ 0 = ç Ñ 0 Ñ Ñ

More information

ピタゴラスの定理の証明4

ピタゴラスの定理の証明4 [ 証明 ] この証明を論理的に厳密に行うには 何回か三角形 四角形の合同を証明しなくてはなりません 以下では 直感的な分かりやすさを重視して この証明を行いません 三角形 において であるとする 辺 を一辺とする正方形 を三角形 の外側につくる 辺 を一辺とする正方形 を三角形 の外側につくる 辺 を一辺とする正方形 Fを三角形 の外側につくる 直線 と直線 との交点を J とし 直線 と直線 F

More information

Microsoft Word - Chap17

Microsoft Word - Chap17 第 7 章化学反応に対する磁場効果における三重項機構 その 7.. 節の訂正 年 7 月 日. 節 章の9ページ の赤枠に記載した説明は間違いであった事に気付いた 以下に訂正する しかし.. 式は 結果的には正しいので安心して下さい 磁場 の存在下でのT 状態のハミルトニアン は ゼーマン項 と時間に依存するスピン-スピン相互作用の項 との和となる..=7.. g S = g S z = S z g

More information

<4D F736F F F696E74202D208AF489BD8A7782C CF97CA82A882DC82AF2E B8CDD8AB B83685D>

<4D F736F F F696E74202D208AF489BD8A7782C CF97CA82A882DC82AF2E B8CDD8AB B83685D> 幾何学と不変量 数学オリンピックの問題への応用 北海道大学 高等教育推進機構西森敏之 この講演では, 数学の長い歴史の中で見つけられた, 不変量 とよばれるものの考え方を, 実際に数学オリンピックの問題を解きながら, 紹介します 1. ウオーミング アップ まず, 少し脳細胞のウオーミング アップをします 定義 ( 分割合同 ) 平面上の 2 つの多角形 P と Q が分割合同とは, 多角形 P をいくつかの直線で切って小片に分けてから,

More information

Microsoft Word - ComplexGeometry1.docx

Microsoft Word - ComplexGeometry1.docx Complex Geometry Speaer(s): Has-Joachim Hei (Imperial College, Loo) vieo のページ : https://www.msri.org/summer_schools/72/scheules/8495 Agea:. 正則関数 (Holomorphic Fuctio) とは 2. ワイエルストラスの予備定理 3. ハルトークスの定理 記号

More information

Microsoft PowerPoint - prog08.ppt

Microsoft PowerPoint - prog08.ppt プログラミング言語 2 第 07 回 (2007 年 06 月 25 日 ) 1 今日の配布物 片面の用紙 1 枚 今日の課題が書かれています 本日の出欠を兼ねています 2/27 1 今日やること http://www.tnlab.ice.uec.ac.jp/~s-okubo/class/language/ にアクセスすると 教材があります 2007 年 06 月 25 日分と書いてある部分が 本日の教材です

More information

memo

memo 数理情報工学特論第一 機械学習とデータマイニング 4 章 : 教師なし学習 3 かしまひさし 鹿島久嗣 ( 数理 6 研 ) kashima@mist.i.~ DEPARTMENT OF MATHEMATICAL INFORMATICS 1 グラフィカルモデルについて学びます グラフィカルモデル グラフィカルラッソ グラフィカルラッソの推定アルゴリズム 2 グラフィカルモデル 3 教師なし学習の主要タスクは

More information

ファイナンスのための数学基礎 第1回 オリエンテーション、ベクトル

ファイナンスのための数学基礎 第1回 オリエンテーション、ベクトル 時系列分析 変量時系列モデルとその性質 担当 : 長倉大輔 ( ながくらだいすけ 時系列モデル 時系列モデルとは時系列データを生み出すメカニズムとなるものである これは実際には未知である 私たちにできるのは観測された時系列データからその背後にある時系列モデルを推測 推定するだけである 以下ではいくつかの代表的な時系列モデルを考察する 自己回帰モデル (Auoregressive Model もっとも頻繁に使われる時系列モデルは自己回帰モデル

More information

OCW-iダランベールの原理

OCW-iダランベールの原理 講義名連続体力学配布資料 OCW- 第 2 回ダランベールの原理 無機材料工学科准教授安田公一 1 はじめに今回の講義では, まず, 前半でダランベールの原理について説明する これを用いると, 動力学の問題を静力学の問題として解くことができ, さらに, 前回の仮想仕事の原理を適用すると動力学問題も簡単に解くことができるようになる また, 後半では, ダランベールの原理の応用として ラグランジュ方程式の導出を示す

More information

学習指導要領

学習指導要領 (1) 数と式 ア整式 ( ア ) 式の展開と因数分解二次の乗法公式及び因数分解の公式の理解を深め 式を多面的にみたり目的に応じて式を適切に変形したりすること (ax b)(cx d) acx (ad bc)x bd などの基本的な公式を活用して 二次式の展開や因数分解ができる また 式の置き換えや一文字に着目するなどして 展開 因数分解ができる ( 例 ) 次の問に答えよ (1) (3x a)(4x

More information

Java Scriptプログラミング入門 3.6~ 茨城大学工学部情報工学科 08T4018Y 小幡智裕

Java Scriptプログラミング入門 3.6~ 茨城大学工学部情報工学科 08T4018Y  小幡智裕 Java Script プログラミング入門 3-6~3-7 茨城大学工学部情報工学科 08T4018Y 小幡智裕 3-6 組み込み関数 組み込み関数とは JavaScript の内部にあらかじめ用意されている関数のこと ユーザ定義の関数と同様に 関数名のみで呼び出すことができる 3-6-1 文字列を式として評価する関数 eval() 関数 引数 : string 式として評価する文字列 戻り値 :

More information

画像処理工学

画像処理工学 画像処理工学 画像の空間周波数解析とテクスチャ特徴 フーリエ変換の基本概念 信号波形のフーリエ変換 信号波形を周波数の異なる三角関数 ( 正弦波など ) に分解する 逆に, 周波数の異なる三角関数を重ねあわせることにより, 任意の信号波形を合成できる 正弦波の重ね合わせによる矩形波の表現 フーリエ変換の基本概念 フーリエ変換 次元信号 f (t) のフーリエ変換 変換 ( ω) ( ) ωt F f

More information

Functional Programming

Functional Programming PROGRAMMING IN HASKELL プログラミング Haskell Chapter 7 - Higher-Order Functions 高階関数 愛知県立大学情報科学部計算機言語論 ( 山本晋一郎 大久保弘崇 2013 年 ) 講義資料オリジナルは http://www.cs.nott.ac.uk/~gmh/book.html を参照のこと 0 Introduction カリー化により

More information

第6章 実験モード解析

第6章 実験モード解析 第 6 章実験モード解析 6. 実験モード解析とは 6. 有限自由度系の実験モード解析 6.3 連続体の実験モード解析 6. 実験モード解析とは 実験モード解析とは加振実験によって測定された外力と応答を用いてモードパラメータ ( 固有振動数, モード減衰比, 正規固有モードなど ) を求める ( 同定する ) 方法である. 力計 試験体 変位計 / 加速度計 実験モード解析の概念 時間領域データを利用する方法

More information

学習指導要領

学習指導要領 (1 ) 数と式 ア数と集合 ( ア ) 実数数を実数まで拡張する意義を理解し 簡単な無理数の四則計算をすること 自然数 整数 有理数 無理数の包含関係など 実 数の構成を理解する ( 例 ) 次の空欄に適当な言葉をいれて, 数の集合を表しなさい 実数の絶対値が実数と対応する点と原点との距離で あることを理解する ( 例 ) 次の値を求めよ (1) () 6 置き換えなどを利用して 三項の無理数の乗法の計

More information