IPAの失態と情報処理技術者試験の今後 〜応用情報処理技術者試験 午後 問２のアルゴリズムの問題点〜
情報処理推進機構（IPA）主催、２００９年秋期、情報処理技術者試験を解いてみた。
毎年、この時期は嫌いである。
今回はITパスポート、基本情報も含め、数多くの情報処理技術者試験を解かないといけないのだ。
とても面倒である。
そしてまた、年々受験者にゴマをするような出題をし、受験者数を稼ごうとするIPAの目論見が垣間見えるような問題が増える様子を見ることも耐え難い。
それで、応用情報技術者試験の午後問題を解いてみると、問２の問題で解きながらとても違和感を感じた。
効率的なアルゴリズムの紹介をしているのだが、どこをどう考えれば効率的なのかわからない。
最強のヒープソートを作ってまだ１年も経ってないのに関わらず、ボケてしまったのか？？？
IPAが効率的だというのだから効率的なのだろうと盲目的に信じて解いていくが、それでも効率的な部分をまるで見い出せない。
効率的と謳ってなければ、さほど難しい内容ではない。
けれど、解説されている文面からすると間違いのない答えと思えるのだが、効率的な要素が見当たらないため自分の導き出した答えは間違いであると判断する以外にない。
何度も繰り返し検証し、やはりIPAの求めている答えは「これ！」だろうと出した答えは、徹底的に非効率なアルゴリズムを作り上げた。
TACやiTecの速報とも同一の答えだったので、間違っているとは考えにくいが、TACやiTecでもこの非効率なアルゴリズムの指摘はなかった。
この１問の問題を解いた時点で１時間が過ぎていた。
応用情報技術者試験の午後問題は１５０分の中で６問を解かなければならない。
そう考えると、１問あたりに使える時間は２５分である。
１問で１時間も使ってしまえば落ちるに決まっている。
つまり、今回私が受けていれば、間違いなく落ちていたはずである。
それでは、ここで、内容をしっかり検証してみよう。
当該問題はここ
方法１のアルゴリズムは発見までに１２回のテキストとパターンの文字比較があり、代入処理は存在しない。
それに対し、方法２のアルゴリズムは「テキスト」と「パターン」の文字比較は８回だが、それ以前に「(1)表の作成」のための「パターン」と「チェック用パターン」の文字比較も行っている。
その処理を考えると P.length(P.length - 1)/2 回分のループ処理の中で、
if C[k]とP[j]が等しい or C[k]と" "が等しい
という形で、２つの文字比較が存在するので、「パターン」の文字数をユニークな５文字とすると、実際の回数は最低１０回、最大２０回となる。
ただし、初期設定で、配列Cに"
"が全て代入されていることを考えると、最低の１０回というケースは存在しないので、多くの文字列比較の出現が予想され、さらに２つの代入処理という比較
以上に処理を遅くする要素も存在しているため、さらなる処理の遅延が予想される。
スキップ数の決定においても、図にもあるように、最低１０回の「テキスト」と「チェック用パターン」との文字比較がここでも存在する。
さらにここでも、記載されたアルゴリズムにおいて、
if C[k]とT[i+P.length-1]が等しい or C[k]と" "が等しい
という形で、２つの文字比較が存在するので、実際の回数は処理系にもよるが最低でも１０回を必ず超える。
合計すると方法２は最低２４回を超える文字比較が存在し、さらにP.lengthの２倍以上の回数の代入処理も存在することになり、効率的な照合方法とはいえない。
設問３の「テキスト」と「パターン」で実際の処理状況を検討してみる。
or演算において「最初の式が真の場合に次の式を評価しない」という演算が最小限となる処理系で考えると、
まず、初期設定の段階で、６回の代入処理が発生する。
次に、表の作成において、６回の文字比較と、４回の代入処理が発生する。
文字の比較においては８回の文字比較が発生する。
スキップ数の決定においては１８回の文字比較と５回の代入処理が発生する。
合計で３２回の文字比較と１５回の代入処理が発生することになる。
ただし、無駄なループの制御変数への代入や演算を加えれば、それ以上の差となる。
効率的な照合どころか、とても非効率的な照合なのである。
それでは、実際にコードを書いてみよう。
gettime.hはここ
#include <stdio.h>mainのforループの中のp1が方法１で、p2が方法２のアルゴリズムを使った探索である。
#include "gettime.h"
int p1(char *,int,char *,int);
int p2(char *,int,char *,int);
int p1(char *t,int tl,char *p,int pl){//方法１（単純な照合方法のアルゴリズム）
int i;
int j;
for(i=0;i<tl-pl+1;i++){
for(j=0;j<pl;j++){
if(t[i+j]==p[j]){
if(j==pl-1)return i+1;
}else{
break;
}
}
}
return -1;
}
int p2(char *t,int tl,char *p,int pl){//方法２（効率的な照合方法のアルゴリズム・・・らしい）
int x;
int i;
int j;
int k;
char c[30];
int d[30];
int dd;
int b=0;
int bb=0;
for(x=0;x<pl;x++){
c[x]=' ';
d[x]=pl;
}
//(1):表の作成
for(j=0;j<pl-1;j++){
for(k=0;k<=j;k++){
if(c[k]==p[j] || c[k]==' '){
c[k]=p[j];
d[k]=pl-j-1;
break;
}
}
}
//文字列を照合する
i=0;
while(i<tl-pl+1){
//(2):文字の比較
for(j=0;j<pl;j++){
if(t[i+j]==p[j]){
if(j==pl-1)return i+1;
}else{
break;
}
}
//(3):スキップ数の決定
for(k=0;k<pl;k++){
if(c[k]==t[i+pl-1] || c[k]==' '){
dd=d[k];
break;
}
}
i=i+dd;
}
return -1;
}
int main(void){
int i;
char t[]="PICKLED_PEPPER"; //テキスト
char p[]="PEP"; //パターン
int tl=strlen(t); //テキストの文字数
int pl=strlen(p); //パターンの文字数
double st; //開始時刻（Start Timeの略）
double pt; //処理時間（Processing Timeの略）
st=gettime(); //開始時刻の取得
for(i=0;i<10000000;i++){
p1(t,tl,p,pl); //プロセス１を実行
// p2(t,tl,p,pl); //プロセス２を実行
}
pt=(gettime()-st)*1000; //処理時間の計算
printf("処理時間： %10.4f ミリ秒¥n",pt); //処理時間の表示
return 0;
}
この方法２を効率の良いアルゴリズムとして考えさせてしまったのである。
アルゴリズムがそれほど得意ではなく、違和感を感じずに解けたのなら問題はないが、アルゴリズムが得意な受験者の多くはきっと違和感を感じて時間を捨ててしまったことだろうと思われる。
アルゴリズムが得意な人ほど解けない問題なのだ。
中にはアルゴリズムが本当に苦手で解けなかった受験者もいるだろう。
その差をどう見るのだろう？
IPAはこの始末をどうつけるのだろう？
ITパスポートのように得点を水増しして合格者を増やすのか？
いずれにしても大問題である。
こんな試験を受けさせられる情報処理技術者の卵たちが可哀想である。
IPAが１日拘束するお金を支払って、アルゴリズムだけの再試験をやるくらいしか正当な再評価はできないだろう。
ただでさえ、午前を考えてもマネジメントとストラテジが４０％近く入ってしまい、情報処理技術者試験というよりは経営管理・経営戦略試験というような悲惨
な状態になっているのに関わらず、肝心の情報技術の問題がこれでは失態もはなはだしい。
今後の情報処理技術者の育成をどうして行くつもりなのだろう？
応用情報技術者試験の合格発表や模範解答開示はまだ先だが、どのように対応するのか寂しく見守ることにする。
ここでの文章、画像、検証結果などは全てDreamHopeに著作権があります。リンクに関してはTopLink、DeepLinkともに構いませんが、全部・一部の「学術論文等許諾の不必要な引用」以外の引用に関しては禁止します。
Copyright (C) 2009 DreamHope All Rights Reserved . Access: