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

Size: px
Start display at page:

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

Transcription

1 オートマトン 形式言語及び演習 3. 酒井正彦 とは ( 正則表現, Regular Expression) オートマトン : 言語を定義する機械 : 言語を記号列で定義 - 記述しやすい ( ユーザフレンドリ ) 例 : UNIX の grep コマンド - UNIX の lex, flex ツールの入力の記述 準備 言語上の演算 和 : 集合の和と同じ L M = {w w L または w M} 連接 : L M = {w w = x y, x L, y M} (L M は L.M とも書く ) ベキ : L 0 = {ε}, L 1 = L, L k+1 = L.L k クリーネ閉包 : L = L i i=0 問 : 0, i, はどんな集合? 3-1 / / / 29 準備 補題 1: 任意の言語 M, N, P に対して 以下が成り立つ (MN)P = M(NP) 証明 : 文字列 x, y, z に対して (xy)z = x(yz) が成り立つことから証明できる 補題 2: 任意の言語 M に対して M i M j = M i+j が成り立つ 証明 : i に関する帰納法で示す - i = 0 のときは明らか - i > 0 のとき 左辺 =(MM i 1 )M j = M(M i 1 M j ) = M(M i+j 1 ) = 右辺 E とそれが表す集合 L(E) の再帰的定義基底 : - ε はで L(ε) = {ε} - はで L( ) = { } - a Σ のとき a はで L(a) = {a} 帰納 :E, F がのとき - (E) はで L((E)) = L(E) - E+F はで L(E+F) = L(E) L(F) - E.F はで L(E.F) = L(E).L(F) - E はで L(E ) = (L(E)) 例 :0 と 1 が交互に現われる文字列全体を表す (01) + (10) + 0(10) + 1(01) 別の表現も可能 (ε + 1)(01) (ε + 0) 演算の優先順序,., + ( 結合の強い方から順に ) 例 : は (0(1 )) + 1 を表す 3-4 / / / 29

2 性質の例 : 任意の E に対して L(E E ) = L(E ) が成り立つ 証明 : L(E E ) = (L(E)).(L(E)) より 任意の言語 M に対して M M = M を示せば十分である w M ならば w M M は ε M より明らか w M M ならば w M を証明する w M M とすると w M i M j を満たす i, j が存在する スライド p.3-4 の補題 2 より w M i+j であるから w M 有限オートマトンと 有限オートマトンとの等価性の証明手順 有限オートマトンからへの変換定理 3.4: 任意の DFA A = (Q, Σ, δ, q 0, F) について L(R) = L(A) を満たす R が存在する証明 : A の状態を {1, 2,..., n} 初期状態を 1 とする A の状態 i から j に至る経路 ( 文字列 ) で k より大きな状態を経由しない文字列全体を表すを で表す 3-7 / / / 29 有限オートマトンからへの変換 証明 ( 続き ): が分かれば L(R) = L(A) を満たす R は R (n) 1j の和 ( ただし j は全ての受理状態 ) で与えられる の k に関する再帰的定義基底 : i j かつ δ(i, a) = j を満たす a を a 1, a 2,..., a m とするとき R (0) = a 1 + a 2 + +a m ただし m = 0 のとき R (0) = i = j かつ δ(i, a) = j を満たす a を a 1, a 2,..., a m とするとき R (0) = a 1 + a 2 + +a m + ε 有限オートマトンからへの変換 証明 ( 続き ): の k に関する再帰的定義 ( 続き ) 帰納 : = R (k 1) + R (k 1) ik (R (k 1) kk ) R (k 1) kj 有限オートマトンからへの変換 例 : 次の DFA が認識する言語を表すを構成する まず R (0) を求める 3-10 / / / 29

3 有限オートマトンからへの変換 以降で使う の簡単化の規則 - R(S + T )=RS + RT - (S + T )R=SR + TR - R (ε + R)=R =(ε + R)R - R i + R =R - (ε + R) = R - R + RS = RS - ε = ε - R = R = - + R = R + = R 有限オートマトンからへの変換 次に R (1) を求める R (1) = R (0) + R (0) i1 (R (0) 11 ) R (0) 1j 有限オートマトンからへの変換 次に R (2) を求める R (2) = R (1) + R (1) i2 (R (1) 22 ) R (1) 2j 3-13 / / / 29 有限オートマトンからへの変換 よって 有限オートマトンからへの変換 II 状態消去法 : ラベルをに拡張したオートマトンを考え 状態を消去する ( 前回の方法より効率的 ) 有限オートマトンからへの変換 II 状態 s を消去する 得られたは R (2) 12 = 1 0(0 + 1) 3-16 / / / 29

4 有限オートマトンからへの変換 II 各々の受理状態 q について q と q 0 以外の状態を全て消去する q q 0 なら 対応するは (R+SU T ) SU 有限オートマトンからへの変換 II 例 : 最後の 2 文字目か 3 文字目に 1 を持つ列を受理するオートマトン 有限オートマトンからへの変換 II 例 ( 続き ): q = q 0 なら 対応するは R ラベルをに変更 状態 C を消去し (0 + 1) 1(0 + 1)(0 + 1) を得る 状態 B を消去 状態 D を消去し (0 + 1) 1(0 + 1) を得る 求めたいは これらの和 3-19 / / / 29 有限オートマトンからへの変換 II 例 ( 続き ): 以上から (0 + 1) 1(0 + 1)(0 + 1) + (0 + 1) 1(0 + 1) を得る からオートマトンへの変換 定理 3.7: 任意の R について L(A) = L(R) を満たす ε-nfa が存在する 証明 :R の構成に基づいて帰納的に A を定義する 基底 :ε a と等価なオートマトンは 以下の通り からオートマトンへの変換定理 3.7 の証明 ( 続き ) 帰納 :R + S RS R と等価なオートマトンは 以下の通り 3-22 / / / 29

5 からオートマトンへの変換例 :(0 + 1) 1(0 + 1) と等価な ε-nfa を作る の代数的法則 結合法則と交換法則 - L + M=M + L - L + (M + N)=(L + M) + N - L(MN)=(LM)N - LM ML 単位限と零元 - + L=L + =L - εl=lε=l - L=L = の代数的法則 分配法則 - R(S + T )=RS + RT - (R + S)T =RT + ST 冪等法則 - R + R=R 閉包に関する法則 - (R ) =R - =ε - ε =ε - R + =RR =R R - R =R + + ε 3-25 / / / 29 の代数的法則 の代数的法則 に関する法則の発見 検証 ( 機械的 ) - 例 :E と F をとするとき E+F = F +E を示す方法 - E を a に F を b に固定する - L(a + b) = L(b + a) を自動検証する (4 章 ) この手法は +. の演算のみを使う限り正しい ( 集合の積では成立しない 教科書 p.135 の囲み記事を参照 ) 例 : (E+F ) =(E F ) の証明には (a + b) と (a b ) の等価性を示せば十分である 例 : E =E E の証明には a と a a の等価性を示せば十分である 問 : E+FE=(E+F)E は成立するか? 3-28 / / 29

オートマトン 形式言語及び演習 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

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

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

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

More information

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

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

More information

オートマトンと言語

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

More information

情報数理学

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

More information

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

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

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

離散数学

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

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

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

Microsoft PowerPoint - 2.ppt [互換モード] 0 章数学基礎 1 大学では 高校より厳密に議論を行う そのために 議論の議論の対象を明確にする必要がある 集合 ( 定義 ) 集合 物の集まりである集合 X に対して X を構成している物を X の要素または元という 集合については 3 セメスタ開講の 離散数学 で詳しく扱う 2 集合の表現 1. 要素を明示する表現 ( 外延的表現 ) 中括弧で 囲う X = {0,1, 2,3} 慣用的に 英大文字を用いる

More information

PowerPoint Presentation

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

More information

経済数学演習問題 2018 年 5 月 29 日 I a, b, c R n に対して a + b + c 2 = a 2 + b 2 + c 2 + 2( a, b) + 2( b, c) + 2( a, c) が成立することを示しましょう.( 線型代数学 教科書 13 ページ 演習 1.17)

経済数学演習問題 2018 年 5 月 29 日 I a, b, c R n に対して a + b + c 2 = a 2 + b 2 + c 2 + 2( a, b) + 2( b, c) + 2( a, c) が成立することを示しましょう.( 線型代数学 教科書 13 ページ 演習 1.17) 経済数学演習問題 8 年 月 9 日 I a, b, c R n に対して a + b + c a + b + c + a, b + b, c + a, c が成立することを示しましょう. 線型代数学 教科書 ページ 演習.7 II a R n がすべての x R n に対して垂直, すなわち a, x x R n が成立するとします. このとき a となることを示しましょう. 線型代数学 教科書

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

融合規則 ( もっとも簡単な形, 選言的三段論法 ) 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

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

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

More information

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

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

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 - 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

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

<4D F736F F D E4F8E9F82C982A882AF82E98D7397F1>

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

More information

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

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

More information

行列、ベクトル

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

More information

線形代数とは

線形代数とは 線形代数とは 第一回ベクトル 教科書 エクササイズ線形代数 立花俊一 成田清正著 共立出版 必要最低限のことに限る 得意な人には物足りないかもしれません 線形代数とは何をするもの? 線形関係 y 直線 yもも 次式で登場する (( 次の形 ) 線形 ただし 次元の話世の中は 3 次元 [4[ 次元 ] 次元 3 次元 4 次元 はどうやって直線を表すの? ベクトルや行列の概念 y A ベクトルを使うと

More information

航空機の運動方程式

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

More information

An Automated Proof of Equivalence on Quantum Cryptographic Protocols

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

More information

オートマトンと言語理論 テキスト 成蹊大学理工学部情報科学科 山本真基 ii iii 1 1 1.1.................................. 1 1.2................................ 5 1.3............................. 5 2 7 2.1..................................

More information

vecrot

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

More information

nlp1-04a.key

nlp1-04a.key 自然言語処理論 I. 文法 ( 構文解析 ) その 構文解析 sytctic lysis, prsig 文の構文的な構造を決定すること句構造文法が使われることが多い文法による構文木は一般に複数ある 構文木の違い = 解釈の違い 構文解析の目的 句構造文法の規則を使って, 文を生成できる構文木を全て見つけだすこと 文法が入力文を生成できるかどうかを調べるだけではない pro I 構文解析とは 構文木の違い

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

ソフトウェア基礎 Ⅰ 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

PowerPoint Presentation

PowerPoint Presentation 様相論理と時相論理 Kripke 構造 K = S, R, L S: 状態の集合 ( 無限かもしれない ) R: 状態間の遷移関係 R S S L: 状態から命題記号の集合への写像 L(s) は 状態 s S において成り立つ命題記号の集合を与える Kripke 構造 K = S, R, L G = S, R 有向グラフ Kripke 構造 K = S, R, L L : S 2 Atom Atom

More information

NOTE P, A,. A P ( A, P ),,.,. P A. (set) (set), (). (element), (element).,.,. ( A, B, X, Y, P ), { } (),..3 (union) A, B,A B, A B (union),. A B = {x x

NOTE P, A,. A P ( A, P ),,.,. P A. (set) (set), (). (element), (element).,.,. ( A, B, X, Y, P ), { } (),..3 (union) A, B,A B, A B (union),. A B = {x x 2. (set)............... 2.2,.... 2.3 (union)............ 2.4 (intersection)......... 2.5 (power set)......... 3.6 (cartesian product set)... 3 2, 3 2. (length)........ 3 2.2 (epsilon)............ 3 2.3

More information

Microsoft PowerPoint - DA2_2017.pptx

Microsoft PowerPoint - DA2_2017.pptx // データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (II)/ 全点対最短路 トポロジカル ソート順による緩和 トポロジカル ソート順に緩和 閉路のない有向グラフ限定 閉路がないならトポロジカル ソート順に緩和するのがベルマン フォードより速い Θ(V + E) 方針 グラフをトポロジカル ソートして頂点に線形順序を与える ソート順に頂点を選び, その頂点の出辺を緩和する 各頂点は一回だけ選択される

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

スライド 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

. R R D e R R 7 () r r R R () l t t R R 7 l () () R r rr r r n r n r r 3 6 r 88 R r 360 r = e t t = e r t rt rt, r t, r 3 t, r t R R R R R D = {e, r,

. R R D e R R 7 () r r R R () l t t R R 7 l () () R r rr r r n r n r r 3 6 r 88 R r 360 r = e t t = e r t rt rt, r t, r 3 t, r t R R R R R D = {e, r, 3 3 3 e X X X X X X . R R D e R R 7 () r r R R () l t t R R 7 l () () R r rr r r n r n r r 3 6 r 88 R r 360 r = e t t = e r t rt rt, r t, r 3 t, r t R R R R R D = {e, r, r, r 3, r, t, rt, r t, r 3 t, r

More information

調和系工学 ゲーム理論編

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

More information

補足 中学で学習したフレミング左手の法則 ( 電 磁 力 ) と関連付けると覚えやすい 電磁力は電流と磁界の外積で表される 力 F 磁 電磁力 F li 右ねじの回転の向き電 li ( l は導線の長さ ) 補足 有向線分とベクトル有向線分 : 矢印の位

補足 中学で学習したフレミング左手の法則 ( 電 磁 力 ) と関連付けると覚えやすい 電磁力は電流と磁界の外積で表される 力 F 磁 電磁力 F li 右ねじの回転の向き電 li ( l は導線の長さ ) 補足 有向線分とベクトル有向線分 : 矢印の位 http://totemt.sur.ne.p 外積 ( ベクトル積 ) の活用 ( 面積, 法線ベクトル, 平面の方程式 ) 3 次元空間の つのベクトルの積が つのベクトルを与えるようなベクトルの掛け算 ベクトルの積がベクトルを与えることからベクトル積とも呼ばれる これに対し内積は符号と大きさをもつ量 ( スカラー量 ) を与えるので, スカラー積とも呼ばれる 外積を使うと, 平行四辺形や三角形の面積,

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

Microsoft Word - thesis.doc

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

More information

Microsoft PowerPoint - LogicCircuits01.pptx

Microsoft PowerPoint - LogicCircuits01.pptx 論理回路 第 回論理回路の数学的基本 - ブール代数 http://www.info.kindai.ac.jp/lc 38 号館 4 階 N-4 内線 5459 takasi-i@info.kindai.ac.jp 本科目の内容 電子計算機 computer の構成 ソフトウェア 複数のプログラムの組み合わせ オペレーティングシステム アプリケーション等 ハードウェア 複数の回路 circuit の組み合わせ

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

書式に示すように表示したい文字列をダブルクォーテーション (") の間に書けば良い ダブルクォーテーションで囲まれた文字列は 文字列リテラル と呼ばれる プログラム中では以下のように用いる プログラム例 1 printf(" 情報処理基礎 "); printf("c 言語の練習 "); printf

書式に示すように表示したい文字列をダブルクォーテーション () の間に書けば良い ダブルクォーテーションで囲まれた文字列は 文字列リテラル と呼ばれる プログラム中では以下のように用いる プログラム例 1 printf( 情報処理基礎 ); printf(c 言語の練習 ); printf 情報処理基礎 C 言語についてプログラミング言語は 1950 年以前の機械語 アセンブリ言語 ( アセンブラ ) の開発を始めとして 現在までに非常に多くの言語が開発 発表された 情報処理基礎で習う C 言語は 1972 年にアメリカの AT&T ベル研究所でオペレーションシステムである UNIX を作成するために開発された C 言語は現在使われている多数のプログラミング言語に大きな影響を与えている

More information

トポス alg-d 年 5 月 5 日 1 トポス 定義. P, Q: C op Set を関手とする.P が Q の部分関手 ( 記号で P Q と書く ) 自然変換 θ : P Q で 各 a C について θ

トポス alg-d 年 5 月 5 日 1 トポス 定義. P, Q: C op Set を関手とする.P が Q の部分関手 ( 記号で P Q と書く ) 自然変換 θ : P Q で 各 a C について θ トポス alg-d http://alg-d.com/math/kan_extension/ 2018 年 5 月 5 日 1 トポス 定義. P, Q: C op Set を関手とする.P が Q の部分関手 ( 記号で P Q と書く ) 自然変換 θ : P Q で 各 a C について θ a : P a Qa が包含写像になっているもの が存在する. P Q を部分関手とすると, 自然性より,f

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

( 最初の等号は,N =0, 番目は,j= のとき j =0 による ) j>r のときは p =0 から和の上限は r で十分 定義 命題 3 ⑵ 実数 ( 0) に対して, ⑴ =[] []=( 0 または ) =[6]+[] [4] [3] [] =( 0 または ) 実数 に対して, π()

( 最初の等号は,N =0, 番目は,j= のとき j =0 による ) j>r のときは p =0 から和の上限は r で十分 定義 命題 3 ⑵ 実数 ( 0) に対して, ⑴ =[] []=( 0 または ) =[6]+[] [4] [3] [] =( 0 または ) 実数 に対して, π() 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 数研通信 70 号を読んで チェビシェフの定理の精密化 と.5 の間に素数がある 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 さい才 の 野 せ瀬 いちろう 一郎 伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊 0. はじめに このたび,

More information

Microsoft PowerPoint - mp13-07.pptx

Microsoft PowerPoint - mp13-07.pptx 数理計画法 ( 数理最適化 ) 第 7 回 ネットワーク最適化 最大流問題と増加路アルゴリズム 担当 : 塩浦昭義 ( 情報科学研究科准教授 ) hiour@di.i.ohoku.c.jp ネットワーク最適化問題 ( 無向, 有向 ) グラフ 頂点 (verex, 接点, 点 ) が枝 (edge, 辺, 線 ) で結ばれたもの ネットワーク 頂点や枝に数値データ ( 距離, コストなど ) が付加されたもの

More information

テンソル ( その ) テンソル ( その ) スカラー ( 階のテンソル ) スカラー ( 階のテンソル ) 階数 ベクトル ( 階のテンソル ) ベクトル ( 階のテンソル ) 行列表現 シンボリック表現 [ ]

テンソル ( その ) テンソル ( その ) スカラー ( 階のテンソル ) スカラー ( 階のテンソル ) 階数 ベクトル ( 階のテンソル ) ベクトル ( 階のテンソル ) 行列表現 シンボリック表現 [ ] Tsor th-ordr tsor by dcl xprsso m m Lm m k m k L mk kk quott rul by symbolc xprsso Lk X thrd-ordr tsor cotrcto j j Copyrght s rsrvd. No prt of ths documt my b rproducd for proft. テンソル ( その ) テンソル ( その

More information

Q E Q T a k Q Q Q T Q =

Q E Q T a k Q Q Q T Q = i 415 q q q q Q E Q T a k Q Q Q T Q = 10 30 j 19 25 22 E 23 R 9 i i V 25 60 1 20 1 18 59R1416R30 3018 1211931 30025R 10T1T 425R 11 50 101233 162 633315 22E1011 10T q 26T10T 12 3030 12 12 24 100 1E20 62

More information

数学の世界

数学の世界 東京女子大学文理学部数学の世界 (2002 年度 ) 永島孝 17 6 行列式の基本法則と効率的な計算法 基本法則 三次以上の行列式についても, 二次の場合と同様な法則がなりたつ ここには三次の場合を例示するが, 四次以上でも同様である 1 単位行列の行列式の値は 1 である すなわち 1 0 0 0 1 0 1 0 0 1 2 二つの列を入れ替えると行列式の値は 1 倍になる 例えば a 13 a

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 PowerPoint ppt

Microsoft PowerPoint ppt 仮想マシン (2), コード生成 http://cis.k.hosei.ac.jp/~asasaki /lect/compiler/2007-1204.pdf ( 訂正版 ) 1 概要 仮想マシン 概要 ( 復習 ) 制御命令 出力命令 コード生成 式のコード生成 文 文の列のコード生成 記号表 2 演習で作るコンパイラの例 test.hcc Int main() { int i j; i = 3;

More information

<4D F736F F D A788EA8E9F95FB92F68EAE>

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

More information

油圧1.indd

油圧1.indd ff ff ff ff f f ff ff ff f f f f f f f f f f f f f f ff ff! f f f f f f f ff ff f f ff f f f f f f f f f f f f f f f f f f f f f f f f f f f f f f S 9 M6 M6 M6 M. 6 6 R/ P M. M. M. M. f f f 96 f f f M.

More information

(35H-3).pm

(35H-3).pm ff f f f f f f f f f f f f f ff ff ff f f ff ff ff f ff ff! f f f f f f f f f f f f f ff ff f f ff f f f f f f f f f f f f f f f f f f f f f S f f f f f f 9 M6 M6 M6 M. M. M. M. M. 6 6 9 R/ R/ P M. M.

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

Microsoft PowerPoint L03-Syntex and Semantics-1-students ( )

Microsoft PowerPoint L03-Syntex and Semantics-1-students ( ) プログラミング言語論 A (Concepts on Programming Languages) 趙建軍 (Jianjun Zhao) http://stap.ait.kyushu-u.ac.jp/~zhao/course/2018/concepts of Programming Languages.html 1 第 3 回 構文と意味 (1) (Syntax and Semantics) 2017.04.26

More information

情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤

情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤 情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤 2017.12.7 前回の演習問題の解答例 1. 四則演算のできる計算機のプログラム ( 括弧も使える ) 2. 実数の扱える四則演算の計算機のプログラム ( 実数 も というより実数 が が正しかったです ) 3. 変数も扱える四則演算の計算機のプログラム ( 変数と実数が扱える ) 演習問題 1 で行うべきこと

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

4 月 東京都立蔵前工業高等学校平成 30 年度教科 ( 工業 ) 科目 ( プログラミング技術 ) 年間授業計画 教科 :( 工業 ) 科目 :( プログラミング技術 ) 単位数 : 2 単位 対象学年組 :( 第 3 学年電気科 ) 教科担当者 :( 高橋寛 三枝明夫 ) 使用教科書 :( プロ

4 月 東京都立蔵前工業高等学校平成 30 年度教科 ( 工業 ) 科目 ( プログラミング技術 ) 年間授業計画 教科 :( 工業 ) 科目 :( プログラミング技術 ) 単位数 : 2 単位 対象学年組 :( 第 3 学年電気科 ) 教科担当者 :( 高橋寛 三枝明夫 ) 使用教科書 :( プロ 4 東京都立蔵前工業高等学校平成 30 年度教科 ( 工業 ) 科目 ( プログラミング技術 ) 年間授業計画 教科 :( 工業 ) 科目 :( プログラミング技術 ) 単位数 : 2 単位 対象学年組 :( 第 3 学年電気科 ) 教科担当者 :( 高橋寛 三枝明夫 ) 使用教科書 :( プログラミング技術 工業 333 実教出版 ) 共通 : 科目 プログラミング技術 のオリエンテーション プログラミング技術は

More information

Microsoft Word - K-ピタゴラス数.doc

Microsoft Word - K-ピタゴラス数.doc - ピタゴラス数の代数と幾何学 津山工業高等専門学校 菅原孝慈 ( 情報工学科 年 ) 野山由貴 ( 情報工学科 年 ) 草地弘幸 ( 電子制御工学科 年 ) もくじ * 第 章ピタゴラス数の幾何学 * 第 章ピタゴラス数の代数学 * 第 3 章代数的極小元の幾何学の考察 * 第 章ピタゴラス数の幾何学的研究の動機 交点に注目すると, つの曲線が直交しているようにみえる. これらは本当に直交しているのだろうか.

More information

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

Microsoft PowerPoint - 03BNFScanner.ppt [互換モード] コンパイラ理論 3 BNF と EBNF そして構文解析へ 3 章ステップ 1: 問題の把握 櫻井彰人 と文法 と EBNF 言語仕様 プログラムと言語仕様との関係 コンパイラ入門 C# で学ぶ理論と実践 より 3.2 BNF(Backus Naur Form) 文法 を記述する表記法 コンピュータ言語を表す為に使われることが多い 英文法 単語と単語の構成 関係を表す 5 文型は単語の品詞から英文の型を表現している

More information

Microsoft PowerPoint - sakurada3.pptx

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

More information

例 e 指数関数的に減衰する信号を h( a < + a a すると, それらのラプラス変換は, H ( ) { e } e インパルス応答が h( a < ( ただし a >, U( ) { } となるシステムにステップ信号 ( y( のラプラス変換 Y () は, Y ( ) H ( ) X (

例 e 指数関数的に減衰する信号を h( a < + a a すると, それらのラプラス変換は, H ( ) { e } e インパルス応答が h( a < ( ただし a >, U( ) { } となるシステムにステップ信号 ( y( のラプラス変換 Y () は, Y ( ) H ( ) X ( 第 週ラプラス変換 教科書 p.34~ 目標ラプラス変換の定義と意味を理解する フーリエ変換や Z 変換と並ぶ 信号解析やシステム設計における重要なツール ラプラス変換は波動現象や電気回路など様々な分野で 微分方程式を解くために利用されてきた ラプラス変換を用いることで微分方程式は代数方程式に変換される また 工学上使われる主要な関数のラプラス変換は簡単な形の関数で表されるので これを ラプラス変換表

More information

Microsoft PowerPoint - ロボットの運動学forUpload'C5Q [互換モード]

Microsoft PowerPoint - ロボットの運動学forUpload'C5Q [互換モード] ロボットの運動学 順運動学とは 座標系の回転と並進 同次座標変換行列 Denavit-Hartenberg の表記法 多関節ロボットの順運動学 レポート課題 & 中間試験について 逆運動学とは ヤコビアン行列 運動方程式 ( 微分方程式 ) ロボットの運動学 動力学 Equation of motion f ( ( t), ( t), ( t)) τ( t) 姿勢 ( 関節角の組合せ ) Posture

More information

2015年度 2次数学セレクション(整数と数列)

2015年度 2次数学セレクション(整数と数列) 05 次数学セレクション問題 [ 千葉大 文 ] k, m, を自然数とする 以下の問いに答えよ () k を 7 で割った余りが 4 であるとする このとき, k を 3 で割った余りは であることを示せ () 4m+ 5が 3 で割り切れるとする このとき, m を 7 で割った余りは 4 ではないことを示せ -- 05 次数学セレクション問題 [ 九州大 理 ] 以下の問いに答えよ () が正の偶数のとき,

More information

A a b c d a b a b c d e a b c g h f i d e f g h i M a b c a b c d M a M b c d a b a b a M b a b a b c a b a M a a M a c d b a b c d a b a b a M c d a b e c M f a b c d e f E F d e a f a M bm c d a M b

More information

代数 幾何 < ベクトル > 1 ベクトルの演算 和 差 実数倍については 文字の計算と同様 2 ベクトルの成分表示 平面ベクトル : a x e y e x, ) ( 1 y1 空間ベクトル : a x e y e z e x, y, ) ( 1 1 z1

代数 幾何 < ベクトル > 1 ベクトルの演算 和 差 実数倍については 文字の計算と同様 2 ベクトルの成分表示 平面ベクトル : a x e y e x, ) ( 1 y1 空間ベクトル : a x e y e z e x, y, ) ( 1 1 z1 代数 幾何 < ベクトル > ベクトルの演算 和 差 実数倍については 文字の計算と同様 ベクトルの成分表示 平面ベクトル :, 空間ベクトル : z,, z 成分での計算ができるようにすること ベクトルの内積 : os 平面ベクトル :,, 空間ベクトル :,,,, z z zz 4 ベクトルの大きさ 平面上 : 空間上 : z は 良く用いられる 5 m: に分ける点 : m m 図形への応用

More information

<8D828D5A838A817C A77425F91E6318FCD2E6D6364>

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

More information

数理論理

数理論理 オートマトンと計算理論 第 1 部正規表現と有限オートマトン 火曜 5 6 限目必修科目 尾張正樹 居室 :J2415 ( 情報 2 号館 4 階 ) masakiowari@inf.shizuoka.ac.jp 講義資料 : fs.inf.in.shizuoka.ac.jp share class 218 オートマトン 本講義の評価について 本講義の成績評価は 課題提出 (web 小テスト ) 期末試験

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

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

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

More information

<4D F736F F F696E74202D2091E6824F82538FCD8CEB82E88C9F8F6F814592F990B382CC8CB4979D82BB82CC82505F D E95848D8682CC90B69

<4D F736F F F696E74202D2091E6824F82538FCD8CEB82E88C9F8F6F814592F990B382CC8CB4979D82BB82CC82505F D E95848D8682CC90B69 第 章 誤り検出 訂正の原理 その ブロック符号とその復号 安達文幸 目次 誤り訂正符号化を用いる伝送系誤り検出符号誤り検出 訂正符号 7, ハミング符号, ハミング符号生成行列, パリティ検査行列の一般形符号の生成行列符号の生成行列とパリティ検査行列の関係符号の訂正能力符号多項式 安達 : コミュニケーション符号理論 安達 : コミュニケーション符号理論 誤り訂正符号化を用いる伝送系 伝送システム

More information

DVIOUT

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

More information

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

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

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

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

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

More information

言語プロセッサ2005 -No.6-

言語プロセッサ2005 -No.6- 言語プロセッサ 2014 -No.5- 東京工科大学 コンピュータサイエンス学部 亀田弘之 お知らせ ( 確認 ) 平成 26 年 11 月 17 日 ( 月 ) は休講 平成 26 年 12 月 20 日 ( 土 ) に補講の予定 ( 注 ) 平成 26 年 1 月 21 日 ( 水 ) も台風補講の予定 言語プロセッサ 2014 担当 : 亀田弘之 ( 東京工科大学 ) 2 これからの内容 1.

More information

Microsoft PowerPoint - 7.pptx

Microsoft PowerPoint - 7.pptx 通信路 (7 章 ) 通信路のモデル 情報 送信者 通信路 受信者 A a,, a b,, b B m = P( b ),, P( b m ) 外乱 ( 雑音 ) n = P( a,, P( a ) n ) 送信情報源 ( 送信アルファベットと生成確率 ) 受信情報源 ( 受信アルファベッと受信確率 ) でもよい 生成確率 ) 受信確率 ) m n 2 イメージ 外乱 ( 雑音 ) により記号 a

More information

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

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

More information

講義の進め方 第 1 回イントロダクション ( 第 1 章 ) 第 2 ~ 7 回第 2 章 ~ 第 5 章 第 8 回中間ミニテスト (11 月 15 日 ) 第 9 回第 6 章 ~ 第 回ローム記念館 2Fの実習室で UML によるロボット制御実習 定期試験 2

講義の進め方 第 1 回イントロダクション ( 第 1 章 ) 第 2 ~ 7 回第 2 章 ~ 第 5 章 第 8 回中間ミニテスト (11 月 15 日 ) 第 9 回第 6 章 ~ 第 回ローム記念館 2Fの実習室で UML によるロボット制御実習 定期試験 2 ソフトウェア工学 第 7 回 木曜 5 限 F205 神原弘之 京都高度技術研究所 (ASTEM RI) http://www.metsa.astem.or.jp/se/ 1 講義の進め方 第 1 回イントロダクション ( 第 1 章 ) 第 2 ~ 7 回第 2 章 ~ 第 5 章 第 8 回中間ミニテスト (11 月 15 日 ) 第 9 回第 6 章 ~ 第 12 14 回ローム記念館 2Fの実習室で

More information

行列代数2010A

行列代数2010A (,) A (,) B C = AB a 11 a 1 a 1 b 11 b 1 b 1 c 11 c 1 c a A = 1 a a, B = b 1 b b, C = AB = c 1 c c a 1 a a b 1 b b c 1 c c i j ij a i1 a i a i b 1j b j b j c ij = a ik b kj b 1j b j AB = a i1 a i a ik

More information

に対して 例 2: に対して 逆行列は常に存在するとは限らない 逆行列が存在する行列を正則行列 (regular matrix) という 正則である 逆行列が存在する 一般に 正則行列 A の逆行列 A -1 も正則であり (A -1 ) -1 =A が成り立つ また 2 つの正則行列 A B の積

に対して 例 2: に対して 逆行列は常に存在するとは限らない 逆行列が存在する行列を正則行列 (regular matrix) という 正則である 逆行列が存在する 一般に 正則行列 A の逆行列 A -1 も正則であり (A -1 ) -1 =A が成り立つ また 2 つの正則行列 A B の積 2 逆行列 逆行列の計算は 連立一次方程式を数値的に解くために利用される 気象学の分野では線形系の応答問題を数値的に解くときに用いられることも多い ここでは計算機を用いて逆行列を求める方法を学ぶ 2.1 はじめにたとえば 次のような連立一次方程式を解くことを考える このような 2 元連立一次方程式は 代入法や消去法によって容易に解くことができる 解法をプログラミング言語によって記述することも困難ではない

More information

JavaプログラミングⅠ

JavaプログラミングⅠ Java プログラミング Ⅰ 5 回目演算子の優先順位と変数の型変換 今日の講義で学ぶ内容 演算子の優先順位 優先順位の変更の方法 キャスト演算子と型変換 演算子の優先順位 演算子の優先順位 式を計算するときの演算の順序です例えば a=b*c+d; では乗算を先に計算するというルールです ( 主な演算子の優先順位 ) 演算子 名前 結合規則 ++ 後置インクリメント 左 -- 後置デクリメント 左!

More information

DVIOUT-SS_Ma

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

More information

Microsoft PowerPoint - Compiler03.pptx

Microsoft PowerPoint - Compiler03.pptx コンパイラ 第 3 回字句解析 決定性有限オートマトンの導出 http://www.info.kindi.c.jp/compiler 38 号館 4 階 N-411 内線 5459 tksi-i@info.kindi.c.jp コンパイラの構造 字句解析系 構文解析系 制約検査系 中間コード生成系 最適化系 目的コード生成系 処理の流れ 情報システムプロジェクト I の場合 write (); 字句解析系

More information

情報量と符号化

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

More information

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

Microsoft PowerPoint - logic ppt [互換モード] 寄せられた質問 : 演習問題について この講義の範囲に含まれる適切な演習問題が載っている参考書がありますか? できれば解答や解説が付いているものがあると良いのですが 第 回の授業の中で 演習問題に取り組む方法を説明しますこの授業は 回だけ行うもので 書籍の1 冊分に比べると少ない分量しかカバーしていません 回の講義の概観 : 1 完全性と不完全性 命題論理 命題論理 ( 真理値 ) ( 公理と推論規則

More information

論理と計算(2)

論理と計算(2) 情報科学概論 Ⅰ アルゴリズムと計算 亀山幸義 http://logic.cs.tsukuba.ac.jp/~kam 計算とは? コンピュータが計算できることは? 1 2 関数 = 計算? NO 部分関数と計算 入力 1 入力 2 関数 出力 入力 1 入力 2 部分関数 出力 停止しない 入力 1 入力 2 コンピュータ 止まらないことがある出力 3 入力 1 入力 2 コンピュータ 出力 停止しない

More information

1/20 平成 29 年 3 月 25 日午前 11 時 7 分第 1 章 :U(N) 群 SU(N) 群 ( 学部 4 年次向 ) 第 1 章 :U(N) 群 SU(N) 群 Ⅰ. 標準模型の素粒子 素粒子の分類図 3 世代 素粒子の標準理論に含まれる素粒子は 素粒子の分類図 から R, G, B

1/20 平成 29 年 3 月 25 日午前 11 時 7 分第 1 章 :U(N) 群 SU(N) 群 ( 学部 4 年次向 ) 第 1 章 :U(N) 群 SU(N) 群 Ⅰ. 標準模型の素粒子 素粒子の分類図 3 世代 素粒子の標準理論に含まれる素粒子は 素粒子の分類図 から R, G, B / 平成 9 年 3 月 5 日午前 時 7 分第 章 :U() 群 SU() 群 ( 学部 4 年次向 ) 第 章 :U() 群 SU() 群 Ⅰ. 標準模型の素粒子 素粒子の分類図 3 世代 素粒子の標準理論に含まれる素粒子は 素粒子の分類図 から R, G, B R, G, B R, G, B u : 5 c :, 6 t :75,e 3 クォーク( quark ) : R, G, B R,

More information