JAIST Repository
https://dspace.jaist.ac.jp/Title

問題データベースの構築

Author(s)浅野, 哲夫

Citation

CGEIアニュアルレポート

Issue Date

2011‑07

TypeResearch Paper

Text version

publisher

URL

http://hdl.handle.net/10119/10546

2010: 21‑25

RightsDescription

Ⅱ．活動報告 / Center Activities, (３) 試験問題データベース構築の検討 / Construction of a Problem
Database

Japan Advanced Institute of Science and Technology

く報告>

問題データペースの構築
浅野哲夫(大学院教育イニシアティブセンター長)Constructionofa ProblemDatabase
TetsuoAsano(Director，CenterforGraduateEducationInitiative)
Abstract:Goodexaminationi
squiteimportantfo
rqual
it
ya
ssu
r
anc
eofe
ac
hc
ou
r
se，
bu
ti
ti
snot
w
idel
yknownwhati
sagoode
x
a
mi
nat
io
nort
he
r
ei
snot
r
ai
n
in
gofp
r
ofe
ssor
st
op
r
e
p
ar
egood
ex
a
min
at
ion
s.T
hi
si
samot
iv
at
io
nfo
ro
u
rd
at
abas
enamedProblemD
atabase. Thedatabaseisacollectionofallkinds ofproblemsr
elatedt
o onefie
ld，i
nou
rc
a
se，algorit
hmsi
ncomputer
師団nce. The databaseen
cou
r
age
spr
of
e
ssor
si
nt
h
e world toshare problems fo
rbetterexaminat
ion
s. T
hi
sr
e
por
t
ssu
rv
eysact
iv
it
i
e
sont
hed
atabaseinou
rcenter.
[キーワード:問題データベース，試験問題，質保証，アルゴリズム]
1 はじめに大学院教育イニシアティプセンターに課せられた課題の一つである「大学院教育における質保証の枠組みに関する提言」にとって，各講義の最後に実施される試験問題は非常に重要である.講義の進め方についてはファカルティー・ディベロップメント活動の一環として取り上げられることは多かったが，優れた試験問題についての議論は十分とは言えないのが現状である。教育学の分野では優れた試験問題の作成についての研究も行われているが，理系の大学院における講義科目の試験ということになると科学的な方法論は確立されていないと言って過言でない。このような現状に鑑みて，本センターでは質保証を支える試験問題の評価・改善に向けて，優れた試験問題作成に向けた全世界的な取り組みとして問題データベースを構築することとした。大学院教育の一環であることを意識して，網羅型のデータベースではなく，一つの学問分野に限定した上で方法論を確立し，その経験を活かして将来的には別の分野にも拡張していくという計画である。本年度は，問題データベースのシステム構築に向けて仕様書の作成から始め，年度末にはシステム完成にまでこぎつけることができたが，以下にその詳細を報告する。
2 問題テータベースの必要性

本データベースの目的は，分野を情報科学の一つの領域に相当する「アルゴリズム」に限定した上で世界中から(試験)問題を収集し，相互利用を通して，より良い試験問題作成に向けた共同研究を行うことである。このプロジェクトは，そもそも試験問題の難しさを科学的に評価することは可能かという聞から始まっている。そもそも，理想的な試験問
題とは何なのかを定義することが困難である。また，理想的には同じ程度の難しさの問題を毎年作る続けることはできるだろうか。理想的な試験問題では，単なる知識の記憶ではなく，講義内容が真の意味で理解できているかを定量的に評価できることが必要であるが，

Ѹ  Ѹ

そのような科学的な方法は存在するだろうか。教育の質保証のためには避けて通れない重要な問題であるが，こと理系の大学院教育に関しては殆ど何も分かっていないのが現状である。

3. 問題データベースの全体像
今 回 開 発 し た 問 題 デ ー タ ベ ー ス シ ス テ ム は 3つ の 部 分 か ら 構 成 さ れ て い る 。 テ キ ス ト 問
題検索部では，アルゴリズム関係のテキストから抽出した膨大な問題の中から興味のある問題をキーワードにより検索して閲覧することを可能にしている。これまでに全世界で使わ れ て い る ア ル ゴ リ ズ ム 関 係 の 英 語 の 図 書 を 約 60冊 購 入 し ， す べ て ス キ ャ ナ で 取 り 込 む 作業を終えている。今後は，それぞれのテキストごとに文字認識の処理を施して問題文をテキ ス ト と し て 抽 出 し ， デ ー タ ベ ー ス に 登 録 す る 予 定 で あ る 。 現 在 の 所 は 最 初 の 1冊 に つ いての作業に取り掛かっているが，何しろ膨大な作業を要するので，自動的に問題に通し番号をつけ，適当なキーワードを付与するプログラムを開発しているところである。

5月 末ま で に は 最 初 の 1冊 に あ る 全 問 題 ( 約 1000問 題 ) を 登 録 完 了 す る 予 定 で あ る 。
試験問題検索部では，アルゴリズム関係の試験問題の中から指定したキーワードに合致する問題を閲覧することができる。全世界の様々な大学にいる本センターのサポートボードメンパーを通じて試験問題の収集を行い，データベースの形にまとめる予定である。試験問題という性格上，学生を含め，世間一般に公開する性格のものではないので，試験問題の提供という形で貢献してくれたメンバーに対してのみユーザとしての資格を与えることにしている。ユーザネームとパスワードで管理する方式が完成したばかりであり，本活的 な 運 用 は 本 年 5月 以 降 を 予 定 し て い る 。 ま た

5月 末 ま で に サ ポ ー ト ボ ー ド メ ン バ ー に問題の提供を呼びかけるメールを発送する予定である。

3. 問題データベースのシステム概要
テキスト問題に関しては著作権の問題があり，試験問題については学生への漏洩を心配する教員も多いことから，データベースへのアクセスを登録者だけに限定することが重要で あ っ た 。 そ の た め に ， 今 回 開 発 し た 問 題 デ ー タ ベ ー ス シ ス テ ム で は 2段 階 の 認 証 に よ りアクセスを可能としている。
予定しているユーザは，試験問題データベースへの試験問題の提供に貢献してくれることを約束している本センターのサポートボードメンバーに限定する。登録メンバーだけがユーザ名とパスワードを保持しており，それによってデータベースにアクセスできる仕組みにしている.セキュリティーのために，問題の登録はシステム管理者のみに許可し，一般のユーザには一切の書き込み処理を許可していない。
図 1に 問 題 デ ー タ ベ ー ス シ ス テ ム の ロ グ イ ン 画 面 と 検 索 画 面 を 示 す

ロ グ イ ン で は 2段階のログイン操作で安全性を担保している。検索においては，テキスト問題と試験問題のどちらを検索対象とするかを選択した後，キーワードあるいは細目表による問題の検索を可能にしている。

Ѹ  Ѹ面 ，ー・PD
8s'e"O巴hAboutPDBSeiJrch。
bjcctlv
c，山r;
主主主主語

~Iã

司五二二主語 J U Jニヒ 3idw回
二‑tz
ペニrLE
ak t z J J法

一 一回，‑0

一
一 一
一一一 一
一

圃・圃園
一・一
一一一
司一一.
̲，
何一一一一四一
一一一ーー一一一一
一一一一・.
.
.
.
̲‑申一一一明白一一一一 時 .，僧}.. 一
一'"岡市'"・b・~

F

一一画面.'"‑PD
Bs'eorehur
c01Ihc.
，←ーAcc.
.
.
.
lo凶 e

よ‑rA
二

包E 申 由 一

日当」血血宅史̲.̲.‑‑，‑血目 白

岡市川町

一司.
.
.
.
，.
.，
". ι、.

.

図 1， 問 題 デ ー タ ベ ー ス . 左 は ロ グ イ ン 画 面 . 右 は 検 索 画 面

4， 問 題 デ ー タ ベ ー ス に 収 録 予 定 の テ キ ス ト と 必 要 な 作 業
下のリストは問題データベースに収録予定のテキストのタイトノレと著者名を示したものである。現在までにすべてのテキストのスキャン作業を終了している。今後，予定される作業は次の通りである.
1.

ス キ ャ ン に よ っ て 得 ら れ t 画 像 デ ー タ (pdf フ ァ イ ル ) に 画 像 エ ン ハ ン ス メ ン ト 処理を施す.

2.

文 字 認 轍 プ ロ グ ラ ム (OCR)を 適 用 し て ， 画 像 デ ー タ を 文 字 デ ー タ に 変 換 す る 。

3.

目次の部分を加工して，キーワードを節ごとに追加できるようにする。

4.

問題文の部分だけをベージ数の情報とともに切り出す。

5.

それぞれの問題文に自動的に通し番号をつける。

6.

各 問 題 文 の 数 式 の 部 分 を LaTeXの 形 式 で 表 現 す る .

7.

問題ごとに取り出して，ディレクトリを作成し，問題文のテキストとキーワード他を蓄えたファイルを自動的に作成する a

8.

問 題 デ ー タ ベ ー ス に 登 録 す る た め の csvフ ァ イ ル を 作 成 す る 。

9.

Csvファイルにより，指で問題を問題データベースに登録する。

(1)Algorithms(SanjoyDasgupta，ChristosPapadimitriou，andUmeshVaziranO(2)AlgorithmDesign(JonKleinbergandEvaTardoo)(3)ALGORITHMDESIGNFoundations，Analysis，andInternetE玄 ample(MichaelT. GoodrichandRobertoTamaooia)(4)Algorithms+DataStructures=Programs(NiklausWirth)(5)AlgorithmsandDataStructure圃 TheBasIcToolbox(KurtMehlhorns.ndPerterSs.ndero)(6)AlgorithmsandProgrammingProblemsandSolutionsSecondEdition(Ale玄 anderShen)(7) Algorithm固 and Theory of Computation Handbook Second Edition Special Topics andѸ  ѸTechniques(MikhailJ.AtallahandMarinaBlanton)f Computation Handbook Second Edition General Concepts and(8) Algorith血 s and Theory oTechniques(MikhailJ.AtallahandMarinaBlanton))(9)AlgorithmsDesignTechniquesandAnalysis(M.H.AlsuwaiyeJ(10)AlgorithmsINC++Part1.
43rdEdition(RobertSedgewick)(11)Algorith血 sINC Part53rdEdition(RobertSedgewick)(12)AlgorithmsINC++Part1.
43rdEdition(RobertSedgewick)(13)AlgorithmsINC++Part53rdEdition(RobertSedgewick)(14)Algorithmso
ftheIntelligentWeb(Harala血 b08MarmanisandDmitryBabenko)(15)ALGORITHMSONSTRINGSTREE，ANDSEQUENCES(DanGU8field)(16)AnIntroductiontoDATASTRUCTURESANDALGORITHMS(J.A.Storer)(17)Analysiso
fAlgorithms(Jeffre
yJ.McConnell)(18)Appro玄 i
血 ationAlgorith血 s(VijayV.Vazirani)(19)COMBINATORIALALGORITHMS:ENLARGEDSECONDEDITION"optimized(T.C.HuandM

T.Shing)
8H. Papadimitriou(20) COMBINATORIAL OPTIMIZATIONAlgorithms and Complexity (Chri叫 0andKennethSteiglitz)(21)COMBINATORIALOPTIMIZATIONTheoryandAlgorith血 s(BernhardKorteandJensVygen)(22)COMPUTABILITYANDUNSOLVABILITY(MartinDavis)(23) Computational Geometry Algoriもhms and Applications 3rdEdition (Mark de Berg，Otfried
Cheong，MarcvanKreveld，andMarkOvermars))(24)COMPUTERALGORITHMSC++2ndEdition(EllisHorowitzandSartajSahni(25)COMPUTERALGORITHMSIntroductiont
oDesign& AnalysisThirdEdition(SaraBaaseand
AllenvanGelder)(26) CONCENTRATION OF MEASURE FOR THE ANALYSIS OF RANDOMIZED ALGORITHMS)(DevdattP.DubhashiandAle8sandroPanconesi(27)CONCRETEMATHMATICSA FOUNDATIONFORCOMPUTERSCIENCE2ndEdition(Ronald.Knuth，andOrenPatashnik)
L.Graham，DonaldE(28)DataStructuresandAlgorithmsinJAVA(MichaelT.GoodrichandRobertoTamassia)(29)DATASTRUCTURES& ALGORITHMSINJAVA(RobertLafore)
nJava2ndEdition(RobertLafore)(30)DataStructures& Algorithmsi)DataStructuresandAlgorithmAnalysisi
nC++3rdEdition(MarkAllenWeiss)(31(32)DataStructuresandAlgorithmAnalysisSECONDEDITION(MarkAllenWei闘)(33) DATASTRUCTURESAND ALGORITHMS (AlfredV. Aho，John E. Hopcroft，andJeffreyDUllman)(34)DATASTRUCTURESANDALGORITHMSINC++ThirdEdition(AdamDrozdek)(35)DataStructuresandAlgorithmsinJava(AdamDrozdek)(36)DataStructuresandAlgorithmsUsingC#(MichaelMcMillan)p(37)FOUNDATIONSOFALGORITHMS4thEdition(RichardNeapolitanandKumars8Nai血 lѸ  Ѹ

(39)INTRODUCTIONTOALGORITHMSA CreativeApproach(UdiManber)(40) INTRODUCTION TO ALGORITHMS SECOND EDITION (Thomas H. Cormen，Charles E.
Leiserson，RonaldL.Rivest，andCliffordStein)(41) INTRODUCTION TO ALGORITHMS THIRD EDITION (Thomas H. Cormen，Charles E.
Leiserson，RonaldL.Rivest，andCliffordStein)(42)INTRODUCTIONTOCOMPUTINGANDALGORITHMS(RussellL.Shackerlford)(43)Introductiont
oTheDesignandAnalysiso
fAlgorith血 s2ndEdition(AnanyLevitin)(44)MasteringAlgorith血 sWithC (KyleLoudon)(45) Maもhe血 aticsfor もheAnalysis ofAlgorithms 3rdEdition (Daniel H. Greene and Donald E.
Knuth)(46)DataStructures(PerterBrass)(47)PLANNINGALGORITHMS(StevenM.LaValle)(48)PRACTICALALGORITHMSFORPROGRAMMERS(AndrewBinstockandJohnRex)(49)Problem SolvingwithAlgorith血 8andDataStructuresusingPy山 on(BradleyN.MillerandDavidL.Ranum)(50)Programmert
oProgrammerBeginningAlgorithms(SimonHarrisandJamesR08S)(51)Program皿 ingChallenges(StevenS.SkienaandMiguelA.Rev
illa)(52)ProgrammingPearls2ndEdition(JonBentley)(53)RandomizedAlgorithm(RajeevM叫 waniandPrabhakarRaghavan)(54)SAMSTeachYourselfDataStructuresandAlgorithmsi
n24Hours(RobertLafore)(55)SelectedPapersonDesigno
fAlgorithms(DonaldE.Knuth)(56)THEAlgorithmDesignMANUAL2ndEdition(StevenS.Skiena)(57) The Art of Co血 puter Progra血 ming VOLUME 1 Fundamental Algorithms Third Edition(DonaldE.Knuth)(58)TheDesignandAnalysiso
fComputerAlgorithms(AlfredV.Aho，JohnE.Hopcroft，andJeffrey
D.Ullman)

5. 今 後 の 予 定
2011年 5月 末

全世界のサポートボードメンパーに試験問題の提供を依頼

2011年 7月 末問題データベースのユーザ登録とパスワードの付与

2011年 9月 末提供された試験問題のデータベースへの登録，および登録ユーザへの試験問題データ
ベースのサーピス開始

2011年 12月 末
2012年 3月 末10冊 分 の テ キ ス ト 問 題 を デ ー タ ベ ー ス に 登 録
3 0冊 分 の テ キ ス ト 問 題 を デ ー タ ベ ー ス に 登 録Ѹ  Ѹ