|
|
|
- みがね にかどり
- 5 years ago
- Views:
Transcription
1 オートマトンと言語理論 テキスト 成蹊大学理工学部情報科学科 山本真基
2
3
4 ii
5 iii DFA NFA ϵ- ϵ-nfa
6 iv
7 Σ Σ Σ x Σ x x x ϵ Σ Σ = 1.1. a, b, c,..., z, A, B, C,..., Z 1.1 ( ). 1. Σ = {0, 1} 2. Σ = {0, 1, 2,..., 9, a,b,c,...,z,a,b,c,...,z, #, $, %} 3. Σ = {0, 1, (, )} 1.2 ( ). Σ = {0, 1, (, )} Σ
8 (101)(((0 3. ((000)(111))(010)(101) 00#11 Σ # Σ 1.1. Σ = {a,b,c} Σ 1.1. Σ p p Σ #include<iostream> using namespace std; int main() { int a=1; cout << a << endl; } 1.1: Σ #include<iostream> using namespace std; int main() { int a=1; cout << a << endl; } 1.2: Σ Σ 1.2 Σ Σ Σ
9 1.1 3 L L L L 1.4 ( ). Σ = {a,b,c} L Σ L = {a, ab, abc, ababa, abbcca}. L = ( ). Σ = {0, 1} L Σ L = {x : n N[x n ]}. L 1.6 ( ). Σ L Σ L = {p : p }. L 1.2. Σ Σ Σ 1.3 Σ k x 1, x 2,..., x k Σ x 1 x 2 x k x 1 = x 2 = = x k = a Σ x 1 x 2 x k a k k = 0 a 0 ϵ 1.4 Σ Σ Σ Σ Σ Σ Σ def = {xy : x, y Σ}.
10 4 1 k N Σ k Σ 0 def = Σ Σ Σ }{{} def = {ϵ} k def = {x 1 x 2... x k : x 1, x 2,..., x k Σ} Σ Σ Σ def = k N {0} Σ k Σ x Σ x Σ L Σ L Σ 1.7. Σ = {0, 1} 1. Σ Σ = {00, 01, 10, 11} 2. Σ 3 = {000, 001, 010, 011, 100, 101, 110, 111} 1. Σ x =000 x Σ 3 Σ 2. Σ L = {000, 111} L Σ 3 Σ 1.1. Σ Σ = n Σ k = n k k = 0 Σ 0 = {ϵ} = Σ Σ Σ Σ Σ ϵ Σ
11 = {ϵ} 1.2 Σ = {0, 1, 2,..., 9,.} Σ L L def = {a Σ : a } L L L L 5. 1 L L 7. 10/3 L L Σ = Σ \ {.}, Σ = Σ \ {0} {0} Σ Σ ({0} Σ Σ ) {.} Σ Σ 1.3 Σ = {0, 1, 2,..., 9,.} Σ L L def = {a Σ : a }. L
12 6 1 Σ 0 Σ. Σ Σ. Σ... Σ 1.3: L
13 Σ L Σ k x 1, x 2,..., x k L x 1 x 2 x k x 1 = x 2 = = x k = y L x 1 x 2 x k y k k = 0 y 0 ϵ 2.2 Σ L, L 1, L 2 Σ : L 1 L 2 def = {x : x L 1 x L 2 }, : L 1 L 2 def = {xy : x L 1 y L 2 }, : L def = {x 1 x 2... x k : k N {0} x 1, x 2,..., x k L}. 2.1 ( ). Σ = {0, 1, #} Σ L 1 = {0 n #1 n : n N {0}}, L 2 = {1 n #0 n : n N {0}}, L 1 L 2 = {0 n #1 n, 1 n #0 n : n N {0}}.
14 L = L 2. ϵ L L {ϵ} L 2.2 ( ). Σ = {0, 1, #} Σ L 1 = {0, 1}, L 2 = {ϵ, #0, #1}, L 1 L 2 = {0, 1, 0#0, 0#1, 1#0, 1#1} L 2 L 1 = {0, 1, #00, #01, #10, #11} L {ϵ} = {ϵ} L = L 2. L = L = 2.3 ( ). Σ = {0, 1, #} L = {00#, 11#}, Σ L = {ϵ, 00#, 11#, 00#00#, 00#11#, 11#00#, 11#11#, 00#00#00#,... } Σ = {0, 1} L = {00, 11} L 000 L ,, L 1 L 2 L (L 1 L 2 ) (L ) (L 1 (L 2 L)) 2.3 Σ Σ L
15 , {ϵ} 2. x Σ {x} 3. L, L 1, L 2 L 1 L 2, L 1 L 2, L Σ Σ,, 2.4 L REG ( ). Σ = {0, 1, #} 1. L = {0, 1} {0} {1} 2. L = {00, 11, 0#, 1#, 01#, 10#} {0} {0} {1} {1} {0} {#} {1} {#} {0} {1} {#} {1} {0} {#}. 3. L = {w Σ : w 1 } Σ {1} Σ Σ Σ L Σ Σ L 2.5 ( ). Σ = {0, 1}
16 10 2 {0} {1} {0} {w Σ : w } {0} {1} {0} {1} {0} {w Σ : w } Σ {010} Σ {w Σ : w 010 } Σ {010} {w Σ : w 010 } {0} Σ Σ {1} {w Σ : w 0 1 } 2.2. Σ = {0, 1} {0 n : n N} {1 n : n N} {0 i 1 j : i, j N} {0 n 1 n : n N}. {0 n : n N} {1 n : n N} {0 i 1 j : i, j N} 2.5. {0 n 1 n : n N} Σ = {0, 1} 1. {0} Σ {0} {1} Σ {1}. 2. (Σ Σ). 3. {1} ({0} {1} {0} {1} ) Σ = {0, 1} 1. {w Σ : w }. 2. {w Σ : w }. 3. {w Σ : w 0 }.
17 Σ = {0, 1} L = {w Σ : w 00 }. L {1} ({01} {1} ) {ϵ, 0} R R = L R L R L ( ) w R w L w 0 R {01} {1} {011 n : n N {0}} 2.8. A A = {011 n : n N {0}} w 0 y 1, y 2,..., y k A k N {0} w w = y 1 y 2... y k w = y 1 y 2... y k w 00 A k k = 0 w = ϵ y 1 y 2... y k 1 y i A 00 y 1 y 2... y k 1 y k y i A w = y 1 y 2... y k 1 00 w ϵ 1 n N {0} y k = 011 n w = w y k 00 ( ) w L w R w 0 w y 1, y 2,..., y k k N {0} w = y 1 y 2... y k
18 w = i [k] i = 1 : y i {1} {01} {1} i [k] \ {1, k} : y i {01} {1} i = k : {01} {1} {ϵ, 0} w = w = w R = {1} ({01} {1} ) {ϵ, 0} Σ = {0, 1} L = {w Σ : w 000 } L Σ L Σ x Σ x L x L
19 Σ = {0, 1} a L = {w Σ : w 01 } b L = {w Σ : w 10 } c L = {w Σ : w 11 } d L = {w Σ : w 001 } e L = {w Σ : w 100 } 2. Σ = {0, 1} a L = {w Σ : w 0 1 } b L = {w Σ : w } c L = {w Σ : w } 3. Σ = {0, 1} a {ϵ, 1} {01} {ϵ, 0}. b {ϵ, 0} ({1} {1} {0}) {1}. c {ϵ, 0, 00} ({1} {1} {0, 00}) {1}.
20
21 DFA 3.1 DFA (Q, Σ, δ, q 0, F ) Q : Σ : δ : Q Σ Q q 0 : q 0 Q F : F Q Q, Σ, F 3.1 ( ). M 1 = (Q, Σ, δ, q 0, {q 1 }) Q = {q 0, q 1 }, Σ = {0, 1} δ : Q Σ Q 0 1 q 0 q 0 q 1 q 1 q 1 q
22 , ( ). M 2 = (Q, Σ, δ, q 0, {q 2 }) Q = {q 0, q 1, q 2 }, Σ = {0, 1, a} δ : Q Σ Q 0 1 a q 0 q 0 q 0 q 1 q 1 q 1 q 1 q 2 q 2 q 2 q 2 q 2 0, 1 0, 1 0, 1, a a 0 1 a M = (Q, Σ, δ, q 0, F ) w = w 1 w 2... w n Σ n w Σ n M w r 0, r 1,..., r n Q 1. r 0 = q 0 2. i [n][δ(r i 1, w i ) = r i ] 3. r n F M L(M) = {w Σ : M w } M L(M) L DFA L DFA = {L : DFA L }
23 3.1 DFA ( ). 3.1 M 1 1, 01, 10, 11, L(M 1 ) 0, 00, 000, L(M 1 ) M 1 L 1 = L(M 1 ) L 1 = {w {0, 1} : w 1 }. 3.4 ( ). 3.2 M 2 aaa, 01a01a, a0a1a0a1a L(M 2 ) 0a1, 1a0, a01010 L(M 2 ) M 2 L 2 = L(M 2 ) L 2 = {w {0, 1, a} : w a } Σ = {0, 1} DFA 1. M = (Q, Σ, δ, q 0, {q 1 }). Q = {q 0, q 1, q 2 } δ : Q Σ Q 0 1 q 0 q 0 q 1 q 1 q 1 q 2 q 2 q 2 q 2 2. M = (Q, Σ, δ, q 0, {q 0 }). Q = {q 0, q 1 } δ : Q Σ Q 0 1 q 0 q 0 q 1 q 1 q 1 q 0 3. M = (Q, Σ, δ, q 0, {q 0 }). Q = {q 0, q 1, q 2 } δ : Q Σ Q 0 1 q 0 q 0 q 1 q 1 q 1 q 2 q 2 q 2 q 0
24 a , a 0, a 0, 1 0, 1, a 4 0, 1, a 3.5. Σ = {0, 1, a} L = {0, 01, 01a} M = (Q, Σ, δ, q 0, F ). Q = {q 0, q 1, q 2, q 3, q 4 }, Σ = {0, 1, a}, F = {q 1, q 2, q 3 } δ : Q Σ Q 0 1 a q 0 q 1 q 4 q 4 q 1 q 4 q 2 q 4 q 2 q 4 q 4 q 3 q 3 q 4 q 4 q 4 q 4 q 4 q 4 q Σ = {0, 1} 1. L = {w Σ : w 010 }. 2. L = {w Σ : w 101 }. 3. L = {w Σ : w 010 }. 4. L = {w Σ : w 101 }. 5. L = {w Σ : w 1 0 }.
25 3.2 NFA NFA 3.3 NFA (Q, Σ, δ, q 0, F ) Q : Σ : δ : Q Σ 2 Q q 0 : q 0 Q F : F Q Q, Σ, F 3.2. Q = {q 0, q 1, q 2 } 2 Q = {, {q 0 }, {q 1 }, {q 2 }, {q 0, q 1 }, {q 0, q 2 }, {q 1, q 2 }, {q 0, q 1, q 2 }} Q DFA 3.6 ( ). N = (Q, Σ, δ, q 0, {q 2 }) Q = {q 0, q 1, q 2 }, Σ = {0, 1} δ : Q Σ 2 Q 0 1 q 0 {q 0 } {q 0, q 1 } q 1 {q 2 } {q 2 } q 2 0, , 1 2
26 20 3 δ(q 2, 0), δ(q 2, 1) N = (Q, Σ, δ, q 0, F ) w = w 1 w 2... w n Σ n w Σ n N w r 0, r 1,..., r n Q 1. r 0 = q 0 2. i [n][r i δ(r i 1, w i )] 3. r n F N L(N) = {w Σ : N w } N L(N) L NFA L NFA = {L : NFA L } ( ). 3.6 N N L = L(N) 10, 11, 111, L(N) 0, 1, 00, 01, 101, L(N) L = {w Σ : w 1 } Σ = {0, 1} NFA 1. N = (Q, Σ, δ, q 0, {q 2 }) Q = {q 0, q 1, q 2 }, Σ = {0, 1} δ : Q Σ 2 Q
27 3.2 NFA x 0 1 x (a) 111 (b) : 0 1 q 0 {q 1 } q 1 {q 1 } {q 1, q 2 } q 2 2. N = (Q, Σ, δ, q 0, {q 2 }) Q = {q 0, q 1, q 2 }, Σ = {0, 1} δ : Q Σ 2 Q 0 1 q 0 {q 1 } q 1 {q 1, q 2 } {q 1 } q Σ = {0, 1} 1. L = {w Σ : w 010 }. 2. L = {w Σ : w 010 }.
28 L DFA DFA DFA NFA 3.1. L NFA = L DFA 3.5 M = (Q, Σ, δ, q 0, F ) δ δ q Q s Σ δ (q, s) = { q s = ϵ δ(δ (q, t), c) s = tc (c Σ) N = (Q, Σ, δ, q 0, F ) δ δ q Q s Σ q s = ϵ δ (q, s) = δ(q, c) s = tc (c Σ) q δ (q,t) DFA M δ (q 0, 000) = q 0 δ (q 0, 010) = q 1 δ (q 1, 000) = q NFA N δ ({q 0 }, 010) = {q 0, q 2 } δ ({q 0, q 1 }, 010) = {q 0, q 2 } δ ({q 1, q 2 }, 010) =
29 3.2 NFA 23. L NFA L DFA L NFA L DFA L NFA L DFA 3.7. L NFA L DFA L NFA L DFA N = (Q, Σ, δ, q 0, F ) D = (Q D, Σ D, δ D, q D, F D ) N L(D) = L(N) N D Q D = 2 Q Σ D = Σ S Q D, a Σ δ D (S, a) = q S δ(q, a) q D = {q 0 } F D = {S Q D : S F } L(D) = L(N) x Σ δd (q D, x) = δ (q 0, x) 3.8. x x = x Σ x 1 x = ya y Σ, a Σ δd(q D, x) = δd(q D, ya) = δ D (δd(q D, y), a) ( δd ) = δ D (δ (q 0, y), a) ( ) = δ(q, a) ( δ D ) q δ (q 0,y) = δ (q 0, ya) ( δ ) = δ (q 0, x).
30 NFA N = (Q, Σ, δ, q 0, F ) DFA M = (Q D, Σ D, δ D, q D, F D ) Q D = {, {q 0 }, {q 1 }, {q 2 }, {q 0, q 1 }, {q 0, q 2 }, {q 1, q 2 }, {q 0, q 1, q 2 }} Σ D = Σ q D = {q 0 } F D = {{q 2 }, {q 0, q 2 }, {q 1, q 2 }, {q 0, q 1, q 2 }} δ D 0 1 {q 0 } {q 0 } {q 0, q 1 } {q 1 } {q 2 } {q 2 } {q 2 } {q 0, q 1 } {q 0, q 2 } {q 0, q 1, q 2 } {q 0, q 2 } {q 0 } {q 0, q 1 } {q 1, q 2 } {q 2 } {q 2 } {q 0, q 1, q 2 } {q 0, q 2 } {q 0, q 1, q 2 } NFA DFA 1. L = {w00 : w {0, 1} } 2. L = {w11 : w {0, 1} } 3.3 ϵ- ϵ-nfa 3.6 Σ ϵ ϵ = 0 Σ ϵ = Σ {ϵ} 3.7 ϵ- ϵ-nfa
31 3.3 ϵ- ϵ-nfa 25 (Q, Σ, δ, q 0, F ) Q : Σ : δ : Q Σ ϵ 2 Q q 0 : q 0 Q F : F Q Q, Σ, F ϵ- L ϵ-nfa L ϵ-nfa = {L : NFA L } 3.11 (ϵ- ). ϵ- N = (Q, Σ, δ, q 0, {q 3, q 6 }) Q = {q 0, q 1, q 2, q 3, q 4, q 5, q 6 }, Σ = {0, 1} δ : Q Σ ϵ 2 Q ϵ 0 1 q 0 {q 1, q 4 } q 1 {q 1, q 2 } {q 1 } q 2 {q 3 } q 3 q 4 {q 4 } {q 4, q 5 } q 5 {q 6 } q 6 0, 1 ε , 1 ε
32 26 3 N L = L(N) L = {w Σ : w } 3.4. δ(q 0, ϵ) = {q 1, q 4 } ϵ- ϵ L NFA NFA 3.12 (ϵ- ). Σ = {a, b, c} L = {a i b j c k Σ : i, j, k N {0}} L ϵ- N = (Q, Σ, δ, q 0, {q 0, q 1, q 2 }) Q = {q 0, q 1, q 2 } δ : Q Σ ϵ 2 Q a b c ε ε L NFA NFA 3.2. L ϵ-nfa = L NFA L REG = L DFA
33 L REG L DFA L REG L DFA 3.4 (L REG L DFA ). L Σ L L ϵ-nfa = L DFA L ϵ-nfa 2.3 ϵ-nfa 1. L = 2. L = {ϵ} 3. x Σ L = {x} NFA DFA k N {0},, k L,, k L = L 1 L 2 L 1, L 2,, k L 1, L 2 NFA N 1, N 2 L NFA N N 1, N L = L 1 L 2 L 1, L 2,, k L 1, L 2 NFA N 1, N 2 L NFA N N 1, N L = L 0 L 0,, k L 0 NFA N 0 L NFA N N NFA
34 28 3 N N 1 N 1 ε N 2 N 2 ε 3.2: L = L 1 L 2 N 1 N 2 N N ε 1 N 2 ε 3.3: L = L 1 L 2
35 N N 0 ε N 0 ε ε ε 3.4: L = L 0 L ϵ-nfa L DFA 3.5 (L REG L DFA ). M L M L. L 3.8 (Q, Σ, δ, q 0, F ) Q : Σ : δ : (Q \ {q accept }) (Q \ {q start }) R q start : q start Q q accept : q accept Q R Σ DFA M G M G 3.1. G L
36 30 3. G L 3.5 GNFA G 1. G GNFA a q Q \ {q start, q accept } b G = (Q, Σ, δ, q start, q accept ) i. Q = Q \ {q} ii. q i Q \ {q, q accept }, q j Q \ {q, q start } δ (q i, q j ) def = R 1 R R 2 R 3. R = δ(q, q) R 1 = δ(q i, q) R 2 = δ(q, q j ) R 3 = δ(q i, q j ) 2. G q start q accept 3.5: GNFA G reg L(G) = L(G reg ). G k k = 2 k 1 GNFA k GNFA G 1 GNFA G 1-(a) q L(G) = L(G ) ( ) w L(G) w G q i1, q i2,..., q in G w q i1 = q start j [n 1] w j δ(q ij, q ij+1 ) w j Σ w G q {q i1, q i2,..., q in } G w
37 q {q i1, q i2,..., q in } q = q ij w j 1 δ(q ij 1, q ij ), w j δ(q ij, q ij+1 ) 1-(b)-(ii) δ w j 1 w j δ (q ij 1, q ij+1 ) w G ( ) w L(G ) w G q i1, q i2,..., q in G w q i1 = q start j [n 1] w j δ(q ij, q ij+1 ) w j Σ w G j [n 1] L(G) = L(G ) G k 1 L(G ) = L(G reg ) L(G) = L(G ) = L(G reg ) ( ). L p p a L a a = xyz 1. i N {0}[xy i z L] 2. y > 0 3. xy p. L L M = (Q, Σ, δ, q 0, F ) p p = Q p a L *1 a = n p a L r 0, r 1,..., r n Q 1. r 0 = q 0 2. i [n][δ(r i 1, a i ) = r i ] 3. r n F 3.3. i, j [p] {0} i < j r i = r j *1
38 32 3. r 0, r 1,..., r p Q = p r i = r j i, j [p] i r i = r j j i < j a a = xyz x y z def = a 1 a i, def = a i+1 a j, def = a j+1 a p. i xy i z L z r n x a j +1 r j +1 a 1 a 2 a i -1 a i r 0 r 1 r r i-1 i a j a i +1 r i +1 r j -1 a i +2 a j -1 y r i+2 r j-2 r * 3.6: xy i z L ( ). L = {w {0, 1} : w } p p w L w w = xyz w = (01) p L w = xyz x = ϵ y = (01) 2 z = (01) p 2
39 w = 0 2p 1 2p L w = xyz x = ϵ y = 0 2 z = 0 2p 2 1 2p 3.7. L = {0 n 1 n : n N}. L p p w L w = 0 p 1 p w = xyz = 0 p 1 p xy p xy = 0 i, z = 0 j 1 p i + j = p y > 0 xyyz L L xyyz L L = {ww : w {0, 1} } 2. L = {ww R : w {0, 1} } 3. L = {w {0, 1} : w = w R }
40 DFA NFA ϵ-nfa a L = {w {0, 1} : w 111 } b L = {w {0, 1} : w i=1 w i 2 0} c L = {w {0, 1, 2} : w i=1 w i 3 0} d {0} {0, 1} {1} e {0} {0, 1} {0, 1} {1} 2. a L = {0 i 1 j : i > j}. b L = {w {0, 1} : w 0 1 }. c L = {1 n2 : n N {0}}. 3. L 1, L 2, L a L 1 L 2 b L 1 L 2 c L
41 (V, Σ, R, S) V : Σ : R : S : S V V, Σ, R x V, y (V Σ) x y 4.1 ( ). G 1 = (V, Σ, R, S) V = {S} Σ = {0, 1} R S 0S1, S ϵ S 0S1 ϵ. 4.2 ( ). G 2 = (V, Σ, R, S) V =
42 36 4 {S, A, B} Σ = {0, 1} R S 0S1 0A 1B, A 0A ϵ, B 1B ϵ. 4.2 G = (V, Σ, R, S) u, v (V Σ) u v u G v G u v x, y, z (V Σ), A V 1. u = xay, 2. v = xzy, 3. (A z) R. w Σ w Σ G w u 0, u 1,..., u n (V Σ) S = u 0 u 1 u n 1 u n = w. S G w G S w 4.3 ( ). 4.1 G 1 S G1 0S1 0S1 G1 00S11 00S11 G1 000S S G S 0S1 00S11 000S ( ). 4.2 G 2 00S11 G2 000S111 00S11 G2 000A11 00S11 G2 001B S G , S G : S 0S1 00S11 000A : S 0S1 00S11 000S B B
43 G 1, G G = (V, Σ, R, S) G L(G) def = {w Σ : S w} G L(G) Σ L Σ G = (V, Σ, R, S) L = L(G) L L CFG 4.5 ( ). 4.1 G 1 L(G 1 ) = {0 n 1 n : n N {0}}. 4.6 ( ). 4.2 G 2 L(G 2 ) = {0 i 1 j : i, j N {0}, i j} L REG L CFG. L REG L CFG L REG L CFG 5.4 L DFA L PDA?? L(G 1 ) L(G 2 ) L REG L CFG 4.7 ( ). Σ = {0, 1} L = {w Σ : w 0 1 } G = (V, Σ, R, S) V = {S, A} R S 0A A1, A 0A 1A ϵ Σ = {0, 1} 1. L 1 = {w Σ : w 010 }
44 L 2 = {w Σ : w 010 } 3. L 3 = {w Σ : w 1 } 4.8 ( ). G = (V, Σ, R, S) V = {S} Σ = {(, ), } R S SS (S) G 4.3. G 1. (( ) ) 2. ( )(( )( )) 4.9 ( ). G = (V, Σ, R, < exp >) V = {< exp >, < term >, < fact >} Σ = {+,,, /, (, )} R R < exp > < term > + < exp > < term > < exp > < term >, < term > < fact > < term > < fact > / < term > < fact >, < fact > (< exp >) a. G a 1 (2 3) < exp > < term > < exp > < fact > < term > 1 < fact > 1 (< exp >) 1 (< term > < exp >) 1 (< fact > < term >) 1 (2 < fact >) 1 (2 3) (1 (2 3)) ( 1) 2 3/5 < exp > < term > < exp > < fact > < term > < fact > < term >
45 (< exp >) < fact > 2 < term > (1 (2 3)) (< exp >) 2 < fact > / < term > (1 (2 3)) (< term >) 2 3/ < fact > (1 (2 3)) (< fact >) 2 3/5 (1 (2 3)) ( 1) 2 3/ (1 2) (2 3)/(3 1) /(1 + 1/(1 + 1/2)) 4.5. Σ = {0, 1} G i = (V i, Σ, R i, S) 1. V 1 = {S, A}, R 1 = {S A1A, A A0 ϵ}. 2. V 2 = {S}, R 2 = {S 0S0 1S1 ϵ}. 3. V 3 = {S}, R 3 = {S 0S0 1S1 0 1 ϵ} Σ = {0, 1} {ww R : w {0, 1} }, {w Σ : w = w R } {ww : w {0, 1} }. {ww R : w {0, 1} }, {w Σ : w = w R } {ww : w {0, 1} } Σ = {0, 1} 1. L 1 = {w Σ : w 1 }. 2. L 2 = {w Σ : w 00 }. 3. L 3 = {w Σ : w 1 }.
46 L 4 = {0 i 1 j : i > j}. 5. L 5 = {w {0, 1} : w 0 1 } Σ = {0, 1} L = Σ \ {0 n 1 n : n N {0}}. L G = (V, Σ, R, S) R L(G) = L S XA B A XXA ϵ X 1 0 B 0B1 Y Y 0Z0 1Z0 1Z1 Z 0Z 1Z ϵ ( ) w L(G) w L S XA w i N S XA XXXA X i A X i X w L S B w i N {0} S B 0B1 00B11 0 i B1 i 0 i Y 1 i 1. 0 i Y 1 i 0 i 0Z01 i 2. 0 i Y 1 i 0 i 1Z01 i 3. 0 i Y 1 i 0 i 1Z11 i Z w L
47 ( ) w L w L(G) w ( ) w S XA w w L w {0 n 1 n : n N {0}} w i N {0} x Σ 1. 0 i 0x01 i 2. 0 i 1x01 i 3. 0 i 1x11 i ( ) w S B G = (V, Σ, R, S) T G 1. T 2. T 3. T S 4. T v v 1,..., v k v v A v 1,..., v k A 1,..., A k A A 1... A k G = (V, Σ, R, S) w (V Σ) T w 1. T G 2. T w a (a) 1 (2 3) (b) (1 (2 3)) ( 1) 2 3/5 (b) (a) (a)
48 42 4 exp term - exp exp fact term term - exp 1 fact fact * term term ( exp ) ( ) fact fact * term term - exp ( exp ) 2 fact / term fact term term 3 fact 2 fact (a) fact (a) 1 (2 3) (b) (1 (2 3)) ( 1) 2 3/5 4.1: (1 2) (2 3)/(3 1) /(1 + 1/(1 + 1/2)) G = (V, Σ, R, S) R G A BC A a A B, C a
49 ( ). L Σ L Σ x Σ x L x L
50 G = (V, Σ, R, S) V = {S, A, B}, Σ = {0, 1}, S AB BA A 0A0 0A1 1A0 1A1 0 B 0B0 0B1 1B0 1B a L 1 = {0 i 1 j : i > 2j}. b L 2 = {0 i 1 i 2 j : i, j N {0}}. c L 3 = {0 i 1 j 2 i : i, j N {0}}.
51 45 5 * PDA (Q, Σ ϵ, Γ ϵ, δ, q 0, F ) Q : Σ ϵ : Γ ϵ : δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ q 0 : q 0 Q F : F Q Q, Σ ϵ, Γ ϵ, F Γ ϵ $ PDA NFA *1 {ww R : w {0, 1} }
52 ( ). N 1 = (Q, Σ ϵ, Γ ϵ, δ, q 0, {q 0, q 3 }) Q = {q 0, q 1, q 2, q 3 }, Σ = {0, 1}, Γ = {0, $} δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ ϕ Σ ϵ 0 1 ϵ Γ ϵ 0 $ ϵ 0 $ ϵ 0 $ ϵ q 0 (q 1, $) q 1 (q 1, 0) (q 2, ϵ) q 2 (q 2, ϵ) (q 3, ϵ) q 3 ϕ 0, ε 0 1, 0 ε ε, ε $ 1, 0 ε ε, $ ε δ δ(q i, y, a) = (q j, b) y Σ ϵ, a, b Γ ϵ y, a b 5.2 ( ). N 2 = (Q, Σ ϵ, Γ ϵ, δ, q 0, {q 3, q 4, q 5, q 6 }) Q = {q 0, q 1, q 2,..., q 6 }, Σ = {0, 1}, Γ = {0, $} δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ 5.2 N = (Q, Σ ϵ, Γ ϵ, δ, q 0, F ) w = w 1 w 2... w n Σ n w Σ n N w w = y 1 y m y i Σ ϵ r 0, r 1,..., r m Q s 0, s 1,..., s m Γ 1. r 0 = q 0, s 0 = ϵ, s 1 = $
53 , ε 0 1, 0 ε ε, 0 ε 3 ε, ε $ 1, 0 ε , ε ε 1, ε ε 1, $ $ , $ $ 0, ε ε 1, ε ε 2. i [m], a, b Γ ϵ, t Γ 3. r m F 1. (r i, b) δ(r i 1, y i, a) 2. s i 1 = at 3. s i = bt N L(N) = {w Σ : N w } N L(N) L PDA L PDA = {L : PDA L } NFA 5.3. δ δ(q i, y, a) = (q j, b) y Σ ϵ, a, b Γ ϵ a b a pop b push *2 a = ϵ : b push b = ϵ : a pop 5.3 ( ). 5.1 N 1 ϵ, 01, 0011, L(N 1 ) 0, 1, 000, 111, 0101, 1001, L(N 1 ) *2 Γ ϵ
54 48 5 N 1 L 1 = L(N 1 ) L 1 = {0 n 1 n : n N {0}}. 5.4 ( ). 5.2 N 2 0, 1, 000, 111, 00011, L(N 2 ) ϵ, 01, 0011, , 0101, 1001 L(N 2 ) N 2 L 2 = L(N 2 ) L 2 = {0 i 1 j : i, j N {0}, i j} L DFA L PDA.. L DFA L PDA DFA PDA DFA PDA L = {0 n 1 n : n N {0}} L L PDA 5.1, 5.3 L L DFA L L DFA L PDA 5.1. Σ = {0, 1} PDA 1. N 1 = (Q, Σ ϵ, Γ ϵ, δ, q 0, {q 0, q 3 }) Σ ϵ 0 1 ϵ Γ ϵ 0 1 $ ϵ 0 1 $ ϵ 0 1 $ ϵ q 0 (q 1, $) q 1 (q 1, 0) (q 1, 1) (q 2, ϵ) q 2 (q 2, ϵ) (q 2, ϵ) (q 3, ϵ) q 3 2. N 2 = (Q, Σ ϵ, Γ ϵ, δ, q 0, {q 0, q 3 }) Σ ϵ 0 1 Γ ϵ 0 1 $ ϵ 0 1 $ ϵ q 0 q 1 (q 1, 0), (q 2, ϵ) (q 1, 1), (q 2, ϵ) q 2 (q 2, ϵ) (q 2, ϵ) q 3
55 Σ ϵ ϵ Γ ϵ 0 1 $ ϵ q 0 (q 1, $) q 1 (q 2, ϵ) q 2 (q 3, ϵ) q Σ = {0, 1} 1. L 1 = {w Σ : w 1 }. 2. L 2 = {w Σ : w 1 }. 3. L 3 = {0 i 1 j : i > j}. 4. L 4 = {0 i 1 j : i < j}. 5. L 5 = {w {0, 1} : w 0 1 } PDA δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ δ(q,, ϵ) = {(q, ) : q Q } δ(q,, a) = {(q, ϵ) : q Q } PDA 5.3. PDA δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ PDA
56 L CFG = L PDA. L CFG L PDA L CFG L PDA 5.5 (L CFG L PDA ). L L. L G = (V, Σ, R, S) L = L(G) G P = (Q, Σ ϵ, Γ ϵ, δ, q 0, F ) Q = {q 0, q loop, q 1 }, Γ = V Σ, F = {q 1 } 5.3 δ : Q Σ ϵ Γ ϵ 2 Q Γ ϵ δ(q 0, ϵ, ϵ) = {(q loop, S)} A B A V Γ, B Γ ϵ δ(q loop, ϵ, A) = {(q loop, B)} a δ(q loop, a, a) = {(q loop, ϵ)} δ(q loop, ϵ, $) = {(q 1, ϵ)} 5.1. L = L(P ). L L(P ) L L(P ) PDA P P L CFG PDA P L = L(P ) = {0 n 1 n : n N {0}} ε, S 0S1 ε, S ε 0, 0 ε 1, 1 ε ε, ε S ε, $ ε 0 loop 1
57 CFG PDA 5.6 (L CFG L PDA ). P = (Q, Σ ϵ, Γ ϵ, δ, q 0, F ) L P L. 5.2 P P F = 1 P G = (V, Σ, R, S) V = {A pq : p, q Q} {S} R S A q0 q accept x Γ (s, x) δ(p, a, ϵ) (t, ϵ) δ(q, b, x) p, q, s, t Q, a, b Σ A pq aa st b A pq A pr A rq A pp ϵ 5.2. L = L(G). L L(G) L L(G) G L ( ). L p p w L w w = axyzb 1. i N {0}[ax i yz i b L] 2. xz > 0 3. xyz p
58 52 5. L G = (V, Σ, R, S) L = L(G) 4.4 G p = 2 V +1 p w L w T 5.3. T T V w T P P V A V P A. P V V + 1 A V P A P v V +1, v V,..., v 1, v 0 a, A V,..., A 1, A 0 v 0 A A i = A j = A i > j v i v j v i T T i v j T T j 5.6. T i V w = axyzb 1 v i v j v i y v i v j ayb ayb L v i v j
59 v i v j a x y z b 5.1: v i = v j y a b 5.2: v j xyz v j v i T i ax 2 yz 2 b ax 2 yz 2 b L ax i yz i b L 1 2 xz = 0 x = z = ϵ v i = v j v i v j xz > T i V +1
60 54 5 v i v i a x v j z b x y z 5.3: xyz 2 V +1 = p 5.6 ( ). L = {ww R : w {0, 1} } 4.2 p p w L w w = axyzb w = 0 p 1 p 1 p 0 p L w = axyzb a = 0 p 1 p 2 x = 1 p 2 y = ϵ z = 1 p 2 b = 1 p 2 0 p 5.8. {ww : w Σ }. L p p w L w = 0 p 1 p 0 p 1 p w = axyzb = 0 p 1 p 0 p 1 p xyz p xyz
61 xyz = 0 i i p 1 i j p 0 i 1 j i + j p 1 i 0 j i + j p axxyzzb L L 5.7. axxyzzb L 5.8. L = {0 n 1 n 2 n : n N {0}}
62 a L = Σ \ {0 n 1 n : n N {0}} b 4.8 c a L = {0 i 1 j 2 k : 0 i j k}. b L = {0 n2 : n N {0}}. 3. L 1, L 2, L a L 1 L 2 b L 1 L 2 c L
63 57 1. Σ abcabca abcdef 2. Σ Σ 3. Σ k Σ k n k 4. Σ Σ 1 ϵ Σ Σ ϵ Σ 5. a ϵ Σ 0 Σ b 0 = {ϵ}, k N[ k = ] 1. a b ϵ 2. a w L wϵ = ϵw = w b xy L x L y y 3. L = {ϵ, 00, 11, 0000, 0011, 1100, 1111, ,... } Σ = {00, 11} L = Σ 4. Σ 5. {0 n : n N} {0} {0} {1 n : n N} {1} {1} {0 i 1 j : i, j N} {0} {0} {1} {1} 6. a {w Σ : w }. b {w Σ : w }.
64 58 c {w Σ : w 0 }. 7. a {0} Σ {1} {1} Σ {0}. b Σ (Σ Σ). c {1} {0} {1} ({0} {1} {0} {1} ). 8. {1} {1 n : n N {0}} {01} {1 n : n N {0}} {011 n : n N {0}} 9. A {1} ({01, 001} {1} ) {ϵ, 0, 00} 1. a {1} {0} b {0} {1} c {0} ({10} {0} ) {ϵ, 1} d {1} ({01} {1} ) {0} e 2. a b {ϵ, 1} {01} {ϵ, 0} c {ϵ, 1, 11} ({0, 00} {1, 11}) {ϵ, 0, 00} 3. a {w Σ : w 0 1 }. b {w Σ : w 00 }. c {w Σ : w 000 }. 1. a {w Σ : w 1 } b {w Σ : w 1 } c {w Σ : w 1 } 2. a 010
65 , b c d e δ(q 0, 1) = {q 0, q 1 } 4. a {w Σ : w 0 1 } b {w Σ : w 1 0 } 5. a 010 0, 1 0, b 010
66 60 0, DFA NFA 8. N x δ (q 0, x) F D x δd (q D, x) F D F D δ (q 0, x) = δd (q D, x) N D 9. x = 0 x = ϵ δd (q D, x) = δ (q 0, x) = {q 0 } 10. a b 11. 0,
67 61 a b c b c c 13. a L = Σ b L = ϵ Σ Σ c L = {x} Σ x Σ 14. i = 0, 1, 2 N i = (Q i, Σ, δ i, p i, F i ) N = (Q, Σ, δ, q 0, F ) δ δ i a δ(q 0, ϵ) = {q 1, q 2 } b q F 1 δ(q, ϵ) = {p 2 } c δ(q 0, ϵ) = {p 0 } q F 0 δ(q, ϵ) = {p 0 } 15. M q 0 F G q start q accept δ(q start, q 0 ) = {ϵ} q F δ(q, q accept ) = {ϵ} δ(q, a) = q δ(q, q ) = {a} q, q q q accept, q q start δ(q, q ) =
68 G w G 17. xyyz = 0 k 1 p k > p 18. a 1 p 0 p 1 p 0 p L 1 p 0 p 1 p 0 p = xyz xy p xy = 1 i, z = 1 j 0 p 1 p 0 p xyyz L b 1 p 0 p 0 p 1 p L 1 p 0 p 0 p 1 p = xyz xy p xy = 1 i, z = 1 j 0 p 0 p 1 p xyyz L c 0 p 10 p L 0 p 10 p = xyz xy p xy = 0 i, z = 0 j 10 p xyyz L L 1, L 2, L M 1, M 2, M R 1, R 2 L 1, L 2 a R 1 R 2 L 1 L 2 M 1 M 2 L 1 L 2 b L 1 L 2 = L 1 L 2 R 1 R 2 L c L 1. G 1 G 2 S 0S1 00S11 001B S 0S1 00S11 000A A a V 1 = {S, A}, R 1 = {S A010A, A A0 A1 ϵ}. b V 2 = {S, A}, R 2 = {S A010, A A0 A1 ϵ}. c V 3 = {S, A}, R 3 = {S A1A, A A0 A1 ϵ}. 3. a S (S) (SS) ((S) ) (( ) ) b S SS (S)(S) ( )(SS) ( )((S)(S)) ( )(( )( )) 4. a < exp > < term > < exp >
69 63 < fact > < term > < exp > 1 < fact > < term > 1 2 < fact > b c < exp > < term > < fact > < term > (< exp >) < fact > / < term > (< term > < exp >) (< exp >)/ < fact > (< fact > < term >) (< term > < exp >)/(< exp >) (1 < fact >) (< fact > < term >)/(< term > < exp >) (1 2) (2 < fact >)/(< fact > < term >) (1 2) (2 3)/(3 < fact >) (1 2) (2 3)/(3 1) < exp > < term > + < exp > < fact > + < term > 1+ < fact > / < term > 1 + 1/ < fact > 1 + 1/(< exp >) 1 + 1/(1 + 1/(< exp >)) 1 + 1/(1 + 1/(< term > + < exp >)) 1 + 1/(1 + 1/(< fact > + < term >)) 1 + 1/(1 + 1/(1+ < fact > / < term >)) 1 + 1/(1 + 1/(1 + 1/ < fact >)) 1 + 1/(1 + 1/(1 + 1/2)) 5. a L 1 = {w Σ : w 1 } b L 2 = {ww R : w {0, 1} } c L 3 = {w {0, 1} : w = w R } 6. a V 1 = {S, A}, R 1 = {S A1A1A, A A0 ϵ}. b V 2 = {S, A}, R 2 = {S 1S 0A ϵ, A 1S ϵ}. c V 3 = {S, A}, R 3 = {S ASA 1, A 0 1}. d V 4 = {S, A}, R 4 = {S 0S1 0A, A 0A ϵ}. e V 5 = {S}, R 5 = {S 0S1S 1S0S ϵ}. ( )
70 L(G) = {xy Σ : x = y x y}. 2. a V 1 = {S, A}, R 1 = {S 00S1 0A, A 0A ϵ}. b V 2 = {S, A, B}, R 2 = {S AB, A 0A1 ϵ, B 2 ϵ}. c V 3 = {S, A}, R 3 = {S 0S2 A, A 1A ϵ}. 1. a L 1 = {ww R : w Σ }. b L 2 = {w Σ : w = w R }. 2. a b 0, ε # 0, # ε 1, ε # 1, # ε ε, ε $ 1, ε ε ε, $ ε c 0, ε 0 1, 0 ε ε, ε $ 1, 0 ε ε, 0 ε , ε ε 4 0, ε ε d
71 65 0, ε 0 1, 0 ε 1, $ $ ε, ε $ 1, 0 ε , $ $ 3 1, ε ε 4 1, ε ε e 0, ε 0 1, 0 ε 0, ε 0 2 ε, $ ε 1, $ $ ε, ε 0 0 ε, ε $ ε, ε 1 0, $ $ 1, ε 1 3 ε, $ ε 1, ε 1 0, 1 ε 0, ε 0 0, 1 ε 1, ε 1 1, 0 ε 0 ε, ε $ 1 ε, $ ε 2
72 66 3. ε, S 0S1 ε, S 0A ε, S 1B 0, 0 ε 1, 1 ε ε, ε S ε, $ ε 0 loop 1 ε, A 0A ε, B 1B ε, A ε, B ε ε 4. A BC A a 5. w p w p l 2 l p = 2 V +1 l V v i, v i+1,..., v V +1 T i 7. xyz = 0 i i p xz > 0 n > p axxyzzb = 0 n 1 p 0 p 1 p L 8. p w L w = 0 p 1 p 2 p 1. a b c 2. a p w L w = 0 p 1 p 2 p b p w L w = 0 p2 w = axyzb xyz p ax 2 yz 2 b p 2 + 2p < (p + 1) 2 3. a L 1 S 1 L 2 S 2 S S 1 S 2 b L 1 = {0 i 1 j 2 j : i, j N {0}}, L 2 = {0 j 1 j 2 i : i, j N {0}} L 1, L 2 *3 L 1 L 2 = {0 n 1 n 2 n : n N} c L 1 = {0 i 1 j 2 j : i, j N {0}}, L 2 = {0 j 1 j 2 i : i, j N {0}} *3
73 67 L 1, L 2 L = L 1 L 2 L L = L 1 L 2
74
75 Introduction to the Theory of Computation, Michael Sipser, Cengage Learning, J. R. J.
76 70, 1, 29 ϵ-, 24, 3, 1, 15, 2, 16, 20, 46, 7, 8, 9, 37, 8, 9, 26, 42, 41, 36, 1, 16, 20, 47, 45, 19, 37, 35, 1, 15, 3
77
78
, = = 7 6 = 42, =
http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1 1 2016.9.26, http://www.ss.u-tokai.ac.jp/~mahoro/2016autumn/alg_intro/ 1.1 1 214 132 = 28258 2 + 1 + 4 1 + 3 + 2 = 7 6 = 42, 4 + 2 = 6 2 + 8
x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y)
x, y x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 1 1977 x 3 y xy 3 x 2 y + xy 2 x 3 + y 3 = 15 xy (x y) (x + y) xy (x y) (x y) ( x 2 + xy + y 2) = 15 (x y) ( x 2 y + xy 2 x 2 2xy y 2) = 15 (x y) (x + y) (xy
ad bc A A A = ad bc ( d ) b c a n A n A n A A det A A ( ) a b A = c d det A = ad bc σ {,,,, n} {,,, } {,,, } {,,, } ( ) σ = σ() = σ() = n sign σ sign(
I n n A AX = I, YA = I () n XY A () X = IX = (YA)X = Y(AX) = YI = Y X Y () XY A A AB AB BA (AB)(B A ) = A(BB )A = AA = I (BA)(A B ) = B(AA )B = BB = I (AB) = B A (BA) = A B A B A = B = 5 5 A B AB BA A
all.dvi
38 5 Cauchy.,,,,., σ.,, 3,,. 5.1 Cauchy (a) (b) (a) (b) 5.1: 5.1. Cauchy 39 F Q Newton F F F Q F Q 5.2: n n ds df n ( 5.1). df n n df(n) df n, t n. t n = df n (5.1) ds 40 5 Cauchy t l n mds df n 5.3: t
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
2016 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 1 16 2 1 () X O 3 (O1) X O, O (O2) O O (O3) O O O X (X, O) O X X (O1), (O2), (O3) (O2) (O3) n (O2) U 1,..., U n O U k O k=1 (O3) U λ O( λ Λ) λ Λ U λ O 0 X 0 (O2) n =
‚åŁÎ“·„´Šš‡ðŠp‡¢‡½‹âfi`fiI…A…‰…S…−…Y…•‡ÌMarkovŸA“½fiI›ð’Í
Markov 2009 10 2 Markov 2009 10 2 1 / 25 1 (GA) 2 GA 3 4 Markov 2009 10 2 2 / 25 (GA) (GA) L ( 1) I := {0, 1} L f : I (0, ) M( 2) S := I M GA (GA) f (i) i I Markov 2009 10 2 3 / 25 (GA) ρ(i, j), i, j I
untitled
1 ( 12 11 44 7 20 10 10 1 1 ( ( 2 10 46 11 10 10 5 8 3 2 6 9 47 2 3 48 4 2 2 ( 97 12 ) 97 12 -Spencer modulus moduli (modulus of elasticity) modulus (le) module modulus module 4 b θ a q φ p 1: 3 (le) module
7 27 7.1........................................ 27 7.2.......................................... 28 1 ( a 3 = 3 = 3 a a > 0(a a a a < 0(a a a -1 1 6
26 11 5 1 ( 2 2 2 3 5 3.1...................................... 5 3.2....................................... 5 3.3....................................... 6 3.4....................................... 7
koji07-01.dvi
2007 I II III 1, 2, 3, 4, 5, 6, 7 5 10 19 (!) 1938 70 21? 1 1 2 1 2 2 1! 4, 5 1? 50 1 2 1 1 2 2 1?? 2 1 1, 2 1, 2 1, 2, 3,... 3 1, 2 1, 3? 2 1 3 1 2 1 1, 2 2, 3? 2 1 3 2 3 2 k,l m, n k,l m, n kn > ml...?
x () g(x) = f(t) dt f(x), F (x) 3x () g(x) g (x) f(x), F (x) (3) h(x) = x 3x tf(t) dt.9 = {(x, y) ; x, y, x + y } f(x, y) = xy( x y). h (x) f(x), F (x
[ ] IC. f(x) = e x () f(x) f (x) () lim f(x) lim f(x) x + x (3) lim f(x) lim f(x) x + x (4) y = f(x) ( ) ( s46). < a < () a () lim a log xdx a log xdx ( ) n (3) lim log k log n n n k=.3 z = log(x + y ),
2012 A, N, Z, Q, R, C
2012 A, N, Z, Q, R, C 1 2009 9 2 2011 2 3 2012 9 1 2 2 5 3 11 4 16 5 22 6 25 7 29 8 32 1 1 1.1 3 1 1 1 1 1 1? 3 3 3 3 3 3 3 1 1, 1 1 + 1 1 1+1 2 2 1 2+1 3 2 N 1.2 N (i) 2 a b a 1 b a < b a b b a a b (ii)
all.dvi
5,, Euclid.,..,... Euclid,.,.,, e i (i =,, ). 6 x a x e e e x.:,,. a,,. a a = a e + a e + a e = {e, e, e } a (.) = a i e i = a i e i (.) i= {a,a,a } T ( T ),.,,,,. (.),.,...,,. a 0 0 a = a 0 + a + a 0
7 3 4 5 a 6 7 8 9 a a a a a 0 3 4 5 6 7 8 9 0 3 DEF ABC 6 MNO 5 JKL 4 GHI 9 XYZ W 8 TUV 7 QRS P 0 POWER ON STD BY a 3 3 4 5 6 7 8 9 0 3 DEF ABC 6 MNO 5 JKL 4 GHI 9 XYZ W 8 TUV 7 QRS P 0 a a a a a a a
F = 0 F α, β F = t 2 + at + b (t α)(t β) = t 2 (α + β)t + αβ G : α + β = a, αβ = b F = 0 F (t) = 0 t α, β G t F = 0 α, β G. α β a b α β α β a b (α β)
19 7 12 1 t F := t 2 + at + b D := a 2 4b F = 0 a, b 1.1 F = 0 α, β α β a, b /stlasadisc.tex, cusp.tex, toileta.eps, toiletb.eps, fromatob.tex 1 F = 0 F α, β F = t 2 + at + b (t α)(t β) = t 2 (α + β)t
9. 05 L x P(x) P(0) P(x) u(x) u(x) (0 < = x < = L) P(x) E(x) A(x) P(L) f ( d EA du ) = 0 (9.) dx dx u(0) = 0 (9.2) E(L)A(L) du (L) = f (9.3) dx (9.) P
9 (Finite Element Method; FEM) 9. 9. P(0) P(x) u(x) (a) P(L) f P(0) P(x) (b) 9. P(L) 9. 05 L x P(x) P(0) P(x) u(x) u(x) (0 < = x < = L) P(x) E(x) A(x) P(L) f ( d EA du ) = 0 (9.) dx dx u(0) = 0 (9.2) E(L)A(L)
ii
ii iii 1 1 1.1..................................... 1 1.2................................... 3 1.3........................... 4 2 9 2.1.................................. 9 2.2...............................
II A A441 : October 02, 2014 Version : Kawahira, Tomoki TA (Kondo, Hirotaka )
II 214-1 : October 2, 214 Version : 1.1 Kawahira, Tomoki TA (Kondo, Hirotaka ) http://www.math.nagoya-u.ac.jp/~kawahira/courses/14w-biseki.html pdf 1 2 1 9 1 16 1 23 1 3 11 6 11 13 11 2 11 27 12 4 12 11
I II III IV V
I II III IV V N/m 2 640 980 50 200 290 440 2m 50 4m 100 100 150 200 290 390 590 150 340 4m 6m 8m 100 170 250 µ = E FRVβ β N/mm 2 N/mm 2 1.1 F c t.1 3 1 1.1 1.1 2 2 2 2 F F b F s F c F t F b F s 3 3 3
newmain.dvi
数論 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. http://www.morikita.co.jp/books/mid/008142 このサンプルページの内容は, 第 2 版 1 刷発行当時のものです. Daniel DUVERNEY: THÉORIE DES NOMBRES c Dunod, Paris, 1998, This book is published
Microsoft PowerPoint - 3.ppt [互換モード]
![Microsoft PowerPoint - 3.ppt [互換モード]](/thumbs/95/124643964.jpg "Microsoft PowerPoint - 3.ppt [互換モード]")
3. プッシュダウンオートマトンと文脈自由文法 1 3-1. プッシュダウンオートマトン オートマトンはメモリがほとんど無かった この制限を除いた機械を考える 理想的なスタックを利用できるようなオートマトンをプッシュダウンオートマトン (Push Down Automaton,PDA) という 0 1 入力テープ 1 a 1 1 0 1 スタッb 入力テープを一度走査したあと ク2 入力テプを度走査したあと
44 4 I (1) ( ) (10 15 ) ( 17 ) ( 3 1 ) (2)
(1) I 44 II 45 III 47 IV 52 44 4 I (1) ( ) 1945 8 9 (10 15 ) ( 17 ) ( 3 1 ) (2) 45 II 1 (3) 511 ( 451 1 ) ( ) 365 1 2 512 1 2 365 1 2 363 2 ( ) 3 ( ) ( 451 2 ( 314 1 ) ( 339 1 4 ) 337 2 3 ) 363 (4) 46
i ii i iii iv 1 3 3 10 14 17 17 18 22 23 28 29 31 36 37 39 40 43 48 59 70 75 75 77 90 95 102 107 109 110 118 125 128 130 132 134 48 43 43 51 52 61 61 64 62 124 70 58 3 10 17 29 78 82 85 102 95 109 iii
koji07-02.dvi
007 I II III 1,, 3, 4, 5, 6, 7 5 4 1 ε-n 1 ε-n ε-n ε-n. {a } =1 a ε N N a a N= a a
IMO 1 n, 21n n (x + 2x 1) + (x 2x 1) = A, x, (a) A = 2, (b) A = 1, (c) A = 2?, 3 a, b, c cos x a cos 2 x + b cos x + c = 0 cos 2x a
1 40 (1959 1999 ) (IMO) 41 (2000 ) WEB 1 1959 1 IMO 1 n, 21n + 4 13n + 3 2 (x + 2x 1) + (x 2x 1) = A, x, (a) A = 2, (b) A = 1, (c) A = 2?, 3 a, b, c cos x a cos 2 x + b cos x + c = 0 cos 2x a = 4, b =
行列代数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
０４年度LS民法Ⅰ教材改訂版.PDF
?? A AB A B C AB A B A B A B A A B A 98 A B A B A B A B B A A B AB AB A B A BB A B A B A B A B A B A AB A B B A B AB A A C AB A C A A B A B B A B A B B A B A B B A B A B A B A B A B A B A B
オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 正規言語の性質 反復補題正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると
オートマトン 形式言語及び演習 4. 正規言語の性質 酒井正彦 www.trs.css.i.nagoya-u.ac.jp/~sakai/lecture/automata/ 正規言語の性質 正規言語が満たす性質 ある与えられた言語が正規言語でないことを証明するために その言語が正規言語であると仮定してを使い 矛盾を導く 閉包性正規言語を演算により組み合わせて得られる言語が正規言語となる演算について調べる
2 2 MATHEMATICS.PDF 200-2-0 3 2 (p n ), ( ) 7 3 4 6 5 20 6 GL 2 (Z) SL 2 (Z) 27 7 29 8 SL 2 (Z) 35 9 2 40 0 2 46 48 2 2 5 3 2 2 58 4 2 6 5 2 65 6 2 67 7 2 69 2 , a 0 + a + a 2 +... b b 2 b 3 () + b n a
.5 z = a + b + c n.6 = a sin t y = b cos t dy d a e e b e + e c e e e + e 3 s36 3 a + y = a, b > b 3 s363.7 y = + 3 y = + 3 s364.8 cos a 3 s365.9 y =,
[ ] IC. r, θ r, θ π, y y = 3 3 = r cos θ r sin θ D D = {, y ; y }, y D r, θ ep y yddy D D 9 s96. d y dt + 3dy + y = cos t dt t = y = e π + e π +. t = π y =.9 s6.3 d y d + dy d + y = y =, dy d = 3 a, b
SO(2)
TOP URL http://amonphys.web.fc2.com/ 1 12 3 12.1.................................. 3 12.2.......................... 4 12.3............................. 5 12.4 SO(2).................................. 6
50 2 I SI MKSA r q r q F F = 1 qq 4πε 0 r r 2 r r r r (2.2 ε 0 = 1 c 2 µ 0 c = m/s q 2.1 r q' F r = 0 µ 0 = 4π 10 7 N/A 2 k = 1/(4πε 0 qq
49 2 I II 2.1 3 e e = 1.602 10 19 A s (2.1 50 2 I SI MKSA 2.1.1 r q r q F F = 1 qq 4πε 0 r r 2 r r r r (2.2 ε 0 = 1 c 2 µ 0 c = 3 10 8 m/s q 2.1 r q' F r = 0 µ 0 = 4π 10 7 N/A 2 k = 1/(4πε 0 qq F = k r
1 0/1, a/b/c/ {0, 1} S = {s 1, s 2,..., s q } S x = X 1 X 2 X 3 X n S (n = 1, 2, 3,...) n n s i P (X n = s i ) X m (m < n) P (X n = s i X n 1 = s j )
(Communication and Network) 1 1 0/1, a/b/c/ {0, 1} S = {s 1, s 2,..., s q } S x = X 1 X 2 X 3 X n S (n = 1, 2, 3,...) n n s i P (X n = s i ) X m (m < n) P (X n = s i X n 1 = s j ) p i = P (X n = s i )
(1) (2) (1) (2) 2 3 {a n } a 2 + a 4 + a a n S n S n = n = S n
. 99 () 0 0 0 () 0 00 0 350 300 () 5 0 () 3 {a n } a + a 4 + a 6 + + a 40 30 53 47 77 95 30 83 4 n S n S n = n = S n 303 9 k d 9 45 k =, d = 99 a d n a n d n a n = a + (n )d a n a n S n S n = n(a + a n
ii 3.,. 4. F. (), ,,. 8.,. 1. (75%) (25%) =7 20, =7 21 (. ). 1.,, (). 3.,. 1. ().,.,.,.,.,. () (12 )., (), 0. 2., 1., 0,.
24(2012) (1 C106) 4 11 (2 C206) 4 12 http://www.math.is.tohoku.ac.jp/~obata,.,,,.. 1. 2. 3. 4. 5. 6. 7.,,. 1., 2007 (). 2. P. G. Hoel, 1995. 3... 1... 2.,,. ii 3.,. 4. F. (),.. 5... 6.. 7.,,. 8.,. 1. (75%)
( 9 1 ) 1 2 1.1................................... 2 1.2................................................. 3 1.3............................................... 4 1.4...........................................
linearal1.dvi
19 4 30 I 1 1 11 1 12 2 13 3 131 3 132 4 133 5 134 6 14 7 2 9 21 9 211 9 212 10 213 13 214 14 22 15 221 15 222 16 223 17 224 20 3 21 31 21 32 21 33 22 34 23 341 23 342 24 343 27 344 29 35 31 351 31 352
入試の軌跡
4 y O x 4 Typed by L A TEX ε ) ) ) 6 4 ) 4 75 ) http://kumamoto.s.xrea.com/plan/.. PDF) Ctrl +L) Ctrl +) Ctrl + Ctrl + ) ) Alt + ) Alt + ) ESC. http://kumamoto.s.xrea.com/nyusi/kumadai kiseki ri i.pdf
2005
20 30 8 3 190 60 A,B 67,2000 98 20 23,600 100 60 10 20 1 3 2 1 2 1 12 1 1 ( ) 340 20 20 30 50 50 ( ) 6 80 5 65 17 21 5 5 12 35 1 5 20 3 3,456,871 2,539,950 916,921 18 10 29 5 3 JC-V 2 ( ) 1 17 3 1 6
meiji_resume_1.PDF
β β β (q 1,q,..., q n ; p 1, p,..., p n ) H(q 1,q,..., q n ; p 1, p,..., p n ) Hψ = εψ ε k = k +1/ ε k = k(k 1) (x, y, z; p x, p y, p z ) (r; p r ), (θ; p θ ), (ϕ; p ϕ ) ε k = 1/ k p i dq i E total = E
25 7 18 1 1 1.1 v.s............................. 1 1.1.1.................................. 1 1.1.2................................. 1 1.1.3.................................. 3 1.2................... 3
T T T T A 0 1 A 1 A P (A 1 ) = C 1 6 C 8C 3 = 15 8, P (A ) = C 6 C 1 8C 3 = 3 8 T 5 B P (A 1 B) = =
4 1.. 3. 4. 1. 1 3 4 5 6 1 3 4 5 6. 1 1 1 A B P (A B) = P (A) + P (B) P (C) = P (A) P (B) 3. 1 1 P (A) = 1 P (A) A A 4. A B P A (B) = n(a B) n(a) = P (A B) P (A) 50 015 016 018 1 4 5 8 8 3 T 1 3 1 T T
x V x x V x, x V x = x + = x +(x+x )=(x +x)+x = +x = x x = x x = x =x =(+)x =x +x = x +x x = x ( )x = x =x =(+( ))x =x +( )x = x +( )x ( )x = x x x R
V (I) () (4) (II) () (4) V K vector space V vector K scalor K C K R (I) x, y V x + y V () (x + y)+z = x +(y + z) (2) x + y = y + x (3) V x V x + = x (4) x V x + x = x V x x (II) x V, α K αx V () (α + β)x
untitled
0. =. =. (999). 3(983). (980). (985). (966). 3. := :=. A A. A A. := := 4 5 A B A B A B. A = B A B A B B A. A B A B, A B, B. AP { A, P } = { : A, P } = { A P }. A = {0, }, A, {0, }, {0}, {}, A {0}, {}.
6kg 1.1m 1.m.1m.1 l λ ϵ λ l + λ l l l dl dl + dλ ϵ dλ dl dl + dλ dl dl 3 1. JIS 1 6kg 1% 66kg 1 13 σ a1 σ m σ a1 σ m σ m σ a1 f f σ a1 σ a1 σ m f 4
35-8585 7 8 1 I I 1 1.1 6kg 1m P σ σ P 1 l l λ λ l 1.m 1 6kg 1.1m 1.m.1m.1 l λ ϵ λ l + λ l l l dl dl + dλ ϵ dλ dl dl + dλ dl dl 3 1. JIS 1 6kg 1% 66kg 1 13 σ a1 σ m σ a1 σ m σ m σ a1 f f σ a1 σ a1 σ m
r 1 m A r/m i) t ii) m i) t B(t; m) ( B(t; m) = A 1 + r ) mt m ii) B(t; m) ( B(t; m) = A 1 + r ) mt m { ( = A 1 + r ) m } rt r m n = m r m n B
1 1.1 1 r 1 m A r/m i) t ii) m i) t Bt; m) Bt; m) = A 1 + r ) mt m ii) Bt; m) Bt; m) = A 1 + r ) mt m { = A 1 + r ) m } rt r m n = m r m n Bt; m) Aert e lim 1 + 1 n 1.1) n!1 n) e a 1, a 2, a 3,... {a n
A 2 3. m S m = {x R m+1 x = 1} U + k = {x S m x k > 0}, U k = {x S m x k < 0}, ϕ ± k (x) = (x 0,..., ˆx k,... x m ) 1. {(U ± k, ϕ± k ) 0 k m} S m 1.2.
A A 1 A 5 A 6 1 2 3 4 5 6 7 1 1.1 1.1 (). Hausdorff M R m M M {U α } U α R m E α ϕ α : U α E α U α U β = ϕ α (ϕ β ϕβ (U α U β )) 1 : ϕ β (U α U β ) ϕ α (U α U β ) C M a m dim M a U α ϕ α {x i, 1 i m} {U,
( ) ( ) lex LL(1) LL(1)
() () lex LL(1) LL(1) http://www.cs.info.mie-u.ac.jp/~toshi/lectures/compiler/ 29 5 14 1 1 () / (front end) (back end) (phase) (pass) 1 2 1 () () var left, right; fun int main() { left = 0; right = 10;
(1.2) T D = 0 T = D = 30 kn 1.2 (1.4) 2F W = 0 F = W/2 = 300 kn/2 = 150 kn 1.3 (1.9) R = W 1 + W 2 = = 1100 N. (1.9) W 2 b W 1 a = 0
1 1 1.1 1.) T D = T = D = kn 1. 1.4) F W = F = W/ = kn/ = 15 kn 1. 1.9) R = W 1 + W = 6 + 5 = 11 N. 1.9) W b W 1 a = a = W /W 1 )b = 5/6) = 5 cm 1.4 AB AC P 1, P x, y x, y y x 1.4.) P sin 6 + P 1 sin 45
zz + 3i(z z) + 5 = 0 + i z + i = z 2i z z z y zz + 3i (z z) + 5 = 0 (z 3i) (z + 3i) = 9 5 = 4 z 3i = 2 (3i) zz i (z z) + 1 = a 2 {
04 zz + iz z) + 5 = 0 + i z + i = z i z z z 970 0 y zz + i z z) + 5 = 0 z i) z + i) = 9 5 = 4 z i = i) zz i z z) + = a {zz + i z z) + 4} a ) zz + a + ) z z) + 4a = 0 4a a = 5 a = x i) i) : c Darumafactory
17 ( :52) α ω 53 (2015 ) 2 α ω 55 (2017 ) 2 1) ) ) 2 2 4) (α β) A ) 6) A (5) 1)
3 3 1 α ω 53 (2015 ) 2 α ω 55 (2017 ) 2 1) 2000 2) 5 2 3 4 2 3 5 3) 2 2 4) (α β) 2 3 4 5 20 A 12 20 5 5 5) 6) 5 20 12 5 A (5) 1) Évariste Galois(1811-1832) 2) Joseph-Louis Lagrange(1736-1813) 18 3),Niels
微分積分 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. このサンプルページの内容は, 初版 1 刷発行時のものです.
微分積分 サンプルページ この本の定価 判型などは, 以下の URL からご覧いただけます. ttp://www.morikita.co.jp/books/mid/00571 このサンプルページの内容は, 初版 1 刷発行時のものです. i ii 014 10 iii [note] 1 3 iv 4 5 3 6 4 x 0 sin x x 1 5 6 z = f(x, y) 1 y = f(x)
x = a 1 f (a r, a + r) f(a) r a f f(a) 2 2. (a, b) 2 f (a, b) r f(a, b) r (a, b) f f(a, b)
2011 I 2 II III 17, 18, 19 7 7 1 2 2 2 1 2 1 1 1.1.............................. 2 1.2 : 1.................... 4 1.2.1 2............................... 5 1.3 : 2.................... 5 1.3.1 2.....................................
1 8, : 8.1 1, 2 z = ax + by + c ax by + z c = a b +1 x y z c = 0, (0, 0, c), n = ( a, b, 1). f = n i=1 a ii x 2 i + i<j 2a ij x i x j = ( x, A x), f =
1 8, : 8.1 1, z = ax + by + c ax by + z c = a b +1 x y z c = 0, (0, 0, c), n = ( a, b, 1). f = a ii x i + i
n (1.6) i j=1 1 n a ij x j = b i (1.7) (1.7) (1.4) (1.5) (1.4) (1.7) u, v, w ε x, ε y, ε x, γ yz, γ zx, γ xy (1.8) ε x = u x ε y = v y ε z = w z γ yz
1 2 (a 1, a 2, a n ) (b 1, b 2, b n ) A (1.1) A = a 1 b 1 + a 2 b 2 + + a n b n (1.1) n A = a i b i (1.2) i=1 n i 1 n i=1 a i b i n i=1 A = a i b i (1.3) (1.3) (1.3) (1.1) (ummation convention) a 11 x
2 7 V 7 {fx fx 3 } 8 P 3 {fx fx 3 } 9 V 9 {fx fx f x 2fx } V {fx fx f x 2fx + } V {{a n } {a n } a n+2 a n+ + a n n } 2 V 2 {{a n } {a n } a n+2 a n+
R 3 R n C n V??,?? k, l K x, y, z K n, i x + y + z x + y + z iv x V, x + x o x V v kx + y kx + ky vi k + lx kx + lx vii klx klx viii x x ii x + y y + x, V iii o K n, x K n, x + o x iv x K n, x + x o x
II 2014 2 (1) log(1 + r/100) n = log 2 n log(1 + r/100) = log 2 n = log 2 log(1 + r/100) (2) y = f(x) = log(1 + x) x = 0 1 f (x) = 1/(1 + x) f (0) = 1
II 2014 1 1 I 1.1 72 r 2 72 8 72/8 = 9 9 2 a 0 1 a 1 a 1 = a 0 (1+r/100) 2 a 2 a 2 = a 1 (1 + r/100) = a 0 (1 + r/100) 2 n a n = a 0 (1 + r/100) n a n a 0 2 n a 0 (1 + r/100) n = 2a 0 (1 + r/100) n = 2
I
I io@hiroshima-u.ac.jp 27 6 A A. /a δx = lim a + a exp π x2 a 2 = lim a + a = lim a + a exp a 2 π 2 x 2 + a 2 2 x a x = lim a + a Sic a x = lim a + a Rect a Gaussia Loretzia Bilateral expoetial Normalized
,2,4
2005 12 2006 1,2,4 iii 1 Hilbert 14 1 1.............................................. 1 2............................................... 2 3............................................... 3 4.............................................
140 120 100 80 60 40 20 0 115 107 102 99 95 97 95 97 98 100 64 72 37 60 50 53 50 36 32 18 H18 H19 H20 H21 H22 H23 H24 H25 H26 H27 1 100 () 80 60 40 20 0 1 19 16 10 11 6 8 9 5 10 35 76 83 73 68 46 44 H11
応力とひずみ.ppt
in yukawa@numse.nagoya-u.ac.jp 2 3 4 5 x 2 6 Continuum) 7 8 9 F F 10 F L L F L 1 L F L F L F 11 F L F F L F L L L 1 L 2 12 F L F! A A! S! = F S 13 F L L F F n = F " cos# F t = F " sin# S $ = S cos# S S
熊本県数学問題正解
00 y O x Typed by L A TEX ε ( ) (00 ) 5 4 4 ( ) http://www.ocn.ne.jp/ oboetene/plan/. ( ) (009 ) ( ).. http://www.ocn.ne.jp/ oboetene/plan/eng.html 8 i i..................................... ( )0... (
( )/2 hara/lectures/lectures-j.html 2, {H} {T } S = {H, T } {(H, H), (H, T )} {(H, T ), (T, T )} {(H, H), (T, T )} {1
( )/2 http://www2.math.kyushu-u.ac.jp/ hara/lectures/lectures-j.html 1 2011 ( )/2 2 2011 4 1 2 1.1 1 2 1 2 3 4 5 1.1.1 sample space S S = {H, T } H T T H S = {(H, H), (H, T ), (T, H), (T, T )} (T, H) S
?
240-8501 79-2 Email: nakamoto@ynu.ac.jp 1 3 1.1...................................... 3 1.2?................................. 6 1.3..................................... 8 1.4.......................................
1 Abstract 2 3 n a ax 2 + bx + c = 0 (a 0) (1) ( x + b ) 2 = b2 4ac 2a 4a 2 D = b 2 4ac > 0 (1) 2 D = 0 D < 0 x + b 2a = ± b2 4ac 2a b ± b 2
1 Abstract n 1 1.1 a ax + bx + c = 0 (a 0) (1) ( x + b ) = b 4ac a 4a D = b 4ac > 0 (1) D = 0 D < 0 x + b a = ± b 4ac a b ± b 4ac a b a b ± 4ac b i a D (1) ax + bx + c D 0 () () (015 8 1 ) 1. D = b 4ac
³ÎΨÏÀ
2017 12 12 Makoto Nakashima 2017 12 12 1 / 22 2.1. C, D π- C, D. A 1, A 2 C A 1 A 2 C A 3, A 4 D A 1 A 2 D Makoto Nakashima 2017 12 12 2 / 22 . (,, L p - ). Makoto Nakashima 2017 12 12 3 / 22 . (,, L p
1990 IMO 1990/1/15 1:00-4:00 1 N N N 1, N 1 N 2, N 2 N 3 N 3 2 x x + 52 = 3 x x , A, B, C 3,, A B, C 2,,,, 7, A, B, C
0 9 (1990 1999 ) 10 (2000 ) 1900 1994 1995 1999 2 SAT ACT 1 1990 IMO 1990/1/15 1:00-4:00 1 N 1990 9 N N 1, N 1 N 2, N 2 N 3 N 3 2 x 2 + 25x + 52 = 3 x 2 + 25x + 80 3 2, 3 0 4 A, B, C 3,, A B, C 2,,,, 7,
II Time-stamp: <05/09/30 17:14:06 waki> ii
II waki@cc.hirosaki-u.ac.jp 18 1 30 II Time-stamp: ii 1 1 1.1.................................................. 1 1.2................................................... 3 1.3..................................................
i
14 i ii iii iv v vi 14 13 86 13 12 28 14 16 14 15 31 (1) 13 12 28 20 (2) (3) 2 (4) (5) 14 14 50 48 3 11 11 22 14 15 10 14 20 21 20 (1) 14 (2) 14 4 (3) (4) (5) 12 12 (6) 14 15 5 6 7 8 9 10 7
( 23 )
( 23 ) 2 9 11 16 21........................................... 21........................................... 24........................................... 28...........................................
経済分析 第82号
6 K Y T YF KT effeive lor servie M H M H effeive mnhour Prouive mnhour mnhour M H M F M F if K M F ii M F M F F F M F F K M F i CoDougls Y Y Ae K K A Y K γ i ii Y * < lnk Y Y Y ˆ ˆ pive M H Brehling M
4.6: 3 sin 5 sin θ θ t θ 2t θ 4t : sin ωt ω sin θ θ ωt sin ωt 1 ω ω [rad/sec] 1 [sec] ω[rad] [rad/sec] 5.3 ω [rad/sec] 5.7: 2t 4t sin 2t sin 4t
![4.6: 3 sin 5 sin θ θ t θ 2t θ 4t : sin ωt ω sin θ θ ωt sin ωt 1 ω ω [rad/sec] 1 [sec] ω[rad] [rad/sec] 5.3 ω [rad/sec] 5.7: 2t 4t sin 2t sin 4t](/thumbs/70/62705042.jpg "4.6: 3 sin 5 sin θ θ t θ 2t θ 4t : sin ωt ω sin θ θ ωt sin ωt 1 ω ω [rad/sec] 1 [sec] ω[rad] [rad/sec] 5.3 ω [rad/sec] 5.7: 2t 4t sin 2t sin 4t")
1 1.1 sin 2π [rad] 3 ft 3 sin 2t π 4 3.1 2 1.1: sin θ 2.2 sin θ ft t t [sec] t sin 2t π 4 [rad] sin 3.1 3 sin θ θ t θ 2t π 4 3.2 3.1 3.4 3.4: 2.2: sin θ θ θ [rad] 2.3 0 [rad] 4 sin θ sin 2t π 4 sin 1 1
A(6, 13) B(1, 1) 65 y C 2 A(2, 1) B( 3, 2) C 66 x + 2y 1 = 0 2 A(1, 1) B(3, 0) P 67 3 A(3, 3) B(1, 2) C(4, 0) (1) ABC G (2) 3 A B C P 6
1 1 1.1 64 A6, 1) B1, 1) 65 C A, 1) B, ) C 66 + 1 = 0 A1, 1) B, 0) P 67 A, ) B1, ) C4, 0) 1) ABC G ) A B C P 64 A 1, 1) B, ) AB AB = 1) + 1) A 1, 1) 1 B, ) 1 65 66 65 C0, k) 66 1 p, p) 1 1 A B AB A 67
The Physics of Atmospheres CAPTER :
The Physics of Atmospheres CAPTER 4 1 4 2 41 : 2 42 14 43 17 44 25 45 27 46 3 47 31 48 32 49 34 41 35 411 36 maintex 23/11/28 The Physics of Atmospheres CAPTER 4 2 4 41 : 2 1 σ 2 (21) (22) k I = I exp(
δ ij δ ij ˆx ˆx ŷ ŷ ẑ ẑ 0, ˆx ŷ ŷ ˆx ẑ, ŷ ẑ ẑ ŷ ẑ, ẑ ˆx ˆx ẑ ŷ, a b a x ˆx + a y ŷ + a z ẑ b x ˆx + b
23 2 2.1 n n r x, y, z ˆx ŷ ẑ 1 a a x ˆx + a y ŷ + a z ẑ 2.1.1 3 a iˆx i. 2.1.2 i1 i j k e x e y e z 3 a b a i b i i 1, 2, 3 x y z ˆx i ˆx j δ ij, 2.1.3 n a b a i b i a i b i a x b x + a y b y + a z b
1/1 lim f(x, y) (x,y) (a,b) ( ) ( ) lim limf(x, y) lim lim f(x, y) x a y b y b x a ( ) ( ) xy x lim lim lim lim x y x y x + y y x x + y x x lim x x 1
1/5 ( ) Taylor ( 7.1) (x, y) f(x, y) f(x, y) x + y, xy, e x y,... 1 R {(x, y) x, y R} f(x, y) x y,xy e y log x,... R {(x, y, z) (x, y),z f(x, y)} R 3 z 1 (x + y ) z ax + by + c x 1 z ax + by + c y x +
(Basics of Proability Theory). (Probability Spacees ad Radom Variables,, (Ω, F, P ),, X,. (Ω, F, P ) (probability space) Ω ( ω Ω ) F ( 2 Ω ) Ω σ (σ-fi
II (Basics of Probability Theory ad Radom Walks) (Preface),.,,,.,,,...,,.,.,,.,,. (Basics of Proability Theory). (Probability Spacees ad Radom Variables...............2, (Expectatios, Meas).............................
直交座標系の回転
b T.Koama x l x, Lx i ij j j xi i i i, x L T L L, L ± x L T xax axx, ( a a ) i, j ij i j ij ji λ λ + λ + + λ i i i x L T T T x ( L) L T xax T ( T L T ) A( L) T ( LAL T ) T ( L AL) λ ii L AL Λ λi i axx
2 1 κ c(t) = (x(t), y(t)) ( ) det(c (t), c x (t)) = det (t) x (t) y (t) y = x (t)y (t) x (t)y (t), (t) c (t) = (x (t)) 2 + (y (t)) 2. c (t) =
1 1 1.1 I R 1.1.1 c : I R 2 (i) c C (ii) t I c (t) (0, 0) c (t) c(i) c c(t) 1.1.2 (1) (2) (3) (1) r > 0 c : R R 2 : t (r cos t, r sin t) (2) C f : I R c : I R 2 : t (t, f(t)) (3) y = x c : R R 2 : t (t,
68 A mm 1/10 A. (a) (b) A.: (a) A.3 A.4 1 1
67 A Section A.1 0 1 0 1 Balmer 7 9 1 0.1 0.01 1 9 3 10:09 6 A.1: A.1 1 10 9 68 A 10 9 10 9 1 10 9 10 1 mm 1/10 A. (a) (b) A.: (a) A.3 A.4 1 1 A.1. 69 5 1 10 15 3 40 0 0 ¾ ¾ É f Á ½ j 30 A.3: A.4: 1/10
第１部 一般的コメント
(( 2000 11 24 2003 12 31 3122 94 2332 508 26 a () () i ii iii iv (i) (ii) (i) (ii) (iii) (iv) (a) (b)(c)(d) a) / (i) (ii) (iii) (iv) 1996 7 1996 12
21 2 26 i 1 1 1.1............................ 1 1.2............................ 3 2 9 2.1................... 9 2.2.......... 9 2.3................... 11 2.4....................... 12 3 15 3.1..........
A A = a 41 a 42 a 43 a 44 A (7) 1 (3) A = M 12 = = a 41 (8) a 41 a 43 a 44 (3) n n A, B a i AB = A B ii aa
1 2 21 2 2 [ ] a 11 a 12 A = a 21 a 22 (1) A = a 11 a 22 a 12 a 21 (2) 3 3 n n A A = n ( 1) i+j a ij M ij i =1 n (3) j=1 M ij A i j (n 1) (n 1) 2-1 3 3 A A = a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33
9 1. (Ti:Al 2 O 3 ) (DCM) (Cr:Al 2 O 3 ) (Cr:BeAl 2 O 4 ) Ĥ0 ψ n (r) ω n Schrödinger Ĥ 0 ψ n (r) = ω n ψ n (r), (1) ω i ψ (r, t) = [Ĥ0 + Ĥint (
9 1. (Ti:Al 2 O 3 ) (DCM) (Cr:Al 2 O 3 ) (Cr:BeAl 2 O 4 ) 2. 2.1 Ĥ ψ n (r) ω n Schrödinger Ĥ ψ n (r) = ω n ψ n (r), (1) ω i ψ (r, t) = [Ĥ + Ĥint (t)] ψ (r, t), (2) Ĥ int (t) = eˆxe cos ωt ˆdE cos ωt, (3)
1 filename=mathformula tex 1 ax 2 + bx + c = 0, x = b ± b 2 4ac, (1.1) 2a x 1 + x 2 = b a, x 1x 2 = c a, (1.2) ax 2 + 2b x + c = 0, x = b ± b 2
filename=mathformula58.tex ax + bx + c =, x = b ± b 4ac, (.) a x + x = b a, x x = c a, (.) ax + b x + c =, x = b ± b ac. a (.3). sin(a ± B) = sin A cos B ± cos A sin B, (.) cos(a ± B) = cos A cos B sin
i I II I II II IC IIC I II ii 5 8 5 3 7 8 iii I 3........................... 5......................... 7........................... 4........................ 8.3......................... 33.4...................
5 n P j j (P i,, P k, j 1) 1 n n ) φ(n) = n (1 1Pj [ ] φ φ P j j P j j = = = = = n = φ(p j j ) (P j j P j 1 j ) P j j ( 1 1 P j ) P j j ) (1 1Pj (1 1P
![5 n P j j (P i,, P k, j 1) 1 n n ) φ(n) = n (1 1Pj [ ] φ φ P j j P j j = = = = = n = φ(p j j ) (P j j P j 1 j ) P j j ( 1 1 P j ) P j j ) (1 1Pj (1 1P](/thumbs/90/103736623.jpg "5 n P j j (P i,, P k, j 1) 1 n n ) φ(n) = n (1 1Pj [ ] φ φ P j j P j j = = = = = n = φ(p j j ) (P j j P j 1 j ) P j j ( 1 1 P j ) P j j ) (1 1Pj (1 1P")
p P 1 n n n 1 φ(n) φ φ(1) = 1 1 n φ(n), n φ(n) = φ()φ(n) [ ] n 1 n 1 1 n 1 φ(n) φ() φ(n) 1 3 4 5 6 7 8 9 1 3 4 5 6 7 8 9 1 4 5 7 8 1 4 5 7 8 10 11 1 13 14 15 16 17 18 19 0 1 3 4 5 6 7 19 0 1 3 4 5 6 7
20 9 19 1 3 11 1 3 111 3 112 1 4 12 6 121 6 122 7 13 7 131 8 132 10 133 10 134 12 14 13 141 13 142 13 143 15 144 16 145 17 15 19 151 1 19 152 20 2 21 21 21 211 21 212 1 23 213 1 23 214 25 215 31 22 33
福岡大学人文論叢47-3
679 pp. 1 680 2 681 pp. 3 682 4 683 5 684 pp. 6 685 7 686 8 687 9 688 pp. b 10 689 11 690 12 691 13 692 pp. 14 693 15 694 a b 16 695 a b 17 696 a 18 697 B 19 698 A B B B A B B A A 20 699 pp. 21 700 pp.
73
73 74 ( u w + bw) d = Ɣ t tw dɣ u = N u + N u + N 3 u 3 + N 4 u 4 + [K ] {u = {F 75 u δu L σ (L) σ dx σ + dσ x δu b δu + d(δu) ALW W = L b δu dv + Aσ (L)δu(L) δu = (= ) W = A L b δu dx + Aσ (L)δu(L) Aσ
B ver B
B ver. 2017.02.24 B Contents 1 11 1.1....................... 11 1.1.1............. 11 1.1.2.......................... 12 1.2............................. 14 1.2.1................ 14 1.2.2.......................
K E N Z OU
K E N Z OU 11 1 1 1.1..................................... 1.1.1............................ 1.1..................................................................................... 4 1.........................................
第１章 国民年金における無年金
1 2 3 4 ILO ILO 5 i ii 6 7 8 9 10 ( ) 3 2 ( ) 3 2 2 2 11 20 60 12 1 2 3 4 5 6 7 8 9 10 11 12 13 13 14 15 16 17 14 15 8 16 2003 1 17 18 iii 19 iv 20 21 22 23 24 25 ,,, 26 27 28 29 30 (1) (2) (3) 31 1 20
情報数理学
2007 年度 情報数理学 履修にあたって 2007 年度大学院奇数セメスター ( 前期 ) 開講 教室 : K336 大学院棟 D46( 次回から ) 時限 : 火曜日 3 時限 (2:50-4:20) 担当 草苅良至 2 講義予定 計算機のいろいろな理論モデル 言語理論 計算の限界 問題の難しさ 現実問題と計算 計算量理論 アルゴリズム論 3 参考書 M. Sipser 著 計算理論の基礎 共立出版