階層的科目体系での卒業単位チェックプログラムにおける再帰的アルゴリズム
松尾太加志＊となり，階層の数を意識したプログラムの設計が必

１．はじめに大学のカリキュラムの科目体系は科目区分が階層要となってしまう．そこで，階層数を特段意識する的な構造をしており，卒業に必要な単位は下位の科必要のない再帰的なアルゴリズムによって実装する

目区分の合計が上位の科目区分に算入されるようにことが必要となる．

なっている．大学の学部学科によって，科目自体は2.2 単位の合計数が一致しないケース異なるものの，このような階層的な構造は共通して一般に，ある科目区分の必要単位数は，その下位おり，卒業に必要な単位のチェックをする際の基本にある複数の科目区分の必要単位数の合計となる．

的なルールや構造は同じである．そのため，卒業単

ただし，場合によっては，科目区分ごとに必要な単位チェックシステムの汎用的なプログラムを開発す位の最低数が定められているだけで，それらの必要ることは困難な課題ではなく，そのようなシステム最低数を合計しても，上位の必要な単位数に満たなが利用できれば，大学の学務においても学生側にといことが多い．各科目区分では必要最低数だけが定っても有益である．

めてあり，上位の合計数を満たすには，各科目区分

そこで，Web で利用できる卒業単位チェックの汎用的なシステムの開発を行ったが1），汎用性をもたせるために，いくつかの工夫が必要であった．とくでの必要単位数を満たした上に，さらに合計数を満たすように，どこかの科目区分から単位を取得しなければならない．に階層的な構造での単位数の計算において，再帰的各科目区分での必要単位数の制約を低くすることアルゴリズムの導入が必要であった．本稿では，科によって，学生は自分が取りたい科目区分での科目目区分ごとに単位が充足しているのかどうかの判定を多く履修し，それらを卒業単位に反映できるため，を行うプログラムにおいて，実装した再帰的なアル学生の科目履修の自由度を高めたカリキュラム体系

ゴリズムについて報告を行う．になっている．このようなカリキュラムの場合，学生によって，科目区分の取得単位数が異なるため，卒業に必要な単位の計算誤りが生じやすくなってい

２．問題
2.1

る．そのため,このようなカリキュラム体系の場合，階層数の違い卒業単位チェックシステム

1）

では，各大学のカリ卒業単位チェックシステム導入の有用性が高い．

キュラムに合わせて，どの科目区分がどの科目区分の合計に算入されるのかを表した科目表を作成するだけで，自動的にその大学に合った単位チェックプログラムが作成される．科目表の作成において，階層の数を意識する必要はない．
プログラムのアルゴリズムとして，階層の数を反復アルゴリ
ズムで実装すると，階層の数が大学によって異なることが問題＊ 正会員 北九州市立大学文学部人間関係学科

図 1 卒業単位チェックシステム 1）の出力例
教授本稿では，以下のような用語の使い方をする．必要最低単位数は各科目区分で最低履修しなければならない単位数とする．また，開講科目数などによって認定される単位数の上限が決まっている場合，それを最大認定単位とよぶ．そして，ある科目区分の必要最低単位数がそれよりも下位の科目区分の必要最低単位数の合計と一致する場合，合計一致型とよび，そうでない場合を合計不一致型とよぶ．
合計一致型の場合，当該の科目区分で定められた

表 1 本稿で例として取り上げる架空の科目体系
必要最低単位数 最大認定単位
20
人文
440
社会
440
自然
440
1212
語学*
英語
88
独語
06
仏語
06
専門30
基礎
1016
実践
0
合計80
＊12単位までしか合計には参入できない
科目区分

教養

単位を超えて取得しても，超過分は合計に算入されない．合計一致型でなくても，合計に算入される単単位と定められているが，「独語」と「仏語」では最位数を限定している場合も，超過分が合計に算入さ低必要単位は定められていない．
「英語」は８単位まれないため，合計一致型と等価となる．このようなでしか取れないため，「独語」か「仏語」のいずれか場合を擬似合計一致型とよぶこととする．ここでは，で４単位取得の必要がある．あるいは「独語」２単合計の算入の上限を算入上限とよぶ．

位，「仏語」２単位でもよい．そのため，「語学」の合計一致型の場合，科目区分ごとに単位の充足判中では合計不一致型となっている．
「専門」は「基礎」定を行えばよいため，判定には比較的単純なアルゴ

10 単位以上であるが「実践」では必要最低単位数はリズムで実現できる．しかし，それが許されるのは定められておらず，合計不一致型となっている．

完全に合計一致型の場合だけであり，合計一致型と3.1 単位チェックの３段階判定

合計不一致型が混在している場合，合計不一致型と単位チェックでは，卒業に必要な単位を以下の３して考えて処理しなければならなくなる．合計不一段階で判定することとした．

致型の場合，当該の科目区分での取得単位数だけで・当該の科目区分において単位充足し，かつ，合計は単位の充足判定ができず，他の科目区分での取得単位数を満たすために取得する必要がない．
（○；単位数によって判定結果が変わってしまう．そのた

緑判定）

め，階層的な科目体系をバックトラックして，他の・当該の科目区分において単位が充足していないか，科目区分での単位の計算を行う必要があり，再帰的全体の合計単位数を満たすために必ず取得の必要プログラムの実装が必要となる．

がある．（×；赤判定）
・当該の科目区分においては単位が充足しているが，３．単位充足判定の概要全体の合計単位数を満たしてない．ただし，他の単位充足判定の説明のために架空の科目体系を用科目区分によっても合計単位数を満たすことが可いて説明する（表１）．「教養」，「語学」，「専門」の能であるため，当該の科目区分で必ずしも取得す３つの科目区分に分かれており，それぞれ必要最低る必要はない．（△；黄判定）

単位数は「教養」20 単位，「語学」12 単位，「専門」

合計一致型の場合，他の科目区分での単位取得状30 単位となっているが，合計では 80 単位必要であ況とは関係なく単位の充足判定ができるため，当該る．これは合計不一致型である．ただし「語学」のの科目区分で単位が充足しているかどうかの判定に単位は 12 単位までしか合計には算入できないようなる．そのため黄判定が生じることなく，あらかじになっている．そのため「語学」に関しては擬似合め定められた最低必要単位数との比較で赤判定か緑計一致型となっている．下位の科目区分をみると，判定かが決まってしまう．

「教養」は３つの分野（人文，社会，自然）に分か主として問題になるのは，合計不一致型の場合，れており，それぞれ最低必要単位は４単位で，それ緑判定か黄判定のいずれになるかの判定である．本らを合計しても「教養」で必要な 20 単位にはならず，システムを利用した判定結果例は図１に示した（実合計不一致型である．「語学」の場合，「英語」は８際は色表示を行っている）．判定には，他の科目区分

見込み単位数（p_max），最小見込み単位数（p_min）
max 最大認定単位
緑判定（○）
単位数の関係を図２に表した．合計一致型の場合，これら４つの変数は同じになるが，合計不一致型の場合，p_max 最大見込み単位

見込み数は動的に変化し，max と min の間で変化することになる．

黄判定（△）
p_min 最小見込み単位
赤判定（×）min 最低必要単位
は認定単位を表す

3.3 単位の充足判定のルール
２つの動的変数の導入によって，単位判定は以下のルールに集約される（図２）．

図２ ２つの動的変数と単位充足判定ルールの関係．認定単位の数によって判定が異なる．

・緑判定

最大見込み単位数以上の場合

・赤判定

最小見込み単位数に満たない場合の単位取得状況によって，どこまで単位を取る必要

・黄判定

最大見込み単位数未満で最小見込み単位があるのかの情報が必要となる．

数以上の場合．合計一致型の場合存在しない．

3.2

動的変数の導入

そこで，各科目区分ごとの単位の取得状況によって動的に変化する見込み単位数の上限と下限の値を上記のように２つの動的変数と実際に取得した認定単位の比較を行うことによって，判定を行うことができる．

算出することによって判定ができるようにした．
・最大見込み単位数 p_max

４．動的変数の算出アルゴリズム

合計不一致型の場合，合計単位数を満たすためにこれまで述べてきたように，単位充足判定においは，最低必要単位数以上の単位を取得しなければなては，動的変数の２つの値を算出することによってらない．その際，合計に算入される他の科目区分の判定が可能となる．最大の問題は動的変数をどのよ単位取得状況によって変化する．他の科目区分で多うに算出するかである．それは以下の３つのフェー

くの単位を取得していれば，少なくてよいが，他のズで行われる．

科目区分での取得単位が少ない場合は多く取得しな

4.1 第１フェーズ

p_min と p_max の静的設定ければならない．その見込み数を表すのが最大見込

p_min と p_max の値を，他の科目区分を考慮せずみ単位数である．取得単位数がこの値以上でなけれに仮設定を行う．設定はいずれの値も，認定されたば合計の単位数は充足しないことになる．

単位と最低必要単位の大きいほうとする．p_min は，・最小見込み単位数 p_min

最低でも最低必要単位をとることになるので，最低当該の科目区分で定められている最低必要単位数必要単位以上になる．ただし，先に述べたように，をまず満たさなければならない．したがって，最小すでに最低必要単位以上の単位を取得していれば，見込み単位数は最低必要単位数となる．ただし，す見込みとしては，それを下回ることはなく，すでにでに最低必要単位数を超えている場合，見込みとし取得した単位を p_min の値として設定する．てはその取得単位を下回ることはあり得ないため，一方，p_max は見込みとして最低でも最低必要単認定されている単位数が最小見込み単位数となる．

位を取るが，すでにそれを越えた単位を取っている

さらに，合計不一致型の場合，最大認定単位の設場合，見込みとしてはその値を下回ることがないた

定，算入上限などがあると，特定の科目区分で最低め，p_min と同様すでに取得した値を設定する．

必要単位数以上の単位を取得しなければならない場

図３には,次の第 2 フェーズでの更新前の第１フ合がある．あらかじめその点を考慮して必要最低単ェーズで設定した２つの動的変数の値を示している．

位数を設けてあればよいが，合計不一致型の場合，4.2

必要最低単位数を指定していない（０と見なす）場
合があり，その際は，最小見込み単位数を算出する必要がある．
最大認定単位(max)，最低必要単位数（min），最大第２フェーズ

他の科目区分での最小取得見込みを考慮した p_max の更新
合計不一致型の場合，当該の科目区分での最低必要単位を満たしただけでは，最終要件を満たさず，それ以上に取得しなければならない．ただし，他の科目区分で単位を多く取っていれば，その必要はない．そのため，他の科目区分での単位取得状況に応じて，当該20

必 最低必要単位
取 認定単位
見大 最大見込み単位数p_max
見小 最小見込み単位数p_min

人文の科目区分で最大何単位まで取ればよいのかを算出する．

2222

たとえば，「人文」の場合 10 単位を取得しており，必要単位は満たしている．

4

社会
必 20
取 16
見大 20
見小 20

38

残422

ところが,上位区分の「教養」20 単位は不足しており，さらに，全体の合計単位まで 30 単位残している．「人文」
でもさらに単位を取得すれば，この 30

自然max 40

2

必 4
取 2
見大 4
見小 4
残2単位残を減らすことができる．しかし，

英語max 8ないところがあり，それらの科目区分

必 80
取 50
見大 80
見小 80

では必ず単位増になるため，30 単位す

残30

他の科目区分で必要単位を満たしてい0

合計2180max 12

語学

べてを満たす必要はない．他の科目区

0max 12

独語かを算出すると，「自然」で２単位，「英語」で２単位，「専門」で８単位不足し仏語は合計を満たすのには使えない．したがって，「自然」の 2 単位と「専門」の26

26

る．仮に，この 20 単位をすべて「人文」でまかなうとすると，現在の認定 108

基礎
必 30
取 22
見大 30
見小 30単位に加算して最大で 30 単位を見込５である．この計算処理では，まず不足単位があって少なくとも何単位増え

残2max 6max 626

専門

８単位分が減じられ，残り 20 単位となリズムとして実装したのが，図４，図

必 8
取 6
見大 8
見小 8

必 0
取 0
見大 0
見小 0

での算入上限があり，ここでの２単位以上の計算処理を再帰的なアルゴ

240ている．ただし，｢英語｣の場合，「語学」

め，「人文」の p_max は 30 単位となる．

24

必 0
取 6
見大 6
見小 6

必 12
取 12
見大 12
見小 12

分で最小で何単位満たすことができる

max 40
必 4
取 4
見大 4
見小 4

単位は 50 単位しか取れておらず，80303020

教養

図３に具体的な算出の流れを示した．

max 40
必 4
取 10
見大 10
見小 10

残8
下位区分に継承する単位数
白ヌキはp_maxの更新となったもの
単位増の見込み数で上位に合計できる

max 16
必 10
取 12
見大 12
見小 12

4826

3816

実践
必 0取 10
見大 10
見小 1036

図３ 第２フェーズの最大見込み単位数(p_max)更新のための計算の流れるのかを科目区分ごとに算出する必要と「実践」での単位増は０でその合計も０である．

がある．それが図４のアルゴリズムである．まず当したがって，「専門」での単位増は８単位だけとなる．

該科目区分での増を算出する（①）．そして，当該科次に，p_max の更新を行うには，こうやって算出目区分の下位科目区分での増の合計を再帰的に最下される単位増の値を使って，最大何単位取得が見込層までたどって合計を行う（②）．下位単位増合計とめるかを階層の上から順番に再帰的に階層をたどっ当該科目増の大きい値がその当該科目区分での増分ていく．そのアルゴリズムが図５である．このアルになる（③）．たとえば，「専門」において当該科目ゴリズムでは同階層の科目区分に関して同時に処理の不足分は８単位である．その下位科目の「基礎」を行う．まず，上位から残単位を継承し，同時に上

p_max_update(科目区分，継承する不足単位数）④ 残り単位 ←Max(上からの継承，上位区分での不足）⑤ 当該区分での単位増の合計 self_sum

科目区分の数だけ繰り返す← sum_increase(科目，算入上限）
other_sum←0⑥

他の区分での単位増の合計 other_sum← other_sum+sum_increase(科目，算入上限）⑦ 不足単位 ←残り単位－other_sum
sum_increase(科目区分，算入上限）⑧ 取るべき単位 ←① 当該科目の増 ←Max(不足単位，self_sum）＋認定単位

Min(p_min，算入上限）－認定単位⑨ 取るべき単位
sum←0②

下位科目区分の数だけ繰り返すp_max ←
取るべき単位＞p_max

再帰呼び出しsum ← sum＋
sum_increase(下位科目，算入上限）⑩ 算入上限p_max ←
算入上限

＞p_max⑪ 最大認定単位p_max ←最大認定単位＞p_max
下位科目単位増合計 ←Min(sum，算入上限－認定単位）⑫③ return Max(下位単位増合計，当該科目増）

図４

少なくとも何単位増えるのかを合計するための再帰的アルゴリズム

p_max_update(下位科目，継承する不足単位数）

図５

再帰呼び出し最大見込み単位数(p_max)更新のための再帰的アルゴリズムの科目区分での不足分と比較し，大きいほうの値が学」では英語」の２単位があるが，算入上限の 12残り単位としてまかなう必要がある（④）．そして，単位を超えるので単位増にカウントされない．ここ

同階層の各科目区分でどれだけの単位増となるかをで，「専門」に着目すると，当該科目区分の単位増合

当該の科目区分（⑤）とそれ以外の科目区分（⑥）

計は８単位，他の科目区分の単位増合計は４単位とで別々に算出する．ここで，先ほどの図４のアルゴなる．残り単位 30 単位から他の科目区分の単位増合

リズムを利用する．他の科目区分の単位増は，残り計４単位を減じると 26 単位となる．この値と当該科単位を減じるのに使え，その残り分が不足単位とな目区分単位増の８単位を比較すると，26 単位が大きる（⑦）．そして，当該科目区分での単位増は取るべいので，この値とすでに認定されている 22 単位を加き単位として考えなければならない．上から継承し算した値 48 単位が「専門」における p_min の値となてきた不足単位と当該科目区分での単位増の大きいる．以下，この残り 26 単位を下に継承し，同様の処ほうの値が取るべき単位となる（⑧）．その値にすで理を行って，「基礎」や「実践」の p_min の値も更新に認定された単位を加えたものが，最大見込み単位される（図３）．

p_max となる（⑧，⑨）．ただし，算入上限(⑩)や最4.3

大認定単位（⑪）を超えないようにする必要がある．
そして，さらに，下位の科目区分でも同様の処理を行っていくために再帰的に行う（⑫）．

第３フェーズ

他の科目区分での最大取得見込みを考慮した p_min の更新
第２フェーズでは p_max の更新を行ったが，第３フェーズでは，p_min の更新を行う．第２フェーズ

具体例を用いて説明を行う（図３）．最上位の「合では，他の科目区分での単位の取得可能性の最低を計」では，上からの継承はないが，「合計」では 30考慮して当該の科目区分で最大の見込み単位を算出

単位不足しているため，残り単位 30 となる．その下したが，第３フェーズでは，他の科目区分での単位位科目の「教養」，「語学」，「専門」でそれぞれの単の取得が最大の可能性を考慮することになる．他の位増は「教養」４単位と「専門」８単位である．
「語科目区分で単位を最大限取得しても，まだ足りない可能性があった場合，足りない単位分は当該の科目区分で取得しなければならない．その単位数がどの程度である-38

必 最低必要単位
取 認定単位
見大 最大見込み単位数p_max
見小 最小見込み単位数p_min

人文20のかを計算して，当該科目区分での最小見込み単位数 p_min を更新する．

04-38

教養

アルゴリズムは第２フェーズの場合とほとんど同じで，単位増の算出の図４のアルゴリズムでは，当該科目の増

62

社会
必 20
取 16
見大 38
見小 20

を p_min から減じていたものを p_max残4から減じることに変更するだけである

2220

ムでは当該科目区分の算出（⑤）が無るだけである．

30

したが，実際に p_min の更新されるの

必 80
取 50
見大 80
見小 80

は「実践」の科目のみである．「実践」

残30

図６では具体例での計算の流れを示

max 40

22

必 4
取 2
見大 24
見小 4
残2

英語

max 8

2-62

0

max 12の場合上からの継承での残り単位が８

語学-2

科目区分の「基礎」からの単位増が最大で４単位でしかないため，差し引き

必 8
取 6
見大 8
見小 8
残2max 12

独語max 6
必 0
取 6
見大 6
見小 6

仏語

max 6

必 12
取 12
見大 12
見小 12単位であるのに対して，同階層の他の

必 4
取 4
見大 24
見小 4

自然0

合計

max 40-36（①）．p_max の更新の図５のプログラ
くなり，self_sum（⑤，⑧）が０とな

max 40
必 4
取 10
見大 30
見小 10-2４単位が残ってしまう．この値を認定

必 0
取 0
見大 0
見小 0

単位 10 単位に加えた 14 単位が p_minの更新の値となる．
8-32-18

専門５.考察
２つの動的変数を導入し，その算出を再帰的アルゴリズムによって実装で

30

基礎
必 30
取 22
見大 48
見小 30

きた．本プログラムの実現によって３

残826

段階の単位充足判定が可能となり，合計不一致型の体系であっても，どの科下位区分に継承する単位数
白ヌキはp_minの更新となったもの

目区分でさらに単位取得が必要である

最大の見込み増4

max 16
必 10
取 12
見大 16
見小 124

実践

26

必 0
取 10
見大 36
見小 10のかが簡単にわかるようになった．
ただし，他の科目区分に単位を流用

14

図６ 第３フェーズの最小見込み単位数(p_min)更新のための計算の流れするプログラムが十分に完成しておらず，今後さらに検討をする必要がある．また，現在のプログラムでは，各科目区分ごとに，他の科目区分で何単位取得する可能性があるのかを計算しており，一度算出した値を再度計算し直す形になっており，無駄な計算を無くすような工夫も必要である．

参考文献1)

松尾太加志: 汎用的な卒業単位チェックシステ
ム，教育システム情報学会第 34 回全国大会講演
論文集，in press, 2009.