Japan Advanced Institute of Science and Technology
JAIST Repository
https://dspace.jaist.ac.jp/ Title 問題データベースの構築 Author(s) 浅野, 哲夫 Citation CGEIアニュアルレポート 2010: 21-25 Issue Date 2011-07Type Research Paper Text version publisher
URL http://hdl.handle.net/10119/10546 Rights Description Ⅱ．活動報告 / Center Activities, (３) 試験問題デ ータベース構築の検討 / Construction of a Problem Database
Ѹ Ѹ
く 報 告 >
問題データペースの構築
浅 野 哲 夫 ( 大 学 院 教 育 イ ニ シ ア テ ィ ブ セ ン タ ー 長 )
Construction of a Problem Database
Tetsuo Asano (Director
，
Center for Graduate Education Initiative)Abstract : Good examination is quite important for quality assurance of each course
，
but it is not widely known what is a good examination or there is no training of professors to prepare good examinations. This is a motivation for our database named Problem Database. The database is a collection of all kinds of problems related to one field， in our case， algorithms in computer師 団nce. The database encourages professors in the world to share problems for better
examinations. This reports surveys activities on the database in our center. [キーワード:問題データベース，試験問題，質保証，アルゴリズム] 1 は じ め に 大 学 院 教 育 イ ニ シ ア テ ィ プ セ ン タ ー に 課 せ ら れ た 課 題 の 一 つ で あ る 「 大 学 院 教 育 に お け る 質 保 証 の 枠 組 み に 関 す る 提 言 」 に と っ て ， 各 講 義 の 最 後 に 実 施 さ れ る 試 験 問 題 は 非 常 に 重 要 で あ る . 講 義 の 進 め 方 に つ い て は フ ァ カ ル テ ィ ー ・ デ ィ ベ ロ ッ プ メ ン ト 活 動 の 一 環 と し て 取 り 上 げ ら れ る こ と は 多 か っ た が ， 優 れ た 試 験 問 題 に つ い て の 議 論 は 十 分 と は 言 え な い の が 現 状 で あ る 。 教 育 学 の 分 野 で は 優 れ た 試 験 問 題 の 作 成 に つ い て の 研 究 も 行 わ れ て い る が ， 理 系 の 大 学 院 に お け る 講 義 科 目 の 試 験 と い う こ と に な る と 科 学 的 な 方 法 論 は 確 立 さ れ て い な い と 言 っ て 過 言 で な い 。 こ の よ う な 現 状 に 鑑 み て ， 本 セ ン タ ー で は 質 保 証 を 支 え る 試 験 問 題 の 評 価 ・ 改 善 に 向 け て ， 優 れ た 試 験 問 題 作 成 に 向 け た 全 世 界 的 な 取 り 組 み と し て 問 題 デ ー タ ベ ー ス を 構 築 す る こ と と し た 。 大 学 院 教 育 の 一 環 で あ る こ と を 意 識 し て ， 網 羅 型 の デ ー タ ベ ー ス で は な く ， 一 つ の 学 問 分 野 に 限 定 し た 上 で 方 法 論 を 確 立 し ， そ の 経 験 を 活 か し て 将 来 的 に は 別 の 分 野 に も 拡 張 し て い く と い う 計 画 で あ る 。 本 年 度 は ， 問 題 デ ー タ ベ ー ス の シ ス テ ム 構 築 に 向 け て 仕 様 書 の 作 成 か ら 始 め ， 年 度 末 に は シ ス テ ム 完 成 に ま で こ ぎ つ け る こ と が で き た が ， 以 下 に そ の 詳 細 を 報 告 す る 。 2 問 題 テ ー タ ベ ー ス の 必 要 性 本 デ ー タ ベ ー ス の 目 的 は ， 分 野 を 情 報 科 学 の 一 つ の 領 域 に 相 当 す る 「 ア ル ゴ リ ズ ム 」 に 限 定 し た 上 で 世 界 中 か ら ( 試 験 ) 問 題 を 収 集 し ， 相 互 利 用 を 通 し て ， よ り 良 い 試 験 問 題 作 成 に 向 け た 共 同 研 究 を 行 う こ と で あ る 。 こ の プ ロ ジ ェ ク ト は ， そ も そ も 試 験 問 題 の 難 し さ を 科 学 的 に 評 価 す る こ と は 可 能 か と い う 聞 か ら 始 ま っ て い る 。 そ も そ も ， 理 想 的 な 試 験 問 題 と は 何 な の か を 定 義 す る こ と が 困 難 で あ る 。 ま た ， 理 想 的 に は 同 じ 程 度 の 難 し さ の 問 題 を 毎 年 作 る 続 け る こ と は で き る だ ろ う か 。 理 想 的 な 試 験 問 題 で は ， 単 な る 知 識 の 記 憶 で は な く ， 講 義 内 容 が 真 の 意 味 で 理 解 で き て い る か を 定 量 的 に 評 価 で き る こ と が 必 要 で あ る が ，
Ѹ Ѹ そ の よ う な 科 学 的 な 方 法 は 存 在 す る だ ろ う か 。 教 育 の 質 保 証 の た め に は 避 け て 通 れ な い 重 要 な 問 題 で あ る が ， こ と 理 系 の 大 学 院 教 育 に 関 し て は 殆 ど 何 も 分 か っ て い な い の が 現 状 で ある。 3. 問 題 デ ー タ ベ ー ス の 全 体 像 今 回 開 発 し た 問 題 デ ー タ ベ ー ス シ ス テ ム は 3つ の 部 分 か ら 構 成 さ れ て い る 。 テ キ ス ト 問 題 検 索 部 で は ， ア ル ゴ リ ズ ム 関 係 の テ キ ス ト か ら 抽 出 し た 膨 大 な 問 題 の 中 か ら 興 味 の あ る 問 題 を キ ー ワ ー ド に よ り 検 索 し て 閲 覧 す る こ と を 可 能 に し て い る 。 こ れ ま で に 全 世 界 で 使 わ れ て い る ア ル ゴ リ ズ ム 関 係 の 英 語 の 図 書 を 約 60冊 購 入 し ， す べ て ス キ ャ ナ で 取 り 込 む 作 業 を 終 え て い る 。 今 後 は ， そ れ ぞ れ の テ キ ス ト ご と に 文 字 認 識 の 処 理 を 施 し て 問 題 文 を テ キ ス ト と し て 抽 出 し ， デ ー タ ベ ー ス に 登 録 す る 予 定 で あ る 。 現 在 の 所 は 最 初 の 1冊 に つ い て の 作 業 に 取 り 掛 か っ て い る が ， 何 し ろ 膨 大 な 作 業 を 要 す る の で ， 自 動 的 に 問 題 に 通 し 番 号 を つ け ， 適 当 な キ ー ワ ー ド を 付 与 す る プ ロ グ ラ ム を 開 発 し て い る と こ ろ で あ る 。 5月 末 ま で に は 最 初 の 1冊 に あ る 全 問 題 ( 約 1000問 題 ) を 登 録 完 了 す る 予 定 で あ る 。 試 験 問 題 検 索 部 で は ， ア ル ゴ リ ズ ム 関 係 の 試 験 問 題 の 中 か ら 指 定 し た キ ー ワ ー ド に 合 致 す る 問 題 を 閲 覧 す る こ と が で き る 。 全 世 界 の 様 々 な 大 学 に い る 本 セ ン タ ー の サ ポ ー ト ボ ー ド メ ン パ ー を 通 じ て 試 験 問 題 の 収 集 を 行 い ， デ ー タ ベ ー ス の 形 に ま と め る 予 定 で あ る 。 試 験 問 題 と い う 性 格 上 ， 学 生 を 含 め ， 世 間 一 般 に 公 開 す る 性 格 の も の で は な い の で ， 試 験 問 題 の 提 供 と い う 形 で 貢 献 し て く れ た メ ン バ ー に 対 し て の み ユ ー ザ と し て の 資 格 を 与 え る こ と に し て い る 。 ユ ー ザ ネ ー ム と パ ス ワ ー ド で 管 理 す る 方 式 が 完 成 し た ば か り で あ り ， 本 活 的 な 運 用 は 本 年 5月 以 降 を 予 定 し て い る 。 ま た 5月 末 ま で に サ ポ ー ト ボ ー ド メ ン バ ー に 問 題 の 提 供 を 呼 び か け る メ ー ル を 発 送 す る 予 定 で あ る 。
3
.
問 題 デ ー タ ベ ー ス の シ ス テ ム 概 要 テ キ ス ト 問 題 に 関 し て は 著 作 権 の 問 題 が あ り ， 試 験 問 題 に つ い て は 学 生 へ の 漏 洩 を 心 配 す る 教 員 も 多 い こ と か ら ， デ ー タ ベ ー ス へ の ア ク セ ス を 登 録 者 だ け に 限 定 す る こ と が 重 要 で あ っ た 。 そ の た め に ， 今 回 開 発 し た 問 題 デ ー タ ベ ー ス シ ス テ ム で は 2段 階 の 認 証 に よ り ア ク セ ス を 可 能 と し て い る 。 予 定 し て い る ユ ー ザ は ， 試 験 問 題 デ ー タ ベ ー ス へ の 試 験 問 題 の 提 供 に 貢 献 し て く れ る こ と を 約 束 し て い る 本 セ ン タ ー の サ ポ ー ト ボ ー ド メ ン バ ー に 限 定 す る 。 登 録 メ ン バ ー だ け が ユ ー ザ 名 と パ ス ワ ー ド を 保 持 し て お り ， そ れ に よ っ て デ ー タ ベ ー ス に ア ク セ ス で き る 仕 組 み に し て い る . セ キ ュ リ テ ィ ー の た め に ， 問 題 の 登 録 は シ ス テ ム 管 理 者 の み に 許 可 し ， 一 般 の ユ ー ザ に は 一 切 の 書 き 込 み 処 理 を 許 可 し て い な い 。 図 1に 問 題 デ ー タ ベ ー ス シ ス テ ム の ロ グ イ ン 画 面 と 検 索 画 面 を 示 す ロ グ イ ン で は 2段 階 の ロ グ イ ン 操 作 で 安 全 性 を 担 保 し て い る 。 検 索 に お い て は ， テ キ ス ト 問 題 と 試 験 問 題 の ど ち ら を 検 索 対 象 と す る か を 選 択 し た 後 ， キ ー ワ ー ド あ る い は 細 目 表 に よ る 問 題 の 検 索 を 可能にしている。Ѹ Ѹ 面 ，
ー
ー
・
“‘司 ~Iã五二二主語
J U Jニヒ
3
i
d
w
回
二
-
t
z
ペ
ニ
r
;
主主主主
語
rLEak t z J J法
よ
-
r A
二
一
一
一
画
面
.
.
.
.
.
.'
"
"
-PD8s'e"O巴h About PDB SeiJrch。
bjcctlvc Acc....lo凶e '"・b・~何
一
一
ー
一
ー
一
一
一
一
一
一
一
明
白
・
.
.
.
.
_
-
申
F 目 白一一一時
一
， 山urc01Ihc ' " 岡 市一・一一一
一
司
一
一
.
_
，
一
一
四
一
一
一
一
一
一
一
岡 市 川 町 ， .僧
.
.
}
一
一
一
圃・圃園
司....，..，". ι、
.
PDBs'eoreh一回，-
0.
，←ー
一
一
一
一
一
一
包E申 由 一一
一
一
日当」血血宅史_._.--，-血 図 1， 問 題 デ ー タ ベ ー ス . 左 は ロ グ イ ン 画 面 . 右 は 検 索 画 面 4， 問 題 デ ー タ ベ ー ス に 収 録 予 定 の テ キ ス ト と 必 要 な 作 業 ‘. 下 の リ ス ト は 問 題 デ ー タ ベ ー ス に 収 録 予 定 の テ キ ス ト の タ イ ト ノ レ と 著 者 名 を 示 し た も の で あ る 。 現 在 ま で に す べ て の テ キ ス ト の ス キ ャ ン 作 業 を 終 了 し て い る 。 今 後 ， 予 定 さ れ る 作 業 は 次 の 通 り で あ る . 1 . ス キ ャ ン に よ っ て 得 ら れt画 像 デ ー タ (pdfフ ァ イ ル ) に 画 像 エ ン ハ ン ス メ ン ト 処 理 を 施 す . 2. 文 字 認 轍 プ ロ グ ラ ム(OCR)を 適 用 し て ， 画 像 デ ー タ を 文 字 デ ー タ に 変 換 す る 。 3. 目 次 の 部 分 を 加 工 し て ， キ ー ワ ー ド を 節 ご と に 追 加 で き る よ う に す る 。4.
問 題 文 の 部 分 だ け を ベ ー ジ 数 の 情 報 と と も に 切 り 出 す 。5.
そ れ ぞ れ の 問 題 文 に 自 動 的 に 通 し 番 号 を つ け る 。 6. 各 問 題 文 の 数 式 の 部 分 を LaTeXの 形 式 で 表 現 す る .7.
問 題 ご と に 取 り 出 し て ， デ ィ レ ク ト リ を 作 成 し ， 問 題 文 の テ キ ス ト と キ ー ワ ー ド 他 を 蓄 え た フ ァ イ ル を 自 動 的 に 作 成 す るa 8. 問 題 デ ー タ ベ ー ス に 登 録 す る た め の csvフ ァ イ ル を 作 成 す る 。 9. Csvファイルにより， 指 で 問 題 を 問 題 デ ー タ ベ ー ス に 登 録 す る 。(1) Algorithms ( Sanjoy Dasgupta ，Christos Papadimitriou， and Umesh VaziranO (2) Algorithm Design (Jon Kleinberg and Eva Tardoo)
(3) ALGORITHM DESIGN Foundations，Analysis，and Internet E玄ample(Michael T. Goodrich and
Roberto Tamaooia)
(4) Algorithms + Data Structures = Programs (Niklaus Wirth)
(5) Algorithms and Data Structure圃 TheBasIc Toolbox (Kurt Mehlhorn s.nd Perter Ss.ndero) (6) Algorithms and Programming Problems and Solutions Second Edition ( Ale玄anderShen)
Ѹ Ѹ
Techniques (Mikhail J. Atallah and Marina Blanton)
(8) Algorith血 s and Theory of Computation Handbook Second Edition General Concepts and
Techniques ( Mikhail J. Atallah and Marina Blanton)
(9) Algorithms Design Techniques and Analysis (M. H. AlsuwaiyeJ) (10) Algorithms IN C++ Part1.4 3rdEdition (Robert Sedgewick) (11) Algorith血 sIN C Part5 3rdEdition (Robert Sedgewick)
(12) Algorithms IN C++ Part1.4 3rdEdition (Robert Sedgewick)
(13) Algorithms IN C++ Part5 3rdEdition (Robert Sedgewick)
(14) Algorithms of the Intelligent Web (Harala血b08Marmanis and Dmitry Babenko)
(15) ALGORITHMS ON STRINGS TREE， AND SEQUENCES (Dan GU8field)
(16) An Introduction to DATA STRUCTURES AND ALGORITHMS (J. A. Storer)
(17) Analysis of Algorithms (Jeffrey J. McConnell)
(18) Appro玄i血 ationAlgorith血s(Vijay V. Vazirani)
(19) COMBINATORIAL ALGORITHMS: ENLARGED SECOND EDITION"optimized (T. C. Hu and M T. Shing)
(20) COMBINATORIAL OPTIMIZATION Algorithms and Complexity (Chri叫08H. Papadimitriou
and Kenneth Steiglitz)
(21) COMBINATORIAL OPTIMIZATION Theory and Algorith血 s(Bernhard Korte and J ens Vygen)
(22) COMPUTABILITY AND UNSOLVABILITY (Martin Davis)
(23) Computational Geometry Algoriもhms and Applications 3rdEdition (Mark de Berg， Otfried
Cheong， Marc van Kreveld， and Mark Overmars)
(24) COMPUTER ALGORITHMS C++ 2ndEdition (Ellis Horowitz and Sartaj Sahni)
(25) COMPUTER ALGORITHMS Introduction to Design & Analysis Third Edition (Sara Baase and Allen van Gelder)
(26) CONCENTRATION OF MEASURE FOR THE ANALYSIS OF RANDOMIZED ALGORITHMS (Devdatt P. Dubhashi and Ale8sandro Panconesi)
(27) CONCRETE MATHMATICS A FOUNDATION FOR COMPUTER SCIENCE 2ndEdition (Ronald L. Graham， Donald E. Knuth， and Oren Patashnik)
(28) Data Structures and Algorithms in JAVA (Michael T. Goodrich and Roberto Tamassia) (29) DATA STRUCTURES & ALGORITHMS IN JAVA (Robert Lafore)
(30) Data Structures & Algorithms in Java 2ndEdition (Robert Lafore)
(31)Data Structures and Algorithm Analysis in C++ 3rdEdition (Mark Allen Weiss) (32) Data Structures and Algorithm Analysis SECOND EDITION (Mark Allen Wei闘)
(33) DATA STRUCTURES AND ALGORITHMS (Alfred V. Aho， John E. Hopcroft， and Jeffrey D Ullman)
(34) DATA STRUCTURES AND ALGORITHMS IN C++ Third Edition (Adam Drozdek) (35) Data Structures and Algorithms in Java (Adam Drozdek)
(36) Data Structures and Algorithms Using C# (Michael McMillan)
Ѹ Ѹ
(39) INTRODUCTION TO ALGORITHMS A Creative Approach (Udi Manber)
(40) INTRODUCTION TO ALGORITHMS SECOND EDITION (Thomas H. Cormen， Charles E. Leiserson， Ronald L. Rivest， and Clifford Stein)
(41)INTRODUCTION TO ALGORITHMS THIRD EDITION (Thomas H. Cormen， Charles E. Leiserson， Ronald L. Rivest， and Clifford Stein)
(42) INTRODUCTION TO COMPUTING AND ALGORITHMS (Russell L. Shackerlford) (43) Introduction to The Design and Analysis of Algorith血 s2ndEdition (Anany Levitin)
(44) Mastering Algorith血 sWith C (Kyle Loudon)
(45) Maもhe血aticsforもheAnalysis of Algorithms 3rdEdition (Daniel H. Greene and Donald E.
Knuth)
(46) Data Structures (Perter Brass)
(47) PLANNING ALGORITHMS (Steven M. LaValle)
(48) PRACTICAL ALGORITHMS FOR PROGRAMMERS (Andrew Binstock and John Rex)
(49) Problem Solving with Algorith血8and Data Structures using Py山on(Bradley N. Miller and
David L. Ranum)
(50) Programmer to Programmer Beginning Algorithms (Simon Harris and James R08S) (51) Program皿ingChallenges (Steven S. Skiena and Miguel A. Revilla)
(52) Programming Pearls 2ndEdition (Jon Bentley)
(53) Randomized Algorithm (Rajeev M叫waniand Prabhakar Raghavan)
(54) SAMS Teach Yourself Data Structures and Algorithms in 24 Hours (Robert Lafore) (55) Selected Papers on Design of Algorithms (Donald E. Knuth)
(56) THE Algorithm Design MANUAL 2ndEdition (Steven S. Skiena)
(57) The Art of Co血puter Progra血ming VOLUME 1 Fundamental Algorithms Third Edition
(Donald E. Knuth)
(58) The Design and Analysis of Computer Algorithms (Alfred V. Aho， John E. Hopcroft， and Jeffrey D. Ullman)
