初学者のプログラムの自動正誤判定における部分点付与の提案

(1)

平成２５年度修士論文

初学者のプログラムの自動正誤判定におけ

る部分点付与の提案

学籍番号１１３１００８

氏名伊藤亜樹

情報・通信工学専攻コンピュータサイエンス

コース

指導教員寺田実准教授

副指導教員角田博保准教授

提出日２０１４年１月２７日

(2)

1

概要

目的

プログラミング学習システムにおいてプログラムを自動正誤判定する場合，テストデータを与えて実行結果から判定するのが一般的であるが，テスト結果が一致しなければ一律に不正解とみなされる．しかしそれでは初学者にはハードルが高いと考えた．本研究では，初学者向けに，意欲向上を目的として，不正解とされるプログラムに対して部分点を与えることとした．

方法

手法としてはプログラムの静的解析を行い，制御構造などの重要な要素に限定して評価を行うこととする．適切な評価値を与えるヒューリスティクスについて検討した．

結論

結果，人間は実行結果を重視していることがわかった．そのため，今回比較対象としたもの以外でも，比較検討する必要があるといえるが，重要度を設定することである程度は人間が考える点数に近付けることができたと考える．

(3)

2

第 1 章序論 6 1.1 背景 . . . 6 1.2 現状の問題 _{. . . .} 6 1.3 目的 . . . 6 1.4 本論文の構成 _{. . . .} 6 第 2 章関連研究 8 2.1 プログラムの正誤判定の方法 . . . 8 2.2 プログラミング初学者のための研究 _{. . . .} 9 2.2.1 初級プログラミング学習のための自動作問システム. . . 9 2.2.2 初学者向けプログラミング学習環境 PEN . . . 10 2.2.3 複数の入出力サンプルによる実行結果との柔軟な照合の実現_{. . . 11} 2.3 本研究では . . . 11 第 3 章提案システム 12 3.1 概要 . . . 12 3.2 尺度 _{. . . 12} 3.3 利用場面 _{. . . 13} 3.4 利点と問題点 . . . 14 第 4 章判定アルゴリズム 15 4.1 重要度の設定 . . . 16 4.2 実行結果が誤りで構造が異なるプログラム _{. . . 18} 4.3 実行結果は正解だが構造が異なるプログラム _{. . . 19} 第 5 章実装 20 5.1 開発環境 _{. . . 20} 5.2 AST とは . . . 20 5.3 システム構成 _{. . . 20} 5.4 システム実行結果 _{. . . 20} 第 6 章実験 23 6.1 実験の目的 _{. . . 23} 6.2 実験の方法と手順 . . . 23 6.3 実験結果 _{. . . 26} 6.3.1 仮説. . . 27 6.3.2 実験結果に基づく重要度の設定 . . . 27

(4)

3

6.3.3 仮説検証結果 _{. . . 28}

第 7 章まとめ 32

7.1 結論 _{. . . 32} 7.2 今後の課題 _{. . . 33}

(5)

4

図目次

2.1 Java ドリルの問題画面（[1] より）. . . 9 2.2 PEN の実行画面1 . . . 10 2.3 川崎ら [3] のプログラムの正誤判定の手順 . . . 11 3.1 尺度の説明 . . . 12 3.2 システム利用の流れ . . . 13 4.1 ペナルティを求めるアルゴリズム _{. . . 15} 4.2 ソースコード 4.2 のペナルティを求めるアルゴリズム . . . 17 4.3 ソースコード 4.3 のペナルティを求めるアルゴリズム . . . 18 4.4 ソースコード 4.5 のペナルティを求めるアルゴリズム . . . 19 5.1 本システム実行例 . . . 21 5.2 ソースコード 5.2 のペナルティを求めるアルゴリズム . . . 22 6.1 素数正解の AST . . . 30 6.2 素数誤り 1 の AST . . . 30 6.3 素数誤り 2 の AST . . . 31 6.4 素数誤り 3 の AST . . . 31

(6)

5

表目次

3.1 提案手法の場合 _{. . . 14} 6.1 実験結果 . . . 26 6.2 実験結果（問題ごとに点数の高い順） _{. . . 26} 6.3 仮説検証結果 . . . 28 6.4 仮説検証結果（問題ごとに点数の高い順） . . . 28 6.5 素数正解の出力結果 _{. . . 30} 6.6 素数誤り 1 の出力結果. . . 30 6.7 素数誤り 2 の出力結果. . . 31 6.8 素数誤り 3 の出力結果. . . 31

(7)

6

第

₁

章

序論

1.1 背景

近年の IT 社会において，プログラミング学習者は増加しており，その学習方法も，一人で学ぶ場合と，講義などで他の人と一緒に学ぶ場合の大きく二つに分けられる．そしてプログラミング学習においては，プログラムの概念の理解だけでなく，実際にその作成の過程を繰り返すことも大事であり，どちらの学習方法であっても，学習意欲を保つことは重要である．

1.2 現状の問題

学習方法の一つとして，オンラインジャッジ1_{や，コンテスト}2_{が挙げられる．そしてそのどちらも正誤} の判定に重点が置かれている．しかし，完答が難しいことも多いプログラミングが不得意な学習者にとっては，それではハードルが高い．理由として，もしも完答できなかった場合，学習者は自分が提出したプログラムがどれくらい合っていたのかを一見して判断することは困難だからである．

1.3 目的

1.2 節より，「完全に合っているか否か」のみで判断するよりも，「どれくらい合っていたか」という判断基準も導入することで，「もう少しで完答できる」という思いから，学習者の学習意欲が高まるのではないかと考えた．前述より，本研究では，プログラミングが不得意な学習者，またはプログラミング学習を始めたばかりの人が書いたプログラムの正誤判定を行った場合に，「どれくらい合っているか」を求めることを検討することとした．プログラムの解析方法には，プログラムを実行させて行う動的解析と，逆に実行することなく行う静的解析があるが，本研究では静的解析を取り扱う．静的解析を行うことによって，コンパイルはできるが実行時エラーは起きてしまうような，だが人間が見た場合に「惜しい」と思われるものに部分点が与えられるようになると考えられる．

1.4 本論文の構成

論文の構成を簡単に説明する. 本章では序論として，研究の背景と問題点，目的について述べた. 第 2 章「関連研究」では，本研究に関連する研究について述べる．

1_{AIZU ONLINE JUDGE Programming Challenge，http://judge.u-aizu.ac.jp/onlinejudge/} 2_{ACM-ICPC，http://icpc.baylor.edu/}

(8)

第 1 章序論 7 第 3 章「提案システム」では, 本研究の提案するシステムについて述べる．第 4 章「判定アルゴリズム」では，本システムで使用するアルゴリムについて述べる．第 5 章「実装」では, 本研究で提案するシステムの実装について述べる．第 6 章「実験」では，実験の結果と考察について述べる．第 7 章「まとめ」では，本論文における結論と今後の課題について述べる．

(9)

8

第

₂

章

2.1 プログラムの正誤判定の方法

プログラムの解析方法には，静的解析と静的解析があり，以下のような特徴がある．動的解析・プログラムを実行させて行う・テストデータを与え，その実行結果に基づいて判定を行う・比較的容易にプログラムの判定を行えるが，部分ごとの評価が行えない静的解析・プログラムを実行することなく行う・ソースコードの記述に基づいて判定を行う・部分ごとの評価が行えるが，プログラムの判定が容易ではないまた，オンラインジャッジでは，動的解析を行っている．その際，プログラムの正解・不正解以外に，プログラムの実行時間，メモリの使用量，プログラムのサイズなどのチェックを行う1_． 1_{AOJ チュートリアルドキュメント，http://judge.u-aizu.ac.jp/onlinejudge/AOJ_tutorial.pdf}

(10)

第 2 章関連研究 9

2.2 プログラミング初学者のための研究

プログラミング初学者のための研究には，さまざまなものがある．

2.2.1 初級プログラミング学習のための自動作問システム

内田 [1] は，反復して演習することができるように穴埋め形式のドリルを，自動生成するシステムを開発した（図 2.1）．予め準備した正解プログラムのソースコードから，静的解析によって，自動的に空所補充問題に生成する．問題の空所となる部分は，乱数によって決められるため，毎回異なる．自由に記述する形式ではなく穴埋め形式にすることで，採点は比較的容易であるが，学習者は記述を制限される．図 2.1: Java ドリルの問題画面（[1] より）

(11)

2.2.2 初学者向けプログラミング学習環境 PEN

中村ら [2] は，プログラミング教育の入門サポートのために，PEN というツールを考案した． PEN は DNCL に準拠，一部拡張した xDNCL 言語を用いている．DNCL は，大学入試科目「情報関係基礎」で用いられている，日本語をベースとした記述言語である． PEN では，入力ミスによる文法エラーを減らすため，制御構造などを「プログラム入力支援ボタン」から入力することができる（図 2.2）．図 2.2: PEN の実行画面2

(12)

2.2.3 複数の入出力サンプルによる実行結果との柔軟な照合の実現

川崎ら [3] は，大学におけるプログラミング演習において，小コンテスト形式を提案している．そして一つの問題に対し，複数の予備テストと最終テストを用意し，段階的な実装を誘導する．最終テストでは完全な解答が要求されるが，予備テストでは，部分点が与えられる．たとえば，平均と最大値を求める問題で，平均だけの出力が合えばよいとしたり，“ 2.00 ”が正解の場合に“ 2 ”が出力された場合でも正解とする．また，実行結果のみに基づいて判定が行われ（図 2.3），ソースコード内部については問われない．ソースコードの類似度を判定するモジュールを組み込んでいるが，不正コピー防止のためであり，正誤判定には使われていない．図 2.3: 川崎ら [3] のプログラムの正誤判定の手順

2.3 本研究では

本研究では，プログラムが「合っているか・合っていないか」よりも，初学者向けに「間違っているプログラムに少しでも点を与える」ために重点を置いた．そのため，静的解析を行い，ソースコード内部の一部の重要な要素に限定して評価を行う．実行結果については問わない．

(13)

12

第

₃

章

提案システム

3.1 概要

本研究では，1 章で述べた問題点を解決するために以下のようなシステムを提案する．正解のプログラムと学習者のプログラムがどれくらい似ているかを，ある尺度を設け，それに従って静的解析によって判定する．対象言語は，Java とする．

3.2 尺度

用いる尺度としては，ソースコード内部における制御構造に着目した．そしてその中でも，プログラムを学ぶ上で重要かつ初期の頃から頻繁に出てくる while，for，if，及び，その条件式のトップレベルに出現する比較演算子を比較対象とした．但し，右オペランドが定数の場合には右オペランドも比較対象とする．制御構造の while，for，if は，図 3.1 のような形になっている．これらの尺度を用いて正解プログラムと学習者のプログラムの判定を行い，ペナルティを与える．

ſ ʳɥƀƇ

䡚

ƈ

řř

ẚ㍑₇⟬Ꮚ

ྑ䜸䝨䝷䞁䝗

図 3.1: 尺度の説明

(14)

第 3 章提案システム 13

3.3 利用場面

1.1 節で述べた通り，プログラミング学習の方法には大きく二つに分けて，「一人で学ぶ場合」と「講義などで他の人と一緒に学ぶ場合」がある．本システムは後者の講義などで使用されることを想定しており，その教師が正解プログラムを用意することとする．システムの流れは，図 3.2 を想定している．

૙ࠖ

ǷǹȆȠ

ゎ䛡䛯䟿

ܖ፼ᎍ

䐠 Ꮫ⩦⪅䛜䝥䝻䜾䝷䝭䞁䜾

䐡 Ꮫ⩦⪅䛜䝅䝇䝔䝮䜢ᐇ⾜

䐟 ᩍᖌ䛜ண䜑

ṇゎ䝥䝻䜾䝷䝮䜢⏝ព

ṇゎ

䝥䝻䜾䝷䝮

Ꮫ⩦⪅

䝥䝻䜾䝷䝮

䐢䝅䝇䝔䝮䛜

Ⅼᩘ䜢ุᐃ

᥇Ⅼ⤖ᯝ

図 3.2: システム利用の流れ

(15)

第 3 章提案システム 14

3.4 利点と問題点

プログラムが正しいとは，「出力が正しい」場合だけでなく，「構造が正しい」こともいえると考える．前者では，部分点は与えづらいが，後者は少しでも点を与えることができる．本研究では，構造が正しいかどうかに着目することにした．本研究で提案する手法では，表 3.1 の場合が考えられる．学習者が作成したプログラムを実行した結果と，提案システムを実行した結果を比較した場合に，「実行結果が正解のプログラムが正解と判断される場合」，「実行結果が誤りのプログラムが誤りと判断される場合」は問題ないといえる．表 3.1 の A の場合，つまり「実行結果は正解だが，本システムでは誤りと判断される場合」だが，対応させるには正解プログラムとして用意する必要がある．表 3.1 の B の場合，つまり「実行結果は誤りだが，本システムでは正解と判断される場合」だが，これは「実行結果は誤りでも，正解プログラムと構造は同じである」と同じ意味であり，正解プログラムと構造が似ているプログラムほど，より点を与えることができる．表 3.1: 提案手法の場合

本システム

正解

誤り

実

行

正解

○ 第一種過誤

A

結

果

誤り

第二種過誤

B

○

そのため本研究で提案する手法には，以下の利点と問題点がある．利点・コンパイルはできるが実行時エラーは起きてしまうようなプログラムに点を与えられる・正解プログラムと構造が似ているプログラムほど，より点を与えることができる問題点・実行結果は正解だが構造が異なるプログラムに対応しておらず，対応させるためには正解プログラムとして予め用意しなければならない

(16)

15

第

₄

章

判定アルゴリズム

本システムでは，メソッド単位で正解プログラムと初学者が作成したプログラムを比較して，その違いを計算する．まず正解プログラムと初学者が作成したプログラムの AST を作ってから，AST に含まれる制御構造を再帰的に比較する．・keyword が等しくない → 10.0 ・keyword が等しい場合・条件式の処理・operator が等しくない → 5.0 ・右 operand が等しくない → 5.0 ・本体の処理・先頭から再帰的に比較 → 1/2n ・keyword の数が等しくない → 5.0 ・重要度の指定が存在 → 各々の重要度をかけていく図 4.1: ペナルティを求めるアルゴリズム図 4.1 は，ペナルティを再帰的に求めるアルゴリズムである．keyword という予約語は，while，if，for のことを指す．但し，keyword が等しいかどうかを判定する際，while と for は同一と見なすとする．n は内側にある keyword の数のことを指す．まず，keyword が等しくなければ，10.0 と重いペナルティを与える．keyword が等しくないのに条件式の処理を行っても意味がないためである．次に，条件式の処理だが，operator や右 operand が等しくない場合は，keyword が等しくなかった場合の半分の 5.0 のペナルティとした．そして，本体の処理については，多重ループのあるプログラムの場合に，先頭から再帰的に比較を行うこととした．また，keyword の数が等しくない場合は，5.0 のペナルティを与える．再帰的に比較する際に 1/2n をかける理由，及び重要度については，4.1 節で述べる．また，keyword の数が等しくない場合については 4.3 節で述べる．

(17)

第 4 章判定アルゴリズム 16

4.1 重要度の設定

ソースコード 4.1 のように，多重ループが使われているプログラムの場合に，内側の率（1/2n，n は内側にある制御構造の数）を設定することによって，ループの内側が間違っていてもペナルティは軽くなる．しかし，ソースコード 4.2 の場合で，13 行目の，出力を行う for がない場合，ループの内側ではないため内側の率は適用されず，ペナルティは重いものとなる．ソースコード 4.2 のペナルティは，「5.0」である． 1 public class A {

2 public static void main(String[] args) {

3 int[] a={10,3,2,1};

4 for(int i=0; i < a.length-1; i++) {

5 for(int j=0; j < a.length-i-1; j++) {

6 if(a[j] > a[j+1]) { 7 int s = a[j]; 8 a[j] = a[j+1]; 9 a[j+1] = s; 10 } 11 } 12 }

13 for(int i = 0; i < a.length; i++) { 14 System.out.print(a[i]+"␣"); 15 } 16 } 17 } ソースコード 4.1: 整数配列 a[] が与えられたとき，その中の値を昇順に並べ替え，その結果を出力するバブルソートのプログラム 1 public class A {

3 int[] a={10,3,2,1};

6 if(a[j] > a[j+1]) { 7 int s = a[j]; 8 a[j] = a[j+1]; 9 a[j+1] = s; 10 } 11 } 12 } 13 } 14 } ソースコード 4.2: ソースコード 4.1 の誤りのプログラム

(18)

第 4 章判定アルゴリズム 17 ・keyword が等しくない → 10.0 ・keyword が等しい場合・条件式の処理・operator が等しくない → 5.0 ・右 operand が等しくない → 5.0 ・本体の処理・先頭から再帰的に比較 → 1/2n ・keyword の数が等しくない → 5.0 ・重要度の指定が存在 → 各々の重要度をかけていく図 4.2: ソースコード 4.2 のペナルティを求めるアルゴリズムソースコード 4.2 は，ソースコード 4.1 と比較した場合に，ソースコード 4.1 では 13 行目の出力を行う for がないため，ループの内側ではないため内側の率は適用されず，ペナルティは重いものとなると述べた．しかし正しい出力がされないものの，それ以外は合っており，人間が見た場合には「とても惜しい」といえる．そのため，このような場合はペナルティを軽くし，逆にここは重要であるという部分にはペナルティを重くするために，任意で重要度を指定できるようにした．予め，教師が正解プログラムにおいて重要度を設定したい keyword のある行で“ // Importance 0.5 ” のように記述すればよい（例：ソースコード 4.3 の 13 行目）．ソースコード 4.3 のペナルティは，5.0*0.5=2.5 で，「2.5」となる． 1 public class A {

3 int[] a={10,3,2,1};

13 for(int i = 0; i < a.length; i++) { // Importance 0.5 14 System.out.print(a[i]+"␣");

15 }

16 }

17 }

(19)

第 4 章判定アルゴリズム 18 ・keyword が等しくない → 10.0 ・keyword が等しい場合・条件式の処理・operator が等しくない → 5.0 ・右 operand が等しくない → 5.0 ・本体の処理・先頭から再帰的に比較 → 1/2n ・keyword の数が等しくない → 5.0 ・重要度の指定が存在 → 各々の重要度をかけていく図 4.3: ソースコード 4.3 のペナルティを求めるアルゴリズム

4.2 実行結果が誤りで構造が異なるプログラム

本節では，本システムでは実行結果が誤りで構造が異なるプログラムを正解プログラムとして用意しなかった場合にペナルティはどのようになるのかを述べる． keyword，つまり制御構造 while，if，for の数が異なるプログラムに対するペナルティは，以下のようになっている．・正解プログラムの keyword の数 < 初学者プログラムの keyword の数の場合・ペナルティは 5.0 そうではなく，・正解プログラムの keyword の数 > 初学者プログラムの keyword の数の場合・初学者プログラムの数から正解プログラムの数の間比較する・重要度の指定が存在 → 各々の重要度をかけていく・重要度の指定が存在しない → ペナルティは 5.0 つまり，初学者が正解プログラムと比べて，余計に制御構造を書いた場合はあまりペナルティを与えず，逆に足りなかった場合はその分のペナルティと，重要度の指定が存在すれば各々の重要度をかけていく．

(20)

第 4 章判定アルゴリズム 19

4.3 実行結果は正解だが構造が異なるプログラム

3.4 節で，本研究で提案する手法では，実行結果は正解だが構造が異なるプログラムには対応していないと述べた．本節では，本システムでは実行結果は正解だが構造が異なるプログラムを正解プログラムとして用意しなかった場合にペナルティはどのようになるのかを述べる．ソースコード 4.4 とソースコード 4.2 はどちらも，1 から 10 までの足し算を行った結果，“ 合計は 55 です ”と出力するプログラムである．

4 行目の for で，ソースコード 4.4 では“ i<=10 ”であるのに対し，ソースコード 4.5 では“ 10>=i ”となっている．ソースコード 4.4 が正解プログラムとして予め用意されている場合に，ソースコード 4.5 のペナルティを求めるアルゴリズムは，表 4.4 のようになる．

ソースコード 4.5 のペナルティは，(5.0*1/2*1)=2.5 で，「2.5」となる． 1 public class A {

3 int sum=0;

4 for(int i=1;i<=10;i++) {

5 sum+=i; 6 } 7 System.out.println("合計は"+sum+"です"); 8 } 9 } ソースコード 4.4: 1 から 10 までの足し算を行い，その結果を出力するプログラム 1 public class B {

3 int sum=0;

4 for(int i=1;10>=i;i++) {

5 sum+=i; 6 } 7 System.out.println("合計は"+sum+"です"); 8 } 9 } ソースコード 4.5: 1 から 10 までの足し算を行い，その結果を出力するプログラム・keyword が等しくない → 10.0 ・keyword が等しい場合・条件式の処理・operator が等しくない → 5.0 ・右 operand が等しくない → 5.0 ・本体の処理・先頭から再帰的に比較 → 1/2n ・keyword の数が等しくない → 5.0 ・重要度の指定が存在 → 各々の重要度をかけていく図 4.4: ソースコード 4.5 のペナルティを求めるアルゴリズム

(21)

20

第

₅

章

実装

5.1 開発環境

対象のプログラムは Java としており，Eclipse を使って Java で生成した AST（抽象構文木，Abstract Syntax Tree）にて比較を行っている．

5.2 AST

とは

プログラムの構造をそのまま木構造で表したものを構文木という．構文木には解析に不要なものも含まれているが，それらを除いたものを，AST（抽象構文木，Abstract Syntax Tree）という．AST を作成し， ASTVisitor で各ノードを訪問する．

5.3 システム構成

本システムはいくつかの Java ファイルで構成されている． Test.java ファイルの読み込み，AST の構築，点数の出力を行う SubASTVisitor.java 重要度のためのコメントを読み込み，木の訪問を行う Node.java 木の構成，ペナルティの計算を行う，木の出力を行う

5.4 システム実行結果

本システムを実行した例として，本システムで正解プログラムとしてソースコード 5.1 と，誤りプログラムとしてソースコード 5.2 を比較した場合，図 5.1 のようになる．

(22)

第 5 章実装 21 図 5.1: 本システム実行例また簡易ではあるが，以下のような要素を表示する（図 5.1 の 1 と 2）．木 1 正解プログラムのこと木 2 誤りプログラムのこと T トップのこと．便宜上使用しているもの

w while のこと．operator と右 operand も表示する f for のこと．operator と右 operand も表示する I if のこと．operator と右 operand も表示する It then のこと Ie else のこと 3 だが，4 章で述べた判定アルゴリズムでペナルティを計算し，更に以下のような出力を行っている． • ペナルティ<=10.0 の場合 – ｛10.0-（ペナルティ）｝点 • ペナルティ>10.0 の場合 – 0 点 例の場合は，正解プログラム（ソースコード 5.1）では 4 行目の for の operator が<であるのが，誤りプログラム（ソースコード 5.2）では>となっている．重要度は設定されていない．つまり，表 5.2 のようになる．つまりペナルティは，(5.0*1/2*1)=2.5 となる．ペナルティ<=10.0 なので，10.0-2.5=7.5 で，結果は「7.5 点」となる．

(23)

第 5 章実装 22 ・keyword が等しくない → 10.0 ・keyword が等しい場合・条件式の処理・operator が等しくない → 5.0 ・右 operand が等しくない → 5.0 ・本体の処理・先頭から再帰的に比較 → 1/2n ・keyword の数が等しくない → 5.0 ・重要度の指定が存在 → 各々の重要度をかけていく図 5.2: ソースコード 5.2 のペナルティを求めるアルゴリズム 1 public class 5A {

3 int sum=0;

4 for(int i=1;i<=10;i++) {

5 sum+=i; 6 } 7 System.out.println("合計は"+sum+"です"); 8 } 9 } ソースコード 5.1: 1 から 10 までの足し算を行い，その結果を出力するプログラム 1 public class 5B {

3 int sum=0;

4 for(int i=1;i>10;i++) {

5 sum+=i; 6 } 7 System.out.println("合計は"+sum+"です"); 8 } 9 } ソースコード 5.2: ソースコード 5.1 の誤りプログラム.java

(24)

23

第

₆

章

実験

6.1 実験の目的

システムと人間が尺度に従って採点を行い，尺度の有効性を検証することとする．評価としては，複数の誤りプログラムをシステムと人間が尺度に従って採点し，あまりその点数に差が出なければ，その尺度は有効であると考えられる．

6.2 実験の方法と手順

2 種類のプログラムに対し，誤ったプログラムをそれぞれ 3 種類用意し，本学の寺田研究室所属の学生 4 名に 10 点満点で自由に採点してもらった．一つ目は，整数配列 a[] が与えられたとき，その中の値を昇順に並べ替える，バブルソート（以下，「バブル」とする）のプログラムである．被験者には，正解プログラムとしてソースコード 6.1 と，誤りプログラムとしてソースコード 6.2，ソースコード 6.3，ソースコード 6.4 が提示されている．二つ目は，n が素数か判定するプログラム（以下，「素数」とする）である．被験者には，正解プログラムとしてソースコード 6.5 と，誤りプログラムとしてソースコード 6.6，ソースコード 6.7，ソースコード 6.8 が提示されている．それぞれ，正解とどこが異なるのかも示した．以下に記す． 1 public class A {

3 int[] a={10,3,2,1};

13 for(int i = 0; i < a.length; i++) { 14 System.out.print(a[i]+"␣");

15 }

16 }

17 }

(25)

第 6 章実験 24

1 public class B {

3 int[] a={10,3,2,1};

5 if(a[i] > a[i+1]) { 6 int s = a[i]; 7 a[i] = a[i+1]; 8 a[i+1] = s; 9 } 10 }

11 for(int i = 0; i < a.length; i++) { 12 System.out.print(a[i]+"␣"); 13 } 14 } 15 } ソースコード 6.2: バブル誤り 1 二つ目（ソースコード 6.1 では 5 行目）の for 文がない． 1 public class B {

3 int[] a={10,3,2,1};

13 for(int i = 0; i > a.length; i++) { 14 System.out.print(a[i]+"␣"); 15 } 16 } 17 } ソースコード 6.3: バブル誤り 2 出力の for 文（13 行目）の<を>にした． 1 public class B {

3 int[] a={10,3,2,1};

6 if(a[j] > a[j+1]) { 7 int s = a[j]; 8 a[j] = a[j+1]; 9 a[j+1] = s; 10 } 11 } 12 } 13 } 14 } ソースコード 6.4: バブル誤り 3 出力の for 文（13 行目）がない．

(26)

第 6 章実験 25

1 public class C {

3 int n = 5;

4 for (int i=2; i<=n; i++){

5 if (i == n) { 6 System.out.println("素数"); 7 } 8 else if (n % i == 0){ 9 System.out.println("素数ではない"); 10 break; 11 } 12 } 13 } 14 } ソースコード 6.5: 素数正解 1 public class D {

3 int n = 5;

4 for (int i=2; i<=n; i++){

5 if (i == n) { 6 System.out.println("素数"); 7 } 8 else{ 9 System.out.println("素数ではない"); 10 break; 11 } 12 } 13 } 14 } ソースコード 6.6: 素数誤り 1 8 行目で，“ else if (n % i == 0) ”を“ else ”にした． 1 public class D {

3 int n = 5;

4 for (int i=2; i<=n; i++){

5 if (i == n) { 6 System.out.println("素数"); 7 } 8 if (n % i == 0){ 9 System.out.println("素数ではない"); 10 break; 11 } 12 } 13 } 14 } ソースコード 6.7: 素数誤り 2 8 行目で，“ else if (n % i == 0) ”を“ if (n % i == 0) ”にした．

(27)

第 6 章実験 26

1 public class D {

3 int n = 5,i = 2; 4 while (i<n){ 5 if (i == n) { 6 System.out.println("素数"); 7 } 8 if (n % i == 1){ 9 System.out.println("素数ではない"); 10 } 11 i++; 12 } 13 } 14 } ソースコード 6.8: 素数誤り 3

4 行目の for 文を while に変更，そこで“ i<=n ”を“ i<n ”に変更，8 行目の“ else if (n % i == 0) ” を“ if (n % i == 1) ”にした．

6.3 実験結果

表 6.1: 実験結果バブル 1 バブル 2 バブル 3 素数 1 素数 2 素数 3 システム 8.75 8.75 5.0 9.6875 7.1875 4.6875 被験者 A 3 8 7 2 6 2 被験者 B 2 6 4 0 6 2 被験者 C 0 6 8 4 7 2 被験者 D 4 8 9 6 9 5 表 6.2: 実験結果（問題ごとに点数の高い順）システムバブル 1 バブル 2 バブル 3 素数 1 素数 2 素数 3 被験者 A バブル 2 バブル 3 バブル 1 素数 2 素数 1 素数 3 被験者 B バブル 2 バブル 3 バブル 1 素数 2 素数 3 素数 1 被験者 C バブル 3 バブル 2 バブル 1 素数 2 素数 1 素数 3 被験者 D バブル 3 バブル 2 バブル 1 素数 2 素数 1 素数 3 実験の結果，表 6.1 のようになった．システムには，重要度は設定していない．表 6.2 は，わかりやすいようにバブルと素数，それぞれ問題ごとに点の高い順で並べたものである．被験者は，バブル 1 のようにロジックが間違っていれば点数を与えないか大幅に減点していた．なお，一部の被験者から誤答プログラムの実行結果を見て回答したという記述があった．先にも述べたが，本システムでは動的解析ではなく静的解析を行っている．そのため，ソースコード内部について判定は行うが実行結果については問わない．また，当然被験者の間でも採点結果には差があるも

(28)

第 6 章実験 27 のの，それでも本システムと人間の点数に差があまり出なかったとはこの結果からは言い難い．だが，予めロジックに対して重要度を設定することで，ある程度システムと人間の点数を近づけることは可能ではないかと考えられる．

6.3.1 仮説

今度は，「システムで予めロジックに対して重要度を設定すれば，ある程度システムと人間の点数を近付けることは可能である」，という仮説に基づき，検証を行う．

6.3.2 実験結果に基づく重要度の設定

まず，仮説に基づき「システムで予めロジックに対して重要度を設定」するため，教師はバブル正解と素数正解のそれぞれのロジック部分に 1.5 を，それ以外に 0.5 の重要度を指定したとする． 1 public class A {

3 int[] a={10,3,2,1};

4 for(int i=0; i < a.length-1; i++) { // Importance 1.5

5 for(int j=0; j < a.length-i-1; j++) { // Importance 1.5

6 if(a[j] > a[j+1]) { // Importance 1.5

7 int s = a[j]; 8 a[j] = a[j+1]; 9 a[j+1] = s; 10 } 11 } 12 }

13 for(int i = 0; i < a.length; i++) { // Importance 0.5 14 System.out.print(a[i]+"␣"); 15 } 16 } 17 } ソースコード 6.9: バブル正解に重要度を設定した例 1 public class C {

3 int n = 5;

4 for (int i=2; i<=n; i++){ // Importance 1.5

5 if (i == n) { // Importance 1.5 6 System.out.println("素数"); 7 } 8 else if (n % i == 0){ // Importance 1.5 9 System.out.println("素数ではない"); 10 break; 11 } 12 } 13 } 14 } ソースコード 6.10: 素数正解に重要度を設定した例

(29)

第 6 章実験 28

6.3.3 仮説検証結果

表 6.3: 仮説検証結果バブル 1 バブル 2 バブル 3 素数 1 素数 2 素数 3 システム（重要度設定なし） 8.75 8.75 5.0 9.6875 7.1875 4.6875 システム（重要度設定済） 7.1875 9.375 7.5 8.41796875 4.66796875 0.91796875 被験者 A 3 8 7 2 6 2 被験者 B 2 6 4 0 6 2 被験者 C 0 6 8 4 7 2 被験者 D 4 8 9 6 9 5 表 6.4: 仮説検証結果（問題ごとに点数の高い順）システム（重要度設定なし）バブル 1 バブル 2 バブル 3 素数 1 素数 2 素数 3 システム（重要度設定済）バブル 2 バブル 3 バブル 1 素数 1 素数 2 素数 3 被験者 A バブル 2 バブル 3 バブル 1 素数 2 素数 1 素数 3 被験者 B バブル 2 バブル 3 バブル 1 素数 2 素数 3 素数 1 被験者 C バブル 3 バブル 2 バブル 1 素数 2 素数 1 素数 3 被験者 D バブル 3 バブル 2 バブル 1 素数 2 素数 1 素数 3 結果，システムの値は表 6.3 のようになった．まずバブルについてだが，「バブル１=バブル 2>バブル 3」だったのが，重要度設定後は「バブル 2>バブル 3>バブル 1」となった．被験者 4 名中，2 名が「バブル 2>バブル 3>バブル 1」で，残り 2 名が「バブル 3>バブル 2>バブル 1」と，評価も分かれている．これはバブルソートを行うロジックそのものに誤りがあるバブル 1 とは異なり，バブル 2 とバブル 3 のどちらも同じ出力部分に誤りがあるためであると考えられる．今回はロジック部分とそれ以外というように重要度を指定したため，重要度を指定してもバブル 1 はシステムと人間の点数は近づいたとは言い難いが，あとは重要度として与える数値を細かく指定すれば，問題ないと考えられる．つまり，バブル 2 もバブル 3 もどちらも人間にとって誤りの度合いは変わらないと考えた場合，概ね人間が考える値に近づけることができたのではないだろうか．次に素数についてだが，被験者の間で評価が分かれることはなかった．しかし，素数についてはほぼ同様の箇所に誤りがあり，その箇所に重要度を設定しても「素数 1>素数 2>素数 3」の関係性が変わることはない．被験者の評価結果からは，「素数 2>素数 1>素数 3」となるはずだが，そもそもシステムの結果はそうならなずに「素数 1>素数 2>素数 3」となったのは，システムは構造で判定を行い，被験者は出力結果で判断するという違いが表れた結果と考えられる．これは，素数正解は図 6.1 と表 6.5，素数誤り 1 は図 6.2 と表 6.6，素数誤り 2 は図 6.3 と表 6.7，素数誤り 3 は図 6.4 と表 6.8 から判断できる．なお，図 6.1，図 6.2，図 6.3，図 6.4 中の☆は，実際には今回は比較対象としないが，わかりやすいように便宜上付けたものである．例えば，図 6.1 の“ for (☆; ☆<=n; ☆) ”は，ソースコード 6.5 の“ for (int

(30)

第 6 章実験 29 較演算子，右オペランド以外を指している．

つまり，構造で判定を行うシステムと，出力結果で判断している被験者で点数に差が出るのは仕方なく，かつ素数の場合は何れもほぼ同じところを間違えているために重要度を設定しても「素数 1>素数 2>素数 3」の関係性が変わらないことは当然といえる．

(31)

第 6 章実験 30 ſ䖪Ś䖪ʳʰŚ䖪ƀ ſ䖪ʰʰƀ ſ䖪ʰʰɥƀ 図 6.1: 素数正解の AST

素数

（

n

が

5 の場合）

素数

素数ではない

（

n

が

6 の場合）

素数ではない

表 6.5: 素数正解の出力結果 ſ䖪Ś䖪ʳʰŚ䖪ƀ ſ䖪ʰʰƀ 図 6.2: 素数誤り 1 の AST

素数

（

n

が

5 の場合）

素数ではない

（

n

が

6 の場合）

素数ではない

表 6.6: 素数誤り 1 の出力結果

(32)

第 6 章実験 31 ſ䖪Ś䖪ʳʰŚ䖪ƀ ſ䖪ʰʰƀ ſ䖪ʰʰɥƀ 図 6.3: 素数誤り 2 の AST

素数

（

n

が

5 の場合）

素数

素数ではない

（

n

が

6 の場合）

素数ではない

表 6.7: 素数誤り 2 の出力結果 ſ䖪ʳƀ ſ䖪ʰʰƀ ſ䖪ʰʰɨƀ 図 6.4: 素数誤り 3 の AST

素数

（

n

が

5 の場合）

素数ではない

（

n

が

6 の場合）

素数ではない

表 6.8: 素数誤り 3 の出力結果

(33)

32

第

₇

章

まとめ

7.1 結論

本研究では，初学習向けにプログラムの静的解析を行い，ソースコード内部の一部の重要な要素に限定して評価を行った．その際，実行結果については問わなかったが，結果として，人間は実行結果を重視するということがわかった．逆に，実行結果を重視しなかった例を挙げる．ソースコード 7.1 とソースコード 7.2 を比較した場合に，ソースコード 7.2 の 12 行目までが合っていても 13 行目の for が合っていなければ正しい出力はされない．だが，6 章の実験結果の通り，被験者は出力部分に対してはあまり重いペナルティを与えていない．もし実行結果のみを重視するのならば，実行はされるが出力はされず，重いペナルティが与えられるはずだ．しかしただ単に出力部分だからペナルティを軽くするというわけではないと考えられ，今後の尺度の設定には検討が必要である．尺度の有効性の検証結果としては，今回比較対象としたもの以外でも，比較検討する必要があるといえるが，重要度を設定することである程度は人間が考える点数に近付けることができたと考える． 1 public class A {

3 int[] a={10,3,2,1};

13 for(int i = 0; i < a.length; i++) { 14 System.out.print(a[i]+"␣"); 15 } 16 } 17 } ソースコード 7.1: 整数配列 a[] が与えられたとき，その中の値を昇順に並べ替え，その結果を出力するバブルソートのプログラム 1 public class B {

3 int[] a={10,3,2,1};

(34)

第 7 章まとめ 33 13 } 14 } ソースコード 7.2: ソースコード 7.1 の誤りのプログラム

7.2 今後の課題

今後の課題は，次の二点が挙げられる．実行結果は正解だが構造が異なるプログラムの場合に，6.3.3 節で述べたように，本システムの現在のペナルティの与え方や重要度の指定では人間の考える点数に近づけることの難しいプログラムもある．そのような，構造が異なるプログラムに対するペナルティの算出方法について，比較検討する必要がある．そして現在，本システムは出力結果が非常に簡素である．実際にプログラムのどの部分を見てペナルティを与えているのかを出力するなど，インタフェース面での改良も必要である．

(35)

34

謝辞

本研究は電気通信大学情報・通信工学専攻寺田研究室において，寺田実准教授の御指導の下で行われました．寺田実准教授には，本研究を進めるにあたり，様々な御助言や御指導を頂きました．心より御礼申し上げます．明星大学情報学部の丸山一貴准教授にも，研究内容や論文についての御意見や御指導など様々な面で御助力をいただきました．深く感謝致します．修士課程二年の石川斉君，佐々木佳祐君，平山拓朗君，学部四年の今井健太君，海老澤雄太君，長利槙吾君，片山信春君，清岡修平君，黒澤大樹君，山本保子さんには，研究についての様々な助言や評価実験, 研究室での生活に関することなど，様々な点でお世話になりました．本当にありがとうございました．

(36)

35

参考文献

[1] 内田保雄，“ 初級プログラミング学習のための自動作問システム ”，『コンピュータと教育』，情報処理学会研究報告，pp.109-113，2007． [2] 中村亮太，西田知博，松浦敏雄，“ 高等学校での「プログラミング」教育の導入-PEN を用いて ”，『コンピュータと教育』，情報処理学会研究報告，pp.41-47，2008． [3] 川崎慎一郎，富永浩之，“ 競争型学習を取り入れた入門的 C プログラミング演習 - 実行テスト系列による部分採点のための柔軟な照合機能 - ”，『コンピュータと教育』，情報処理学会研究報告，pp.1-8，2010．

初学者のプログラムの自動正誤判定における部分点付与の提案

平成２５年度修士論文