基本情報平成27年秋期の良問、文字列比較アルゴリズムBM法

2015年秋の基本情報はものすごい良問が出題されました。

事前の知識を必要とせずにその場で考える頭さえあれば解答できるという素晴らしい問題です。

例えば「英国で議院内閣制の原型をつくった第一大蔵卿の名前を答えよ」なんて問題がでても、これはいくら試験中に考えても知らなければ解けないわけです。ですが基本情報で出題される問題は「知らないと解けない」という側面が他の情報処理技術者試験の試験種より少ないのが良いところです。

そして2015年秋の基本情報では近年稀に見る良問が問8の「データ構造及びアルゴリズム」で出題されました。

理系で情報科学や情報工学を専攻してない人にとっては、なんだこれはというのが率直な感想でしょう。必須問題だけど飛ばしたくなった人もいるかもしれません。

逆に、こういった分野を専攻してきた人にとっては「おおこれを出題してくるか。IPAも枯れてないな。」と思わせる出題です。IPA(情報処理推進機構)の中にも侍がいると思わせます。

 

大学でアルゴリズムを勉強したことのある人なら、文字列比較アルゴリズムはソートと同じくらいしっかりやらされていると言っていいでしょう。

文字列比較アルゴリズムはソートに比べればバリエーションが少なく、原始的な力ずく法(brute force)、KMP法、BM法 この3つくらいです。

このKMPですらかなり頭を回転させないと理解すらできません。よく言われる有名な話が、このKMPアルゴリズムを理解できなかったために、単純に1文字ずつずらしていくという誰でも思いつく「力ずく法」の実装で妥協してしまった技術者がいるという逸話です。

はっきりいって私もBM法の具体的アルゴリズムなんて忘れていました。基本情報はマークシートだからいいですが、白紙の解答用紙に具体的手順を書けと言われてもかけなかったでしょう。親切な誘導があったからこそ問題が解けるといえます。とはいえ一度もやったことのない人にとってはきつく、試験時間中のリソースを相当消費しないと満点は難しいでしょう。逆に一度やったことがあれば「そういえばこんな感じだったな」と少しずつ思い出しながら文字列比較アルゴリズムの復習ができる点でおもしろい問題です。

そういった意味ではIPAもなかなか粋なことをしてきたと言えます。

情報科学や情報工学といった数学を重視したアカデミックな勉強をしてこなかった人には正直”酷”と言える出題かもしれません。

もしIPAがそういった分野を専攻してきた人に下駄を履かせるような意図があったとしたら、はやり基本情報は大学生などのアカデミック分野に身を置いている人こそ取って欲しい、そういった人でないと合格が難しいような問題を出題するというIPAの意思が見て取れると言えます。