PowerPoint Presentation

Size: px
Start display at page:

Download "PowerPoint Presentation"

Transcription

1 様相論理と時相論理

2 Kripke 構造 K = S, R, L S: 状態の集合 ( 無限かもしれない ) R: 状態間の遷移関係 R S S L: 状態から命題記号の集合への写像 L(s) は 状態 s S において成り立つ命題記号の集合を与える

3 Kripke 構造 K = S, R, L G = S, R 有向グラフ

4 Kripke 構造 K = S, R, L L : S 2 Atom Atom : 命題記号の全体 P Atom = {P, } P, P

5 様々な Kripke 構造 木 P 森 無限木 P, P, P

6 様相論理式 ϕ, ψ ::= P 命題記号 ϕ 否定 ϕ ψ 連言 ϕ ψ 選言 ϕ 必然 ϕ 可能

7 意味論 s = P iff P L(s) s = ϕ iff not s = ϕ s = ϕ ψ iff s = ϕ and s = ψ s = ϕ ψ iff s = ϕ or s = ψ s = ϕ iff t = ϕ for any t s.t. R(s, t) s = ϕ iff t = ϕ for some t s.t. R(s, t) ϕ は ϕ に同値

8 意味論 (P ) P P P, P

9 で成り立っているのは? (P ) 3. P P P, P

10 で成り立っているのは? (P ) 3. P P P, P

11 で は成り立っている? 1. Yes 2. No P Yes 0% 0% No P, P

12 様々な様相論理 以上は最小様相論理 K 遷移関係を限定 反射的 T / 推移的 K4 再帰的な命題 計算木論理 様相 µ 計算 多重の様相 様相 ( 遷移関係 ) の演算 ブール論理 動的論理 グラフ上の経路による解釈 線形時間時相論理 グラフを木に限定

13 充足可能性と有限モデル性 様相論理式 ϕ が充足可能 あるKripke 構造 K とその状態 s が存在して s = ϕ K を ϕ のモデルという 最小論理においては 充足可能な論理式は有限モデルを持つ しかも 有限の木モデルを持つ

14 様相論理の木モデル性 一般に Kripke 構造 ( グラフ ) をノード s から展開すると ( 無限の ) 木が得られる s において論理式が充足可能ならば 展開した木の根においても充足可能 P s s P P, P, P, P P

15 時相論理 (Temporal Logic) 状態の遷移や時間の経過の観点よりシステムの性質を記述するための論理体系 線形時間時相論理 LTL(Linear Time Temporal Logic) 分岐時間時相論理 CTL(Computation Tree Logic) μ 計算 (µ-calculus) モデル検査 時相論理で表現された性質をシステムが満たすかどうかを検査すること

16 例 :Peterson のアルゴリズム me = 0, 1 you = 1, 0 for (;;) { flags[me] = true; turn = you; while (flags[you] == true) { if (turn!= you) break; } // the critical section flags[me] = false; // the idle part }

17 Peterson のアルゴリズム 0: flags[me] = true; 1: turn = you; 2: if (flags[you]!= true) goto 4; 3: if (turn!= you) goto 4; else goto 2; 4: critical section; 5: flags[me] = false; 6: either goto 6 or goto 0; 状態 :(pc0, pc1, flags[0], flags[1], turn) pc0, pc1: 0..6 flags[0], flags[1]: {true, false} turn: {0, 1}

18 (pc0, pc1, flags[0], flags[1], turn) = (2,2,t,t,1) から遷移可能な状態は? 1. (2,4,t,t,1) 2. (3,2,t,t,1) 3. (4,2,t,t,1) 0: flags[me] = true; 1: turn = you; 2: if (flags[you]!= true) goto 4; 3: if (turn!= you) goto 4; else goto0% 2; 4: critical section; 5: flags[me] = false; 6: either goto 6 or goto 0; 0% 0% (2,4,t,t,1) (3,2,t,t,1) (4,2,t,t,1)

19 (pc0, pc1, flags[0], flags[1], turn) = (3,2,t,t,1) から遷移可能な状態は? 1. (2,2,t,t,1) 2. (3,4,t,t,1) 3. (4,2,t,t,1) 0: flags[me] = true; 1: turn = you; 2: if (flags[you]!= true) goto 4; 3: if (turn!= you) goto 4; else goto0% 2; 4: critical section; 5: flags[me] = false; 6: either goto 6 or goto 0; 0% 0% (2,2,t,t,1) (3,4,t,t,1) (4,2,t,t,1)

20 状態遷移系について検証すべき性質 安全性 (safety) 好ましくないことが決して起こらないこと 活性 (liveness) 好ましいことが必ず起こること 活性が成り立つためには公平性が必要 公平性が成り立たないと 特定のプロセスばかり実行されてしまう 公平性 (fairness) の仮定 無条件の公平性 (unconditional fairness) 弱い公平性 (weak fairness) 強い公平性 (strong fairness)

21 次のうち活性はどれか? 1. デッドロックが起こらない 2. 開こうとするファイルは必ず存在する 3. 開いたファイルは必ず閉じられる 4. 配列のインデックスは常にその範囲内に納まっている 0% 0% 0% 0% デッドロックが起こらない 開こうとするファイル... 開いたファイルは必ず... 配列のインデックスは...

22 Peterson のアルゴリズムの場合 安全性 二つのプロセスが同時にはcritical sectionに入らない pc0=pc1=4にはならない 活性 ( 飢餓が起きないこと ) プロセスがヘッダ部に入ったら 必ずいつかはcritical sectionに入ることができる 活性が成り立つためには公平性が必要 どちらのプロセスも必ず進んでいなければならない ここでは,critical sectionで無限ループに陥らないと仮定 公平性 (fairness) の仮定 どちらのプロセスも無限回実行される 無条件の公平性

23 Petersonのアルゴリズムの正当性の時相論理による表現 安全性 LTL(Linear Time Temporal Logic) G( (pc0=4 pc1=4)) CTL(Computation Tree Logic) AG( (pc0=4 pc1=4)) 活性 ( 飢餓が起きないこと ) LTL G(pc0=0 F(pc0=4)) CTL AG(pc0=0 AF(pc0=4)) 公平性 (fairness) の仮定 LTL G(pc0=0 F(pc0=1))... LTLならば書けるが CTLでは書けない

24 公平性 (fairness) の仮定 無条件の公平性 (unconditional fairness) どのプロセスもいつかは必ず実行される 弱い公平性 (weak fairness) 実行可能であり続けるプロセスは いつかは必ず実行される 実行されないにもかかわらず 連続的に実行可能で有り続けることはない 強い公平性 (strong fairness) 実行されないにもかかわらず 断続的にも実行可能で有り続けることはない

25 Java の場合 public class LockTest extends Thread { static Object lock = new Object (); public void run () { while ( true ) { requestlock (); synchronized ( lock ) { acquirelock (); }}}} public static void main ( String [] args ) { LockTest th1 = new LockTest (); LockTest th2 = new LockTest (); th1. start (); th2. start (); } static public void requestlock () {} static public void acquirelock () {}}

26 どちらのスレッドも ackquirelock を 呼べるためには? 1. 弱い公平性で十分である 2. 強い公平性が必要である 3. 無条件の公平性が要請される 0% 0% 0% 弱い公平性で十分である 強い公平性が必要である 無条件の公平性が要...

27 計算木論理 (Computation Tree Logic) 分岐時間時相論理 (branching-time temporal logic) の一種 ϕ, ψ ::=... AGϕ globally on any path AFϕ finally on any path EGϕ globally on some path EFϕ finally on some path は AX は EX と書く

28 経路 (path) について 計算木論理では 無限の経路を考える 行き止まりの状態があると面倒なので どの状態からも次の状態があると仮定 たとえば 終了状態には 便宜上 自分自身への遷移を付加する

29 意味論 s = AGϕ iff s から到達できる任意の状態 t において t = ϕ s = AFϕ iff s から始まる任意の経路上に t = ϕ を満たす状態 t が存在する

30 で成り立っているのは? 1. AG P 2. AG P 3. AF 4. AF P P, P,

31 意味論 s = EFϕ iff s から到達できる状態 t が存在して t = ϕ s = EGϕ iff s から始まる経路が存在して その経路上の任意の状態 t において t = ϕ

32 で成り立っているのは? 1. EF (P ) 2. EF AG P 3. EG 4. EG P P, P,

33 で AF AG は成り立っている? 1. Yes 2. No P Yes 0% 0% No P, P,

34 状態集合の計算 大域的なモデル検査 [[φ]] = {s S s = φ } とおく [[P]] = { s S P L(s) } [[ ϕ]] = S [[ϕ]] [[ϕ ψ]] = [[ϕ]] [[ψ]] [[ϕ ψ]] = [[ϕ]] [[ψ]] [[ ϕ]] = { s S 任意の t S に対して R(s,t) ならば t [[φ]] } [[ ϕ]] = { s S ある t S が存在して R(s,t) かつ t [[φ]] }

35 [[EFφ]] の計算 状態集合の計算 X := loop Y := [[φ]] { s S ある t S が存在し R(s,t) かつ t X } if Y==X then break X := Y end Y := の右辺を f(x) とおいたとき X = f(x) を満たす最小の X を求めている

36 EF P P P, P,

37 EF P P P, P,

38 EF P P P, P,

39 [[EGφ]] の計算 状態集合の計算 X := S loop Y := [[φ]] { s S ある t S が存在し R(s,t) かつ t X } if Y==X then break X := Y end Y := の右辺を f(x) とおいたとき X = f(x) を満たす最大の X を求めている

40 EG P P, P,

41 EG P P, P,

42 [[AGφ]] の計算 状態集合の計算 X := S loop Y := [[φ]] { s S 任意の t S は R(s,t) ならば t X } if Y==X then break X := Y end Y := の右辺を f(x) とおいたとき X = f(x) を満たす最大の X を求めている

43 AG P P, P,

44 AG P P, P,

45 AG P P, P,

46 [[AFφ]] の計算 状態集合の計算 X := loop Y := [[φ]] { s S 任意の t S は R(s,t) ならば t X } if Y==X then break X := Y end Y := の右辺を f(x) とおいたとき X = f(x) を満たす最小の X を求めている

47 AF AG P P, P,

48 AF AG P P, P,

49 AF AG P P, P,

50 AF AG P P, P,

51 まとめ [[EFφ]] = [[φ EFφ]] 最小 [[EGφ]] = [[φ EGφ]] 最大 [[AGφ]] = [[φ AGφ]] 最大 [[AFφ]] = [[φ AFφ]] 最小

52 まとめ [[EFφ]] = [[φ EFφ]] 最小 [[EGφ]] = [[φ EGφ]] 最大 [[AGφ]] = [[φ AGφ]] 最大 [[AFφ]] = [[φ AFφ]] 最小

53 まとめ [[EFφ]] = [[φ EFφ]] 最小 [[EGφ]] = [[φ EGφ]] 最大 [[AGφ]] = [[φ AGφ]] 最大 [[AFφ]] = [[φ AFφ]] 最小

54 様相 µ 計算 (modal µ-calculus) 命題変数に対する再帰的定義が可能 X = ϕ X 最小不動点か最大不動点か? 最小不動点の場合 µx. ϕ X EFϕ に一致 最小不動点の場合恒真になってしまう 最大不動点の例 νx. ϕ X AGϕ に一致

55 AFφ を表すのは? 1. µx. ϕ X 2. µx. ϕ X 3. νx. ϕ X 4. νx. ϕ X 5. µx. ϕ X 6. µx. ϕ X 7. νx. ϕ X 8. νx. ϕ X

56 線形時間時相論理 (linear-time temporal logic) Kripke 構造上の経路において論理式を解釈する 計算木論理においても 部分的に経路の概念が入っている ここから先はずっと線形時間時相論理の話

57 Kripke 構造 K = S, R, L S: 状態の集合 R: 状態間の遷移関係 R S S L: 状態から原子論理式の集合への写像 L(s) は 状態 s S において成り立つ原子論理式の集合を与える

58 状態の無限列 --- 実行経路 π=π 0,π 1,π 2, π i S ( i 0) suffix R(π i, π i+1 ) ( i 0) π i =π i,π i+1,π i+2,

59 論理式 ϕ, ψ ::= P 命題記号 ϕ 否定 ϕ ψ 連言 ϕ ψ 選言 ϕ (Xϕ) ϕ (Gϕ) ϕ (Fϕ) until は ここでは 考えない

60 意味論 π = P iff P L(π 0 ) π = ϕ iff not π = ϕ π = ϕ ψ iff π = ϕ and π = ψ π = ϕ ψ iff π = ϕ or π = ψ π = ϕ iff π 1 = ϕ π = ϕ iff π i = ϕ for any i 0 π = ϕ iff π i = ϕ for some i 0 と の意味が これまでと違うことに注意 ϕ は π において成り立つ π = ϕ --- π は ϕ のモデルである

61 この経路で成り立っているのは? 1. P 2. P 3. (P ) 4. (P ) P P, P,

62 は成り立っているか? 1. Yes 2. No P Yes 0% 0% No P, P,

63 P は成り立っているか? 1. Yes 2. No P Yes 0% 0% No P, P,

64 P は成り立っているか? 1. Yes 2. No P Yes 0% 0% No P, P,

65 P π = P が成り立っていると π = P なので π i = P を満たす i が存在 π = P なので π i+1 = P が成り立ち π j = P を満たす j>i が存在 同様にして π i = P を満たす無限個の i が存在することがわかる 逆に π i = P を満たす無限個の i が存在すれば π = P が成り立つ

66 公平性の表現 E をあるプロセスが実行可能であること R をそのプロセスが実行されていることを表す 無条件の公平性 R 弱い公平性 ( Ε R) (Ε R) 強い公平性 Ε R Ε R

67 と と π = ϕ iff π = ϕ π = ϕ iff π = ϕ

68 論理式 ( 正形式 ) ϕ, ψ ::= P P ϕ ψ ϕ ψ ϕ ϕ ϕ 任意の論理式に対して それと同値な正形式が存在する

69 (a b) と同値な正形式は? 1. (a b) 2. (a b) 3. (a b) 4. (a b) 5. ( a b) 6. ( a b) 7. ( a b) 8. ( a b)

70 と と π = ϕ iff π = ϕ iff π = ϕ ϕ π = ϕ ϕ

71 cl(ϕ 0 ): ϕ 0 の閉包 以下の性質を満たす最小の ( 論理式の ) 集合 ϕ 0 cl(ϕ 0 ) ϕ 1 ϕ 2 cl(ϕ 0 ) ならば ϕ 1 cl(ϕ 0 ) かつ ϕ 2 cl(ϕ 0 ) ϕ 1 ϕ 2 cl(ϕ 0 ) ならば ϕ 1 cl(ϕ 0 ) かつ ϕ 2 cl(ϕ 0 ) ϕ cl(ϕ 0 ) ならば ϕ cl(ϕ 0 ) ϕ cl(ϕ 0 ) ならば ϕ ϕ cl(ϕ 0 ) ϕ cl(ϕ 0 ) ならば ϕ ϕ cl(ϕ 0 ) P cl(ϕ 0 ) ならば P cl(ϕ 0 ) という条件はなくてもよい

72 ϕ = 0 (a b) cl(ϕ 0 ) : (a b) (a b) (a b) a b (a b) a b b b b b

73 ϕ 0 型 Γ cl(ϕ 0 ) ϕ 1 ϕ 2 Γ ならば ϕ 1 Γ かつ ϕ 2 Γ ϕ 1 ϕ 2 Γ ならば ϕ 1 Γ または ϕ 2 Γ P Γ かつ P Γ となることはない ϕ Γ ならば ϕ ϕ Γ ϕ Γ ならば ϕ ϕ Γ

74 ϕ 0 型の選択と ϕ 0 型間の遷移 ϕ 0 を含む極小のϕ 0 型をすべて選ぶ ϕ 0 型 Γ cl(ϕ 0 ) が選ばれたら {ϕ cl(ϕ 0 ) ϕ Γ} を含む極小のϕ 0 型 Γ をすべて選ぶ Γ Γ とおく ( 遷移 ) 以上の繰り返し

75 Γ ア : (a b)

76 Γ ア : (a b) (a b) (a b)

77 Γ ア : (a b) (a b) (a b) a b Γ イ : (a b) (a b) (a b) (a b)

78 Γ ア : (a b) (a b) (a b) a b a b Γ イ : (a b) (a b) (a b) (a b)

79 Γ ア : (a b) (a b) (a b) a b a b b b Γ イ : (a b) (a b) (a b) (a b)

80 Γ ア : (a b) (a b) (a b) a b a b b b b Γ b イ : (a b) (a b) (a b) (a b)

81 Γ アからの遷移先に含まれるのは? Γ ア : (a b) (a b) (a b) a b a b b b b b 1. a 2. b 3. b 4. a b 5. (a b)

82 Γ ア : (a b) (a b) (a b) a b a b b b b Γ ウ : Γ b イ : b (a b) (a b) (a b) (a b)

83 Γ ア : (a b) (a b) (a b) a b a b b b b Γ ウ : Γ b イ : b (a b) (a b) (a b) b b (a b)

84 Γ ア : (a b) (a b) (a b) a b a b b b b Γ ウ : Γ b イ : b (a b) (a b) (a b) b b (a b) b b

85 アから遷移可能なのは? 1. ない 2. ア 3. アとイ 4. アとウ 5. アとイとウ 6. イ 7. イとウ 8. ウ イ : ア : (a b) (a b) (a b) a b a b b b b b (a b) (a b) (a b) (a b) ウ : b b b b b 0% 0% 0% 0% 0% 0% 0% 0% ない ア アとイ アとウ アとイとウ イ イとウ ウ

86 イから遷移可能なのは? 1. ない 2. ア 3. アとイ 4. アとウ 5. アとイとウ 6. イ 7. イとウ 8. ウ イ : ア : (a b) (a b) (a b) a b a b b b b b (a b) (a b) (a b) (a b) ウ : b b b b b 0% 0% 0% 0% 0% 0% 0% 0% ない ア アとイ アとウ アとイとウ イ イとウ ウ

87 ウから遷移可能なのは? 1. ない 2. ア 3. アとイ 4. アとウ 5. アとイとウ 6. イ 7. イとウ 8. ウ イ : ア : (a b) (a b) (a b) a b a b b b b b (a b) (a b) (a b) (a b) ウ : b b b b b 0% 0% 0% 0% 0% 0% 0% 0% ない ア アとイ アとウ アとイとウ イ イとウ ウ

88 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

89 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

90 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

91 ア イ ウ

92 モデルの 記号 化 π=π 0,π 1,π 2, を ϕ 0 のモデルとしたとき 以下の条件を満たす ϕ 0 型の無限列 Π = Γ 0, Γ 1, Γ 2, が存在する ϕ 0 Γ 0 任意の ϕ Γ i に対して π i = ϕ を満たす Γ i Γ i+1 ϕ Γ i ならば ある j i が存在して ϕ Γ j

93 π = π 0, π 1, π 2, π 3, π 4, π 5, π 6, π 7, π 1 = π 1, π 2, π 3, π 4, π 5, π 6, π 7, π 2 = π 2, π 3, π 4, π 5, π 6, π 7, π 3 = π 3, π 4, π 5, π 6, π 7, π 4 = π 4, π 5, π 6, π 7, = ϕ 0 = ψ = ψ = θ Π = Γ 0, Γ 1, Γ 2, Γ 3, Γ 4, Γ 5, π 5 = π 5, π 6, π 7, = θ

94 ア イ ウ

95 逆に ϕ 0 型 Γ i cl(ϕ 0 ) から成る無限列 Π=Γ 0,Γ 1,Γ 2, が以上の条件を満たし さらに以下の条件を満たせば 任意の ϕ Γ i に対して π i = ϕ が成り立つ ( 特に π = ϕ 0 ) P Γ i ならば P L(π i ) である P Γ i ならば P L(π i ) でない

96 ω オートマトン 以上の条件を満たす無限列を特徴付けるため ϕ 0 型 Γ cl(ϕ 0 ) を状態とする ωオートマトンを構成する 遷移は Γ Γ によって定義

97 初期状態 特に π = ϕ 0 を満たす π を求めたいので ϕ 0 Γ 0 を要請する このためには ϕ 0 を含むϕ 0 型を初期状態とすればよい ( 複数あり得ることに注意 )

98 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

99 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

100 ア イ ウ

101 ラベル 以下の条件を調べるために 命題記号とその否定を状態 (ϕ 0 型 ) のラベルとして明示 P Γ i ならば P L(π i ) である P Γ i ならば P L(π i ) でない

102 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

103 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

104 ア a b イ ウ b

105 経路の条件 ωオートマトン上の無限経路 Π=Γ 0,Γ 1,Γ 2, で 以下の条件を満たすものを特徴付けたい ϕ Γ i ならば ある j i が存在して ϕ Γ j

106 経路の条件 以上の無限経路の条件は 次のように言い換えることができる Π=Γ 0,Γ 1,Γ 2, は 各 ϕ cl(ϕ 0 ) に対して F( ϕ) の要素を無限回含む ここで F( ϕ) = {Γ ϕ Γ または ϕ Γ}

107 F( (a b)) は? 1. ない 2. ア 3. アとイ 4. アとウ 5. アとイとウ 6. イ 7. イとウ 8. ウ イ : ア : (a b) (a b) (a b) a b a b b b b b (a b) (a b) (a b) (a b) ウ : b b b b b F( ϕ) = {Γ ϕ Γ または ϕ Γ} ない 0% 0% 0% 0% 0% 0% 0% 0% ア アとイ アとウ アとイとウ イ イとウ ウ

108 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

109 ア : (a b) (a b) (a b) a b a b b b b b イ : (a b) (a b) (a b) (a b) ウ : b b b b b

110 ア a b イ ウ F( (a b)) = { ア, ウ } b

111 モデル検査 Kripke 構造 K= S, R, L 初期状態 s 0 S 論理式 ϕ 0 に対して π 0 =s 0 を満たす ϕ 0 のモデル π=π 0,π 1,π 2, が存在するか?

112 これは以下と等価 ωオートマトン上の無限経路 Π=Γ 0,Γ 1,Γ 2, で以下の条件を満たすものが存在するか? 各 ϕ cl(ϕ 0 ) に対して F( ϕ) の要素を無限回含む P Γ i ならば P L(π i ) である P Γ i ならば P L(π i ) でない

113 同期積 π の存在と Π の存在を一度に調べるために ωオートマトンと K との 同期積 を作る 状態 : s, Γ where {P P Γ} L(s) {P P Γ} L(s) = 初期状態 : s 0, Γ 0 それぞれの初期状態の組 遷移 : s, Γ s, Γ iff R(s, s ) and Γ Γ

114 同期積 a b a b a b

115 同期積 a b a b a b

116 存在しないのは? 20% 20% 20% a20% b 20% a b a b

117 同期積 a b a b a b

118 存在する遷移は? a b a a b 17% 17% 17% 17% 17% 17% b

119 同期積 a b a b a b

120 同期積 a b a b b

121 モデルが存在するための条件 ϕ 0 のモデル π=π 0,π 1,π 2, が存在するための必要十分条件 : 同期積における無限経路 π 0, Γ 0 π 1, Γ 1... で 各 ϕ cl(ϕ 0 ) に対して F( ϕ) の要素を無限回含むものが存在する ある種のループの存在

122 同期積 a b a b a b

123 同期積 a b a b b

124 ループの条件 ループは 初期状態から到達可能 ループは 各 ϕ cl(ϕ 0 ) に対して F( ϕ) の要素を含む 同期積の強連結成分を求めれば 上のようなループが存在するか 判定可能

125 レポート課題 ( e r) (a b) が常に成り立つことを検証するための ωオートマトンを構成せよ 以下のKripke 構造において 上記論理式が常に成り立つことを示せ a e r b

126 until π = ϕ until ψ iff π i = ψ for some i 0 and π j = ϕ for any j<i

127 release π = ϕ release ψ iff π i = ϕ for some i 0 and π j = ψ for any j i or π j = ψ for any j

128 until と release と π = (ϕ until ψ) iff π = ϕ release ψ π = (ϕ release ψ) iff π = ϕ until ψ

129 until と release と π = ϕ until ψ iff π = ψ (ϕ until ψ) π = release ψ iff π = ψ (ϕ release ψ)

プログラム理論2014.key

プログラム理論2014.key (temporal logic) (modal logic)!! LTL! CTL! liveness safety properties! (Model Checking)! LTL (linear-time temporal logic) Syntax! p Atoms (propositional atoms)! φ::= T p ( φ) (φ φ) (φ φ) (φ φ) (X φ)!!

More information

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

情報処理Ⅰ

情報処理Ⅰ Java フローチャート -1- フローチャート ( 流れ図 ) プログラムの処理手順 ( アルゴリズム ) を図示したもの 記号の種類は下記のとおり 端子記号 ( 開始 終了 ) 処理記号計算, 代入等 条件の判定 条件 No ループ処理 LOOP start Yes データの入力 出力 print など 定義済み処理処理名 end サンプルグログラム ( 大文字 小文字変換 ) 大文字を入力して下さい

More information

handout.dvi

handout.dvi http://www.kurims.kyoto-u.ac.jp/ ichiro 1 1.1 (formal verification, formal methods) [3] 2 theorem prover proof assistant PVSIsabell/HOLCoq Kripke M ϕ M ϕ M = ϕ model checker M ϕ M ϕ M M ϕ state explosion

More information

Java講座

Java講座 ~ 第 1 回 ~ 情報科学部コンピュータ科学科 2 年竹中優 プログラムを書く上で Hello world 基礎事項 演算子 構文 2 コメントアウト (//, /* */, /** */) をしよう! インデントをしよう! 変数などにはわかりやすい名前をつけよう! 要するに 他人が見て理解しやすいコードを書こうということです 3 1. Eclipse を起動 2. ファイル 新規 javaプロジェクト

More information

プログラミング基礎

プログラミング基礎 C プログラミング Ⅰ 条件分岐 : if 文, if~else 文 条件分岐 条件分岐とは ある条件が成立したときとしないときで処理の内容を変更する場合に応じた, 複雑な処理を行うことができる 条件分岐 yes 成績が良かったか? no ご褒美に何か買ってもらう お小遣いが減らされる C 言語では,if 文,if~else 文,if~else if~else 文,switch 文で条件分岐の処理を実現できる

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

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

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

More information

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

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

More information

論理学補足文書 7. 恒真命題 恒偽命題 1. 恒真 恒偽 偶然的 それ以上分割できない命題が 要素命題, 要素命題から 否定 連言 選言 条件文 双 条件文 の論理演算で作られた命題が 複合命題 である 複合命題は, 命題記号と論理記号を 使って, 論理式で表現できる 複合命題の真偽は, 要素命題

論理学補足文書 7. 恒真命題 恒偽命題 1. 恒真 恒偽 偶然的 それ以上分割できない命題が 要素命題, 要素命題から 否定 連言 選言 条件文 双 条件文 の論理演算で作られた命題が 複合命題 である 複合命題は, 命題記号と論理記号を 使って, 論理式で表現できる 複合命題の真偽は, 要素命題 7. 恒真命題 恒偽命題. 恒真 恒偽 偶然的 それ以上分割できない命題が 要素命題, 要素命題から 否定 連言 選言 条件文 双 条件文 の論理演算で作られた命題が 複合命題 である 複合命題は, 命題記号と論理記号を 使って, 論理式で表現できる 複合命題の真偽は, 要素命題の真偽によって, 真になる場合もあれば, 偽になる場合もある 例えば, 次の選言は, A, の真偽によって, 真にも偽にもなる

More information

プログラミングA

プログラミングA プログラミング A 第 5 回 場合に応じた処理 繰り返し 2019 年 5 月 13 日 東邦大学金岡晃 場合に応じた処理 1 こういうプログラムを作りたい 5 教科のテスト 100 点以上各科目の点数の合計が 100 点未満 おめでとう! これで 100 点越えのプレゼントを獲得! というメッセージを出力 残念!100 点越えのプレゼントまであと ** 点! というメッセージを出力 5 教科の点数の合計が

More information

7 ソフトウェア工学 Software Engineering モデル検査 MODEL CHECKING 1 モデル検査の概要 並行システム : 相互排他, デッドロック, スタベーションなどの現象 入出力関係に着目した 停止性 + 部分正当性 のみでは正当性を言えない 振る舞い ( 途中の状態遷移

7 ソフトウェア工学 Software Engineering モデル検査 MODEL CHECKING 1 モデル検査の概要 並行システム : 相互排他, デッドロック, スタベーションなどの現象 入出力関係に着目した 停止性 + 部分正当性 のみでは正当性を言えない 振る舞い ( 途中の状態遷移 7 ソフトウェア工学 Software Engineering モデル検査 MODEL CHECKING 1 モデル検査の概要 並行システム : 相互排他, デッドロック, スタベーションなどの現象 入出力関係に着目した 停止性 + 部分正当性 のみでは正当性を言えない 振る舞い ( 途中の状態遷移 ) の考慮の必要性 behaviors モデル検査 : 有限状態遷移系の振る舞いの検証を自動で行う技術

More information

Java プログラミング Ⅰ 7 回目 switch 文と論理演算子 条件判断文 3 switch 文 switch 文式が case の値と一致した場合 そこから直後の break; までを処理し どれにも一致しない場合 default; から直後の break; までを処理する 但し 式や値 1

Java プログラミング Ⅰ 7 回目 switch 文と論理演算子 条件判断文 3 switch 文 switch 文式が case の値と一致した場合 そこから直後の break; までを処理し どれにも一致しない場合 default; から直後の break; までを処理する 但し 式や値 1 Java プログラミング Ⅰ 7 回目 switch 文と論理演算子 条件判断文 3 switch 文 switch 文式が case の値と一致した場合 そこから直後の までを処理し どれにも一致しない場合 default; から直後の までを処理する 但し 式や値 1 値 2は整数または文字である switch( 式 ) case 値 1: // コロン : です セミコロン ; と間違えないように!!

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

Java プログラミング Ⅰ 7 回目 switch 文と論理演算子 今日の講義講義で学ぶ内容 switch 文 論理演算子 条件演算子 条件判断文 3 switch 文 switch 文 式が case のラベルと一致する場所から直後の break; まで処理しますどれにも一致致しない場合 def

Java プログラミング Ⅰ 7 回目 switch 文と論理演算子 今日の講義講義で学ぶ内容 switch 文 論理演算子 条件演算子 条件判断文 3 switch 文 switch 文 式が case のラベルと一致する場所から直後の break; まで処理しますどれにも一致致しない場合 def Java プログラミング Ⅰ 7 回目 switch 文と論理演算子 今日の講義講義で学ぶ内容 switch 文 論理演算子 条件演算子 条件判断文 3 switch 文 switch 文 式が case のラベルと一致する場所から直後の まで処理しますどれにも一致致しない場合 default: から直後の まで処理します 式の結果 ラベル 定数 整数または文字 (byte, short, int,

More information

プログラミングA

プログラミングA プログラミング A 第 5 回 場合に応じた処理 繰り返し 2017 年 5 月 15 日 東邦大学金岡晃 前回の復習 (1) このプログラムを作成し実行してください 1 前回の復習 (2) このプログラムを作成し実行してください 2 前回の復習 (3) 3 前回の復習 演算子 代入演算子 インクリメント シフト演算子 型変換 4 場合に応じた処理 5 こういうプログラムを作りたい 5 教科のテスト

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

ただし 無作為にスレッドを複数実行すると 結果不正やデッドロックが起きる可能性がある 複数のスレッド ( マルチスレッド ) を安全に実行する ( スレッドセーフにする ) ためには 同期処理を用いるこ とが必要になる 同期処理は 予約語 synchronized で行うことができる ここでは sy

ただし 無作為にスレッドを複数実行すると 結果不正やデッドロックが起きる可能性がある 複数のスレッド ( マルチスレッド ) を安全に実行する ( スレッドセーフにする ) ためには 同期処理を用いるこ とが必要になる 同期処理は 予約語 synchronized で行うことができる ここでは sy オブジェクト指向プログラミング演習 2010/10/27 演習課題 スレッド ( その 2) 同期処理 結果不正 デッドロック 前回のスレッドの演習では 複数のスレッドを実行し 一つのプログラムの中の違う処理を同時に実行し た ただし 無作為にスレッドを複数実行すると 結果不正やデッドロックが起きる可能性がある 複数のスレッド ( マルチスレッド ) を安全に実行する ( スレッドセーフにする )

More information

An Automated Proof of Equivalence on Quantum Cryptographic Protocols

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

More information

Microsoft Word - VBA基礎(3).docx

Microsoft Word - VBA基礎(3).docx 上に中和滴定のフローチャートを示しました この中で溶液の色を判断する部分があります このような判断はプログラムではどのように行うのでしょうか 判断に使う命令は IF 文を使います IF は英語で もし何々なら という意味になります 条件判断条件判断には次の命令を使います If 条件式 1 Then ElseIf 条件式 2 Then ElseIf 条件式 3 Then 実行文群 1 実行文群 2 実行文群

More information

オートマトンと言語

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

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

break 文 switch ブロック内の実行中の処理を強制的に終了し ブロックから抜けます switch(i) 強制終了 ソースコード例ソースファイル名 :Sample7_1.java // 入力値の判定 import java.io.*; class Sample7_1 public stati

break 文 switch ブロック内の実行中の処理を強制的に終了し ブロックから抜けます switch(i) 強制終了 ソースコード例ソースファイル名 :Sample7_1.java // 入力値の判定 import java.io.*; class Sample7_1 public stati Java プログラミング Ⅰ 7 回目 switch 文と論理演算子 今日の講義で学ぶ内容 switch 文 論理演算子 条件演算子 条件判断文 3 switch 文 switch 文 式が case のラベルと一致する場所から直後の まで処理しますどれにも一致しない場合 default: から直後の まで処理します 式は byte, short, int, char 型 ( 文字または整数 ) を演算結果としますラベルには整数リテラル

More information

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

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

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

生命情報学

生命情報学 生命情報学 5 隠れマルコフモデル 阿久津達也 京都大学化学研究所 バイオインフォマティクスセンター 内容 配列モチーフ 最尤推定 ベイズ推定 M 推定 隠れマルコフモデル HMM Verアルゴリズム EMアルゴリズム Baum-Welchアルゴリズム 前向きアルゴリズム 後向きアルゴリズム プロファイル HMM 配列モチーフ モチーフ発見 配列モチーフ : 同じ機能を持つ遺伝子配列などに見られる共通の文字列パターン

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

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

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

More information

Microsoft PowerPoint - 05.pptx

Microsoft PowerPoint - 05.pptx アルゴリズムとデータ構造第 5 回 : データ構造 (1) 探索問題に対応するデータ構造 担当 : 上原隆平 (uehara) 2015/04/17 アルゴリズムとデータ構造 アルゴリズム : 問題を解く手順を記述 データ構造 : データや計算の途中結果を蓄える形式 計算の効率に大きく影響を与える 例 : 配列 連結リスト スタック キュー 優先順位付きキュー 木構造 今回と次回で探索問題を例に説明

More information

Microsoft PowerPoint - DA2_2017.pptx

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

More information

プログラミング入門1

プログラミング入門1 プログラミング入門 1 第 5 回 繰り返し (while ループ ) 授業開始前に ログオン後 不要なファイルを削除し て待機してください Java 1 第 5 回 2 参考書について 参考書は自分にあったものをぜひ手元において自習してください 授業の WEB 教材は勉強の入り口へみなさんを案内するのが目的でつくられている これで十分という訳ではない 第 1 回に紹介した本以外にも良書がたくさんある

More information

040402.ユニットテスト

040402.ユニットテスト 2. ユニットテスト ユニットテスト ( 単体テスト ) ユニットテストとはユニットテストはプログラムの最小単位であるモジュールの品質をテストすることであり その目的は結合テスト前にモジュール内のエラーを発見することである テストは機能テストと構造テストの2つの観点から行う モジュールはプログラムを構成する要素であるから 単体では動作しない ドライバとスタブというテスト支援ツールを使用してテストを行う

More information

知識工学 II ( 第 2 回 ) 二宮崇 ( ) 論理的エージェント (7 章 ) 論理による推論 命題論理 述語論理 ブール関数 ( 論理回路 )+ 推論 ブール関数 +( 述語 限量子 ( ) 変数 関数 定数 等号 )+ 推論 7.1 知識

知識工学 II ( 第 2 回 ) 二宮崇 ( ) 論理的エージェント (7 章 ) 論理による推論 命題論理 述語論理 ブール関数 ( 論理回路 )+ 推論 ブール関数 +( 述語 限量子 ( ) 変数 関数 定数 等号 )+ 推論 7.1 知識 知識工学 II ( 第 回 ) 二宮崇 ( ninomiya@cs.ehime-u.ac.jp ) 論理的エージェント (7 章 ) 論理による推論 命題論理 述語論理 ブール関数 ( 論理回路 )+ 推論 ブール関数 +( 述語 限量子 ( ) 変数 関数 定数 等号 )+ 推論 7. 知識に基づくエージェント知識ベース (knowledge base, KB): 文 の集合 他の 文 から導出されない

More information

問題1 以下に示すプログラムは、次の処理をするプログラムである

問題1 以下に示すプログラムは、次の処理をするプログラムである 問題 1 次のプログラムの出力結果を a~d の中から選べ public class Problem1 { int i=2; int j=3; System.out.println("i"+j); a) 23,b) 5,c) i3,d) ij 問題 2 次のプログラムの出力結果を a~d の中から選べ public class Problem2 { int a=6; if((a>=2)&&(a

More information

Microsoft PowerPoint - prog03.ppt

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

More information

Microsoft PowerPoint - ●SWIM_ _INET掲載用.pptx

Microsoft PowerPoint - ●SWIM_ _INET掲載用.pptx シーケンスに基づく検索モデルの検索精度について 東京工芸大学工学部コンピュータ応用学科宇田川佳久 (1/3) (2/3) 要員数 情報システム開発のイメージソースコード検索機能 他人が作ったプログラムを保守する必要がある 実務面での応用 1 バグあるいは脆弱なコードを探す ( 品質の高いシステムを開発する ) 2 プログラム理解を支援する ( 第 3 者が書いたコードを保守する ) 要件定義外部設計内部設計

More information

( ) P, P P, P (negation, NOT) P ( ) P, Q, P Q, P Q 3, P Q (logical product, AND) P Q ( ) P, Q, P Q, P Q, P Q (logical sum, OR) P Q ( ) P, Q, P Q, ( P

( ) P, P P, P (negation, NOT) P ( ) P, Q, P Q, P Q 3, P Q (logical product, AND) P Q ( ) P, Q, P Q, P Q, P Q (logical sum, OR) P Q ( ) P, Q, P Q, ( P Advent Calendar 2018 @Fukuso Sutaro,,, ( ) Davidson, 5, 1 (quantification) (open sentence) 1,,,,,, 1 1 (propositional logic) (truth value) (proposition) (sentence) 2 (2-valued logic) 2, true false (truth

More information

情報数理学

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

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 - 2.ppt [互換モード]

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

More information

グラフの探索 JAVA での実装

グラフの探索 JAVA での実装 グラフの探索 JAVA での実装 二つの探索手法 深さ優先探索 :DFS (Depth-First Search) 幅優先探索 :BFS (Breadth-First Search) 共通部分 元のグラフを指定して 極大木を得る 探索アルゴリズムの利用の観点から 利用する側からみると 取り替えられる部品 どちらの方法が良いかはグラフに依存 操作性が同じでなければ 共通のクラスの派生で作ると便利 共通化を考える

More information

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

Microsoft PowerPoint - 06graph3.ppt [互換モード] I118 グラフとオートマトン理論 Graphs and Automata 担当 : 上原隆平 (Ryuhei UEHARA) uehara@jaist.ac.jp http://www.jaist.ac.jp/~uehara/ 1/20 6.14 グラフにおける探索木 (Search Tree in a Graph) グラフG=(V,E) における探索アルゴリズム : 1. Q:={v { 0 }

More information

< F2D834F838C A815B A CC>

< F2D834F838C A815B A CC> グレゴリー ライプニッツの公式 [Java アプレット ] [Java アプリケーション ] 1. はじめに 次のグレゴリー ライプニッツの公式を用いて π の近似値を求めてみましょう [ グレゴリー ライプニッツの公式 ] π 4 =1-1 3 + 1 5-1 7 + 1 9-1 + 11 シミュレーションソフト グレゴリー ライプニッツの公式による π の近似 を使って π の近似値が求まる様子を観察してみてください

More information

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

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

More information

離散数学

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

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

< F2D B838A835882CC8CF68EAE2E6A7464>

< F2D B838A835882CC8CF68EAE2E6A7464> ウォーリスの公式 [Java アプレット ] [Java アプリケーション ] 1. はじめに 次のウォーリスの公式を用いて π の近似値を求めてみましょう [ ウォーリスの公式 ] π=2{ 2 2 4 4 6 6 1 3 3 5 5 7 シミュレーションソフト ウォーリスの公式による π の近似 を使って π の近似値が求まる様子を観察してみてください 2.Java アプレット (1) Javaプログラムリスト

More information

Javaによるアルゴリズムとデータ構造

Javaによるアルゴリズムとデータ構造 1 algorithm List 1-1 a, b, c List 1-1 // import java.util.scanner; class Max3 { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); int a, b, c; int max; // Chap01/Max3.java

More information

Microsoft PowerPoint - HITproplogic.ppt

Microsoft PowerPoint - HITproplogic.ppt 人工知能論理と推論 (1) 知識を組み合わせて知識を生み出す 命題論理 (Propositional Logic) 人工知能と論理 命題論理の構文 命題論理の意味 節形式 1 なぜ人工知能で論理を学ぶのか なぜ人工知能で論理 (LOGIC) を学ぶのか. 言語としての論理 構文, 意味 アルゴリズムとしての論理 推論 知識ベース ELL, ASK 知識 知識 推論アルゴリズム (= LOGIC) 知識

More information

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

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

More information

2

2 問題 次の設問に答えよ 設問. Java のソースコードをコンパイルするコマンドはどれか a) java b) javac c) javadoc d) javaw 設問. Java のバイトコード ( コンパイル結果 ) を実行するコマンドはどれか a) java b) javac c) javadoc d).jar 設問. Java のソースコードの拡張子はどれか a).c b).java c).class

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 - 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 - logic ppt [互換モード]

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

More information

JavaプログラミングⅠ

JavaプログラミングⅠ Java プログラミング Ⅰ 6 回目 if 文と if else 文 今日の講義で学ぶ内容 関係演算子 if 文と if~else 文 if 文の入れ子 関係演算子 関係演算子 ==,!=, >, >=,

More information

新・明解Javaで学ぶアルゴリズムとデータ構造

新・明解Javaで学ぶアルゴリズムとデータ構造 第 1 章 基本的 1 n 21 1-1 三値 最大値 algorithm List 1-1 a, b, c max // import java.util.scanner; class Max3 { public static void main(string[] args) { Scanner stdin = new Scanner(System.in); List 1-1 System.out.println("");

More information

人工知能入門

人工知能入門 藤田悟 黄潤和 探索とは 探索問題 探索解の性質 探索空間の構造 探索木 探索グラフ 探索順序 深さ優先探索 幅優先探索 探索プログラムの作成 バックトラック 深さ優先探索 幅優先探索 n 個の ueen を n n のマスの中に 縦横斜めに重ならないように配置する 簡単化のために 4-ueen を考える 正解 全状態の探索プログラム 全ての最終状態を生成した後に 最終状態が解であるかどうかを判定する

More information

Prog1_3rd

Prog1_3rd 2019 年 10 月 10 日 ( 木 ) 実施 プログラムの制御構造 1960 年代後半にダイクストラが提唱した構造化プログラミングという考え方では, 手続き型のプログラムを記述する際には, 順次, 選択, 反復という標準的な制御構造のみを用い, 先ずプログラムの概略構造を設計し, その大まかな単位を段階的に詳細化して処理を記述していく 順次構造順次構造とは, プログラム中の文を処理していく順に記述したものである

More information

Microsoft PowerPoint - DA2_2017.pptx

Microsoft PowerPoint - DA2_2017.pptx 1// 小テスト内容 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I) 1 1 第 章の構成. 単一始点最短路問題 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 1 1 単一始点最短路問題とは 単一始点最短路問題とは 前提 : 重み付き有向グラフ

More information

やさしいJavaプログラミング -Great Ideas for Java Programming サンプルPDF

やさしいJavaプログラミング -Great Ideas for Java Programming サンプルPDF pref : 2004/6/5 (11:8) pref : 2004/6/5 (11:8) pref : 2004/6/5 (11:8) 3 5 14 18 21 23 23 24 28 29 29 31 32 34 35 35 36 38 40 44 44 45 46 49 49 50 pref : 2004/6/5 (11:8) 50 51 52 54 55 56 57 58 59 60 61

More information

Thread

Thread 14 2013 7 16 14.1....................................... 14 1 14.2 Thread................................... 14 1 14.3............................. 14 5 14.4....................................... 14 10

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 - DA2_2018.pptx

Microsoft PowerPoint - DA2_2018.pptx 1//1 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I). 単一始点最短路問題 第 章の構成 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 単一始点最短路問題とは 単一始点最短路問題とは 前提 : 重み付き有向グラフ 特定の開始頂点 から任意の頂点

More information

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

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

More information

プログラミング基礎

プログラミング基礎 C プログラミング Ⅰ 条件分岐 if~else if~else 文,switch 文 条件分岐 if~else if~else 文 if~else if~else 文 複数の条件で処理を分ける if~else if~else 文の書式 if( 条件式 1){ 文 1-1; 文 1-2; else if( 条件式 2){ 文 2-1; 文 2-2; else { 文 3-1; 文 3-2; 真条件式

More information

GEC-Java

GEC-Java Copyright (C) Junko Shirogane, Waseda University 2019, All rights reserved. 1 プログラミング初級 (Java) 第 14 回継承 白銀純子 第 14 回の内容 継承 オーバーライド ポリモーフィズム Copyright (C) Junko Shirogane, Waseda University 2019, All rights

More information

2

2 問題 1 次の設問 1~5 に答えよ 設問 1. Java のソースプログラムをコンパイルするコマンドはどれか a) java b) javac c) javadoc d) jdb 設問 2. Java のバイトコード ( コンパイル結果 ) を実行するコマンドはどれか a) java b) javac c) javadoc d) jdb 設問 3. Java のソースプログラムの拡張子はどれか a).c

More information

ex04_2012.ppt

ex04_2012.ppt 2012 年度計算機システム演習第 4 回 2012.05.07 第 2 回課題の補足 } TSUBAMEへのログイン } TSUBAMEは学内からのログインはパスワードで可能 } } } } しかし 演習室ではパスワードでログインできない設定 } 公開鍵認証でログイン 公開鍵, 秘密鍵の生成 } ターミナルを開く } $ ssh-keygen } Enter file in which to save

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

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション 解けない問題 を知ろう 保坂和宏 ( 東京大学 B2) 第 11 回 JOI 春合宿 2012/03/19 概要 計算量に関して P と NP NP 完全 決定不能 いろいろな問題 コンテストにおいて Turing 機械 コンピュータの計算のモデル 計算 を数学的に厳密に扱うためのもの メモリのテープ (0/1 の列 ), ポインタ, 機械の内部状態を持ち, 規則に従って状態遷移をする 本講義では

More information

K227 Java 2

K227 Java 2 1 K227 Java 2 3 4 5 6 Java 7 class Sample1 { public static void main (String args[]) { System.out.println( Java! ); } } 8 > javac Sample1.java 9 10 > java Sample1 Java 11 12 13 http://java.sun.com/j2se/1.5.0/ja/download.html

More information

メソッドのまとめ

メソッドのまとめ メソッド (4) 擬似コードテスト技法 http://java.cis.k.hosei.ac.jp/ 授業の前に自己点検以下のことがらを友達に説明できますか? メソッドの宣言とは 起動とは何ですか メソッドの宣言はどのように書きますか メソッドの宣言はどこに置きますか メソッドの起動はどのようにしますか メソッドの仮引数 実引数 戻り値とは何ですか メソッドの起動にあたって実引数はどのようにして仮引数に渡されますか

More information

1. A0 A B A0 A : A1,...,A5 B : B1,...,B12 2. 5 3. 4. 5. A0 (1) A, B A B f K K A ϕ 1, ϕ 2 f ϕ 1 = f ϕ 2 ϕ 1 = ϕ 2 (2) N A 1, A 2, A 3,... N A n X N n X N, A n N n=1 1 A1 d (d 2) A (, k A k = O), A O. f

More information

Microsoft PowerPoint - 9.pptx

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

More information

1. A0 A B A0 A : A1,...,A5 B : B1,...,B

1. A0 A B A0 A : A1,...,A5 B : B1,...,B 1. A0 A B A0 A : A1,...,A5 B : B1,...,B12 2. 3. 4. 5. A0 A, B Z Z m, n Z m n m, n A m, n B m=n (1) A, B (2) A B = A B = Z/ π : Z Z/ (3) A B Z/ (4) Z/ A, B (5) f : Z Z f(n) = n f = g π g : Z/ Z A, B (6)

More information

Java演習(4) -- 変数と型 --

Java演習(4)   -- 変数と型 -- 50 20 20 5 (20, 20) O 50 100 150 200 250 300 350 x (reserved 50 100 y 50 20 20 5 (20, 20) (1)(Blocks1.java) import javax.swing.japplet; import java.awt.graphics; (reserved public class Blocks1 extends

More information

コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n

コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n を入力してもらい その後 1 から n までの全ての整数の合計 sum を計算し 最後にその sum

More information

デジタル表現論・第4回

デジタル表現論・第4回 デジタル表現論 第 4 回 劉雪峰 ( リュウシュウフォン ) 2016 年 5 月 2 日 劉 雪峰 ( リュウシュウフォン ) デジタル表現論 第 4 回 2016 年 5 月 2 日 1 / 14 本日の目標 Java プログラミングの基礎 出力の復習 メソッドの定義と使用 劉 雪峰 ( リュウシュウフォン ) デジタル表現論 第 4 回 2016 年 5 月 2 日 2 / 14 出力 Systemoutprint()

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 PowerPoint - qcomp.ppt [互換モード]

Microsoft PowerPoint - qcomp.ppt [互換モード] 量子計算基礎 東京工業大学 河内亮周 概要 計算って何? 数理科学的に 計算 を扱うには 量子力学を計算に使おう! 量子情報とは? 量子情報に対する演算 = 量子計算 一般的な量子回路の構成方法 計算って何? 計算とは? 計算 = 入力情報から出力情報への変換 入力 計算機構 ( デジタルコンピュータ,etc ) 出力 計算とは? 計算 = 入力情報から出力情報への変換 この関数はどれくらい計算が大変か??

More information

Microsoft PowerPoint ppt

Microsoft PowerPoint ppt 独習 Java ( 第 3 版 ) 6.7 変数の修飾子 6.8 コンストラクタの修飾子 6.9 メソッドの修飾子 6.10 Object クラスと Class クラス 6.7 変数の修飾子 (1/3) 変数宣言の直前に指定できる修飾子 全部で 7 種類ある キーワード final private protected public static transient volatile 意味定数として使える変数同じクラスのコードからしかアクセスできない変数サブクラスまたは同じパッケージ内のコードからしかアクセスできない変数他のクラスからアクセスできる変数インスタンス変数ではない変数クラスの永続的な状態の一部ではない変数不意に値が変更されることがある変数

More information

このルールをそのまま正規表現として書くと 下記のようになります ^A[0-9]{2}00[0-9]{3}([0-9]{2})?$ ちょっと難しく見えるかもしれませんが 下記のような対応になっています 最初 固定 年度 固定 通番 ( 枝番 ) 最後 ルール "A" 数字 2 桁 0 を 2 桁 数字

このルールをそのまま正規表現として書くと 下記のようになります ^A[0-9]{2}00[0-9]{3}([0-9]{2})?$ ちょっと難しく見えるかもしれませんが 下記のような対応になっています 最初 固定 年度 固定 通番 ( 枝番 ) 最後 ルール A 数字 2 桁 0 を 2 桁 数字 正規表現について 作成日 : 2016/01/21 作成者 : 西村 正規表現? 正規表現 (Regular Expression Regex) というと難しいもののように感じますが 正規表現 というのは 文字のパターンを表したもの です ( 例 ) これはソエルで使用している見積書の番号です A1500033 この番号は 下記のルールで付けられています 固定 年度 固定 通番 ( 枝番 ) ルール

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

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

Microsoft PowerPoint - ca ppt [互換モード] 大阪電気通信大学情報通信工学部光システム工学科 2 年次配当科目 コンピュータアルゴリズム 良いアルゴリズムとは 第 2 講 : 平成 20 年 10 月 10 日 ( 金 ) 4 限 E252 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nakamr@is.naist.jp http://narayama.naist.jp/~y-nakamr/ 第 1 講の復習

More information

PowerPoint プレゼンテーション

PowerPoint プレゼンテーション ループ ループとは? ある条件を満たすまで 指定の命令を繰り返す Do... Loop For Next For Each Next While WEnd ループの種類 Do Loop Do While 条件 ステートメント Loop Do ステートメント Loop While 条件 Do Until 条件 ステートメント Loop Do ステートメント Until Loop 条件 Do Loop

More information

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include <stdiu.h> #define InFile "data.txt" #define OutFile "surted.txt" #def

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include <stdiu.h> #define InFile data.txt #define OutFile surted.txt #def C プログラミング演習 1( 再 ) 6 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include #define InFile "data.txt" #define OutFile "surted.txt"

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

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

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

More information

航空機の運動方程式

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

More information

プログラムの基本構成

プログラムの基本構成 Java 入門 この 2 回 ( 今回と次回 ) が勝負だ! プログラムは自転車の練習と同じだ! 今日の予定先ず プログラムの構造を学び (p.2~6) jcpad でプログラム ( 計算機実習室 ) 戻ってきてプログラムの解読手書きプログラムを TA にみてもらい OK の出た人は計算機実習室でプログラム作成し実行実行結果を TA がチェックして帰り プログラムの基本構成 Step1: 入力 Step2:

More information

問題1 以下に示すプログラムは、次の処理をするプログラムである

問題1 以下に示すプログラムは、次の処理をするプログラムである 問題 1 次に示すプログラムは 配列 a の値を乱数で設定し 配列 a の値が 333 より大きく 667 以下の値 の合計値を求めるプログラムである 1 と 2 に適切なコードを記述してプログラムを完 成させよ class TotalNumber { public static void main(string[] args) { int[] a = new int[1000]; // 1 解答条件

More information

新・明解Javaで学ぶアルゴリズムとデータ構造

新・明解Javaで学ぶアルゴリズムとデータ構造 第 3 章 探索 Arrays.binarySearch 743 3-1 探索 探索 searching key 配列 探索 Fig.3-1 b c 75 a 6 4 3 2 1 9 8 2 b 64 23 53 65 75 21 3-1 53 c 5 2 1 4 3 7 4 Fig.3-1 a 763 3-2 線形探索 線形探索 linear search sequential search 2

More information

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include <stdio.h> #define InFile "data.txt" #define OutFile "sorted.txt" #def

関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include <stdio.h> #define InFile data.txt #define OutFile sorted.txt #def C プログラミング演習 1( 再 ) 6 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 関数の呼び出し ( 選択ソート ) 選択ソートのプログラム (findminvalue, findandreplace ができているとする ) #include #define InFile "data.txt" #define OutFile "sorted.txt"

More information

教材ドットコムオリジナル教材 0から始めるiアフ リ リファレンス i アプリ簡易リファレンス ver i アプリ Java 独自のメソッド (1)iアプリの命令を使えるようにする import com.nttdocomo.ui.*; (2) 乱数を使う import java.u

教材ドットコムオリジナル教材 0から始めるiアフ リ リファレンス i アプリ簡易リファレンス ver i アプリ Java 独自のメソッド (1)iアプリの命令を使えるようにする import com.nttdocomo.ui.*; (2) 乱数を使う import java.u i アプリ簡易リファレンス ver0.1.5.1 1.i アプリ Java 独自のメソッド (1)iアプリの命令を使えるようにする import com.nttdocomo.ui.*; (2) 乱数を使う import java.util.random; int ; Random =new Random(); =Math.abs(.nextInt()% ); 0~ まで乱数を発生させます (3) 機種ごとの縦横幅を調べる

More information

JavaプログラミングⅠ

JavaプログラミングⅠ Java プログラミング Ⅰ 8 回目 for 文 今日の講義で学ぶ内容 for 文 変数のスコープ for 文の入れ子 繰り返し文 1 for 文 for 文最初に一度だけ初期化の式を処理します条件が true の場合 文を実行し 更新の式を処理して繰り返します条件が false の場合 for 文を終了します 条件は boolean 型で 関係演算子で表現される式などを記述します for( 初期化の式

More information

1 JAVA APPLET 実習 1. はじめに Java フォルダに applet フォルダを作成する 2. 実習問題の作成 J01.java public class J01 extends Applet{ public void paint(graphics kaku){ kaku.drawstring("hello World from Java!",60,70); j01.html

More information

.NETプログラマー早期育成ドリル ~VB編 付録 文法早見表~

.NETプログラマー早期育成ドリル ~VB編 付録 文法早見表~ .NET プログラマー早期育成ドリル VB 編 付録文法早見表 本資料は UUM01W:.NET プログラマー早期育成ドリル VB 編コードリーディング もしくは UUM02W:.NET プログラマー早期育成ドリル VB 編コードライティング を ご購入頂いた方にのみ提供される資料です 資料内容の転載はご遠慮下さい VB プログラミング文法早見表 < 基本文法 > 名前空間の定義 Namespace

More information

Microsoft PowerPoint - class04.ppt

Microsoft PowerPoint - class04.ppt フローチャート フローチャートとは プログラムの処理の流れを整理し 図的に順序立てて描いたもの 流れ図流れ図ともいう 例 : 始め 半径 R 端子 : 開始 終了 停止などを示す 手操作入力 : キーボードなどから手で操作して入力することを示す 面積 S πr 2 処理 : あらゆる種類の処理を示す S 終わり 表示 : ディスプレイ表示を示す このようにフローチャートでは 記号形状自体が処理の意味を示している

More information

1. 入力画面

1. 入力画面 指定した時刻に指定したマクロ (VBA) を実行するプログラム (VBA) 益永八尋 様々な業務を行っている場合には 指定した時刻に指定したマクロ (Macro VBA) を実行したくなる場合がある たとえば 9:00 17: 00 や 1 時間 6 時間間隔に指定したマクロ (Macro VBA) を実行する この様な場合に対応できるように汎用性の高いプログラムを作成した この場合に注意する必要があるのは

More information

cp-7. 配列

cp-7. 配列 cp-7. 配列 (C プログラムの書き方を, パソコン演習で学ぶシリーズ ) https://www.kkaneko.jp/cc/adp/index.html 金子邦彦 1 本日の内容 例題 1. 月の日数配列とは. 配列の宣言. 配列の添え字. 例題 2. ベクトルの内積例題 3. 合計点と平均点例題 4. 棒グラフを描く配列と繰り返し計算の関係例題 5. 行列の和 2 次元配列 2 今日の到達目標

More information