Carter Wegman[8] [1] error-correctiong code[9] [6] [14]( ) Impagliazzo,Levin,Luby [17] leftover hash lemma ( leftover hash lemma Impagliazzo Zu

Save this PDF as:
 WORD  PNG  TXT  JPG

Size: px
Start display at page:

Download "1 1979 Carter Wegman[8] [1] error-correctiong code[9] [6] [14]( ) Impagliazzo,Levin,Luby [17] leftover hash lemma ( leftover hash lemma Impagliazzo Zu"

Transcription

1 Leftover Hash Lemma M1 Universal hash families and the leftover hash lemma, and applications to cryptography and computing D.R.Stinson Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario, NL 3G1, Canada January 15, 00 1

2 Carter Wegman[8] [1] error-correctiong code[9] [6] [14]( ) Impagliazzo,Levin,Luby [17] leftover hash lemma ( leftover hash lemma Impagliazzo Zuckerman [16]) smoothing entropy theorem extractor δ- leftover hash lemma leftover hash lemma 8 BPP extractor 9 10 (D; N, M) X = N Y = M f F f : X Y D F

3 (D; N, M)- F δ-universal x 1, x X f(x 1 ) = f(x ) f F δd δ collision probability δuniversal δ-u (D; N, M)- F strongly universal x 1, x X y 1, y Y ( ) {f F : f(x i ) = y i, i = 1, } = D M. strongly universal SU (D; N, M)- F F X M D N f x f(x) f F x X A(F) F array representation F δ -U(D; N, M) A(F) A(F) δd Y q (n, K, d, q)code C d Y n K codewords C linear q Y = F q C (F q ) n k = log q K dimension [n, k, d, q]code Bierbrauer,Johansson,Kabatianskii,Smeets [7].1. (n, K, d, q)code 1 d -U(n; K, q) n δ-u(d; N, M) (D, N, D(1 δ), M)code.1 F cordwords A(F) U(3; 9, 3) {f i : i Z 3 } (3, 9,, 3)code (0, 0) (0, 1) (0, ) (1, 0) (1, 1) (1, ) (, 0) (, 1) (, ) f 0 : f 1 : f : orthogonal array OA λ (N, M) λ M N λm F SU(D; N, M)- λ = D/M A(F) OA λ (N, M) ([5]) 3

4 .. SU(D; N, M)-λ = D/M OA λ (N, M).. SU(9; 3, 3)- {f i,j : i, j Z 3 } OA 1 (3, 3) 0 1 f 0,0 : f 0,1 : 1 f 0, : 0 0 f 1,0 : f 1,1 : 1 f 1, : 0 0 f,0 : f,1 : 1 f, : orthogonal arrays 1947 Rao [4] 3.1. l q X (F q ) l F q r (F q ) l f r:x Fq f r ( x) = r x. F(q, l, X) = f r : r (F q ) l. F(q, l, X) SU(q l ; X, q)-. (q l ; X, q)- SU x 1, x (F q ) l ( x 1 x ) y 1, y F q r x 1 = y 1 r x = y. r (F q ) l x 1 x F q r = (r 1,, r l ) r 1,, r l l F q r q l SU 4

5 q 3.1. q a, b F q f a,b : F q F q f a,b (x) = ax + b. {f a,b : a, b F q } SU(q ; q, q)-. l = X = F q {1} [18] 3.. l q X = {0, 1} l \ {(0,, 0)} r (F q ) l f r : X F q f r ( x) = r x. {f r : r (F q ) l } SU(q l ; l 1, q)- SU [10] 3.. q a, b F q f a,b : F q f a,b (x) = (x + a) + b. {f a,b : a, b F q } SU(q ; q, q)-. (q ; q, q)- SU x 1, x (F q ) l ( x 1 x ) y 1, y F q (x 1 + a) + b = y 1 (x + a) + b = y. (a, b) (F q ) a a = y 1 y (x 1 x ) x 1 + x a b 3. q. SU(9; 3, 3) 3..1 δ-u [7] 5

6 3.3. q a 1 k q 1 a F q f a : (F q ) k F q k 1 f a (x 0,, x k 1 ) = x 0 + x i a i. {f a F q } k 1-U(q; q qk, q). (q; q k, q) k 1 -U q (x 0,, x k 1 ), (x 0,, x k 1) (F q ) k k 1 k 1 x i a i = x ia i a F q i=0 i=0 k 1 (x i x i)a i = 0 i=0 i=1 F q k 1 k 1 a k 1 k 1-U q [6] Bose Bush[15] q a s t s, t ϕ : F q s (F q ) t q- x, y F q s ϕ(x + y) = ϕ(x) + ϕ(y) a F q, x F q s ϕ(ax) = aϕ(x) a F q s f a : F q s (F q ) t f a (x) = ϕ(ax) {f a : a F q s} 1 q t -U(q s ; q s, q t ). (q s ; q s, q t ) 1 q t -U x 1, x F q s, x 1 x ϕ(ax 1 ) = ϕ(ax ) a F q ϕ ϕ(a(x 1 x )) = 0 ϕ ker(ϕ) = q s t x 1 x 0 a(x 1 x) ker(ϕ) a q s t 1 q t -U 6

7 [0] δ -U δ 1 -U (δ 1 + δ )-U concatenated coce 3.5. F 1 X Y 1 δ 1 -U(D 1 ; N, M 1 ) F Y 1 Y δ -U(D ; M 1, M ) f 1 F 1,f F f 1 f : X Y f 1 f (x) = f (f 1 (x)) {f 1 f : f 1 F 1, f F } (δ 1 + δ )-U(D 1 D ; N, M ). x, x X f (f 1 (x)) = f (f 1 (x )) (f 1, f ) G = {f 1 F 1 : f 1 (x) = f 1 (x )}. G δ 1 D 1 f 1 G f F f (f 1 (x)) = f (f 1 (x )) f 1 F 1 \ G f 1 (x) f 1 (x ) f 1 F 1 \ G f (f 1 (x)) = f (f 1 (x )) f F δ D f (f 1 (x)) = f (f 1 (x )) (f 1, f ) G D + (D 1 G )δ D G D + D 1 δ D δ 1 D 1 D + D 1 δ D = (δ 1 + δ )D 1 D. (δ 1 + δ )-U F X Y SU(D; N, M) f F x X X p x y = f(x) y f F D, N, M p 7

8 BPV ([18]) 3. p X l 1 l r (Z p ) l f r F(p, l, X) x x f r ( x) BPV α p F p y (y, α y ) BPV y x 0, 1 l r = (r 1,, r l ) (F p ) l y = f r ( x) = r x α r 1,, α r l α y = α r i {i:x i =1} l p F p l Bennett,Brassard,Robert([]) Alice Bob x X Eve X p x Alice Bob p p ( 5.5 ) F X Y δ-u(d; N, M) f F Alice Bob Alice Bob y = f(x) Eve y 9 D, N, M p Eve y 5 F X Y SU(D; N, M), f F x X 8

9 f(x) 5.1 Y p Y (Y, p) Y u Y y Y 1/ Y (Y, p) Y : Y R Y E(Y) E(Y) = y Y p(y)y(y) Y var(y) var(y) = E(Y ) (E(Y)) = E((Y E(Y)) ). p E p (Y) var p (Y) 5.1. ( ) Y Pr[ Y(y) E(Y) ϵ] var(y) ϵ. 5.. ( ) I R Y I f : I R I E(f(Y)) f(e(y)). f(x) = x I = R 5.3. Y (E(Y)) E(Y ). f(x) = log x I = (0, ) 5.4. Y log E(Y) E(log Y). 9

10 5. p, q Y p, q d(p, q) d(p, q) = 1 p(y) q(y). y Y p, q 0 d(p, q) p, q Y max{p(y), q(y)} = d(p, q) + 1 y Y. Y p = {y Y : p(y) q(y)} d(p, q) = 1 (p(y) q(y)) + 1 (q(y) p(y)) y Y p y Y \Y p = 1 p(y) 1 p(y) 1 q(y) + 1 q(y) y Y p y Y \Y p y Y p y Y \Y p ( = 1 p(y) 1 1 ) ( p(y) 1 q(y) ) q(y) y Y p y Y p y Y p y Y p = y Y p p(y) y Y p q(y) max{p(y), q(y)} = p(y) + y Y p y Y q(y) y Y \Y p = p(y) + 1 q(y) (5.1) y Y p y Y p max{p(y), q(y)} = d(p, q) + 1 y Y Y p Y 0 Y p(y 0 ) = y Y 0 p(y). 10

11 5.. p, q Y d(p, q) = max{ p(y 0 ) q(y 0 ) : Y 0 Y } Y p p(y p ) q(y p ) = (p(y) q(y)). y Y p 5.1 y Y p (p(y) q(y)) = d(p, q) p(y p ) q(y p ) = d(p, q) q(y \ Y p ) p(y \ Y p ) = d(p, q) Y 0 Y p(y p ) q(y p ) p(y 0 ) q(y 0 ) Y 0 Y Y 1 = Y 0 Y p Y = Y 0 (Y \ Y p ) p(y 1 ) q(y 1 ) > 0 p(y ) q(y ) < 0 p(y 0 ) q(y 0 ) = p(y 1 ) q(y 1 ) + (p(y ) q(y )) p(y 1 ) q(y 1 ) p(y p ) q(y p ) sincey 1 Y p = p(y p ) q(y p ). q(y 0 ) p(y 0 ) = q(y ) p(y ) + (q(y 1 ) p(y 1 )) q(y ) p(y ) q(y \ Y p ) p(y \ Y p ) sincey Y \ Y p = p(y p ) q(y p ). p(y 0 ) q(y 0 ) p(y p ) q(y p ) {y 1, y, y 3, y 4 } p, q p(y i ) q(y i ) y 1 1/3 1/4 y 1/3 1/4 y 3 1/6 1/4 y 4 1/6 1/4 11

12 3 d(p,q) d(p, q) = = d(p, q) = = 1 6. d(p, q) = p({y 1, y ) q({y 1, y }) = 3 1 = p 0, p 1 Y q Y i 0, 1 y Y p i (y) q(y) = p 0 + p 1 (y) f : Y 0, 1 y Y q i = 0 i = 1 corr(f) f y i f y Y p f(y) (y) p 0 (y) + p 1 (y) corr(f) = y Y p 0 (y) + p 1 (y) p f ( y)(y) p 0 (y) + p 1 (y) = y Y p f( y)(y). y Y i p i (y) y 1 i (y) f f (y) = { 0 ifp 1 < p 0 (y) 1 ifp 1 p 0 (y) 1

13 f corr(f ) = y Y max{p 0 (y), p 1 (y)} = d(p 0, p 1 ) (Y, p 0 ) (Y, p 1 ) f f f, f p 0, p p 0, p 1 Y f : Y 0, 1 E(f p1 ) E(f p0 ) E(f p 1 ) E(f p 1 ) = d(p 0, p 1 ). E(f p 1 ) E(f p 0 ) = d(p 0, p 1 ) E(f p 1 ) = y Y = E(f p 0 ) = f (y)p 1 (y) {y Y :p 1 (y) p 1 (y)} {y Y :p 1 (y) p 0 (y)} 5.1 E(f p 1 ) E(f p 0 ) = d(p 0, p 1 ) E(f p1 ) E(f p0 ) d(p 0, p 1 ) 5. E(f p1 ) E(f p0 ) p 1 (f 1 (1)) p 0 (f 1 (1)) = d(p 0, p 1 ) (Y, p) Y 0 Y ϵ > 0 p Y 0 ϵ p(y 0) Y 0 Y ϵ. p ϵ Y 0 Y p(y 0) Y 0 Y ϵ. u Y (Y 0 ) = Y 0 / Y u Y Y Y p ϵ d(p, u Y ) ϵ 13

14 5.5 (Y, p) p p = y Y (p(y)). p = u Y p 1/ Y Impagliazzo Zuckerman[16] 5.4. (Y, p) p p Y 1/. Y = M p = (p(y)) ( p(y) 1 M y Y ) = p 1 M (Y, u Y ) Y Y(y) = p(y) (1/M) ( ) E(Y) = 1 p 1 = pm 1. M M M 5.3 E(Y) E(Y) = p M 1. M d(p, u Y ) = 1 p(y) 1 M = M E(Y) y Y p M Shannon,Renyi,Min (Y, p) (Y, p) Renyi entropy h Ren (p) h Ren (p) = log p. (Y, p) min entropy h min (p) h min (p) = min{ log p(y) : y Y } = log (max{p(y) : y Y }). 14

15 (Y, p) Shannon entropy h(p) h(p) = y Y p(y) log p(y). u Y h(u Y ) = h Ren (u Y ) = h min (u Y ) = log Y 5.5. (Y, p) h Ren (p)/ h min (p) h Ren (p) h(p). (max{p(y) : y Y }) (p(y)). h Ren (p)/ h min (p) (p(y)) (p(y) max{p(y) : y Y }) = max{p(y) : y Y }. h min (p) h Ren (p) (Y, p) Y Y(y) = p(y) E(Y) = (p(y)) E(log Y) = p(y) log p(y) 5.4 ( log (p(y)) ) p(y) log p(y). h Ren (p) h(p) 4 min entropy Renyi entropy 6 SU SU [5] [13] (X, p) F X Y SU(D; N, M) f F Y q f y Y q f (y) = p(x) x f 1 (y) 15

16 q f f y x X p y Y (F, u F ) χ y f F χ y (f) = q f (y) χ y (f) = D M. f F E(χ y ) = 1 M. (6.1) 6.1. (X, p) F X Y SU(D; N, M) y Y F χ y f F (χ y (f)) = D(1 + (M 1) p) M.. y (f)) f F(χ = ( ) p(x) f F x f 1 (y) = p(x 1 )p(x ) + f F x 1 f 1 (y) x f 1 (y),x x 1 f F = D p(x M 1 )p(x ) + D (p(x)) M x 1 X x X,x x 1 x X ( ) ( ) D D = (1 M p ) + p M = D(1 + (M 1) p). M x 1 f 1 (y) (p(x)) 6.1. p X SU(9; 3, 3) χ 0 16

17 p(0) = 1/ p(1) = 1/4 p() = 1/4 χ 0 1 f 0, f 0, f 0, f 1, f 1, f 1, f, f, f, ( )) (χ0 (f a,b )) = (3 1) (( 1 ) + 14 ) + 14 ) 4 = 6.1 E(χ y ) = 1 + (M 1) p M. (6.) (6.1) (6.) var(χ y ) = E(χ y ) (E(χ y )) = (M 1) p M. Chebyshev ( 5.1) 3 Pr[ χ y (f) E(χ y ) ϵ] (M 1) p ϵ M. χ y (f) E(χ y ) = q f(y) 1 M. q f y χ y (f) E(χ y ) ϵ [13] [14] 6.1. (X, p) F X Y SU(D; N, M) y Y f F q f ϵ y (M 1) p ϵ M. Y 0 Y 17

18 6.. (X, p) F X Y SU(D; N, M) Y 0 Y f F q f ϵ Y 0 Y 0 (M Y 0 ) p ϵ M (X, p) F X Y SU(D; N, M) f F q f ϵ p M(M 1) 4ϵ. y Y q f(y) 1 M < ϵ M d(q f, u Y ) ϵ 5.3 q f ϵ f F y Y q f(y) 1 M < ϵ M p (M 1) (ϵ/m) M = p(m 1) 4ϵ y Y M y Y q f (y) 1 M > ϵ/m p M(M 1)/4ϵ 7 Leftover Hash Lemma leftover hash lemma [17] [3][13][16][11] F Y f F p x X f(x) r leftover hash lemma r r r(f, y) = q f(y) D = χ y(f) D. F δ-u

19 7.1. (X, p) F X Y δ-u(d; N, M) y Y f F χ y (f) = q f (y) (χ y (y)) D(δ + (1 δ) p ). y Y f F 7.1. p X 1 -(4; 4, ) χ 0 χ 1 1 i=0 p(0) = 1/ p(1) = 1/6 p() = 1/6 p(3) = 1/6 χ 0 χ 1 1 f f f f ( 4 (χ i (f j )) = 8 3 = j=0 ( 1 1 ) ( ( ) ( ) ( ) ( ) )) F X Y δ-u(d; N, M) X p r F Y r δ + (1 δ) p. D 7.1. F X Y δ-u(d; N, M) X p r F Y d(u F Y, r) M(δ + (1 δ) ) 1. 8 Extractors F X Y δ-u(d; N, M) X p r 7 F Y d(u F Y, r) < ϵ h Ren (p) k F (k, ϵ)-extractor extractor 19

20 8.1. δ-u(d; N, M) (k, ϵ)-extractor M(δ + k ) 1 ϵ. p = k 7.1 M(δ + (1 δ) k ) 1 M(δ + k ) 1 d(u F Y,r ) < ϵ 4. (k, 1/4)-extractor BBP k /N F X Y δ-u(d; N, M) Y BBP A I problem instance x X A(I, f(x)) f F B(I, x) yes no B [1] [1] A.S.Hedayat, N.J.A. Sloane, and J.Stufken. Orthogonal arrays:theory and applications. Springer-Verlag, [] C.H.Bennett and G.Brassard adn J-M.Robert. Privacy amplification by public discussion. SIMA Journal on Computing, No. 17, pp. 10 9, [3] C.H.Bennett, G.Brassard, C.Crepeau, and U.Maurer. Generalized privacy amplification. IEEE Transactions on Information Theory, No. 41, pp , [4] C.R.Rao. Factorial experiments derivable from combinatorial arrangements of arrays. Journal of the Royal Statistical Society, No. 9, pp , [5] D.R.Stinson. Combinatorial techniques for universal hashing. Journal of Computer and System Sciences, No. 48, pp , [6] D.R.Stinson. On the connections between universal hashing, combinatorial designs and error-correcting codes. Congressus Numerantium, No. 114, pp. 7 7, [7] J.Bierbrauer, T.Johansson, G.Kabatianskill, and B.Smeets. On families of hash functions via geometric codes and concatenation. Lecture Notes in Computer Science, No. 773, pp , [8] J.L.Carter and M.N.Wegman. Universal classes of hash functions. Jounal of Computer and System Sciences, No. 18, pp ,

21 [9] F.J. MacWilliams and N.J.A. Sloane. The theory of error-correctiong codes. North- Holland, [10] M.Etzel, S.Patel, and Z.Ramzan. Square hash:fast message authenticaiton via optimized universal hash functions. Lecture Notes in Computer Science, Vol. CRYPTO 99, No. 1666, pp , [11] M.Luby. Pseudorandomness and cryptographic applications. Princeton University Press, [1] N.Nisan and A.Ta-Shma. Extracting randomness:a survey and new constructions. J. Comput. System Sci, No. 58, pp , [13] O.Goldreich. Modern cryptography, probabilistic proofs and pseudorandomness. [14] P.Nguyen and J.Stern. The hardness of the hidden subset sum problem and its cryptographic application. Lecture Notes in Computer Science, Vol. CRYPTO 99, No. 1666, pp , [15] R.C.Bose and K.A.Bush. Orthogonal arrays of strength two and three. Annals Math.Statistics, No. 3, pp , 195. [16] R.Impagliazzo and D.Zuckerman. How to recycle random bits. In 30th IEEE Symposium on Foundations of Computer Science, pp. 1 4, [17] R.Impagliazzo, L.Levin, and M.Luby. Pseudo-random generation from one-way functions. In 1st ACM Symposium on Theory of Computing, pp. 1 4, [18] V.Boyko, M.Peinado, and R.Venkatesan. Speeding up discrete log and factoring based schemes via precomputation. Lecture Notes in Computer Science, Vol. EUROCRYPT 98, No. 1403, pp. 1 35,

25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52

25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52 26 1 11M15133 25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52 1 2 2 4 2.1.............................. 4 2.2.................................. 5 2.2.1...........................

More information

0 1-4. 1-5. (1) + b = b +, (2) b = b, (3) + 0 =, (4) 1 =, (5) ( + b) + c = + (b + c), (6) ( b) c = (b c), (7) (b + c) = b + c, (8) ( + b)c = c + bc (9

0 1-4. 1-5. (1) + b = b +, (2) b = b, (3) + 0 =, (4) 1 =, (5) ( + b) + c = + (b + c), (6) ( b) c = (b c), (7) (b + c) = b + c, (8) ( + b)c = c + bc (9 1-1. 1, 2, 3, 4, 5, 6, 7,, 100,, 1000, n, m m m n n 0 n, m m n 1-2. 0 m n m n 0 2 = 1.41421356 π = 3.141516 1-3. 1 0 1-4. 1-5. (1) + b = b +, (2) b = b, (3) + 0 =, (4) 1 =, (5) ( + b) + c = + (b + c),

More information

1 1 3 1.1 (Frequecy Tabulatios)................................ 3 1........................................ 8 1.3.....................................

1 1 3 1.1 (Frequecy Tabulatios)................................ 3 1........................................ 8 1.3..................................... 1 1 3 1.1 (Frequecy Tabulatios)................................ 3 1........................................ 8 1.3........................................... 1 17.1................................................

More information

2003/9 Vol. J86 D I No. 9 GA GA [8] [10] GA GA GA SGA GA SGA2 SA TS GA C1: C2: C3: 1 C4: C5: 692

2003/9 Vol. J86 D I No. 9 GA GA [8] [10] GA GA GA SGA GA SGA2 SA TS GA C1: C2: C3: 1 C4: C5: 692 Comparisons of Genetic Algorithms for Timetabling Problems Hiroaki UEDA, Daisuke OUCHI, Kenichi TAKAHASHI, and Tetsuhiro MIYAHARA GA GA GA GA GA SGA GA SGA2SA TS 6 SGA2 GA GA SA 1. GA [1] [12] GA Faculty

More information

(a) 1 (b) 3. Gilbert Pernicka[2] Treibitz Schechner[3] Narasimhan [4] Kim [5] Nayar [6] [7][8][9] 2. X X X [10] [11] L L t L s L = L t + L s

(a) 1 (b) 3. Gilbert Pernicka[2] Treibitz Schechner[3] Narasimhan [4] Kim [5] Nayar [6] [7][8][9] 2. X X X [10] [11] L L t L s L = L t + L s 1 1 1, Extraction of Transmitted Light using Parallel High-frequency Illumination Kenichiro Tanaka 1 Yasuhiro Mukaigawa 1 Yasushi Yagi 1 Abstract: We propose a new sharpening method of transmitted scene

More information

xx/xx Vol. Jxx A No. xx 1 Fig. 1 PAL(Panoramic Annular Lens) PAL(Panoramic Annular Lens) PAL (2) PAL PAL 2 PAL 3 2 PAL 1 PAL 3 PAL PAL 2. 1 PAL

xx/xx Vol. Jxx A No. xx 1 Fig. 1 PAL(Panoramic Annular Lens) PAL(Panoramic Annular Lens) PAL (2) PAL PAL 2 PAL 3 2 PAL 1 PAL 3 PAL PAL 2. 1 PAL PAL On the Precision of 3D Measurement by Stereo PAL Images Hiroyuki HASE,HirofumiKAWAI,FrankEKPAR, Masaaki YONEDA,andJien KATO PAL 3 PAL Panoramic Annular Lens 1985 Greguss PAL 1 PAL PAL 2 3 2 PAL DP

More information

(Basic of Proability Theory). (Probability Spacees ad Radom Variables , (Expectatios, Meas) (Weak Law

(Basic of Proability Theory). (Probability Spacees ad Radom Variables , (Expectatios, Meas) (Weak Law I (Radom Walks ad Percolatios) 3 4 7 ( -2 ) (Preface),.,,,...,,.,,,,.,.,,.,,. (,.) (Basic of Proability Theory). (Probability Spacees ad Radom Variables...............2, (Expectatios, Meas).............................

More information

(4) ω t(x) = 1 ω min Ω ( (I C (y))) min 0 < ω < C A C = 1 (5) ω (5) t transmission map tmap 1 4(a) 2. 3 2. 2 t 4(a) t tmap RGB 2 (a) RGB (A), (B), (C)

(4) ω t(x) = 1 ω min Ω ( (I C (y))) min 0 < ω < C A C = 1 (5) ω (5) t transmission map tmap 1 4(a) 2. 3 2. 2 t 4(a) t tmap RGB 2 (a) RGB (A), (B), (C) (MIRU2011) 2011 7 890 0065 1 21 40 105-6691 1 1 1 731 3194 3 4 1 338 8570 255 346 8524 1836 1 E-mail: {fukumoto,kawasaki}@ibe.kagoshima-u.ac.jp, ryo-f@hiroshima-cu.ac.jp, fukuda@cv.ics.saitama-u.ac.jp,

More information

2 3, 4, 5 6 2. [1] [2] [3]., [4], () [3], [5]. Mel Frequency Cepstral Coefficients (MFCC) [9] Logan [4] MFCC MFCC Flexer [10] Bogdanov2010 [3] [14],,,

2 3, 4, 5 6 2. [1] [2] [3]., [4], () [3], [5]. Mel Frequency Cepstral Coefficients (MFCC) [9] Logan [4] MFCC MFCC Flexer [10] Bogdanov2010 [3] [14],,, DEIM Forum 2016 E1-4 525-8577 1 1-1 E-mail: is0111rs@ed.ritsumei.ac.jp, oku@fc.ritsumei.ac.jp, kawagoe@is.ritsumei.ac.jp 373 1.,, itunes Store 1, Web,., 4,300., [1], [2] [3],,, [4], ( ) [3], [5].,,.,,,,

More information

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

More information

(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 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] = α = α [ α ]

More information

…K…E…X„^…x…C…W…A…fi…l…b…g…‘†[…N‡Ì“‚¢−w‘K‡Ì‹ê™v’«‡É‡Â‡¢‡Ä

…K…E…X„^…x…C…W…A…fi…l…b…g…‘†[…N‡Ì“‚¢−w‘K‡Ì‹ê™v’«‡É‡Â‡¢‡Ä 2009 8 26 1 2 3 ARMA 4 BN 5 BN 6 (Ω, F, µ) Ω: F Ω σ 1 Ω, ϕ F 2 A, B F = A B, A B, A\B F F µ F 1 µ(ϕ) = 0 2 A F = µ(a) 0 3 A, B F, A B = ϕ = µ(a B) = µ(a) + µ(b) µ(ω) = 1 X : µ X : X x 1,, x n X (Ω) x 1,,

More information

福岡大学人文論叢47-3

福岡大学人文論叢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.

More information

[Oc, Proposition 2.1, Theorem 2.4] K X (a) l (b) l (a) (b) X [M3] Huber adic 1 Huber ([Hu1], [Hu2], [Hu3]) adic 1.1 adic A I I A {I n } 0 adic 2

[Oc, Proposition 2.1, Theorem 2.4] K X (a) l (b) l (a) (b) X [M3] Huber adic 1 Huber ([Hu1], [Hu2], [Hu3]) adic 1.1 adic A I I A {I n } 0 adic 2 On the action of the Weil group on the l-adic cohomology of rigid spaces over local fields (Yoichi Mieda) Graduate School of Mathematical Sciences, The University of Tokyo 0 l Galois K F F q l q K, F K,

More information

syuu_2_10_3.dvi

syuu_2_10_3.dvi [1] [1, 2, 3] [1, 4, 5] 6 7 3 (0.66) (0.65) 1 [6] 0 1 1 2 3 2.1................................ 3 2.1.1.................................. 3 2.1.2.................................. 3 2.2...........................

More information

1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4..

1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4.. 2010 8 3 ( ) 1 2 1.1............................................ 3 1.2.................................... 7 1.3........................................... 9 1.4........................................

More information

繝励Μ繝ウ繝

繝励Μ繝ウ繝 2012. January vol.609 2 3 2012. January vol.609 4 5 2012. January vol.609 6 7 2012. January vol.609 8 9 2012. January vol.609 10 11 2012. January vol.609 12 13 2012. January vol.609 14 15 2012. January

More information

8.1 Fubini 8.2 Fubini 9 (0%) 10 (50%) 10.1 10.2 Carathéodory 10.3 Fubini 1 Introduction [1],, [2],, [3],, [4],, [5],, [6],, [7],, [8],, [1, 2, 3] 1980

8.1 Fubini 8.2 Fubini 9 (0%) 10 (50%) 10.1 10.2 Carathéodory 10.3 Fubini 1 Introduction [1],, [2],, [3],, [4],, [5],, [6],, [7],, [8],, [1, 2, 3] 1980 % 100% 1 Introduction 2 (100%) 2.1 2.2 2.3 3 (100%) 3.1 3.2 σ- 4 (100%) 4.1 4.2 5 (100%) 5.1 5.2 5.3 6 (100%) 7 (40%) 8 Fubini (90%) 2006.11.20 1 8.1 Fubini 8.2 Fubini 9 (0%) 10 (50%) 10.1 10.2 Carathéodory

More information

Lyra 2 2 2 X Y X Y ivis Designer Lyra ivisdesigner Lyra ivisdesigner 2 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) (1) (2) (3) (4) (5) Iv Studio [8] 3 (5) (4) (1) (

Lyra 2 2 2 X Y X Y ivis Designer Lyra ivisdesigner Lyra ivisdesigner 2 ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) (1) (2) (3) (4) (5) Iv Studio [8] 3 (5) (4) (1) ( 1,a) 2,b) 2,c) 1. Web [1][2][3][4] [5] 1 2 a) ito@iplab.cs.tsukuba.ac.jp b) misue@cs.tsukuba.ac.jp c) jiro@cs.tsukuba.ac.jp [6] Lyra[5] ivisdesigner[6] [7] 2 Lyra ivisdesigner c 2012 Information Processing

More information

t14.dvi

t14.dvi version 1 1 (Nested Logit IIA(Independence from Irrelevant Alternatives [2004] ( [2004] 2 2 Spence and Owen[1977] X,Y,Z X Y U 2 U(X, Y, Z X Y X Y Spence and Owen Spence and Owen p X, p Y X Y X Y p Y p

More information

0 1 0 *1 A4 A4 1. 2. 3. 4. 5. 6. *1

0 1 0 *1 A4 A4 1. 2. 3. 4. 5. 6. *1 2011 11 7 0 1 1 2 2 2 3 2 4 2 4.1................................ 2 4.2.............................................. 3 4.3................................................ 4 4.4...............................................

More information

untitled

untitled 13 50 15 6.0 0.25 220 23 92 960 16 16 3.9 3.9 12.8 83.3 7 10 1150 90 1035 1981 1850 4700 4700 15 15 1150 1150 10 12 31 1.5 3.7%(224 ) 1.0 1.5 25.4%(1522 ) 0.7 30.6 1835 ) 0.7 1.0 40.3 (2421 ) 7.3

More information

258 5) GPS 1 GPS 6) GPS DP 7) 8) 10) GPS GPS 2 3 4 5 2. 2.1 3 1) GPS Global Positioning System

258 5) GPS 1 GPS 6) GPS DP 7) 8) 10) GPS GPS 2 3 4 5 2. 2.1 3 1) GPS Global Positioning System Vol. 52 No. 1 257 268 (Jan. 2011) 1 2, 1 1 measurement. In this paper, a dynamic road map making system is proposed. The proposition system uses probe-cars which has an in-vehicle camera and a GPS receiver.

More information

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

More information

082_rev2_utf8.pdf

082_rev2_utf8.pdf 3 1. 2. 3. 4. 5. 1 3 3 3 2008 3 2008 2008 3 2008 2008, 1 5 Lo and MacKinlay (1990a) de Jong and Nijman (1997) Cohen et al. (1983) Lo and MacKinlay (1990a b) Cohen et al. (1983) de Jong and Nijman (1997)

More information

OS Windows Vista Windows XP PowerPoint2003 Word2003 (a Test No. OS 1 Windows Vista PPT2003 2 Windows Vista Word2003 3 Windows XP PPT2003 4 Windows XP

OS Windows Vista Windows XP PowerPoint2003 Word2003 (a Test No. OS 1 Windows Vista PPT2003 2 Windows Vista Word2003 3 Windows XP PPT2003 4 Windows XP C ommunication In embedded softwares, designing a test process that considers how to perform tests in an efficient way, has been an important problem in a whole development process. By the software test,

More information

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

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,

More information

June 2016 i (statistics) F Excel Numbers, OpenOffice/LibreOffice Calc ii *1 VAR STDEV 1 SPSS SAS R *2 R R R R *1 Excel, Numbers, Microsoft Office, Apple iwork, *2 R GNU GNU R iii URL http://ruby.kyoto-wu.ac.jp/statistics/training/

More information

Vol. 23 No. 4 Oct. 2006 37 2 Kitchen of the Future 1 Kitchen of the Future 1 1 Kitchen of the Future LCD [7], [8] (Kitchen of the Future ) WWW [7], [3

Vol. 23 No. 4 Oct. 2006 37 2 Kitchen of the Future 1 Kitchen of the Future 1 1 Kitchen of the Future LCD [7], [8] (Kitchen of the Future ) WWW [7], [3 36 Kitchen of the Future: Kitchen of the Future Kitchen of the Future A kitchen is a place of food production, education, and communication. As it is more active place than other parts of a house, there

More information

1 4 2 4 3 5 4? 7 5 9 6 10 7 11 8 13 9 16 10 17 11 19 12 20 13 21 2

1 4 2 4 3 5 4? 7 5 9 6 10 7 11 8 13 9 16 10 17 11 19 12 20 13 21 2 78-2 (2002) p.172-193 1 1 4 2 4 3 5 4? 7 5 9 6 10 7 11 8 13 9 16 10 17 11 19 12 20 13 21 2 ( ) ( )? 3 1 N i p i log p i i p i log p i i N i q i N i p i log q i N i p i { ( log q i ) ( log p i ) } = N i

More information

Part. 4. () 4.. () 4.. 3 5. 5 5.. 5 5.. 6 5.3. 7 Part 3. 8 6. 8 6.. 8 6.. 8 7. 8 7.. 8 7.. 3 8. 3 9., 34 9.. 34 9.. 37 9.3. 39. 4.. 4.. 43. 46.. 46..

Part. 4. () 4.. () 4.. 3 5. 5 5.. 5 5.. 6 5.3. 7 Part 3. 8 6. 8 6.. 8 6.. 8 7. 8 7.. 8 7.. 3 8. 3 9., 34 9.. 34 9.. 37 9.3. 39. 4.. 4.. 43. 46.. 46.. Cotets 6 6 : 6 6 6 6 6 6 7 7 7 Part. 8. 8.. 8.. 9..... 3. 3 3.. 3 3.. 7 3.3. 8 Part. 4. () 4.. () 4.. 3 5. 5 5.. 5 5.. 6 5.3. 7 Part 3. 8 6. 8 6.. 8 6.. 8 7. 8 7.. 8 7.. 3 8. 3 9., 34 9.. 34 9.. 37 9.3.

More information

untitled

untitled 10 log 10 W W 10 L W = 10 log 10 W 10 12 10 log 10 I I 0 I 0 =10 12 I = P2 ρc = ρcv2 L p = 10 log 10 p 2 p 0 2 = 20 log 10 p p = 20 log p 10 0 2 10 5 L 3 = 10 log 10 10 L 1 /10 +10 L 2 ( /10 ) L 1 =10

More information

1) (AI) 5G AI AI Google IT Deep Learning RWC (RWCP) RWC Web RWCP [1] 2. RWC ETL-Mark I, II (1952, 1955) (ETL) (ETL-Mark

1) (AI) 5G AI AI Google IT Deep Learning RWC (RWCP) RWC Web RWCP [1] 2. RWC ETL-Mark I, II (1952, 1955) (ETL) (ETL-Mark RWC 10 RWC 1992 4 2001 13 RWC 21 RWC 1. RWC (Real World Computing ) (1982 1992 ) 3 1992 2001 10 21 RWCP 5 1992 1996 5 1997 2001 RWC (RWI) (PDC) 2 RWC (5G) 1 1) (AI) 5G AI AI Google IT Deep Learning RWC

More information

6_27.dvi

6_27.dvi Vol. 49 No. 6 1932 1941 (June 2008) RFID 1 2 RFID RFID RFID 13.56 MHz RFID A Experimental Study for Measuring Human Activities in A Bathroom Using RFID Ryo Onishi 1 and Shigeyuki Hirai 2 A bathroom is

More information

金融機関の資産取引ネットワーク

金融機関の資産取引ネットワーク 103-8660 30 2003 7 30 e-mail: inaoka@eri.u-tokyo.ac.jp e-mail: takuto.ninomiya@boj.or.jp e-mail: ken.taniguchi@boj.or.jp e-mail: tokiko.shimizu@boj.or.jp e-mail: takayasu@csl.sony.co.jp * 2 1 2 1 2 Barabási

More information

1 2 2005 1983 1 ()1984 2 1947 1950 19791996 1

1 2 2005 1983 1 ()1984 2 1947 1950 19791996 1 KEO Discussion Paper No.104 19451947 * ** 2006 11 19451947 * ** 1 2 2005 1983 1 ()1984 2 1947 1950 19791996 1 4 A A A A A 3 3 1990 19952003A2003B 4 2 198719941997 1995 1995 3 5 6 1998: 30 40 19701992 7

More information

F8302D_1目次_160527.doc

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.

More information

日立評論2007年3月号 : ソフトウェア開発への

日立評論2007年3月号 : ソフトウェア開発への Vol.89 No.3 298-299 Application of Statistical Process Control to Software Development Mutsumi Komuro 1 23 1985 ACM IEEE 1 195QC Quality Control 1 2 CMM Capability Maturity Model CMMI Capability Maturity

More information

α = 2 2 α 2 = ( 2) 2 = 2 x = α, y = 2 x, y X 0, X 1.X 2,... x 0 X 0, x 1 X 1, x 2 X 2.. Zorn A, B A B A B A B A B B A A B N 2

α = 2 2 α 2 = ( 2) 2 = 2 x = α, y = 2 x, y X 0, X 1.X 2,... x 0 X 0, x 1 X 1, x 2 X 2.. Zorn A, B A B A B A B A B B A A B N 2 1. 2. 3. 4. 5. 6. 7. 8. N Z 9. Z Q 10. Q R 2 1. 2. 3. 4. Zorn 5. 6. 7. 8. 9. x x x y x, y α = 2 2 α x = y = 2 1 α = 2 2 α 2 = ( 2) 2 = 2 x = α, y = 2 x, y X 0, X 1.X 2,... x 0 X 0, x 1 X 1, x 2 X 2.. Zorn

More information

第86回日本感染症学会総会学術集会後抄録(II)

第86回日本感染症学会総会学術集会後抄録(II) χ μ μ μ μ β β μ μ μ μ β μ μ μ β β β α β β β λ Ι β μ μ β Δ Δ Δ Δ Δ μ μ α φ φ φ α γ φ φ γ φ φ γ γδ φ γδ γ φ φ φ φ φ φ φ φ φ φ φ φ φ α γ γ γ α α α α α γ γ γ γ γ γ γ α γ α γ γ μ μ κ κ α α α β α

More information

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)

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

More information

31 gh gw

31 gh gw 30 31 gh gw 32 33 1406 1421 640 0 (mm) (mm) MAX1513 MIN349 MIN280 MAX900 gh gw 34 gh gh gw gw gh gh gw gw gh gh gw gw 35 175 176 177 178 179 180 181 195 196 197 198 202 203 2 1 L L L2 L2 L2 L 2 2 1 L L

More information

example2_time.eps

example2_time.eps Google (20/08/2 ) ( ) Random Walk & Google Page Rank Agora on Aug. 20 / 67 Introduction ( ) Random Walk & Google Page Rank Agora on Aug. 20 2 / 67 Introduction Google ( ) Random Walk & Google Page Rank

More information

Centralizers of Cantor minimal systems

Centralizers of Cantor minimal systems Centralizers of Cantor minimal systems 1 X X X φ (X, φ) (X, φ) φ φ 2 X X X Homeo(X) Homeo(X) φ Homeo(X) x X Orb φ (x) = { φ n (x) ; n Z } x φ x Orb φ (x) X Orb φ (x) x n N 1 φ n (x) = x 1. (X, φ) (i) (X,

More information

4 2 p = p(t, g) (1) r = r(t, g) (2) p r t g p r dp dt = p dg t + p g (3) dt dr dt = r dg t + r g dt 3 p t p g dt p t 3 2 4 r t = 3 4 2 Benefit view dp

4 2 p = p(t, g) (1) r = r(t, g) (2) p r t g p r dp dt = p dg t + p g (3) dt dr dt = r dg t + r g dt 3 p t p g dt p t 3 2 4 r t = 3 4 2 Benefit view dp ( ) 62 1 1 47 2 3 47 2 e-mail:miyazaki@ngu.ac.jp 1 2000 2005 1 4 2 p = p(t, g) (1) r = r(t, g) (2) p r t g p r dp dt = p dg t + p g (3) dt dr dt = r dg t + r g dt 3 p t p g dt p t 3 2 4 r t = 3 4 2 Benefit

More information

4 i

4 i 22 Quantum error correction and its simulation 1135071 2011 3 1 4 i Abstract Quantum error correction and its simulation Hiroko Dehare Researches in quantum information theory and technology, that mix

More information

光学

光学 Fundamentals of Projector-Camera Systems and Their Calibration Methods Takayuki OKATANI To make the images projected by projector s appear as desired, it is e ective and sometimes an only choice to capture

More information

yy yy ;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;; ;;; ;;; ;;; ;;; ;;; ;;; ;;; ;;; ;;; ;;; ;;; ;;; ; ; ; ;; ;; ;; ;;; ;;; ;;; ;; ;; ;; ;; ;; ; ; ; ; ; ; ;

More information

2010 : M0107189 3DCG 3 (3DCG) 3DCG 3DCG 3DCG S

2010 : M0107189 3DCG 3 (3DCG) 3DCG 3DCG 3DCG S 2010 M0107189 2010 : M0107189 3DCG 3 (3DCG) 3DCG 3DCG 3DCG S 1 1 1.1............................ 1 1.2.............................. 4 2 5 2.1............................ 5 2.2.............................

More information

2/ 36 2012 2012 ERATO

2/ 36 2012 2012 ERATO 2013 2 18 1,2 1. 2. JST, ERATO, 2/ 36 2012 2012 ERATO Given n n A 1,..., A N Find P s.t. P A 1 P,..., P A N P A 1 A 2 A N simultaneously P A 1 P P A 2 P P A N P 3/ 36 4/ 36 5/ 36 6/ 36 [Wigner 1931 ].

More information

f (x) f (x) f (x) f (x) f (x) 2 f (x) f (x) f (x) f (x) 2 n f (x) n f (n) (x) dn f f (x) dx n dn dx n D n f (x) n C n C f (x) x = a 1 f (x) x = a x >

f (x) f (x) f (x) f (x) f (x) 2 f (x) f (x) f (x) f (x) 2 n f (x) n f (n) (x) dn f f (x) dx n dn dx n D n f (x) n C n C f (x) x = a 1 f (x) x = a x > 5.1 1. x = a f (x) a x h f (a + h) f (a) h (5.1) h 0 f (x) x = a f +(a) f (a + h) f (a) = lim h +0 h (5.2) x h h 0 f (a) f (a + h) f (a) f (a h) f (a) = lim = lim h 0 h h 0 h (5.3) f (x) x = a f (a) =

More information

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

More information

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

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

More information

1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value D

1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value D P2P 1,a) 1 1 Peer-to-Peer P2P P2P P2P Chord P2P Chord Consideration for Efficient Construction of Distributed Hash Trees on P2P Systems Taihei Higuchi 1,a) Masakazu Soshi 1 Tomoyuki Asaeda 1 Abstract:

More information

Taro13-第6章(まとめ).PDF

Taro13-第6章(まとめ).PDF % % % % % % % % 31 NO 1 52,422 10,431 19.9 10,431 19.9 1,380 2.6 1,039 2.0 33,859 64.6 5,713 10.9 2 8,292 1,591 19.2 1,591 19.2 1,827 22.0 1,782 21.5 1,431 17.3 1,661 20.0 3 1,948 1,541 79.1 1,541 79.1

More information

http://www2.math.kyushu-u.ac.jp/~hara/lectures/lectures-j.html 2 N(ε 1 ) N(ε 2 ) ε 1 ε 2 α ε ε 2 1 n N(ɛ) N ɛ ɛ- (1.1.3) n > N(ɛ) a n α < ɛ n N(ɛ) a n

http://www2.math.kyushu-u.ac.jp/~hara/lectures/lectures-j.html 2 N(ε 1 ) N(ε 2 ) ε 1 ε 2 α ε ε 2 1 n N(ɛ) N ɛ ɛ- (1.1.3) n > N(ɛ) a n α < ɛ n N(ɛ) a n http://www2.math.kyushu-u.ac.jp/~hara/lectures/lectures-j.html 1 1 1.1 ɛ-n 1 ɛ-n lim n a n = α n a n α 2 lim a n = 1 n a k n n k=1 1.1.7 ɛ-n 1.1.1 a n α a n n α lim n a n = α ɛ N(ɛ) n > N(ɛ) a n α < ɛ

More information

34 2 2 h = h/2π 3 V (x) E 4 2 1 ψ = sin kxk = 2π/λ λ = h/p p = h/λ = kh/2π = k h 5 2 ψ = e ax2 ガウス 型 関 数 1.2 1 関 数 値 0.8 0.6 0.4 0.2 0 15 10 5 0 5 10

34 2 2 h = h/2π 3 V (x) E 4 2 1 ψ = sin kxk = 2π/λ λ = h/p p = h/λ = kh/2π = k h 5 2 ψ = e ax2 ガウス 型 関 数 1.2 1 関 数 値 0.8 0.6 0.4 0.2 0 15 10 5 0 5 10 33 2 2.1 2.1.1 x 1 T x T 0 F = ma T ψ) 1 x ψ(x) 2.1.2 1 1 h2 d 2 ψ(x) + V (x)ψ(x) = Eψ(x) (2.1) 2m dx 2 1 34 2 2 h = h/2π 3 V (x) E 4 2 1 ψ = sin kxk = 2π/λ λ = h/p p = h/λ = kh/2π = k h 5 2 ψ = e ax2

More information

,.,.,,. [15],.,.,,., 2003 3 2006 2 3. 2003 3 2004 2 2004 3 2005 2, 1., 2005 3 2006 2, 1., 1,., 1,,., 1. i

,.,.,,. [15],.,.,,., 2003 3 2006 2 3. 2003 3 2004 2 2004 3 2005 2, 1., 2005 3 2006 2, 1., 1,., 1,,., 1. i 200520866 ( ) 19 1 ,.,.,,. [15],.,.,,., 2003 3 2006 2 3. 2003 3 2004 2 2004 3 2005 2, 1., 2005 3 2006 2, 1., 1,., 1,,., 1. i 1 1 1.1..................................... 1 1.2...................................

More information

チュートリアル:ノンパラメトリックベイズ

チュートリアル:ノンパラメトリックベイズ { x,x, L, xn} 2 p( θ, θ, θ, θ, θ, } { 2 3 4 5 θ6 p( p( { x,x, L, N} 2 x { θ, θ2, θ3, θ4, θ5, θ6} K n p( θ θ n N n θ x N + { x,x, L, N} 2 x { θ, θ2, θ3, θ4, θ5, θ6} log p( 6 n logθ F 6 log p( + λ θ F θ

More information

DSGE Dynamic Stochastic General Equilibrium Model DSGE 5 2 DSGE DSGE ω 0 < ω < 1 1 DSGE Blanchard and Kahn VAR 3 MCMC 2 5 4 1 1 1.1 1. 2. 118

DSGE Dynamic Stochastic General Equilibrium Model DSGE 5 2 DSGE DSGE ω 0 < ω < 1 1 DSGE Blanchard and Kahn VAR 3 MCMC 2 5 4 1 1 1.1 1. 2. 118 7 DSGE 2013 3 7 1 118 1.1............................ 118 1.2................................... 123 1.3.............................. 125 1.4..................... 127 1.5...................... 128 1.6..............

More information

5 36 5................................................... 36 5................................................... 36 5.3..............................

5 36 5................................................... 36 5................................................... 36 5.3.............................. 9 8 3............................................. 3.......................................... 4.3............................................ 4 5 3 6 3..................................................

More information

FX ) 2

FX ) 2 (FX) 1 1 2009 12 12 13 2009 1 FX ) 2 1 (FX) 2 1 2 1 2 3 2010 8 FX 1998 1 FX FX 4 1 1 (FX) () () 1998 4 1 100 120 1 100 120 120 100 20 FX 100 100 100 1 100 100 100 1 100 1 100 100 1 100 101 101 100 100

More information

DM

DM ( ) FAX DM DM PR 300 - - - - - - - - - - - - - - - - - - 6 3 1 4 3 - - - - PR P173 FAX (2001) (2000) (1999) 1986 http://kimono-yamato.com/04-kiso/qa.html Q&A http://web.sfc.keio.ac.jp/~t00524sh/chousa/rich/kimonobegin.html

More information

5 5 5 Barnes et al

5 5 5 Barnes et al 11 2014 1 59 72 Ryuichi NAKAMOTO Abstract This paper introduces the method of active learning using case methods. We explain how to apply the method to a lecture in social sciences a field in which application

More information

2 p T, Q

2 p T, Q 270 C, 6000 C, 2 p T, Q p: : p = N/ m 2 N/ m 2 Pa : pdv p S F Q 1 g 1 1 g 1 14.5 C 15.5 1 1 cal = 4.1855 J du = Q pdv U ( ) Q pdv 2 : z = f(x, y). z = f(x, y) (x 0, y 0 ) y y = y 0 z = f(x, y 0 ) x x =

More information

2 36 41 41 42 44 44 1 2 16 17 18 19 20 25 26 27 28 29 4 4.12 32 4.2 4.2.1 36 4.2.2 41 4.2.3 41 4.2.4 42 4.3 4.3.1 44 4.3.2 44 31 1 32 33 < 2 x 1 x x 2 < x 1 x1x 2 x1x 2 34 36 4.2 (1) (4) (1)

More information

B HNS 7)8) HNS ( ( ) 7)8) (SOA) HNS HNS 4) HNS ( ) ( ) 1 TV power, channel, volume power true( ON) false( OFF) boolean channel volume int

B HNS 7)8) HNS ( ( ) 7)8) (SOA) HNS HNS 4) HNS ( ) ( ) 1 TV power, channel, volume power true( ON) false( OFF) boolean channel volume int SOA 1 1 1 1 (HNS) HNS SOA SOA 3 3 A Service-Oriented Platform for Feature Interaction Detection and Resolution in Home Network System Yuhei Yoshimura, 1 Takuya Inada Hiroshi Igaki 1, 1 and Masahide Nakamura

More information

2008 (2008/09/30) 1 ISBN 7 1.1 ISBN................................ 7 1.2.......................... 8 1.3................................ 9 1.4 ISBN.............................. 12 2 13 2.1.....................

More information

ICT a) Caption Presentation Method with Speech Expression Utilizing Speech Bubble Shapes for Video Content Yuko KONYA a) and Itiro SIIO 1. Graduate Sc

ICT a) Caption Presentation Method with Speech Expression Utilizing Speech Bubble Shapes for Video Content Yuko KONYA a) and Itiro SIIO 1. Graduate Sc VOL. J98-A NO. 1 JANUARY 2015 本 PDFの 扱 いは 電 子 情 報 通 信 学 会 著 作 権 規 定 に 従 うこと なお 本 PDFは 研 究 教 育 目 的 ( 非 営 利 )に 限 り 著 者 が 第 三 者 に 直 接 配 布 すること ができる 著 者 以 外 からの 配 布 は 禁 じられている ICT a) Caption Presentation Method

More information

地域総合研究第40巻第1号

地域総合研究第40巻第1号 * abstract This paper attempts to show a method to estimate joint distribution for income and age with copula function. Further, we estimate the joint distribution from National Survey of Family Income

More information

1 1 2 3 2.1.................. 3 2.2.......... 6 3 7 3.1......................... 7 3.1.1 ALAGIN................ 7 3.1.2 (SVM).........................

1 1 2 3 2.1.................. 3 2.2.......... 6 3 7 3.1......................... 7 3.1.1 ALAGIN................ 7 3.1.2 (SVM)......................... [5] Yahoo! Yahoo! (SVM) 3 F 7 7 (SVM) 3 F 6 0 1 1 2 3 2.1.................. 3 2.2.......... 6 3 7 3.1......................... 7 3.1.1 ALAGIN................ 7 3.1.2 (SVM)........................... 8

More information

<4D6963726F736F667420576F7264202D2088E293608E71836C83628367838F815B834E89C28E8B89BB2E646F63>

<4D6963726F736F667420576F7264202D2088E293608E71836C83628367838F815B834E89C28E8B89BB2E646F63> 西 山 慧 子 * 伊 藤 貴 之 ** (*) お 茶 の 水 女 子 大 学 大 学 院 人 間 文 化 研 究 科 (**) お 茶 の 水 女 子 大 学 理 学 部 情 報 科 学 科 E-mail : {nishy, itot}@itol.is.ocha.ac.jp 1. NA [1] A B C E F B,E 1 A, 1 A,B,E B E C,F 1 1 A 2 3 C,F A

More information

2

2 Copyright 2008 Nara Institute of Science and Technology / Osaka University 2 Copyright 2008 Nara Institute of Science and Technology / Osaka University CHAOS Report in US 1994 http://www.standishgroup.com/sample_research/

More information

1 1.1 R (ring) R1 R4 R1 R (commutative [abelian] group) R2 a, b, c R (ab)c = a(bc) (associative law) R3 a, b, c R a(b + c) = ab + ac, (a + b)c = ac +

1 1.1 R (ring) R1 R4 R1 R (commutative [abelian] group) R2 a, b, c R (ab)c = a(bc) (associative law) R3 a, b, c R a(b + c) = ab + ac, (a + b)c = ac + ALGEBRA II Hiroshi SUZUKI Department of Mathematics International Christian University 2004 1 1 1 2 2 1 3 3 1 4 4 1 5 5 1 6 6 1 7 7 1 7.1....................... 7 1 7.2........................... 7 4 8

More information

05-5.dvi

05-5.dvi 131 71 71 71 71 71 71 71 7 1 71 71 71 71 71 7 1 71 71 71 71 71 71 7 1 71 71 71 71 71 71 71 71 7 1 1 71 71 71 71 71 71 71 71 71 7 1 75(468) 1 71 71 7 517.95 1 7.1 7. 1 71 71 71 71 71 71 71 7, 1 7.1 7. 1

More information

(Basics of Proability Theory). (Probability Spacees ad Radom Variables,, (Ω, F, P ),, X,. (Ω, F, P ) (probability space) Ω ( ω Ω ) F ( 2 Ω ) Ω σ (σ-fi

(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).............................

More information