1
|
|
|
- もりより ひろなが
- 5 years ago
- Views:
Transcription
1 1
2
3 PTAS FPTAS
4 N, Z, Q, R Q +, R + n N [n] = {1,,..., n} [n] = [n] {0} = {0, 1,,..., n} Z n = {0, 1,,..., n 1} f(n) = O(g(n)) c, n 0, n n 0 [f(n) cg(n)] f(n) = Ω(g(n)) c, n 0, n n 0 [f(n) cg(n)] log, ln log e ln x R + log x = x, e ln x = x G = (V, E) V = {v 1, v,..., v n } E = {e 1, e,..., e m } G = (V, E) v V N v U V N(U) N v v V d v 4
5 1 1.1 V = {v 1, v,..., v n } matching G = (V, E) M E s.t. e, e M : e e [e e = ] M shortest path G = (V, E), c : E R + s t u 1, u,..., u k V s.t. 1. (u 1, u k ) = (s, t),. i, j [k] : i j[u i u j ] 3. i [k 1][(u i, u i+1 ) E] i [k 1] c(u i, u i+1 ) 1.1. independent set G = (V, E) D V s.t. u, v D : u v[(u, v) E] D traveling salesman G = (V, E), c : E R + u 1, u,..., u n V s.t. i, j [n] : i j[u i u j ] i [n] c(u i, u i+1 ) 1.. NP 1. 1 NP 5
6 NP NP P NP I P S I val(s) 1.1. D D u 1,..., u n i [n] c(u i, u i+1 ) 1.. NP 1. P NP I P I OPT(I) 1.. OPT(G) G OPT(G) G 1.3 P P I A r(a) 1 { } r(a) def val(opt(i)) = max. I I val(a(i)) I I val(opt(i)) r(a) val(a(i)) 1.3 ( ). r A G D = OPT(G), D = A(G) P NP D r D. 6
7 1.4 P P I A r(a) 1 { } r(a) def val(a(i)) = max. I I val(opt(i)) I I val(a(i)) r(a) val(opt(i)) 1.4 ( ). r A (G, c) (u 1,..., u n ) = OPT(G, c), (w 1,..., w n ) = A(G, c) s = i [n] c(u i, u i+1 ), s = i [n] c(w i, w i+1 ) s r s P P r A r(a) r 3 7
8 G = (V, E) S V cut {(u, v) E : u S, v S}.1 ( )..1. G = (V, E) 1. S = {1} S. i [n] \ {1} (a) A, B E A B def = {(u, v i ) E : u S}, def = {(u, v i ) E : u {v j : j [i 1]} \ S}. (b) A B S = S {v i } 3. S 1: S S G = (V, E) E i [n] \ {1} E i def = {(v j, v i ) E : j < i}. [E,..., E n ] E E = i [n]\{1} E i 1. E = i [n]\{1} E i. i, j [n] \ {1} : i j[e i E j = ] 8
9 .. [E,..., E n ] E -(a) i [n] \ {1} A, B A i, B i E i = A i B i A i B i =.3. i [n] \ {1} E i = A i B i A i B i = i S A i B i 1. val(s) = i [n]\s A i + i S\{1} B i,. i [n] \ S[ A i E i /], 3. i S \ {1}[ B i E i /]..4. 1,, 3 val(s )/val(s) val(s) = = i [n]\s = E i [n]\{1} A i + E i i [n]\{1} E i val(s ). i S\{1} B i
10 3 set cover U S 1, S,..., S m U S i1,..., S ik s.t. S i1 S ik = U k 3.1 ( ) U = n ln n + 1 U S 1, S,..., S m U 1. W = U, A = A [m]. W (a) j = arg max i [m]\a { S i W } (b) W = W \ S j, A = A {j} 3. A : 3.1. U = {1,..., 7}. k i A A i A 0 =, A i = i A k A i W W i w i = W i W 0 = U, w 0 = n 3.1. i [k] A A [m] \ A i 1 {S j W i 1 : j A } W i 1 W i 1 = j A (S j W i 1 ) i [k] W i 1 W i W i 1 / A 10
11 3.3. i [k] w i ( 1 1 ) A w i 1. i [k] w i ( 1 1 ) i A w 0 e i/ A n. ( ) i e i/ A n < 1 w i < 1 w i = 0 W i = w i e i/ A n < 1 ln n < i A, i (ln n) A < i k (ln n) A < k k (ln n) A + 1 k = A k = val(a k ) val(a k )/val(a ) ln n x R 1 + x e x 11
12 4 G = (V, E) vertex cover S V s.t. e E, v S[e v ] S 4.1 ( ) E = m ln m + 1 G = (V, E) 1. F = E, S = S V. F (a) G = (V, F ) u = arg max v V {d G (v)} (b) S = S {u} (c) F = F \ {e F : v N u [e = (u, v)]} 3. S 3: k i S S i S 0 =, S i = i S k S i F F i f i = F i F 0 = E, f 0 = m 4.1. i [k] S S V \ S i 1 S F i
13 4.. i [k] F i 1 F i F i 1 / S 4.3. i [k] f i ( 1 1 ) S f i 1 i [k] f i ( 1 1 ) i S f 0 e i/ S m. i e i/ S m < 1 f i < 1 f i = 0 F i = f i e i/ S m < 1 ln m < i S, i (ln m) S < i k (ln m) S < k k (ln m) S + 1 k = S k = val(s k ) val(s k )/val(s ) ln m + 1 G = (X, Y, E) X n ln n, Y = n 3 ln n X i [n] X i def = {x X : d x = i}, X i = n/i X = i [n] X i = i [n] n/i n ln n. i [n] x X i Y i x i X i d x = i, X i = n/i N(X i ) Y Y 3 X val(s) val(s ) = = X Y n ln n n = ln n G = (X, Y, E) ln n E n / 4.4. Y 3 X 13
14 4.. G = (V, E) 1. U = V, S =, v V [w(v) = 1] S V. U (a) G = G[U] (b) D G U = U \ D (c) c = min u U {w(u)/d G (u)} (d) S = {u U : w(u)/d G (u) = c} (e) S = S S (f) U = U \ S (g) u U w(u) = w(u) c d G (u) 3. S 4: S S k i S S i S = S 1 S S k, S k = i D D i V \ S = D 1 D D k S (u, v) E u D i, v D j D i, D j i G = G[U] c = min u U {w(u)/d G (u)} t i : U [0, 1] t i (u) = c d G (u) D U U i 4.3. i [k] v S i t i (v) v S U i t i (v).. S i U i t i (v) = c d G (v) c d G (v) = c E(G ) v S i v S i v U i S G G[U i ] S U i G = G[U i ] c E(G ) c v S U i d G (v) = 14 v S U i t i (v).
15 t i (v) t i (v). v S i v S U i S w v S i [k] t i(v) = 1 val(s) = t i (v) = t i (v). v S i [k] i [k] v S i v V i [k] t i(v) 1 val(s) = i [k] t i (v) v S i i [k] t i (v) = t i (v) val(s ). v S U i v S i [k] val(s)/val(s ) 4.3. G = (V, E) 1. F = E, S = S V. F (a) f = (u, v) F (b) S = S {u, v} (c) F = F \ (f {(u, w) F : w N u } {(v, w) F : w N v }) 3. S 5: S S k i {u, v} S i = {a i, b i } S = S 1 S S k 4.4. i, j [k] : i j S i S j = 15
16 i [k] a i S b i S 4.8. S S val(s)/val(s ) 4.9. S S
17 5 independent set G = (V, E) S V s.t. u, v S : u v[(u, v) E] S 5.1 ( ) E / V = c c + 1 G = (V, E) 1. U = V, S = S V. U (a) G[U] u (b) S = S {u} (c) U = U \ (N u {u}) 3. S 6: S S k k = S = val(s) -(a) i u i G[U] u i d i (d i + 1) = n. (1) i [k] 5.. i ( d i ) +1 ( ) di (d i + 1) m = cn. i [k] 17
18 5.3. d i (d i + 1) cn. () i [k] (1) () (d i + 1) (c + 1)n. i [k] (d i + 1) i [k] ( i [k] (d i + 1)) k = n k. n k (c + 1)n. n/k c + 1 val(s) = k n val(s ) val(s )/val(s) c E / V = c c S S k k = S = val(s) -(a) i u i G[U] u i d i (d i + 1) = n. i [k] S i U k i k i = S (N ui {u i }) k i = S. i [k] i ( d i ) ( +1 + ki ) ( di (d i + 1) + k ) i(k i 1) m = cn. i [k]
19 i [k](d i + 1) + i [k] k i cn + n + S = (c + 1)n + S. (d i + 1) ( i (d i + 1)) k i [k] ki ( i k i) k i [k] = S k = n k k = S n + S S 1 S S S (c + 1)n + S. (c + 1)n + S n + S. n/ S = 1 (c + 1) + S /n n/ S + S /n. (3) S S (c + 1) = c (3) n/ S = 1 val(s) = S val(s ) = S val(s )/val(s) c
20 6 traveling salesman G = (V, E), c : E R + u 1, u,..., u n V s.t. i, j [n] : i j[u i u j ] i [n] c(u i, u i+1 ) 6.1 ( ) V = n P N P α : N R + α(n). α : N R + α(n) P = N P α(n) A A P = N P G = (V, E) c : V V R + e V V { c(e) def = 1 : e E n α(n) : e E V c A A S val(s) n α(n) YES NO G = (V, E), c : E R + a, b, c V [c(a, b) + c(b, c) c(a, c)] G = (V, E), c : E R + (log n + 1)/
21 G = (V, E) V = {v 1,..., v n }, c : E R + 1. U = V \ {v 1 }, S = (v 1 ), v = v 1 S. U (a) u = arg min u U {c(v, u)} (b) U = U \ {u }, S = S (u ), v = u 3. S 7:. 7 S = (u 1, u,..., u n ) S f : V R + f(u i ) def = c(u i, u i+1 ). val(s) = i [n] f(u i ) i, j [n] : i j[c(u i, u j ) min{f(u i ), f(u j )}],. i [n][f(u i ) val(s )/].. c i < j i < j f(u i ) = c(u i, u i+1 ) c(u i, u j ) min{f(u i ), f(u j )} c(u i, u j ) S = (u i P 1 u i+1 P u i ) c(u i, u i+1 ) c(p 1 ) c(u i, u i+1 ) c(p ) c(u i, u i+1 ) c(p 1 ) + c(p ) = val(s ) f(u i ) = c(u i, u i+1 ) f(u i ) val(s )/ f(u 1 ) f(u ) f(u n ) S {u 1, u,..., u k } S k 6.. k [n] val(s k ). k i=k/ val(s n) f(u i ) > n i=n/ k i=k/+1 f(u i ) f(u i )
22 log n k=0 val(s k ) log n k=0 k i= k /+1 f(u i ) = f(u i ). i [n] (log n + 1)val(S ) = val(s) val(s)/val(s ) (log n + 1)/ 6.. G = (V, E), c : E R 6. G = (V, E), c : E R + G T = (V, E ) T G e E c(e) T = (V, E ) G = (V, E) G 6.3. G G G G = (V, E), c : E R + 1. G T = (V, E ). T T 3. T C 4. v 1 C 8:
23 T. 8 S = (u 1, u,..., u n ) S e E c(e) val(s ) val(s) e C c(e) = e E c(e) val(s) val(s ). val(s)/val(s ) 6.3. G = (V, E), c : E R G = (V, E), c : E R M E e, e M[e e = ] M M v V, e M[v e] M e M c(e) M G[V ] 3
24 G = (V, E), c : E R + 1. G T = (V, E ). T V 3. G[V ] M 4. T = (V, E M) C 5. v 1 C 9: T. 9 S = (u 1, u,..., u n ) S 1. c(e) val(s ), e E. val(s) c(e). e C 6.3. e M c(e) val(s ).. S = (s 1,..., s n ) M s i1,..., s ik S 1 S def S 1 S = = {(s i1, s i ), (s i3, s i4 ),..., (s ik 1, s ik )} E, def = {(s i, s i3 ), (s i4, s i5 ),..., (s ik, s i1 )} E. e S 1 S c(e) val(s ). i 1 i i k M S 1 S = c(e) min c(e), c(e) 1 c(e). e M e S 1 e S e S 1 S
25 e M c(e) val(s ). val(s) e C c(e) = = e E c(e) + e M e E M c(e) c(e) val(s ) + val(s ) = 3 val(s ). 5
26 7 knapsack U = {u 1, u,..., u n } (a 1, p 1 ), (a, p ),..., (a n, p n ) R + R +, b R + S [n] s.t. i S a i b i S p i 7.1 ( ) U = {u 1, u,..., u n } (a 1, p 1 ), (a, p ),..., (a n, p n ) R + R +, b R + 1. S = x = arg max i [n] {p i } S [n]. p i /a i U p 1 /a 1 p n /a n 3. i [n] (a) ( j S a j) + a i b S = S {i} 4. j S p j < p x {x} S 10: 7.1. U = {u 1, u,..., u n } (a 1, p 1 ), (a, p ),..., (a n, p n ) R + R +, b R + i [n][a i b] a i > b u i U S S 3 3-(a) i [n] i 0 i 0 [n] a j b a j > b j [i 0 1] j [i 0 ] [i 0 1] S b 0 = j [i 0 1] a j j [i 0 1] p j val(s). 6
27 7.1. j [i 0 1] p j + p i 0 a i0 (b b 0 ) val(s ) val(s ) < j [i 0 ] p j j [i 0 1] p j p i0 val(s ) < j [i 0 1] p j < p i0 val(s ) < j [i 0 1] p j + p i0 j [i 0 1] j [i 0 1] p j val(s). j [i 0 1] p j val(s) p j + p i0 < p i0 p x val(s). ( p x val(s)) val(s )/val(s) j S p j < p x 7
28 8 8.1 P NP P I A polynomial time approximation scheme: PTAS ϵ > 0 : max I I : max I I { } val(opt(i)) val(a(i, ϵ)) { } val(a(i, ϵ)) val(opt(i)) (1 + ϵ) (1 + ϵ) A I 8. A fully polynomial time approximation scheme: FPTAS A PTAS A I, 1/ϵ 8.1 PTAS 8.1. PTAS U = {u 1, u,..., u n } (a 1, p 1 ), (a, p ),..., (a n, p n ) R + R +, b R +, ϵ > 0 1. k = 1/ϵ. S [n] : S k (a) T = [n] \ S T = n (b) p i /a i T p 1 /a 1 p n /a n (c) i [n ] ( j S a j) + a i b S = S {i} 3. i S p i S 11: 8.1. ϵ =
29 . 11 S S val(s ) (1 + ϵ)val(s) ϵ = 1/k k S = [k ] val(s ) = k > k S p i k [k] i [k ] p i. min {p i} i [k] max {p i} i [k ]\[k] [k ] \ [k] p i /a i i, j [k ] \ [k] : i < j p i /a i p j /a j [k] S S [n] : S k [k ] \ [k] S m [k ] \ [k] {k + 1,..., m 1} S m S m S, b e : i S \ S a i b e : < a m, b e b = i [m 1] a i + + b e. 8.. G = S \ [k] val(s) = i [k] p i + val(g) m S i S \ S p i /a i p m /a m val(g) m 1 i=k+1 p i + pm a m [k ] \ [k] p i /a i k p i p m b a m a i. i=m i [m 1] 8.4. val(s ) = k p i + i=1 m 1 i=k+1 p i + k i=m p i 9
30 ( ) p i + val(g) pm + p m b a m a m i [k] = i [k] p i + val(g) + p m a m = val(s) + p m a m b e val(s) + p m. b i [m 1] i [m 1] i [k] p m p i k p m val(s) a i a i 8.5. val(s ) val(s) + p m val(s) + val(s)/k = (1 + 1/k)val(S) = (1 + ϵ)val(s). i [k] ( n i) = O(n k ) O(n) U p i /a i -(b) T O(n k n) = O(n k+1 ) = O(n 1+1/ϵ ) 8. FPTAS 8.. U = {u 1,..., u n }, (a 1, p 1 ),..., (a n, p n ) R + R +, b R + i [n][a i Z + ] W = max{a 1,..., a n } O(nW ) 8.6. i [n][a i Z + ] 8.1. W = poly(n) n FPTAS 8.. U = {u 1,..., u n }, (a 1, p 1 ),..., (a n, p n ) R + R +, b R + i [n][p i Z + ] P = max{p 1,..., p n } O(n P ) 30
31 . S : [n] [np ] [n] i [n], p [np ] S(i, p) def = arg min a j : p j = p. S [i] j S p [np ] j a j = p j a j = arg min S(i, p) = S {S(i 1,p),S(i 1,p p i )} j S j S a j : p i p S(i 1, p) : p i > p (4) 8.7. (4) arg max S(n,p):p [np ] p : j S(n,p) a j b. (5) 8.8. (5) 1 j a j = np + 1 U = {u 1,..., u n }, (a 1, p 1 ),..., (a n, p n ) R + R +, b R + i [n][p i Z + ] 1. S(1, p 1 ) = {1} p [np ] \ {p 1 } S(1, p) =. i [n] \ {1}, p [np ] (a) p i p X = S(i 1, p), Y = S(i 1, p p i ) {i} j X a j j Y a j S(i, p) = X S(i, p) = Y (b) p i > p S(i, p) = S(i 1, p) 3. (5) 1: S [n] [np ] n P O(n P ) RS(i, p) p {np, np 1, np,...,, 1} 31
32 1. S = RS(n, p) RS(n, p). i S a i b S RS(i, p) 8.3. FPTAS U = {u 1,..., u n }, (a 1, p 1 ),..., (a n, p n ) R + R +, b R +, ϵ > 0 1. P = max{p 1,..., p n } K = P (ϵ/n). p i = p i/k A 3. A 13:. 13 S S (1 ϵ)val(s ) val(s) ϵ > 0 val(s )/val(s) 1/(1 ϵ) 1 + ϵ p i i [n] p ik p i p ik + K. {p 1,..., p n} S i S p i i S p i val(s) = p i p ik p ik (p i K) i S i S i S i S p i nk i S ( S n) = val(s ) nk. K = P (ϵ/n) val(s ) P val(s) val(s ) nk = val(s ) ϵp val(s ) ϵval(s ) = (1 ϵ)val(s ). P = max{p i } = n/ϵ O(n P ) = O(n 3 /ϵ) 3
33 9 9.1 X x X x x CNF k k-cnf 9.1 ( ). φ x 1, x, x 3, x 4, x 5 3-CNF φ = x 1 ( x 1 x ) (x 1 x x 3 ) ( x 1 x 3 x 4 ) x ( x 3 x 4 x 5 ) f : {0, 1} n {0, 1} CNF CNF φ φ = x 1 ( x 1 x )(x 1 x x 3 )( x 1 x 3 x 4 ) x ( x 3 x 4 x 5 ). CNF φ φ = {x 1, ( x 1 x ), (x 1 x x 3 ), ( x 1 x 3 x 4 ), x, ( x 3 x 4 x 5 )}. C φ C φ φ x C x C 9. φ X CNF C φ t : X {0, 1} X t C C t satisfiability X CNF φ X t : X {0, 1} t φ CNF φ φ = 6 t(x) = (1, 1, 1, 1, 1) φ 4 t(x) = (1, 1, 1, 1, 0) φ
34 X CNF φ 1. t : X {0, 1} t. x X (a) P, N φ P N def = {C φ : x C}, def = {C φ : x C}. (b) t(x) = 1, φ = φ \ P : P N, t(x) = 0, φ = φ \ N : o.w. 3. t 14: t t X = n i i [n] P N A i = P, B i = N A i = N, B i = P val(t) = A i i [n]. (A i B i ) = φ. i [n] 9.. val(t) = A i = A i A i + B i = A i A i + B i A i + B i ( A i + B i ) i [n] i [n] i [n] 1 ( A i + B i ) ( A i B i ) i [n] 1 A i B i ( A i + B i A i B i ) i [n] 1 (A i B i ) ( ) i [n] 34
35 = 1 φ val(t ). val(t )/val(t) A A Pr{A} r A Pr r {A} 9.4 Z Z E[Z] r Z E r [Z] 9.. Z a R E[a Z] = a E[Z] 9.3. Z 1, Z E[Z 1 + Z ] = E[Z 1 ] + E[Z ] E[a 1 Z 1 + a Z ] = a 1 E[Z 1 ] + a E[Z ] 9.5. t : {x 1,..., x n } {0, 1} C = (x 1 x k ) k n Pr t {t C } = 1 k k N f(k) def = 1 k 35
36 9.1. f(k) k f(k) k N 1/ f(k) < 1 X CNF φ 1. t : X {0, 1} 15: φ X CNF 15 t φ t E[val(t)] val(t )/. t Et[val(t )/val(t)]. φ = {C j : j [m]} E t [val(t)] m/ m val(t ) j [m] Z j { 1 : t C j Z j = 0 : Z = j [m] Z j val(t) = Z E t [val(t)] = E t [Z] E[val(t)] = E[Z] = E Z j = E[Z j ]. t t t t j [m] 9.. C j k E t [Z j ] = f(k) 1/ j [m] 9.7. E t [val(t)] = j [m] E t [Z j ] = j [m] f(k) m/ k k-cnf E t [val(t)] f(k)val(t ) E t [val(t )/val(t)] f(k) 36
37 P int φ = {C j : j [m]} X = {x 1,..., x n } CNF : : j [m] y j z i + (1 z i ) y j for j [m] x i C j x i C j y j, z i {0, 1} 9.3. X = {x 1,..., x 5 } 3-CNF φ φ = {x 1, ( x 1 x ), (x 1 x x 3 ), ( x 1 x 3 x 4 ), x, ( x 3 x 4 x 5 )} φ : : j [6] y j z 1 y 1 (1 z 1 ) + z y z 1 + (1 z ) + (1 z 3 ) y 3 (1 z 1 ) + (1 z 3 ) + z 4 y 4 1 z y 5 (1 z 3 ) + (1 z 4 ) + (1 z 5 ) y 6 y j, z i {0, 1} y j, z i P lin y j, z i {0, 1} y j, z i [0, 1] : : j [m] y j z i + (1 z i ) y j for j [m] x i C j x i C j y j, z i [0, 1] 9.7. NP 9.8. φ = {C j : j [m]} t φ P lin y j, z i [0, 1] y j val(t ). j [m] 37
38 9.9. X CNF φ 1. P lin y [0, 1] m, z [0, 1] n. t : X {0, 1} Pr t {x i = 1} = z i Pr t {x i = 0} = 1 z i 16: φ X k-cnf 16 t φ t E t [val(t)] (1 (1 1/k) k )val(t ).. φ = {C j : j [m]} j [m] C j C 1 = (x 1 x k ) C 1 Pr{t C 1 } = 1 (1 z i ) t i [k] ( i [k] 1 (1 z ) k i) ( ) k ( i [k] = 1 1 z ) k i k 1 (1 y 1 /k) k z i y 1 i [k] (1 (1 1/k) k )y 1. ( ) 38
39 9.11. h(z) = 1 (1 z/k) k k 0 z 1 h(z) (1 (1 1/k) k )z. C 1 = (x 1 x k ) 9.1. C 1 = (x 1 x x 3 ) C 1 j [m] 9. val(t) = Z = j [m] Z j E t [val(t)] = j [m] = j [m] E t [Z j ] Pr t {t C j } (1 (1 1/k j ) k j )y j ( C j = k j ) j [m] (1 (1 1/k) k ) j [m] (1 (1 1/k) k )val(t ). ( ) y j ( 1 (1 1/k) k ) (1 1/k) k k k N g(k) def = 1 (1 1/k) k 9.. g(k) k P lin g(k) k N 1 1/e g(k) < k (1 1/k) k 1/e 9.3. f(k) g(k) f(k) g(k) f(k) = g(k) k = f() = g() = 0.75 k f(k) g(k)
40 X CNF φ 1. P lin y [0, 1] m, z [0, 1] n. t 1 : X {0, 1} Pr{x i = 1} = z i Pr{x i = 0} = 1 z i 3. t t 1 t t 17: 9.4. φ X k-cnf 17 t φ t E t [val(t)] (3/4)val(t ).. φ = {C j : j [m]} j [m] C j C 1 = (x 1 x k ) C 1 Pr t {t C 1 } 1 f(k) + 1 g(k)y 1 = 1 (1 k ) + 1 (1 (1 1/k)k )y 1 1 ( ) y 1 (1 k ) + (1 (1 1/k) k ) ( y 1 1) = 1 y 1 ( k (1 1/k) k) 3 4 y 1 ( ) j [m] 9. val(t) = Z = j [m] Z j E t [val(t)] = j [m] E t [Z j ] = j [m] Pr t {t C j } (3/4)y i (3/4)val(t ). j [m] k 1 ( k (1 1/k) k ) 3/ 40
41 E, F F E Pr{E F } Pr{E F } def = Pr{E F }. Pr{F } 9.4. E, F, G E F G def = def = def = Pr{E F } = 1 Pr{F E} = 1 Pr{G (E F )} = 1 3 ( Pr{G (E F )} = = 1/4 Pr{E F } 3/4 = 1 ) E, F Pr{E} = Pr{F } Pr{E F } + Pr{ F } Pr{E F } φ = {C j : j [m]} X CNF t : X {0, 1} j [m] Z j { 1 : t C j Z j = 0 : Z = j [m] Z j α(φ) def = E t [Z] = j [m] E t [Z j ] = j [m] Pr t {t C j } φ = {C j : j [m]} X CNF t : X {0, 1} α(φ) m/ 9. 41
42 9.9 φ = {C j : j [m]} X CNF t : X {0, 1} X X t φ CNF φ t X = {x 1,..., x n } CNF φ 1. t : X {0, 1}. i [n] (a) α(φ xi =1) α(φ xi =0) t(x) = 1 t(x) = 0 (b) φ = φ t 3. t 18: φ X CNF 18 t φ t val(t) val(t )/. val(t )/val(t) E t [val(t)] val(t )/. φ = {C j : j [m]} 18 t φ t 9.3. α(φ) val(t )/ α(φ t ) = val(t) α(φ x1 =1) α(φ x1 =0) r : X {0, 1} 9.4. j [m] Pr r {C j x 1 = 1} j [m] Pr r {C j x 1 = 0}. 4
43 9.19. α(φ) = j [m] = Pr r {x 1 = 1} = 1 j [m] = 1 j [m] j [m] = α(φ x1 =1). j [m] E r [Z j ] = j [m] Pr r {C j } Pr r {C j x 1 = 1} + Pr r {x 1 = 0} Pr r {C j x 1 = 1} + 1 j [m] Pr r {C j x 1 = 1} + Pr r {C j x 1 = 1} j [m] ( ) i [n] t(x i ) = 1 j [m] Pr r {C j x 1 = 0} Pr{C j x 1 = 0} r Pr r {C j x 1 = 0} α(φ) α(φ x1 =1) α(φ x1 =1,x =1)... α(φ x1 =1,x =1,...,x n =1). val(t )/ α(φ) α(φ x1 =1,x =1,...,x n=1) = α(φ t ) = val(t). val(t )/val(t) α 43
44 9.5 X -CNF φ MAXSAT X t : X {0, 1} t φ X = {x 1,..., x n } -CNF φ x i {0, 1} y i { 1, 1} x i x i = 0 y i = 1 x i = 1 y i = 1 (6) (x i ), ( x i ) (x i ) (x i ) 1 y i ( x i ) 1 + y i (x i ) = 0 1 y i (x i ) = 1 1 y i = 0 ( x i = 0, y i = 1) = 1 ( x i = 1, y i = 1) ( x i ) ( x i ) = y i ( x i ) = y i = 0 ( x i = 1, y i = 1) = 1 ( x i = 0, y i = 1) (x i x j ) (x i x j ) = y i 1 + y j = y i + y j + y i y j 4 = 1 y i y j y iy j ( x i x j ) y 0 = 1 (x i x j ) (x i x j ) = 1 y i 4 = 1 y 0y i y j y 0y j y iy j y iy j 4 44
45 MAXSAT P quad φ = {C j : j [m]} X = {x 1,..., x n } CNF : a ij (1 + y i y j ) + b ij (1 y i y j ) i,j [n] :i<j : yi = 1 y i Z, y 0 = CNF y i P vect y i Z v i R n+1 : a ij (1 + v i v j ) + b ij (1 v i v j ) i,j [n] :i<j : v i = 1 v i R n+1, v 0 = (1, 0,..., 0) NP ϵ n ln(1/ϵ) X -CNF φ 1. P vect v 0, v 1,..., v n R n+1. r R n+1 r = 1 3. r v i t : X {0, 1} { 1 : r v i 0 t(x i ) = 0 : o.w. 4. t 19: 9.6. φ X -CNF 19 t φ t E t [val(t)] α val(t ). α def = π min θ 0 θ π 1 cos θ. 45
46 . (6) t i {0, 1} y i { 1, 1} P quad E[val(t)] t = E t (a ij (1 + y i y j ) + b ij (1 y i y j )) i,j [n] :i<j = (a ij E t [1 + y i y j ] + b ij E t [1 y i y j ]). i,j [n] :i<j 9.5. i, j [n] : i j Et[1 + y i y j ] = Pr{y i = y j }. t Et[1 y i y j ] = Pr{y i y j }. t 9.4. E t [val(t)] = = i,j [n] :i<j i,j [n] :i<j (a ij E t [1 + y i y j ] + b ij E t [1 y i y j ]) ( ) a ij Pr{y i = y j } + b ij Pr{y i y j }. t t 9.6. i, j [n] : i j 9.5. Pr{y i = y j } = 1 θ ij t π. Pr{y i y j } = θ ij t π. E t [val(t)] = = i,j [n] :i<j i,j [n] :i<j ( ) a ij Pr{y i = y j } + b ij Pr{y i y j } t t (a ij (1 θ ij /π) + b ij θ ij /π) θ : 0 θ π 1 θ π α (1 + cos θ). θ π α (1 cos θ)
47 E[val(t)] = (a ij (1 θ ij /π) + b ij θ ij /π) i,j [n] :i<j i,j [n] :i<j = α = α a ij α(1 + cos θ ij ) + b ij α(1 cos θ ij ) i,j [n] :i<j i,j [n] :i<j α val(t ). a ij (1 + cos θ ij ) + b ij (1 cos θ ij ) a ij (1 + v i v j ) + b ij (1 v i v j ) MAXSAT α = π min 0 θ π θ 1 cos θ
48 10 G = (V, E) coloring c : V [k] s.t. (u, v) E[c(u) c(v)] k 10.1 ( ) V = n (4/3) n G = (V, E) 1. U = V c : V [k] c. G[U] n + 1 (a) G = G[U] u = arg max v U {d G (v)} (b) G = G[N u {u}] G c (c) U = U \ (N u {u}) 3. G[U] n 4. c 0: (b) G u G[N u ] G[U] n Brooks G[U] n 4 4 G[U] 48
49 c c u n + 1 U n + n n + n n n. 3 n 3 n 4 n 3 val(c)/val(c ) 4 n/ ( 3/3) n 3/3 < 4/3 10. G = (V, E) V = [n] P vect : d : v i v j d for (i, j) E v i = 1 v i R n 10.. d P vect G = (V, E) d 1/ G = (V, E) G 1 t = log 3 1 1/ log n 0.63 log n/ (d) G[U] t s {+, } t U s t. 1 c c 3 i V V i V 1 = V = [n] 49
50 G = (V, E) // V = [n] 1. c : V [k] c. P vect v 1,..., v n R n 3. V (a) r 1,..., r t R n r i = 1 (b) s {+, } t C s = {i V : j [t][sgn(v i, r j ) = s j ]}. (c) s {+, } t U s = {i C s : j C s [(i, j) E]}, U = s {+, } t U s (d) G[U] t c (e) V = V \ U 4. c 1: 50
51 10.1. i E[ V i+1 Vi ] V i /3. (x, y) E(G[V i ]) x, y j [t] Pr{sgn(v x, r j ) = sgn(v y, r j )} 1 r j Pr{x, y } = Pr{ j [t][sgn(v x, r j ) = sgn(v y, r j )]} (1/3) t 1 3. E[ E(G[V i+1 ]) V i ] = (x,y) E(G[V i ]) V i = V i Pr{(x, y) } E[ V i+1 Vi ] E[E(G[V i+1 ]) Vi ] V i / i Pr r 1,...,r t { V i+1 > V i / Vi ] 1 log n. log n 1 1/ log n t t log n log 3 log n = log 3 log n 0.63 log n. 3 val(c)/val(c ) 0.63 log n/3 51
52 10.. V = n 1 1/ log n n
53 11 (under construction) 53
54 1 1.1 ( ). n a, b R n (a, b) a b ai b i 1.1. n a R n a i b i. ( a i ) a i. n. b = 1 n 1.. i, j p 1,..., p i R +, a 1,..., a i R + q 1,..., q j R +, b 1,..., b j R + q j q 1 p i p 1 b j b 1 a i a 1 b b j a a i q q j p p i.. q q j > p p i b b j a a i q q j b b j > p p i a a i q q j q 1 b b j b 1 p p i p i a a i a i q 1 /b 1 > p i /a i q 1 /b 1 p i /a i ( q j q ) 1 ( b j b 1 p i p ) 1 a i a 1 1. ( ). n N a 1,..., a n i [n] n a i a i. n i [n] 1.3. x R 1 + x e x 1.4. n N i [n] 1 i log n ( ). Z = i [n] Z i E[Z] = i [n] Z i 54
55
56
ii
ii iii 1 1 1.1..................................... 1 1.2................................... 3 1.3........................... 4 2 9 2.1.................................. 9 2.2...............................
?
240-8501 79-2 Email: nakamoto@ynu.ac.jp 1 3 1.1...................................... 3 1.2?................................. 6 1.3..................................... 8 1.4.......................................
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 =
2016
2016 1 G x x G d G (x) 1 ( ) G d G (x) = 2 E(G). x V (G) 2 ( ) 1.1 1: n m on-off ( 1 ) off on 1: on-off ( on ) G v v N(v) on-off G S V (G) N(v) S { 3 G v S v S G G = 1 OK ( ) G 2 3.1 u S u u u 1 G u S
1. (8) (1) (x + y) + (x + y) = 0 () (x + y ) 5xy = 0 (3) (x y + 3y 3 ) (x 3 + xy ) = 0 (4) x tan y x y + x = 0 (5) x = y + x + y (6) = x + y 1 x y 3 (
1 1.1 (1) (1 + x) + (1 + y) = 0 () x + y = 0 (3) xy = x (4) x(y + 3) + y(y + 3) = 0 (5) (a + y ) = x ax a (6) x y 1 + y x 1 = 0 (7) cos x + sin x cos y = 0 (8) = tan y tan x (9) = (y 1) tan x (10) (1 +
A, B, C. (1) A = A. (2) A = B B = A. (3) A = B, B = C A = C. A = B. (3)., f : A B g : B C. g f : A C, A = C. 7.1, A, B,. A = B, A, A A., A, A
91 7,.,, ( ).,,.,.,. 7.1 A B, A B, A = B. 1), 1,.,. 7.1 A, B, 3. (i) A B. (ii) f : A B. (iii) A B. (i) (ii)., 6.9, (ii) (iii).,,,. 1), Ā = B.. A, Ā, Ā,. 92 7 7.2 A, B, C. (1) A = A. (2) A = B B = A. (3)
24 I ( ) 1. R 3 (i) C : x 2 + y 2 1 = 0 (ii) C : y = ± 1 x 2 ( 1 x 1) (iii) C : x = cos t, y = sin t (0 t 2π) 1.1. γ : [a, b] R n ; t γ(t) = (x
![24 I ( ) 1. R 3 (i) C : x 2 + y 2 1 = 0 (ii) C : y = ± 1 x 2 ( 1 x 1) (iii) C : x = cos t, y = sin t (0 t 2π) 1.1. γ : [a, b] R n ; t γ(t) = (x](/thumbs/94/118744578.jpg "24 I ( ) 1. R 3 (i) C : x 2 + y 2 1 = 0 (ii) C : y = ± 1 x 2 ( 1 x 1) (iii) C : x = cos t, y = sin t (0 t 2π) 1.1. γ : [a, b] R n ; t γ(t) = (x")
24 I 1.1.. ( ) 1. R 3 (i) C : x 2 + y 2 1 = 0 (ii) C : y = ± 1 x 2 ( 1 x 1) (iii) C : x = cos t, y = sin t (0 t 2π) 1.1. γ : [a, b] R n ; t γ(t) = (x 1 (t), x 2 (t),, x n (t)) ( ) ( ), γ : (i) x 1 (t),
Part () () Γ Part ,
Contents a 6 6 6 6 6 6 6 7 7. 8.. 8.. 8.3. 8 Part. 9. 9.. 9.. 3. 3.. 3.. 3 4. 5 4.. 5 4.. 9 4.3. 3 Part. 6 5. () 6 5.. () 7 5.. 9 5.3. Γ 3 6. 3 6.. 3 6.. 3 6.3. 33 Part 3. 34 7. 34 7.. 34 7.. 34 8. 35
2 G(k) e ikx = (ik) n x n n! n=0 (k ) ( ) X n = ( i) n n k n G(k) k=0 F (k) ln G(k) = ln e ikx n κ n F (k) = F (k) (ik) n n= n! κ n κ n = ( i) n n k n
. X {x, x 2, x 3,... x n } X X {, 2, 3, 4, 5, 6} X x i P i. 0 P i 2. n P i = 3. P (i ω) = i ω P i P 3 {x, x 2, x 3,... x n } ω P i = 6 X f(x) f(x) X n n f(x i )P i n x n i P i X n 2 G(k) e ikx = (ik) n
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
4‐E ) キュリー温度を利用した消磁：熱消磁
( ) () x C x = T T c T T c 4D ) ) Fe Ni Fe Fe Ni (Fe Fe Fe Fe Fe 462 Fe76 Ni36 4E ) ) (Fe) 463 4F ) ) ( ) Fe HeNe 17 Fe Fe Fe HeNe 464 Ni Ni Ni HeNe 465 466 (2) Al PtO 2 (liq) 467 4G ) Al 468 Al ( 468
II 2 3.,, A(B + C) = AB + AC, (A + B)C = AC + BC. 4. m m A, m m B,, m m B, AB = BA, A,, I. 5. m m A, m n B, AB = B, A I E, 4 4 I, J, K
II. () 7 F 7 = { 0,, 2, 3, 4, 5, 6 }., F 7 a, b F 7, a b, F 7,. (a) a, b,,. (b) 7., 4 5 = 20 = 2 7 + 6, 4 5 = 6 F 7., F 7,., 0 a F 7, ab = F 7 b F 7. (2) 7, 6 F 6 = { 0,, 2, 3, 4, 5 },,., F 6., 0 0 a F
Z: Q: R: C: sin 6 5 ζ a, b
Z: Q: R: C: 3 3 7 4 sin 6 5 ζ 9 6 6............................... 6............................... 6.3......................... 4 7 6 8 8 9 3 33 a, b a bc c b a a b 5 3 5 3 5 5 3 a a a a p > p p p, 3,
(2 X Poisso P (λ ϕ X (t = E[e itx ] = k= itk λk e k! e λ = (e it λ k e λ = e eitλ e λ = e λ(eit 1. k! k= 6.7 X N(, 1 ϕ X (t = e 1 2 t2 : Cauchy ϕ X (t
![(2 X Poisso P (λ ϕ X (t = E[e itx ] = k= itk λk e k! e λ = (e it λ k e λ = e eitλ e λ = e λ(eit 1. k! k= 6.7 X N(, 1 ϕ X (t = e 1 2 t2 : Cauchy ϕ X (t](/thumbs/67/56612994.jpg "(2 X Poisso P (λ ϕ X (t = E[e itx ] = k= itk λk e k! e λ = (e it λ k e λ = e eitλ e λ = e λ(eit 1. k! k= 6.7 X N(, 1 ϕ X (t = e 1 2 t2 : Cauchy ϕ X (t")
6 6.1 6.1 (1 Z ( X = e Z, Y = Im Z ( Z = X + iy, i = 1 (2 Z E[ e Z ] < E[ Im Z ] < Z E[Z] = E[e Z] + ie[im Z] 6.2 Z E[Z] E[ Z ] : E[ Z ] < e Z Z, Im Z Z E[Z] α = E[Z], Z = Z Z 1 {Z } E[Z] = α = α [ α ]
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
e a b a b b a a a 1 a a 1 = a 1 a = e G G G : x ( x =, 8, 1 ) x 1,, 60 θ, ϕ ψ θ G G H H G x. n n 1 n 1 n σ = (σ 1, σ,..., σ N ) i σ i i n S n n = 1,,
01 10 18 ( ) 1 6 6 1 8 8 1 6 1 0 0 0 0 1 Table 1: 10 0 8 180 1 1 1. ( : 60 60 ) : 1. 1 e a b a b b a a a 1 a a 1 = a 1 a = e G G G : x ( x =, 8, 1 ) x 1,, 60 θ, ϕ ψ θ G G H H G x. n n 1 n 1 n σ = (σ 1,
(iii) 0 V, x V, x + 0 = x. 0. (iv) x V, y V, x + y = 0., y x, y = x. (v) 1x = x. (vii) (α + β)x = αx + βx. (viii) (αβ)x = α(βx)., V, C.,,., (1)
1. 1.1...,. 1.1.1 V, V x, y, x y x + y x + y V,, V x α, αx αx V,, (i) (viii) : x, y, z V, α, β C, (i) x + y = y + x. (ii) (x + y) + z = x + (y + z). 1 (iii) 0 V, x V, x + 0 = x. 0. (iv) x V, y V, x + y
(yx4) 1887-1945 741936 50 1995 1 31 http://kenboushoten.web.fc.com/ OCR TeX 50 yx4 e-mail: yx4.aydx5@gmail.com i Jacobi 1751 1 3 Euler Fagnano 187 9 0 Abel iii 1 1...................................
chap1.dvi
1 1 007 1 e iθ = cos θ + isin θ 1) θ = π e iπ + 1 = 0 1 ) 3 11 f 0 r 1 1 ) k f k = 1 + r) k f 0 f k k = 01) f k+1 = 1 + r)f k ) f k+1 f k = rf k 3) 1 ) ) ) 1+r/)f 0 1 1 + r/) f 0 = 1 + r + r /4)f 0 1 f
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}, {}.
1 1.1 H = µc i c i + c i t ijc j + 1 c i c j V ijklc k c l (1) V ijkl = V jikl = V ijlk = V jilk () t ij = t ji, V ijkl = V lkji (3) (1) V 0 H mf = µc
013 6 30 BCS 1 1.1........................ 1................................ 3 1.3............................ 3 1.4............................... 5 1.5.................................... 5 6 3 7 4 8
1.2 y + P (x)y + Q(x)y = 0 (1) y 1 (x), y 2 (x) y 1 (x), y 2 (x) (1) y(x) c 1, c 2 y(x) = c 1 y 1 (x) + c 2 y 2 (x) 3 y 1 (x) y 1 (x) e R P (x)dx y 2
1 1.1 R(x) = 0 y + P (x)y + Q(x)y = R(x)...(1) y + P (x)y + Q(x)y = 0...(2) 1 2 u(x) v(x) c 1 u(x)+ c 2 v(x) = 0 c 1 = c 2 = 0 c 1 = c 2 = 0 2 0 2 u(x) v(x) u(x) u (x) W (u, v)(x) = v(x) v (x) 0 1 1.2
1. 2 P 2 (x, y) 2 x y (0, 0) R 2 = {(x, y) x, y R} x, y R P = (x, y) O = (0, 0) OP ( ) OP x x, y y ( ) x v = y ( ) x 2 1 v = P = (x, y) y ( x y ) 2 (x
. P (, (0, 0 R {(,, R}, R P (, O (0, 0 OP OP, v v P (, ( (, (, { R, R} v (, (, (,, z 3 w z R 3,, z R z n R n.,..., n R n n w, t w ( z z Ke Words:. A P 3 0 B P 0 a. A P b B P 3. A π/90 B a + b c π/ 3. +
n ξ n,i, i = 1,, n S n ξ n,i n 0 R 1,.. σ 1 σ i .10.14.15 0 1 0 1 1 3.14 3.18 3.19 3.14 3.14,. ii 1 1 1.1..................................... 1 1............................... 3 1.3.........................
prime number theorem
For Tutor MeBio ζ Eite by kamei MeBio 7.8.3 : Bernoulli Bernoulli 4 Bernoulli....................................................................................... 4 Bernoulli............................................................................
+ 1 ( ) I IA i i i 1 n m a 11 a 1j a 1m A = a i1 a ij a im a n1 a nj a nm.....
+ http://krishnathphysaitama-uacjp/joe/matrix/matrixpdf 1 ( ) I IA i i i 1 n m a 11 a 1j a 1m A = a i1 a ij a im a n1 a nj a nm (1) n m () (n, m) ( ) n m B = ( ) 3 2 4 1 (2) 2 2 ( ) (2, 2) ( ) C = ( 46
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
2009 IA 5 I 22, 23, 24, 25, 26, (1) Arcsin 1 ( 2 (4) Arccos 1 ) 2 3 (2) Arcsin( 1) (3) Arccos 2 (5) Arctan 1 (6) Arctan ( 3 ) 3 2. n (1) ta
009 IA 5 I, 3, 4, 5, 6, 7 6 3. () Arcsin ( (4) Arccos ) 3 () Arcsin( ) (3) Arccos (5) Arctan (6) Arctan ( 3 ) 3. n () tan x (nπ π/, nπ + π/) f n (x) f n (x) fn (x) Arctan x () sin x [nπ π/, nπ +π/] g n
c 2009 i
I 2009 c 2009 i 0 1 0.0................................... 1 0.1.............................. 3 0.2.............................. 5 1 7 1.1................................. 7 1.2..............................
‚åŁÎ“·„´Šš‡ðŠ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
29
9 .,,, 3 () C k k C k C + C + C + + C 8 + C 9 + C k C + C + C + C 3 + C 4 + C 5 + + 45 + + + 5 + + 9 + 4 + 4 + 5 4 C k k k ( + ) 4 C k k ( k) 3 n( ) n n n ( ) n ( ) n 3 ( ) 3 3 3 n 4 ( ) 4 4 4 ( ) n n
1 Ricci V, V i, W f : V W f f(v ) = Imf W ( ) f : V 1 V k W 1
1 Ricci V, V i, W f : V W f f(v = Imf W ( f : V 1 V k W 1 {f(v 1,, v k v i V i } W < Imf > < > f W V, V i, W f : U V L(U; V f : V 1 V r W L(V 1,, V r ; W L(V 1,, V r ; W (f + g(v 1,, v r = f(v 1,, v r
ω 0 m(ẍ + γẋ + ω0x) 2 = ee (2.118) e iωt x = e 1 m ω0 2 E(ω). (2.119) ω2 iωγ Z N P(ω) = χ(ω)e = exzn (2.120) ϵ = ϵ 0 (1 + χ) ϵ(ω) ϵ 0 = 1 +
2.6 2.6.1 ω 0 m(ẍ + γẋ + ω0x) 2 = ee (2.118) e iωt x = e 1 m ω0 2 E(ω). (2.119) ω2 iωγ Z N P(ω) = χ(ω)e = exzn (2.120) ϵ = ϵ 0 (1 + χ) ϵ(ω) ϵ 0 = 1 + Ne2 m j f j ω 2 j ω2 iωγ j (2.121) Z ω ω j γ j f j
2000年度『数学展望 I』講義録
2000 I I IV I II 2000 I I IV I-IV. i ii 3.10 (http://www.math.nagoya-u.ac.jp/ kanai/) 2000 A....1 B....4 C....10 D....13 E....17 Brouwer A....21 B....26 C....33 D....39 E. Sperner...45 F....48 A....53
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 =
2.2 h h l L h L = l cot h (1) (1) L l L l l = L tan h (2) (2) L l 2 l 3 h 2.3 a h a h (a, h)
1 16 10 5 1 2 2.1 a a a 1 1 1 2.2 h h l L h L = l cot h (1) (1) L l L l l = L tan h (2) (2) L l 2 l 3 h 2.3 a h a h (a, h) 4 2 3 4 2 5 2.4 x y (x,y) l a x = l cot h cos a, (3) y = l cot h sin a (4) h a
iii 1 1 1 1................................ 1 2.......................... 3 3.............................. 5 4................................ 7 5................................ 9 6............................
(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
(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
X G P G (X) G BG [X, BG] S 2 2 2 S 2 2 S 2 = { (x 1, x 2, x 3 ) R 3 x 2 1 + x 2 2 + x 2 3 = 1 } R 3 S 2 S 2 v x S 2 x x v(x) T x S 2 T x S 2 S 2 x T x S 2 = { ξ R 3 x ξ } R 3 T x S 2 S 2 x x T x S 2
1 1 sin cos P (primary) S (secondly) 2 P S A sin(ω2πt + α) A ω 1 ω α V T m T m 1 100Hz m 2 36km 500Hz. 36km 1
sin cos P (primary) S (secondly) 2 P S A sin(ω2πt + α) A ω ω α 3 3 2 2V 3 33+.6T m T 5 34m Hz. 34 3.4m 2 36km 5Hz. 36km m 34 m 5 34 + m 5 33 5 =.66m 34m 34 x =.66 55Hz, 35 5 =.7 485.7Hz 2 V 5Hz.5V.5V V
SO(3) 49 u = Ru (6.9), i u iv i = i u iv i (C ) π π : G Hom(V, V ) : g D(g). π : R 3 V : i 1. : u u = u 1 u 2 u 3 (6.10) 6.2 i R α (1) = 0 cos α
SO(3) 48 6 SO(3) t 6.1 u, v u = u 1 1 + u 2 2 + u 3 3 = u 1 e 1 + u 2 e 2 + u 3 e 3, v = v 1 1 + v 2 2 + v 3 3 = v 1 e 1 + v 2 e 2 + v 3 e 3 (6.1) i (e i ) e i e j = i j = δ ij (6.2) ( u, v ) = u v = ij
x (x, ) x y (, y) iy x y z = x + iy (x, y) (r, θ) r = x + y, θ = tan ( y ), π < θ π x r = z, θ = arg z z = x + iy = r cos θ + ir sin θ = r(cos θ + i s
... x, y z = x + iy x z y z x = Rez, y = Imz z = x + iy x iy z z () z + z = (z + z )() z z = (z z )(3) z z = ( z z )(4)z z = z z = x + y z = x + iy ()Rez = (z + z), Imz = (z z) i () z z z + z z + z.. z
n Y 1 (x),..., Y n (x) 1 W (Y 1 (x),..., Y n (x)) 0 W (Y 1 (x),..., Y n (x)) = Y 1 (x)... Y n (x) Y 1(x)... Y n(x) (x)... Y n (n 1) (x) Y (n 1)
D d dx 1 1.1 n d n y a 0 dx n + a d n 1 y 1 dx n 1 +... + a dy n 1 dx + a ny = f(x)...(1) dk y dx k = y (k) a 0 y (n) + a 1 y (n 1) +... + a n 1 y + a n y = f(x)...(2) (2) (2) f(x) 0 a 0 y (n) + a 1 y
z f(z) f(z) x, y, u, v, r, θ r > 0 z = x + iy, f = u + iv C γ D f(z) f(z) D f(z) f(z) z, Rm z, z 1.1 z = x + iy = re iθ = r (cos θ + i sin θ) z = x iy
z fz fz x, y, u, v, r, θ r > z = x + iy, f = u + iv γ D fz fz D fz fz z, Rm z, z. z = x + iy = re iθ = r cos θ + i sin θ z = x iy = re iθ = r cos θ i sin θ x = z + z = Re z, y = z z = Im z i r = z = z
(2018 2Q C) [ ] R 2 2 P = (a, b), Q = (c, d) Q P QP = ( ) a c b d (a c, b d) P = (a, b) O P ( ) a p = b P = (a, b) p = ( ) a b R 2 {( ) } R 2 x = x, y
![(2018 2Q C) [ ] R 2 2 P = (a, b), Q = (c, d) Q P QP = ( ) a c b d (a c, b d) P = (a, b) O P ( ) a p = b P = (a, b) p = ( ) a b R 2 {( ) } R 2 x = x, y](/thumbs/101/151465237.jpg "(2018 2Q C) [ ] R 2 2 P = (a, b), Q = (c, d) Q P QP = ( ) a c b d (a c, b d) P = (a, b) O P ( ) a p = b P = (a, b) p = ( ) a b R 2 {( ) } R 2 x = x, y")
(2018 2Q C) [ ] R 2 2 P = (a, b), Q = (c, d) Q P QP = a c b d (a c, b d) P = (a, b) O P a p = b P = (a, b) p = a b R 2 { } R 2 x = x, y R y 2 a p =, c q = b d p + a + c q = b + d q p P q a p = c R c b
I ( ) ( ) (1) C z = a ρ. f(z) dz = C = = (z a) n dz C n= p 2π (ρe iθ ) n ρie iθ dθ 0 n= p { 2πiA 1 n = 1 0 n 1 (2) C f(z) n.. n f(z)dz = 2πi Re
I ( ). ( ) () a ρ. f() d ( a) n d n p π (ρe iθ ) n ρie iθ dθ n p { πia n n () f() n.. n f()d πi es f( k ) k n n. f()d n k k f()d. n f()d πi esf( k ). k I ( ). ( ) () f() p g() f() g()( ) p. f(). f() A
III 1 (X, d) d U d X (X, d). 1. (X, d).. (i) d(x, y) d(z, y) d(x, z) (ii) d(x, y) d(z, w) d(x, z) + d(y, w) 2. (X, d). F X.. (1), X F, (2) F 1, F 2 F
III 1 (X, d) d U d X (X, d). 1. (X, d).. (i) d(x, y) d(z, y) d(x, z) (ii) d(x, y) d(z, w) d(x, z) + d(y, w) 2. (X, d). F X.. (1), X F, (2) F 1, F 2 F F 1 F 2 F, (3) F λ F λ F λ F. 3., A λ λ A λ. B λ λ
A = A x x + A y y + A, B = B x x + B y y + B, C = C x x + C y y + C..6 x y A B C = A x x + A y y + A B x B y B C x C y C { B = A x x + A y y + A y B B
9 7 A = A x x + A y y + A, B = B x x + B y y + B, C = C x x + C y y + C..6 x y A B C = A x x + A y y + A B x B y B C x C y C { B = A x x + A y y + A y B B x x B } B C y C y + x B y C x C C x C y B = A
1 : f(z = re iθ ) = u(r, θ) + iv(r, θ). (re iθ ) 2 = r 2 e 2iθ = r 2 cos 2θ + ir 2 sin 2θ r f(z = x + iy) = u(x, y) + iv(x, y). (x + iy) 2 = x 2 y 2 +
1.3 1.4. (pp.14-27) 1 1 : f(z = re iθ ) = u(r, θ) + iv(r, θ). (re iθ ) 2 = r 2 e 2iθ = r 2 cos 2θ + ir 2 sin 2θ r f(z = x + iy) = u(x, y) + iv(x, y). (x + iy) 2 = x 2 y 2 + i2xy x = 1 y (1 + iy) 2 = 1
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 ),
() n C + n C + n C + + n C n n (3) n C + n C + n C 4 + n C + n C 3 + n C 5 + (5) (6 ) n C + nc + 3 nc n nc n (7 ) n C + nc + 3 nc n nc n (
3 n nc k+ k + 3 () n C r n C n r nc r C r + C r ( r n ) () n C + n C + n C + + n C n n (3) n C + n C + n C 4 + n C + n C 3 + n C 5 + (4) n C n n C + n C + n C + + n C n (5) k k n C k n C k (6) n C + nc
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,
z f(z) f(z) x, y, u, v, r, θ r > 0 z = x + iy, f = u + iv C γ D f(z) f(z) D f(z) f(z) z, Rm z, z 1.1 z = x + iy = re iθ = r (cos θ + i sin θ) z = x iy
f f x, y, u, v, r, θ r > = x + iy, f = u + iv C γ D f f D f f, Rm,. = x + iy = re iθ = r cos θ + i sin θ = x iy = re iθ = r cos θ i sin θ x = + = Re, y = = Im i r = = = x + y θ = arg = arctan y x e i =
数学Ⅱ演習（足助・09夏）
II I 9/4/4 9/4/2 z C z z z z, z 2 z, w C zw z w 3 z, w C z + w z + w 4 t R t C t t t t t z z z 2 z C re z z + z z z, im z 2 2 3 z C e z + z + 2 z2 + 3! z3 + z!, I 4 x R e x cos x + sin x 2 z, w C e z+w
1. 4cm 16 cm 4cm 20cm 18 cm L λ(x)=ax [kg/m] A x 4cm A 4cm 12 cm h h Y 0 a G 0.38h a b x r(x) x y = 1 h 0.38h G b h X x r(x) 1 S(x) = πr(x) 2 a,b, h,π
![1. 4cm 16 cm 4cm 20cm 18 cm L λ(x)=ax [kg/m] A x 4cm A 4cm 12 cm h h Y 0 a G 0.38h a b x r(x) x y = 1 h 0.38h G b h X x r(x) 1 S(x) = πr(x) 2 a,b, h,π](/thumbs/101/149329485.jpg "1. 4cm 16 cm 4cm 20cm 18 cm L λ(x)=ax [kg/m] A x 4cm A 4cm 12 cm h h Y 0 a G 0.38h a b x r(x) x y = 1 h 0.38h G b h X x r(x) 1 S(x) = πr(x) 2 a,b, h,π")
. 4cm 6 cm 4cm cm 8 cm λ()=a [kg/m] A 4cm A 4cm cm h h Y a G.38h a b () y = h.38h G b h X () S() = π() a,b, h,π V = ρ M = ρv G = M h S() 3 d a,b, h 4 G = 5 h a b a b = 6 ω() s v m θ() m v () θ() ω() dθ()
limit&derivative
- - 7 )................................................................................ 5.................................. 7.. e ).......................... 9 )..........................................
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
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
) ] [ h m x + y + + V x) φ = Eφ 1) z E = i h t 13) x << 1) N n n= = N N + 1) 14) N n n= = N N + 1)N + 1) 6 15) N n 3 n= = 1 4 N N + 1) 16) N n 4
![) ] [ h m x + y + + V x) φ = Eφ 1) z E = i h t 13) x << 1) N n n= = N N + 1) 14) N n n= = N N + 1)N + 1) 6 15) N n 3 n= = 1 4 N N + 1) 16) N n 4](/thumbs/92/107866707.jpg ") ] [ h m x + y + + V x) φ = Eφ 1) z E = i h t 13) x << 1) N n n= = N N + 1) 14) N n n= = N N + 1)N + 1) 6 15) N n 3 n= = 1 4 N N + 1) 16) N n 4")
1. k λ ν ω T v p v g k = π λ ω = πν = π T v p = λν = ω k v g = dω dk 1) ) 3) 4). p = hk = h λ 5) E = hν = hω 6) h = h π 7) h =6.6618 1 34 J sec) hc=197.3 MeV fm = 197.3 kev pm= 197.3 ev nm = 1.97 1 3 ev
( )
18 10 01 ( ) 1 2018 4 1.1 2018............................... 4 1.2 2018......................... 5 2 2017 7 2.1 2017............................... 7 2.2 2017......................... 8 3 2016 9 3.1 2016...............................
untitled
1 n m (ICA = independent component analysis) BSS (= blind source separation) : s(t) =(s 1 (t),...,s n (t)) R n : x(t) =(x 1 (t),...,x n (t)) R m 1 i s i (t) a ji R j 2 (A =(a ji )) x(t) =As(t) (1) n =
arctan 1 arctan arctan arctan π = = ( ) π = 4 = π = π = π = =
arctan arctan arctan arctan 2 2000 π = 3 + 8 = 3.25 ( ) 2 8 650 π = 4 = 3.6049 9 550 π = 3 3 30 π = 3.622 264 π = 3.459 3 + 0 7 = 3.4085 < π < 3 + 7 = 3.4286 380 π = 3 + 77 250 = 3.46 5 3.45926 < π < 3.45927
II 2 II
II 2 II 2005 yugami@cc.utsunomiya-u.ac.jp 2005 4 1 1 2 5 2.1.................................... 5 2.2................................. 6 2.3............................. 6 2.4.................................
I A A441 : April 15, 2013 Version : 1.1 I Kawahira, Tomoki TA (Shigehiro, Yoshida )
I013 00-1 : April 15, 013 Version : 1.1 I Kawahira, Tomoki TA (Shigehiro, Yoshida) http://www.math.nagoya-u.ac.jp/~kawahira/courses/13s-tenbou.html pdf * 4 15 4 5 13 e πi = 1 5 0 5 7 3 4 6 3 6 10 6 17
30
3 ............................................2 2...........................................2....................................2.2...................................2.3..............................
CV CV CV --
30 4 30 0 30 60 V/Hz V/Hz CV CV -- CV CV CV -- CV 3 AVR -3- 5m/ 0.5G 3m/ 0.3G 3 0.5Hz 0Hz 0.5Hz 0Hz 3 54kV 3 5 m/ 0.5G 3 3 5m/ 0.5G -4- V & bc 0.0VPT Z & G Z & L V& bc Z & L j0.50 0.0 0.0 5.7 V Z & + Z
36 3 D f(z) D z f(z) z Taylor z D C f(z) z C C f (z) C f(z) f (z) f(z) D C D D z C C 3.: f(z) 3. f (z) f 2 (z) D D D D D f (z) f 2 (z) D D f (z) f 2 (
3 3. D f(z) D D D D D D D D f(z) D f (z) f (z) f(z) D (i) (ii) (iii) f(z) = ( ) n z n = z + z 2 z 3 + n= z < z < z > f (z) = e t(+z) dt Re z> Re z> [ ] f (z) = e t(+z) = (Rez> ) +z +z t= z < f(z) Taylor
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
p = mv p x > h/4π λ = h p m v Ψ 2 Ψ
II p = mv p x > h/4π λ = h p m v Ψ 2 Ψ Ψ Ψ 2 0 x P'(x) m d 2 x = mω 2 x = kx = F(x) dt 2 x = cos(ωt + φ) mω 2 = k ω = m k v = dx = -ωsin(ωt + φ) dt = d 2 x dt 2 0 y v θ P(x,y) θ = ωt + φ ν = ω [Hz] 2π
構造と連続体の力学基礎
II 37 Wabash Avenue Bridge, Illinois 州 Winnipeg にある歩道橋 Esplanade Riel 橋6 6 斜張橋である必要は多分無いと思われる すぐ横に道路用桁橋有り しかも塔基部のレストランは 8 年には営業していなかった 9 9. 9.. () 97 [3] [5] k 9. m w(t) f (t) = f (t) + mg k w(t) Newton
°ÌÁê¿ô³ØII
July 14, 2007 Brouwer f f(x) = x x f(z) = 0 2 f : S 2 R 2 f(x) = f( x) x S 2 3 3 2 - - - 1. X x X U(x) U(x) x U = {U(x) x X} X 1. U(x) A U(x) x 2. A U(x), A B B U(x) 3. A, B U(x) A B U(x) 4. A U(x),
untitled
1 17 () BAC9ABC6ACB3 1 tan 6 = 3, cos 6 = AB=1 BC=2, AC= 3 2 A BC D 2 BDBD=BA 1 2 ABD BADBDA ABC6 BAD = (18 6 ) / 2 = 6 θ = 18 BAD = 12 () AD AD=BADCAD9 ABD ACD A 1 1 1 1 dsinαsinα = d 3 sin β 3 sin β
36 th IChO : - 3 ( ) , G O O D L U C K final 1
36 th ICh - - 5 - - : - 3 ( ) - 169 - -, - - - - - - - G D L U C K final 1 1 1.01 2 e 4.00 3 Li 6.94 4 Be 9.01 5 B 10.81 6 C 12.01 7 N 14.01 8 16.00 9 F 19.00 10 Ne 20.18 11 Na 22.99 12 Mg 24.31 Periodic
untitled
( ) c a sin b c b c a cos a c b c a tan b a b cos sin a c b c a ccos b csin (4) Ma k Mg a (Gal) g(98gal) (Gal) a max (K-E) kh Zck.85.6. 4 Ma g a k a g k D τ f c + σ tanφ σ 3 3 /A τ f3 S S τ A σ /A σ /A
(2016 2Q H) [ ] R 2 2 P = (a, b), Q = (c, d) Q P QP = ( ) a c b d (a c, b d) P = (a, b) O P ( ) a p = b P = (a, b) p = ( ) a b R 2 {( ) } R 2 x = x, y
![(2016 2Q H) [ ] R 2 2 P = (a, b), Q = (c, d) Q P QP = ( ) a c b d (a c, b d) P = (a, b) O P ( ) a p = b P = (a, b) p = ( ) a b R 2 {( ) } R 2 x = x, y](/thumbs/98/136512264.jpg "(2016 2Q H) [ ] R 2 2 P = (a, b), Q = (c, d) Q P QP = ( ) a c b d (a c, b d) P = (a, b) O P ( ) a p = b P = (a, b) p = ( ) a b R 2 {( ) } R 2 x = x, y")
(2016 2Q H) [ ] R 2 2 P = (a, b), Q = (c, d) Q P QP = a c b d (a c, b d) P = (a, b) O P a p = b P = (a, b) p = a b R 2 { } R 2 x = x, y R y 2 a p =, c q = b d p + a + c q = b + d q p P q a p = c R c b
v v = v 1 v 2 v 3 (1) R = (R ij ) (2) R (R 1 ) ij = R ji (3) 3 R ij R ik = δ jk (4) i=1 δ ij Kronecker δ ij = { 1 (i = j) 0 (i
1. 1 1.1 1.1.1 1.1.1.1 v v = v 1 v 2 v 3 (1) R = (R ij ) (2) R (R 1 ) ij = R ji (3) R ij R ik = δ jk (4) δ ij Kronecker δ ij = { 1 (i = j) 0 (i j) (5) 1 1.1. v1.1 2011/04/10 1. 1 2 v i = R ij v j (6) [
(ii) (iii) z a = z a =2 z a =6 sin z z a dz. cosh z z a dz. e z dz. (, a b > 6.) (z a)(z b) 52.. (a) dz, ( a = /6.), (b) z =6 az (c) z a =2 53. f n (z
B 4 24 7 9 ( ) :,..,,.,. 4 4. f(z): D C: D a C, 2πi C f(z) dz = f(a). z a a C, ( ). (ii), a D, a U a,r D f. f(z) = A n (z a) n, z U a,r, n= A n := 2πi C f(ζ) dζ, n =,,..., (ζ a) n+, C a D. (iii) U a,r
F8302D_1目次_160527.doc
N D F 830D.. 3. 4. 4. 4.. 4.. 4..3 4..4 4..5 4..6 3 4..7 3 4..8 3 4..9 3 4..0 3 4. 3 4.. 3 4.. 3 4.3 3 4.4 3 5. 3 5. 3 5. 3 5.3 3 5.4 3 5.5 4 6. 4 7. 4 7. 4 7. 4 8. 4 3. 3. 3. 3. 4.3 7.4 0 3. 3 3. 3 3.
2019 1 5 0 3 1 4 1.1.................... 4 1.1.1......................... 4 1.1.2........................ 5 1.1.3................... 5 1.1.4........................ 6 1.1.5......................... 6 1.2..........................
TOP URL 1
TOP URL http://amonphys.web.fc.com/ 1 19 3 19.1................... 3 19.............................. 4 19.3............................... 6 19.4.............................. 8 19.5.............................
¥¢¥ë¥´¥ê¥º¥à¥¤¥ó¥È¥í¥À¥¯¥·¥ç¥ó ÎØ¹Ö #1
#1 id:motemen August 27, 2008 id:motemen 1-3 1-5 6-9 10-14 1 2 : n < a 1, a 2,..., a n > a 1 a 2 a n < a 1, a 2,..., a n > : Google: insertion sort site:youtube.com 1 : procedure Insertion-Sort(A) for
: , 2.0, 3.0, 2.0, (%) ( 2.
2017 1 2 1.1...................................... 2 1.2......................................... 4 1.3........................................... 10 1.4................................. 14 1.5..........................................
II (Percolation) ( 3-4 ) 1. [ ],,,,,,,. 2. [ ],.. 3. [ ],. 4. [ ] [ ] G. Grimmett Percolation Springer-Verlag New-York [ ] 3
![II (Percolation) ( 3-4 ) 1. [ ],,,,,,,. 2. [ ],.. 3. [ ],. 4. [ ] [ ] G. Grimmett Percolation Springer-Verlag New-York [ ] 3](/thumbs/94/121840826.jpg "II (Percolation) ( 3-4 ) 1. [ ],,,,,,,. 2. [ ],.. 3. [ ],. 4. [ ] [ ] G. Grimmett Percolation Springer-Verlag New-York [ ] 3")
II (Percolation) 12 9 27 ( 3-4 ) 1 [ ] 2 [ ] 3 [ ] 4 [ ] 1992 5 [ ] G Grimmett Percolation Springer-Verlag New-York 1989 6 [ ] 3 1 3 p H 2 3 2 FKG BK Russo 2 p H = p T (=: p c ) 3 2 Kesten p c =1/2 ( )
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
1 9 v.0.1 c (2016/10/07) Minoru Suzuki T µ 1 (7.108) f(e ) = 1 e β(e µ) 1 E 1 f(e ) (Bose-Einstein distribution function) *1 (8.1) (9.1)
1 9 v..1 c (216/1/7) Minoru Suzuki 1 1 9.1 9.1.1 T µ 1 (7.18) f(e ) = 1 e β(e µ) 1 E 1 f(e ) (Bose-Einstein distribution function) *1 (8.1) (9.1) E E µ = E f(e ) E µ (9.1) µ (9.2) µ 1 e β(e µ) 1 f(e )
18 I ( ) (1) I-1,I-2,I-3 (2) (3) I-1 ( ) (100 ) θ ϕ θ ϕ m m l l θ ϕ θ ϕ 2 g (1) (2) 0 (3) θ ϕ (4) (3) θ(t) = A 1 cos(ω 1 t + α 1 ) + A 2 cos(ω 2 t + α
18 I ( ) (1) I-1,I-2,I-3 (2) (3) I-1 ( ) (100 ) θ ϕ θ ϕ m m l l θ ϕ θ ϕ 2 g (1) (2) 0 (3) θ ϕ (4) (3) θ(t) = A 1 cos(ω 1 t + α 1 ) + A 2 cos(ω 2 t + α 2 ), ϕ(t) = B 1 cos(ω 1 t + α 1 ) + B 2 cos(ω 2 t
VI VI.21 W 1,..., W r V W 1,..., W r W W r = {v v r v i W i (1 i r)} V = W W r V W 1,..., W r V W 1,..., W r V = W 1 W
3 30 5 VI VI. W,..., W r V W,..., W r W + + W r = {v + + v r v W ( r)} V = W + + W r V W,..., W r V W,..., W r V = W W r () V = W W r () W (W + + W + W + + W r ) = {0} () dm V = dm W + + dm W r VI. f n
A 2008 10 (2010 4 ) 1 1 1.1................................. 1 1.2..................................... 1 1.3............................ 3 1.3.1............................. 3 1.3.2..................................
Chap9.dvi
.,. f(),, f(),,.,. () lim 2 +3 2 9 (2) lim 3 3 2 9 (4) lim ( ) 2 3 +3 (5) lim 2 9 (6) lim + (7) lim (8) lim (9) lim (0) lim 2 3 + 3 9 2 2 +3 () lim sin 2 sin 2 (2) lim +3 () lim 2 2 9 = 5 5 = 3 (2) lim
. ev=,604k m 3 Debye ɛ 0 kt e λ D = n e n e Ze 4 ln Λ ν ei = 5.6π / ɛ 0 m/ e kt e /3 ν ei v e H + +e H ev Saha x x = 3/ πme kt g i g e n
003...............................3 Debye................. 3.4................ 3 3 3 3. Larmor Cyclotron... 3 3................ 4 3.3.......... 4 3.3............ 4 3.3...... 4 3.3.3............ 5 3.4.........
ŠéŒØ‘÷†u…x…C…W…A…fi…l…b…g…‘†[…NfiüŒå†v(fl|ŁŠ−Ù) 4. −mŠ¦fiI’—Ÿ_ 4.1 −mŠ¦ŁªŁz‡Ì„v”Z
( ) 4. 4.1 2009 1 14 ( ) ( ) 4. 2009 14.1 14 ( ) 1 / 41 1 2 3 4 5 4.1 ( ) 4. 2009 14.1 14 ( ) 2 / 41 X i (Ω)
TOP URL 1
TOP URL http://amonphys.web.fc.com/ 3.............................. 3.............................. 4.3 4................... 5.4........................ 6.5........................ 8.6...........................7
30 (11/04 )
30 (11/04 ) i, 1,, II I?,,,,,,,,, ( ),,, ϵ δ,,,,, (, ),,,,,, 5 : (1) ( ) () (,, ) (3) ( ) (4) (5) ( ) (1),, (),,, () (3), (),, (4), (1), (3), ( ), (5),,,,,,,, ii,,,,,,,, Richard P. Feynman, The best teaching
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
CG38.PDF
............3...3...6....6....8.....8.....4...9 3....9 3.... 3.3...4 3.4...36...39 4....39 4.....39 4.....4 4....49 4.....5 4.....57...64 5....64 5....66 5.3...68 5.4...7 5.5...77...8 6....8 6.....8 6.....83
II 1 II 2012 II Gauss-Bonnet II
II 1 II 212 II Gauss-Bonnet II 1 1 1.1......................................... 1 1.2............................................ 2 1.3.................................. 3 1.4.............................................
2009 I 2 II III 14, 15, α β α β l 0 l l l l γ (1) γ = αβ (2) α β n n cos 2k n n π sin 2k n π k=1 k=1 3. a 0, a 1,..., a n α a
009 I II III 4, 5, 6 4 30. 0 α β α β l 0 l l l l γ ) γ αβ ) α β. n n cos k n n π sin k n π k k 3. a 0, a,..., a n α a 0 + a x + a x + + a n x n 0 ᾱ 4. [a, b] f y fx) y x 5. ) Arcsin 4) Arccos ) ) Arcsin
Gmech08.dvi
145 13 13.1 13.1.1 0 m mg S 13.1 F 13.1 F /m S F F 13.1 F mg S F F mg 13.1: m d2 r 2 = F + F = 0 (13.1) 146 13 F = F (13.2) S S S S S P r S P r r = r 0 + r (13.3) r 0 S S m d2 r 2 = F (13.4) (13.3) d 2
S I. dy fx x fx y fx + C 3 C dy fx 4 x, y dy v C xt y C v e kt k > xt yt gt [ v dt dt v e kt xt v e kt + C k x v + C C k xt v k 3 r r + dr e kt S dt d
S I.. http://ayapin.film.s.dendai.ac.jp/~matuda /TeX/lecture.html PDF PS.................................... 3.3.................... 9.4................5.............. 3 5. Laplace................. 5....