2 HI LO ZDD 2 ZDD 2 HI LO 2 ( ) HI (Zero-suppress ) Zero-suppress ZDD ZDD Zero-suppress 1 ZDD abc a HI b c b Zero-suppress b ZDD ZDD 5) ZDD F 1 F = a
|
|
- なごみ わたぬき
- 5 years ago
- Views:
Transcription
1 ZDD 1, 2 1, 2 1, 2 2 2, 1 #P- Knuth ZDD (Zero-suppressed Binary Decision Diagram) 2 ZDD ZDD ZDD Knuth Knuth ZDD ZDD Path Enumeration Algorithms Using ZDD and Their Performance Evaluations Toshiki Saitoh, 1, 2 Jun Kawahara, 1, 2 Ryo Yoshinaka, 1, 2 Hiromu Suzuki 2 and Shin-ichi Minato 2, 1 The listing of all paths in a given graph is a classical problem. Although there are known algorithms for the problem, the number of the solutions tends to be huge and the counting problem is #P-hard. Recently, Knuth has proposed an algorithm for enumerating paths by using the ZDD (zero-suppressed binary decision diagram). The ZDD is a condensed representation of a family of sets. By identifying a path in a graph as a set of edges, the sets of paths can be represented by ZDD. His algorithm outputs a ZDD representing a set of paths. In this paper, we first introduce Knuth s 1. algorithm, and propose an algorithm where ZDD operations implemented polynomial many times by extending Knuth s algorithm. We experiment with these algorithms and a known enumeration algorithm, and discuss the advantage of the algorithms using ZDD from the experimental result. 2 1),7) 6) #P- NP ZDD (Zero-suppressed Binary Decision Diagram) 4) ZDD VLSI Knuth 3) ZDD 2 Knuth Knuth ZDD ZDD 2. Zero-Suppressed Binary Decision Diagram ZDD 4) 2 ZDD ZDD ZDD 1 1 ERATO 2 1 c 2011 Information Processing Society of Japan
2 2 HI LO ZDD 2 ZDD 2 HI LO 2 ( ) HI (Zero-suppress ) Zero-suppress ZDD ZDD Zero-suppress 1 ZDD abc a HI b c b Zero-suppress b ZDD ZDD 5) ZDD F 1 F = a + ac + b + bc + c + F abc F F + abc F = a + abc + ac + b + bc + c F d F F d c 1 b a c 実線は HI 枝を, 点線は LO 枝を表す {a, b, c, ac, bc} ZDD F = ad + abcd + acd + bcd + bd + cd / F F F/a F = d + bcd + cd % F F F % c F = d 2 F, G ZDD ZDD 3. ZDD G = (V, E) i {1, 2,..., l 1} {v i, v i+1 } E (v 1, v 2,..., v l ) i j v i v j v 1 v l (v 1, v 2,..., v l ) {{v i, v i+1 } i {1,..., l 1}} G = (V, E) 2 s t s t ZDD. ZDD G G e E ZDD s t P ZDD P HI P LO ZDD 1 Knuth 3) Simpath 2 c 2011 Information Processing Society of Japan
3 2 Simpath ZDD 3.1 Simpath Simpath P P 1 P P P e P e Pnew P Pnew P s t Simpath E E P, P E P E \E P P s t P P s t P P Simpath mate mate V mate P j P i j mate[i] = i i 0 i P mate Simpath ZDD ZDD ZDD ZDD ZDD 3) Simpath ZDD mate LO HI N LO HI LO(N) HI(N) Simpath ZDD (1) 1. P := {N 0}, Pnew := /* N 0 */ 2. For each e E do 3. For each N P do 4. N e N HI 5. N e N LO 6. For X = HI, LO do 7. If N X Pnew N then N X := N 8. Else N X Pnew 9. If N X mate 1 s-t then X(N) := 10. Else If N X mate then X(N) := 11. Else X(N) := N X 12. End For 13. End For 14. P := Pnew, Pnew 15. End For 4. N e = {u, v} N mate mate mate[u] = w mate[v] = x mate[x] = w mate[w] = x v x mate[v] = 0 u w mate[u] = 0 9. mate 1 s-t mate[s] = t mate[t] = s mate[i] mate[i] = 0 or i mate 1 s-t HI X(N) := N N HI LO N 10. mate mate (i), (ii) (i) mate (ii) v (v s v t) v 1 (i) mate[u] = v (mate[v] = u) mate[u] = 0 mate[v] = 0 mate (ii) mate[v] = v mate[v] = 0 mate 3 c 2011 Information Processing Society of Japan
4 s 処理済の辺 E a c b P P s e d 未処理の辺 処理済の辺 E a c b e d 未処理の辺 2 a e s b, c d 2 P P 7. mate ( E ) ( E \ E ) ( 2) 2 mate mate mate mate ZDD 3.2 Bottom-up Mate-ZDD Bottom-up Mate-ZDD Mate-ZDD Simpath Simpath mate ( )ZDD Mate-ZDD ZDD ZDD Mate-ZDD ZDD F mate mate[i] = j (j 0) Mate- ZDD t i,j t i,j HI i j Mate-ZDD F F = t 1,1... t n,n ( 1,..., n ) mate ZDD E E P P := {P P E } V F F = F P, P P F P = i,j V, mate[i]=j, i j t i,j e k,l P F P 1 P e 1 P t P mate e k,l. {u, v} w, x V F = F + (F/t u,w/t v,x) e u,v t x,w v v 1 w v F = F % t v,w v F = F/t v,v ZDD F t s,t F = F/t s,t ZDD 4. Mate-ZDD Knuth 3) Simpath Read Tarjan Backtrack 6) ( CyPath 8) ) JapanMap ( ) 46 JapanMap 2 JapanMap 1 CPU AMD Quad-Core Opteron 8393 SE 3.09GHz 512GB JapanMap 2 552,990,153,767,713,569,683,921,601,890,579,271,385,088 Simpath Mate-ZDD 17,036,796 ZDD 2 4 c 2011 Information Processing Society of Japan
5 CyPath Simpath Mate-ZDD ZDD JM > 1000 < 0.01 < JM 2 > JapanMap (JM) JapanMap 2 (JM 2 ) n CyPath Simpath Mate-ZDD ZDD n CyPath Simpath Mate-ZDD ZDD 8 > > > > > n CyPath Simpath Mate-ZDD ZDD n p = n = 15, 16, 17 3 n n n 3, 4 5. Knuth ZDD Simpath Bottom-up Mate-ZDD (CyPath 8) ) ZDD Mate-ZDD Simpath (1) Simpath ZDD Mate-ZDD ZDD (2) Simpath 1 mate t Mate-ZDD 2 ZDD Simpath mate ZDD ZDD ZDD ZDD 1) E.T.Bax. Algorithms to Count Paths and Cycles. Information Processing Letters, 52, pp , ) M.B.Javanbarg, C.Scawthorn, J.Kiyono, and Y.Ono. Minimal Path Sets Seismic Reliability Evaluation of Lifeline Networks with Link and Node Failures. In Proc. Lifeline Earthquake Engineering in a Multihazard Environment. 3) D.Knuth. The Art of Computer Programming, Volume 4, Fascicle 1. 4) S.Minato. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems. In DAC, pp , ) S.Minato. Fast Factorization Method for Implicit Cube Set Representation. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, VOL. 15, No. 4, pp , ) R.C.Read and R.E.Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, 5 c 2011 Information Processing Society of Japan
6 Paths, and Spanning Trees. Networks, 5, pp , ) K.Sekine and H.Imai. Counting the Number of Paths in a Graph via BDDs. IEICE TRANS. FUNDAMENTALS, VOL. E80-A(4), pp , ) T.Uno. CyPath. 6 c 2011 Information Processing Society of Japan
1 Fig. 1 Extraction of motion,.,,, 4,,, 3., 1, 2. 2.,. CHLAC,. 2.1,. (256 ).,., CHLAC. CHLAC, HLAC. 2.3 (HLAC ) r,.,. HLAC. N. 2 HLAC Fig. 2
CHLAC 1 2 3 3,. (CHLAC), 1).,.,, CHLAC,.,. Suspicious Behavior Detection based on CHLAC Method Hideaki Imanishi, 1 Toyohiro Hayashi, 2 Shuichi Enokida 3 and Toshiaki Ejima 3 We have proposed a method for
More informationDPA,, ShareLog 3) 4) 2.2 Strino Strino STRain-based user Interface with tacticle of elastic Natural ObjectsStrino 1 Strino ) PC Log-Log (2007 6)
1 2 1 3 Experimental Evaluation of Convenient Strain Measurement Using a Magnet for Digital Public Art Junghyun Kim, 1 Makoto Iida, 2 Takeshi Naemura 1 and Hiroyuki Ota 3 We present a basic technology
More information258 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 informationIPSJ SIG Technical Report Vol.2012-CG-148 No /8/29 3DCG 1,a) On rigid body animation taking into account the 3D computer graphics came
3DCG 1,a) 2 2 2 2 3 On rigid body animation taking into account the 3D computer graphics camera viewpoint Abstract: In using computer graphics for making games or motion pictures, physics simulation is
More informationA Feasibility Study of Direct-Mapping-Type Parallel Processing Method to Solve Linear Equations in Load Flow Calculations Hiroaki Inayoshi, Non-member
A Feasibility Study of Direct-Mapping-Type Parallel Processing Method to Solve Linear Equations in Load Flow Calculations Hiroaki Inayoshi, Non-member (University of Tsukuba), Yasuharu Ohsawa, Member (Kobe
More information1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The Boston Public Schools system, BPS (Deferred Acceptance system, DA) (Top Trading Cycles system, TTC) cf. [13] [
Vol.2, No.x, April 2015, pp.xx-xx ISSN xxxx-xxxx 2015 4 30 2015 5 25 253-8550 1100 Tel 0467-53-2111( ) Fax 0467-54-3734 http://www.bunkyo.ac.jp/faculty/business/ 1 [1, 2, 3, 4, 5, 8, 9, 10, 12, 15] The
More information,,,,., C Java,,.,,.,., ,,.,, i
24 Development of the programming s learning tool for children be derived from maze 1130353 2013 3 1 ,,,,., C Java,,.,,.,., 1 6 1 2.,,.,, i Abstract Development of the programming s learning tool for children
More informationn 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i
15 Comparison and Evaluation of Dynamic Programming and Genetic Algorithm for a Knapsack Problem 1040277 2004 2 25 n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i Abstract Comparison and
More information23 Study on Generation of Sudoku Problems with Fewer Clues
23 Study on Generation of Sudoku Problems with Fewer Clues 1120254 2012 3 1 9 9 21 18 i Abstract Study on Generation of Sudoku Problems with Fewer Clues Norimasa NASU Sudoku is puzzle a kind of pencil
More informationIPSJ SIG Technical Report Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for
1 2 3 3 1 Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for Mobile Terminals Kaoru Wasai 1 Fumio Sugai 2 Yosihiro Kita 3 Mi RangPark 3 Naonobu
More informationOS 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 information2017 (413812)
2017 (413812) Deep Learning ( NN) 2012 Google ASIC(Application Specific Integrated Circuit: IC) 10 ASIC Deep Learning TPU(Tensor Processing Unit) NN 12 20 30 Abstract Multi-layered neural network(nn) has
More informationInput image Initialize variables Loop for period of oscillation Update height map Make shade image Change property of image Output image Change time L
1,a) 1,b) 1/f β Generation Method of Animation from Pictures with Natural Flicker Abstract: Some methods to create animation automatically from one picture have been proposed. There is a method that gives
More information2 ( ) i
25 Study on Rating System in Multi-player Games with Imperfect Information 1165069 2014 2 28 2 ( ) i ii Abstract Study on Rating System in Multi-player Games with Imperfect Information Shigehiko MORITA
More information4.1 % 7.5 %
2018 (412837) 4.1 % 7.5 % Abstract Recently, various methods for improving computial performance have been proposed. One of these various methods is Multi-core. Multi-core can execute processes in parallel
More informationWeb Web Web Web Web, i
22 Web Research of a Web search support system based on individual sensitivity 1135117 2011 2 14 Web Web Web Web Web, i Abstract Research of a Web search support system based on individual sensitivity
More informationTCP/IP IEEE Bluetooth LAN TCP TCP BEC FEC M T M R M T 2. 2 [5] AODV [4]DSR [3] 1 MS 100m 5 /100m 2 MD 2 c 2009 Information Processing Society of
IEEE802.11 [1]Bluetooth [2] 1 1 (1) [6] Ack (Ack) BEC FEC (BEC) BEC FEC 100 20 BEC FEC 6.19% 14.1% High Throughput and Highly Reliable Transmission in MANET Masaaki Kosugi 1 and Hiroaki Higaki 1 1. LAN
More information12) NP 2 MCI MCI 1 START Simple Triage And Rapid Treatment 3) START MCI c 2010 Information Processing Society of Japan
1 1, 2 1, 2 1 A Proposal of Ambulance Scheduling System Based on Electronic Triage Tag Teruhiro Mizumoto, 1 Weihua Sun, 1, 2 Keiichi Yasumoto 1, 2 and Minoru Ito 1 For effective life-saving in MCI (Mass
More informationID 3) 9 4) 5) ID 2 ID 2 ID 2 Bluetooth ID 2 SRCid1 DSTid2 2 id1 id2 ID SRC DST SRC 2 2 ID 2 2 QR 6) 8) 6) QR QR QR QR
Vol. 51 No. 11 2081 2088 (Nov. 2010) 2 1 1 1 which appended specific characters to the information such as identification to avoid parity check errors, before QR Code encoding with the structured append
More information1 2 4 5 9 10 12 3 6 11 13 14 0 8 7 15 Iteration 0 Iteration 1 1 Iteration 2 Iteration 3 N N N! N 1 MOPT(Merge Optimization) 3) MOPT 8192 2 16384 5 MOP
10000 SFMOPT / / MOPT(Merge OPTimization) MOPT FMOPT(Fast MOPT) FMOPT SFMOPT(Subgrouping FMOPT) SFMOPT 2 8192 31 The Proposal and Evaluation of SFMOPT, a Task Mapping Method for 10000 Tasks Haruka Asano
More information1_26.dvi
C3PV 1,a) 2,b) 2,c) 3,d) 1,e) 2012 4 20, 2012 10 10 C3PV C3PV C3PV 1 Java C3PV 45 38 84% Programming Process Visualization for Supporting Students in Programming Exercise Hiroshi Igaki 1,a) Shun Saito
More information23 Fig. 2: hwmodulev2 3. Reconfigurable HPC 3.1 hw/sw hw/sw hw/sw FPGA PC FPGA PC FPGA HPC FPGA FPGA hw/sw hw/sw hw- Module FPGA hwmodule hw/sw FPGA h
23 FPGA CUDA Performance Comparison of FPGA Array with CUDA on Poisson Equation (lijiang@sekine-lab.ei.tuat.ac.jp), (kazuki@sekine-lab.ei.tuat.ac.jp), (takahashi@sekine-lab.ei.tuat.ac.jp), (tamukoh@cc.tuat.ac.jp),
More informationsoturon.dvi
12 Exploration Method of Various Routes with Genetic Algorithm 1010369 2001 2 5 ( Genetic Algorithm: GA ) GA 2 3 Dijkstra Dijkstra i Abstract Exploration Method of Various Routes with Genetic Algorithm
More information,4) 1 P% P%P=2.5 5%!%! (1) = (2) l l Figure 1 A compilation flow of the proposing sampling based architecture simulation
1 1 1 1 SPEC CPU 2000 EQUAKE 1.6 50 500 A Parallelizing Compiler Cooperative Multicore Architecture Simulator with Changeover Mechanism of Simulation Modes GAKUHO TAGUCHI 1 YOUICHI ABE 1 KEIJI KIMURA 1
More informationQ [4] 2. [3] [5] ϵ- Q Q CO CO [4] Q Q [1] i = X ln n i + C (1) n i i n n i i i n i = n X i i C exploration exploitation [4] Q Q Q ϵ 1 ϵ 3. [3] [5] [4]
1,a) 2,3,b) Q ϵ- 3 4 Q greedy 3 ϵ- 4 ϵ- Comparation of Methods for Choosing Actions in Werewolf Game Agents Tianhe Wang 1,a) Tomoyuki Kaneko 2,3,b) Abstract: Werewolf, also known as Mafia, is a kind of
More informationB 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 informationVol.55 No (Jan. 2014) saccess 6 saccess 7 saccess 2. [3] p.33 * B (A) (B) (C) (D) (E) (F) *1 [3], [4] Web PDF a m
Vol.55 No.1 2 15 (Jan. 2014) 1,a) 2,3,b) 4,3,c) 3,d) 2013 3 18, 2013 10 9 saccess 1 1 saccess saccess Design and Implementation of an Online Tool for Database Education Hiroyuki Nagataki 1,a) Yoshiaki
More informationjohnny-paper2nd.dvi
13 The Rational Trading by Using Economic Fundamentals AOSHIMA Kentaro 14 2 26 ( ) : : : The Rational Trading by Using Economic Fundamentals AOSHIMA Kentaro abstract: Recently Artificial Markets on which
More informationT rank A max{rank Q[R Q, J] t-rank T [R T, C \ J] J C} 2 ([1, p.138, Theorem 4.2.5]) A = ( ) Q rank A = min{ρ(j) γ(j) J J C} C, (5) ρ(j) = rank Q[R Q,
(ver. 4:. 2005-07-27) 1 1.1 (mixed matrix) (layered mixed matrix, LM-matrix) m n A = Q T (2m) (m n) ( ) ( ) Q I m Q à = = (1) T diag [t 1,, t m ] T rank à = m rank A (2) 1.2 [ ] B rank [B C] rank B rank
More informationkut-paper-template.dvi
26 Discrimination of abnormal breath sound by using the features of breath sound 1150313 ,,,,,,,,,,,,, i Abstract Discrimination of abnormal breath sound by using the features of breath sound SATO Ryo
More information12 DCT A Data-Driven Implementation of Shape Adaptive DCT
12 DCT A Data-Driven Implementation of Shape Adaptive DCT 1010431 2001 2 5 DCT MPEG H261,H263 LSI DDMP [1]DDMP MPEG4 DDMP MPEG4 SA-DCT SA-DCT DCT SA-DCT DDMP SA-DCT MPEG4, DDMP,, SA-DCT,, ο i Abstract
More informationFig. 3 Flow diagram of image processing. Black rectangle in the photo indicates the processing area (128 x 32 pixels).
Fig. 1 The scheme of glottal area as a function of time Fig. 3 Flow diagram of image processing. Black rectangle in the photo indicates the processing area (128 x 32 pixels). Fig, 4 Parametric representation
More information58 10
57 Multi-channel MAC Protocol with Multi-busytone in Ad-hoc Networks Masatoshi Fukushima*, Ushio Yamamoto* and Yoshikuni Onozato* Abstract Multi-channel MAC protocols for wireless ad hoc networks have
More information25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble
25 II 25 2 6 13:30 16:00 (1),. Do not open this problem boolet until the start of the examination is announced. (2) 3.. Answer the following 3 problems. Use the designated answer sheet for each problem.
More informationIPSJ SIG Technical Report Vol.2014-CG-155 No /6/28 1,a) 1,2,3 1 3,4 CG An Interpolation Method of Different Flow Fields using Polar Inter
,a),2,3 3,4 CG 2 2 2 An Interpolation Method of Different Flow Fields using Polar Interpolation Syuhei Sato,a) Yoshinori Dobashi,2,3 Tsuyoshi Yamamoto Tomoyuki Nishita 3,4 Abstract: Recently, realistic
More informationP2P P2P peer peer P2P peer P2P peer P2P i
26 P2P Proposed a system for the purpose of idle resource utilization of the computer using the P2P 1150373 2015 2 27 P2P P2P peer peer P2P peer P2P peer P2P i Abstract Proposed a system for the purpose
More information1., 1 COOKPAD 2, Web.,,,,,,.,, [1]., 5.,, [2].,,.,.,, 5, [3].,,,.,, [4], 33,.,,.,,.. 2.,, 3.., 4., 5., ,. 1.,,., 2.,. 1,,
THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE.,, 464 8601 470 0393 101 464 8601 E-mail: matsunagah@murase.m.is.nagoya-u.ac.jp, {ide,murase,hirayama}@is.nagoya-u.ac.jp,
More information(a) Picking up of six components (b) Picking up of three simultaneously. components simultaneously. Fig. 2 An example of the simultaneous pickup. 6 /
*1 *1 *1 *2 *2 Optimization of Printed Circuit Board Assembly Prioritizing Simultaneous Pickup in a Placement Machine Toru TSUCHIYA *3, Atsushi YAMASHITA, Toru KANEKO, Yasuhiro KANEKO and Hirokatsu MURAMATSU
More informationPage 1 of 6 B (The World of Mathematics) November 20, 2006 Final Exam 2006 Division: ID#: Name: 1. p, q, r (Let p, q, r are propositions. ) (10pts) (a
Page 1 of 6 B (The World of Mathematics) November 0, 006 Final Exam 006 Division: ID#: Name: 1. p, q, r (Let p, q, r are propositions. ) (a) (Decide whether the following holds by completing the truth
More informationVRSJ-SIG-MR_okada_79dce8c8.pdf
THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. 630-0192 8916-5 E-mail: {kaduya-o,takafumi-t,goshiro,uranishi,miyazaki,kato}@is.naist.jp,.,,.,,,.,,., CG.,,,
More information第62巻 第1号 平成24年4月/石こうを用いた木材ペレット
Bulletin of Japan Association for Fire Science and Engineering Vol. 62. No. 1 (2012) Development of Two-Dimensional Simple Simulation Model and Evaluation of Discharge Ability for Water Discharge of Firefighting
More informationDTN DTN DTN DTN i
28 DTN Proposal of the Aggregation Message Ferrying for Evacuee s Data Delivery in DTN Environment 1170302 2017 2 28 DTN DTN DTN DTN i Abstract Proposal of the Aggregation Message Ferrying for Evacuee
More informationVol. 42 No. SIG 8(TOD 10) July HTML 100 Development of Authoring and Delivery System for Synchronized Contents and Experiment on High Spe
Vol. 42 No. SIG 8(TOD 10) July 2001 1 2 3 4 HTML 100 Development of Authoring and Delivery System for Synchronized Contents and Experiment on High Speed Networks Yutaka Kidawara, 1 Tomoaki Kawaguchi, 2
More informationフカシギおねえさん問題の高速計算アルゴリズム
JST ERATO 2013/7/26 Joint work with 1 / 37 1 2 3 4 5 6 2 / 37 1 2 3 4 5 6 3 / 37 : 4 / 37 9 9 6 10 10 25 5 / 37 9 9 6 10 10 25 Bousquet-Mélou (2005) 19 19 3 1GHz Alpha 8 Iwashita (Sep 2012) 21 21 3 2.67GHz
More information1,a) 1,b) TUBSTAP TUBSTAP Offering New Benchmark Maps for Turn Based Strategy Game Tomihiro Kimura 1,a) Kokolo Ikeda 1,b) Abstract: Tsume-shogi and Ts
JAIST Reposi https://dspace.j Title ターン制戦略ゲームにおけるベンチマークマップの提 案 Author(s) 木村, 富宏 ; 池田, 心 Citation ゲームプログラミングワークショップ 2016 論文集, 2016: 36-43 Issue Date 2016-10-28 Type Conference Paper Text version author
More information& Vol.5 No (Oct. 2015) TV 1,2,a) , Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Ro
TV 1,2,a) 1 2 2015 1 26, 2015 5 21 Augmented TV TV AR Augmented Reality 3DCG TV Estimation of TV Screen Position and Rotation Using Mobile Device Hiroyuki Kawakita 1,2,a) Toshio Nakagawa 1 Makoto Sato
More informationMhij =zhij... (2) Đhij {1, 2,...,lMhij}... (3)
An Autonomous Decentralized Algorithm for a Large Scale Scheduling Problem Approach Based on Backward Scheduling Ichimi Norihisa, Non-member (Toshiba Corporation), lima Hitoshi, Member, Sannomiya Nobuo,
More information1 1 tf-idf tf-idf i
14 A Method of Article Retrieval Utilizing Characteristics in Newspaper Articles 1055104 2003 1 31 1 1 tf-idf tf-idf i Abstract A Method of Article Retrieval Utilizing Characteristics in Newspaper Articles
More information4. C i k = 2 k-means C 1 i, C 2 i 5. C i x i p [ f(θ i ; x) = (2π) p 2 Vi 1 2 exp (x µ ] i) t V 1 i (x µ i ) 2 BIC BIC = 2 log L( ˆθ i ; x i C i ) + q
x-means 1 2 2 x-means, x-means k-means Bayesian Information Criterion BIC Watershed x-means Moving Object Extraction Using the Number of Clusters Determined by X-means Clustering Naoki Kubo, 1 Kousuke
More information[2] OCR [3], [4] [5] [6] [4], [7] [8], [9] 1 [10] Fig. 1 Current arrangement and size of ruby. 2 Fig. 2 Typography combined with printing
1,a) 1,b) 1,c) 2012 11 8 2012 12 18, 2013 1 27 WEB Ruby Removal Filters Using Genetic Programming for Early-modern Japanese Printed Books Taeka Awazu 1,a) Masami Takata 1,b) Kazuki Joe 1,c) Received: November
More informationIPSJ SIG Technical Report Vol.2009-DPS-141 No.23 Vol.2009-GN-73 No.23 Vol.2009-EIP-46 No /11/27 t-room t-room 2 Development of
t-room 1 2 2 2 2 1 1 2 t-room 2 Development of Assistant System for Ensemble in t-room Yosuke Irie, 1 Shigemi Aoyagi, 2 Toshihiro Takada, 2 Keiji Hirata, 2 Katsuhiko Kaji, 2 Shigeru Katagiri 1 and Miho
More informationBulletin of JSSAC(2014) Vol. 20, No. 2, pp (Received 2013/11/27 Revised 2014/3/27 Accepted 2014/5/26) It is known that some of number puzzles ca
Bulletin of JSSAC(2014) Vol. 20, No. 2, pp. 3-22 (Received 2013/11/27 Revised 2014/3/27 Accepted 2014/5/26) It is known that some of number puzzles can be solved by using Gröbner bases. In this paper,
More information1 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 informationIPSJ SIG Technical Report Vol.2012-HCI-149 No /7/20 1 1,2 1 (HMD: Head Mounted Display) HMD HMD,,,, An Information Presentation Method for Weara
1 1,2 1 (: Head Mounted Display),,,, An Information Presentation Method for Wearable Displays Considering Surrounding Conditions in Wearable Computing Environments Masayuki Nakao 1 Tsutomu Terada 1,2 Masahiko
More information[2] 2. [3 5] 3D [6 8] Morishima [9] N n 24 24FPS k k = 1, 2,..., N i i = 1, 2,..., n Algorithm 1 N io user-specified number of inbetween omis
1,a) 2 2 2 1 2 3 24 Motion Frame Omission for Cartoon-like Effects Abstract: Limited animation is a hand-drawn animation style that holds each drawing for two or three successive frames to make up 24 frames
More informationCore1 FabScalar VerilogHDL Cache Cache FabScalar 1 CoreConnect[2] Wishbone[3] AMBA[4] AMBA 1 AMBA ARM L2 AMBA2.0 AMBA2.0 FabScalar AHB APB AHB AMBA2.0
AMBA 1 1 1 1 FabScalar FabScalar AMBA AMBA FutureBus Improvement of AMBA Bus Frame-work for Heterogeneos Multi-processor Seto Yusuke 1 Takahiro Sasaki 1 Kazuhiko Ohno 1 Toshio Kondo 1 Abstract: The demand
More information189 2015 1 80
189 2015 1 A Design and Implementation of the Digital Annotation Basis on an Image Resource for a Touch Operation TSUDA Mitsuhiro 79 189 2015 1 80 81 189 2015 1 82 83 189 2015 1 84 85 189 2015 1 86 87
More information1: A/B/C/D Fig. 1 Modeling Based on Difference in Agitation Method artisoc[7] A D 2017 Information Processing
1,a) 2,b) 3 Modeling of Agitation Method in Automatic Mahjong Table using Multi-Agent Simulation Hiroyasu Ide 1,a) Takashi Okuda 2,b) Abstract: Automatic mahjong table refers to mahjong table which automatically
More informationIPSJ SIG Technical Report Vol.2017-ARC-225 No.12 Vol.2017-SLDM-179 No.12 Vol.2017-EMB-44 No /3/9 1 1 RTOS DefensiveZone DefensiveZone MPU RTOS
1 1 RTOS DefensiveZone DefensiveZone MPU RTOS RTOS OS Lightweight partitioning architecture for automotive systems Suzuki Takehito 1 Honda Shinya 1 Abstract: Partitioning using protection RTOS has high
More informationuntitled
c NUMA 1. 18 (Moore s law) 1Hz CPU 2. 1 (Register) (RAM) Level 1 (L1) L2 L3 L4 TLB (translation look-aside buffer) (OS) TLB TLB 3. NUMA NUMA (Non-uniform memory access) 819 0395 744 1 2014 10 Copyright
More information日本感性工学会論文誌
pp.343-351 2013 Changes in Three Attributes of Color by Reproduction of Memorized Colors Hiroaki MIYAKE, Takeshi KINOSHITA and Atsushi OSA Graduate School of Science and Engineering, Yamaguchi University,
More information6_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 informationHPC pdf
GPU 1 1 2 2 1 1024 3 GPUGraphics Unit1024 3 GPU GPU GPU GPU 1024 3 Tesla S1070-400 1 GPU 2.6 Accelerating Out-of-core Cone Beam Reconstruction Using GPU Yusuke Okitsu, 1 Fumihiko Ino, 1 Taketo Kishi, 2
More information知能と情報, Vol.30, No.5, pp
1, Adobe Illustrator Photoshop [1] [2] [3] Initital Values Assignment of Parameters Using Onomatopoieas for Interactive Design Tool Tsuyoshi NAKAMURA, Yuki SAWAMURA, Masayoshi KANOH, and Koji YAMADA Graduate
More informationVol. 48 No. 3 Mar PM PM PMBOK PM PM PM PM PM A Proposal and Its Demonstration of Developing System for Project Managers through University-Indus
Vol. 48 No. 3 Mar. 2007 PM PM PMBOK PM PM PM PM PM A Proposal and Its Demonstration of Developing System for Project Managers through University-Industry Collaboration Yoshiaki Matsuzawa and Hajime Ohiwa
More informationPowerPoint Presentation
ビッグデータ分析技術ワークショップ ~ 大規模グラフマイニング技術と応用 ~ JST ERATO 湊離散構造処理系プロジェクトの成果とその後の取り組み 平成 29 年 3 月 5 日 湊真一 ( 北海道大学情報科学研究科 ) Introduction of speaker Shin-ichi Minato, Prof. of Hokkaido Univ., Sapporo, Japan. Worked
More informationTsuken Technical Information 1
March 2004 Vol.6 Tsuken Technical Information 1 Since microprocessors (MPUs) first appeared in the 1970s, they have developed at a remarkable pace, and now found in a huge range of devices that we use
More information修士論文
27 Mobile Ad Hoc Networks An Ant-based Routing Algorithm with Multi-phase Pheromone and Power-saving in Mobile Ad Hoc Networks 14T0013 Shohei Miyashita E-mail: shohei.miyashita.4j@stu.hosei.ac.jp : Abstract
More information7 July 005 n SSP n n SSP SSP SSP n n. Selected Sequence-PairSSP. Sequence-PairSeq-Pair sequence-pair ) seq-pair n Γ + Γ (Γ + ;Γ ) n (n!) Γ + (i) Γ + i
Vol. 6 No. 7 July 005 Selected Sequence-Pair n n sequence-pair n n selected sequence-pair sequence-pair Simulated Annealing selected sequence-pair An Efficient MOVE Operation for Selected Sequence-Pair
More information1 Table 1: Identification by color of voxel Voxel Mode of expression Nothing Other 1 Orange 2 Blue 3 Yellow 4 SSL Humanoid SSL-Vision 3 3 [, 21] 8 325
社団法人人工知能学会 Japanese Society for Artificial Intelligence 人工知能学会研究会資料 JSAI Technical Report SIG-Challenge-B3 (5/5) RoboCup SSL Humanoid A Proposal and its Application of Color Voxel Server for RoboCup SSL
More information1 # include < stdio.h> 2 # include < string.h> 3 4 int main (){ 5 char str [222]; 6 scanf ("%s", str ); 7 int n= strlen ( str ); 8 for ( int i=n -2; i
ABC066 / ARC077 writer: nuip 2017 7 1 For International Readers: English editorial starts from page 8. A : ringring a + b b + c a + c a, b, c a + b + c 1 # include < stdio.h> 2 3 int main (){ 4 int a,
More informationEQUIVALENT TRANSFORMATION TECHNIQUE FOR ISLANDING DETECTION METHODS OF SYNCHRONOUS GENERATOR -REACTIVE POWER PERTURBATION METHODS USING AVR OR SVC- Ju
EQUIVALENT TRANSFORMATION TECHNIQUE FOR ISLANDING DETECTION METHODS OF SYNCHRONOUS GENERATOR -REACTIVE POWER PERTURBATION METHODS USING AVR OR SVC- Jun Motohashi, Member, Takashi Ichinose, Member (Tokyo
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
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 information28 Horizontal angle correction using straight line detection in an equirectangular image
28 Horizontal angle correction using straight line detection in an equirectangular image 1170283 2017 3 1 2 i Abstract Horizontal angle correction using straight line detection in an equirectangular image
More informationVol. 48 No. 4 Apr LAN TCP/IP LAN TCP/IP 1 PC TCP/IP 1 PC User-mode Linux 12 Development of a System to Visualize Computer Network Behavior for L
Vol. 48 No. 4 Apr. 2007 LAN TCP/IP LAN TCP/IP 1 PC TCP/IP 1 PC User-mode Linux 12 Development of a System to Visualize Computer Network Behavior for Learning to Associate LAN Construction Skills with TCP/IP
More informationIPSJ SIG Technical Report Vol.2015-CVIM-196 No /3/6 1,a) 1,b) 1,c) U,,,, The Camera Position Alignment on a Gimbal Head for Fixed Viewpoint Swi
1,a) 1,b) 1,c) U,,,, The Camera Position Alignment on a Gimbal Head for Fixed Viewpoint Swiveling using a Misalignment Model Abstract: When the camera sets on a gimbal head as a fixed-view-point, it is
More information2006 [3] Scratch Squeak PEN [4] PenFlowchart 2 3 PenFlowchart 4 PenFlowchart PEN xdncl PEN [5] PEN xdncl DNCL 1 1 [6] 1 PEN Fig. 1 The PEN
PenFlowchart 1,a) 2,b) 3,c) 2015 3 4 2015 5 12, 2015 9 5 PEN & PenFlowchart PEN Evaluation of the Effectiveness of Programming Education with Flowcharts Using PenFlowchart Wataru Nakanishi 1,a) Takeo Tatsumi
More information2. CABAC CABAC CABAC 1 1 CABAC Figure 1 Overview of CABAC 2 DCT 2 0/ /1 CABAC [3] 3. 2 値化部 コンテキスト計算部 2 値算術符号化部 CABAC CABAC
H.264 CABAC 1 1 1 1 1 2, CABAC(Context-based Adaptive Binary Arithmetic Coding) H.264, CABAC, A Parallelization Technology of H.264 CABAC For Real Time Encoder of Moving Picture YUSUKE YATABE 1 HIRONORI
More information3_23.dvi
Vol. 52 No. 3 1234 1244 (Mar. 2011) 1 1 mixi 1 Casual Scheduling Management and Shared System Using Avatar Takashi Yoshino 1 and Takayuki Yamano 1 Conventional scheduling management and shared systems
More informationFig. 3 3 Types considered when detecting pattern violations 9)12) 8)9) 2 5 methodx close C Java C Java 3 Java 1 JDT Core 7) ) S P S
1 1 1 Fig. 1 1 Example of a sequential pattern that is exracted from a set of method definitions. A Defect Detection Method for Object-Oriented Programs using Sequential Pattern Mining Goro YAMADA, 1 Norihiro
More informationエンタープライズサーチ・エンジンQ u i c k S o l u t i o n ® の開発
Development of Enterprise Search Engine QuickSolution by Yoshinori Takenami, Masahiro Kishida and Yasuo Tanabe As document digitization and information sharing increase in enterprises, the volume of information
More informationTable 1. Reluctance equalization design. Fig. 2. Voltage vector of LSynRM. Fig. 4. Analytical model. Table 2. Specifications of analytical models. Fig
Mover Design and Performance Analysis of Linear Synchronous Reluctance Motor with Multi-flux Barrier Masayuki Sanada, Member, Mitsutoshi Asano, Student Member, Shigeo Morimoto, Member, Yoji Takeda, Member
More information& Vol.2 No (Mar. 2012) 1,a) , Bluetooth A Health Management Service by Cell Phones and Its Us
1,a) 1 1 1 1 2 2 2011 8 10, 2011 12 2 1 Bluetooth 36 2 3 10 70 34 A Health Management Service by Cell Phones and Its Usability Evaluation Naofumi Yoshida 1,a) Daigo Matsubara 1 Naoki Ishibashi 1 Nobuo
More informationxx/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 informationRun-Based Trieから構成される 決定木の枝刈り法
Run-Based Trie 2 2 25 6 Run-Based Trie Simple Search Run-Based Trie Network A Network B Packet Router Packet Filtering Policy Rule Network A, K Network B Network C, D Action Permit Deny Permit Network
More informationRead the following text messages. Study the names carefully. 次のメッセージを読みましょう 名前をしっかり覚えましょう Dear Jenny, Iʼm Kim Garcia. Iʼm your new classmate. These ar
LESSON GOAL: Can read a message. メッセージを読めるようになろう Complete the conversation using your own information. あなた自身のことを考えて 会話を完成させましょう 1. A: Whatʼs your name? B:. 2. A: Whatʼs your phone number, (tutor says studentʼs
More informationTHE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE.
THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE. E-mail: {ytamura,takai,tkato,tm}@vision.kuee.kyoto-u.ac.jp Abstract Current Wave Pattern Analysis for Anomaly
More informationIPSJ SIG Technical Report Vol.2009-HCI-134 No /7/17 1. RDB Wiki Wiki RDB SQL Wiki Wiki RDB Wiki RDB Wiki A Wiki System Enhanced by Visibl
1. RDB Wiki 1 1 2 Wiki RDB SQL Wiki Wiki RDB Wiki RDB Wiki A Wiki System Enhanced by Visible RDB Operations Toshiya Okumura, 1 Minoru Terada 1 and Kazutaka Maruyama 2 Although Wiki systems can easily be
More informationDEIM Forum 2009 B4-6, Str
DEIM Forum 2009 B4-6, 305 8573 1 1 1 152 8550 2 12 1 E-mail: tttakuro@kde.cs.tsukuba.ac.jp, watanabe@de.cs.titech.ac.jp, kitagawa@cs.tsukuba.ac.jp StreamSpinner PC PC StreamSpinner Development of Data
More informationThe 19th Game Programming Workshop 2014 SHOT 1,a) 2 UCT SHOT UCT SHOT UCT UCT SHOT UCT An Empirical Evaluation of the Effectiveness of the SHOT algori
SHOT 1,a) 2 UCT SHOT UCT SHOT UCT UCT SHOT UCT An Empirical Evaluation of the Effectiveness of the SHOT algorithm in Go and Gobang Masahiro Honjo 1,a) Yoshimasa Tsuruoka 2 Abstract: Today, UCT is the most
More information,,.,.,,.,.,.,.,,.,..,,,, i
22 A person recognition using color information 1110372 2011 2 13 ,,.,.,,.,.,.,.,,.,..,,,, i Abstract A person recognition using color information Tatsumo HOJI Recently, for the purpose of collection of
More information, IT.,.,..,.. i
25 To construct the system that promote a interactive method as a knowledge acquisition 1140317 2014 2 28 , IT.,.,..,.. i Abstract To construct the system that promote a interactive method as a knowledge
More informationKII, Masanobu Vol.7 No Spring
KII, Masanobu 1 2 3 4 5 2 2.1 1945 60196075 19759019904 002 Vol.7 No.1 2004 Spring 1194560 1 1946 2 195328 3 4 1958 1960 2196075 5 6 7 8 1946 2 1972 1/23/4 1974 1968481973 1969 3197590 9 1980 1987 41990
More informationIPSJ SIG Technical Report Vol.2016-CE-137 No /12/ e β /α α β β / α A judgment method of difficulty of task for a learner using simple
1 2 3 4 5 e β /α α β β / α A judgment method of difficulty of task for a learner using simple electroencephalograph Katsuyuki Umezawa 1 Takashi Ishida 2 Tomohiko Saito 3 Makoto Nakazawa 4 Shigeichi Hirasawa
More information( )
NAIST-IS-MT0851100 2010 2 4 ( ) CR CR CR 1980 90 CR Kerberos SSH CR CR CR CR CR CR,,, ID, NAIST-IS- MT0851100, 2010 2 4. i On the Key Management Policy of Challenge Response Authentication Schemes Toshiya
More informationIPSJ SIG Technical Report Vol.2010-GN-74 No /1/ , 3 Disaster Training Supporting System Based on Electronic Triage HIROAKI KOJIMA, 1 KU
1 2 2 1, 3 Disaster Training Supporting System Based on Electronic Triage HIROAKI KOJIMA, 1 KUNIAKI SUSEKI, 2 KENTARO NAGAHASHI 2 and KEN-ICHI OKADA 1, 3 When there are a lot of injured people at a large-scale
More informationIPSJ SIG Technical Report 1, Instrument Separation in Reverberant Environments Using Crystal Microphone Arrays Nobutaka ITO, 1, 2 Yu KITANO, 1
1, 2 1 1 1 Instrument Separation in Reverberant Environments Using Crystal Microphone Arrays Nobutaka ITO, 1, 2 Yu KITANO, 1 Nobutaka ONO 1 and Shigeki SAGAYAMA 1 This paper deals with instrument separation
More information新製品開発プロジェクトの評価手法
CIRJE-J-60 2001 8 A note on new product project selection model: Empirical analysis in chemical industry Kenichi KuwashimaUniversity of Tokyo Junichi TomitaUniversity of Tokyo August, 2001 Abstract By
More information...
m cm ... ..... A.B..C..D. MOOK 18 ,.. p........................................ .... ............................ Joy Vision p p............ p p p........ ... The Significance of Near Vision Visual Acuity
More information