関東地区

教育システム情報学会

2017年度学生研究発表会

アルゴリズムの特徴理解を促すアルゴリズムアニメーションの開発
Development of Algorithm Animation to Promote Understanding of Algorithm
Characteristics
下川 輝*1, 仲林 清*2
Hikaru SHIMOKAWA*1, Kiyoshi NAKABAYASHI*2*1 千葉工業大学情報ネットワーク学科*1 School of Informatic Network, Chiba Institute of Technology*2 千葉工業大学*2 Chiba Institute of Technology
Email: s1432078qy@s.chibakoudai.jp
あらまし：アルゴリズムアニメーションは文章や静的な図形による解説では理解することが難しいアルゴ
リズムの動的な振舞いを学習者に伝えやすい点というメリットがあるが，アルゴリズムの特徴を理解させるためには不十分な場合がある．本研究では文字列検索アルゴリズムのボイヤー・ムーア法のアニメーシ
ョンを開発し，さらに特徴理解を促すための学習課題を取り入れた．具体的には，他のアルゴリズムの動作と比較させること，特徴が顕著にあらわれる文字列の動作を確認させることと考えた．実験の結果，大半の学習者の理解度が向上したが，一部特徴では曖昧な理解となってしまった．また実験方法にも改善が必要な結果となった．
キーワード：アルゴリズムアニメーション，アルゴリズム学習，特徴理解，文字列検索1.

実用的であると気づかせることができると考えた．

はじめにアルゴリズムアニメーションとは，データ構造などを視覚的に表現して，それらを動的に変化させることにより，アルゴリズムの動作を直感的に学習者に伝えようとするものである．アニメーションの利点として教科書中の文章による解説や静的な図形による解説では理解することが難しいアルゴリズムの動的な振舞いを学習者に伝えやすい点が挙げられる(1)．
しかし，アルゴリズムアニメーションはアルゴリズムの特徴を理解させるためには不十分であると考えた．本研究では文字列検索アルゴリズムのボイヤー・ムーア法（以下 BM 法）を対象として，アルゴリズムアニメーションを開発し，さらに特徴理解を促す学習課題を取り入れる．具体的には，他の文字列検索アルゴリズムの動作と比較させること，入力機能を用いて特徴が顕著にあらわれる文字列の動作を確認させることを課題とする．

2.

2.2 特定の文字列の動作確認BM 法の特徴が顕著にあらわれる文字列を 2 種類用意した．用意した文字列を表 2 に示す．
「aaaaaaaaa」「baa」は最大時間計算量の文字列，「This is an apple」「apple」は平均的な時間計算量の文字列である．学
習者は最低限この文字列のアニメーションを確認す
る．これらの文字列のアニメーションを確認することによって時間計算量や実際の文書処理で実用的であると気づかせることができると考えた．
表 1 理解させる BM 法の特徴
パターンの末尾から照合
不一致情報をもとに，何文字ずらすかを決定
実際の文書処理等において，実用的である
最大時間計算量 O（mn）
平均的な時間計算量 O（m/n）
m:テキストの長さ，ｎ:パターンの長さ
表 2 用意した文字列
テキスト
パターン
aaaaaaaaa
baaThis is an appleapple

学習課題

BM 法の特徴理解を促す学習課題について説明する．学習者に理解させる BM 法の特徴(2)を表 1 に示
す．

アニメーション教材について

2.1 他の文字列検索アルゴリズムとの比較

3.

BM 法の他に力まかせ法，クヌース・モーリス・プラット法のアニメーションを実装した．これらの文字列検索アルゴリズムと BM 法との違いはパターンの先頭から照合することや不一致情報を利用しないことである(1)．学習者は同じ文字列に対して，それぞれの文字列検索アルゴリズムのアニメーションを確認することで BM 法の特徴や実際の文書処理でアニメーション教材について説明する．アニメー
ション教材はブラウザ上で動作するものとした．ア
ニメーション教材の全体図を図 1 に，出力結果を図2 に示す．アニメーションは照合するごとにテキストの照合位置が緑色に変化していき．不一致となった場合は照合位置が赤色に変化し，次の照合位置にパターンをずらすという動作をする．

41

関東地区

教育システム情報学会

5.

実験結果

事前・事後問題の結果を表 3 に示す．問 1,問 2 では時間計算量以外の特徴に関する問題，問 3,問 4 では時間計算量に関する問題を出題した．評価方法は○，△，×の 3 段階評価とした．未回答や的外れな解
答は×，抽象的な解答や不足している解答は△，具体的な解答は○とする．
事前と事後問題の実験結果を比較すると大半の学習者の解答に改善が見られた．特に問 3，問 4 においては事前問題では×の解答が目立っていたが，事後問題では大半の解答に改善が見られた．
アンケートの結果としては「アニメーションで動作を実際に見ることで，直感的に理解」や「最悪の場合の時間計算量は，アニメーションによってどのようになるのかを実際に見ることによって何がよくないことなのかを理解できた」などのアニメーションを実際に見ることで理解できたという回答が見られた．また，「遅い理由，早い理由がテキスト量とパターンによって変わるという事が分かったが，文章にするのが難しいと感じた」や「一般的な時間計算量では，説明をするのは難しい」などの時間計算量がなぜそうなるのかを文章にすることが難しいという回答が見られた．
表 3 事前・事後問題の結果

図 1 アニメーション教材の全体図

学習者問題番号問1問2問3問4

図 2 結果の説明4.

2017年度学生研究発表会

実験について6.

4.1 実験概要

ABC
D
事前 事後 事前 事後 事前 事後 事前 事後〇〇△〇△〇△〇×△△〇△〇△△×〇×△×〇
×△〇〇
×〇×〇〇
〇

考察と課題

実験結果およびアンケートの結果より大半の学習者の解答に改善が見られたことからアニメーション教材は有効であると考えた．しかし，他のアルゴリズムと比較させる方法では指示の出し方や学習者に操作を任せてしまったこと，実験内容に問題があったことから有効か判断できなかった．また特定の文字列を操作させる方法だけでは時間計算量はぼんやりとした理解となってしまう結果となった．そのため今後の課題として，指示の出し方，実験の内容を改善すること，時間計算量を深く理解させるために特定の文字列操作に別な方法を加える必要があると考える．また，アンケート結果から「表示エラーの改善」や「入力文字列を記録するログ機能」などの機能の改善も必要である．

本研究では，学習者に BM 法に関する問題を出題し，BM 法の動作を示した静的な図を参照した場合の解答と，アニメーション教材および特徴理解を促す学習課題を用いた場合の解答を比較して，学習方法が有効であるかを検証する．またアンケートを実施し，BM 法の特徴の理解度や実装してほしい機能や改善点について調査を行う．
実験は情報系学科 4 年生 4 人に対して行った．実験期間は 1 週間とし， 実験中は他の被験者との相談およびインターネットの閲覧は禁止とした．
4.2 実験の流れ実験は以下の手順で行った．
(ア) 文字列検索アルゴリズムの動作を示した図を参照しながら問題に取り組む．
（事前問題）(イ) アニメーション教材および学習課題の操作を行い，問題に取り組む．（事後問題）問題の内容は事前問題と同じである．
(ウ) アンケートへの回答
以上の作業が完了したら実験終了である．

参考文献
(1)

(2)

42

古川勝康，井上勝行，魚井宏高，首藤勝:“制御の流れに重点をおいてアルゴリズム学習を支援するシス
テ ム の 構 想 ”， 電 子 情 報 通 信 学 会 技 術 報
告,pp159-166(1997-03-15)
大森克志，木村春彦，広瀬貞樹:“アルゴリズムの基礎”(1997)