並列処理のフロー
並列処理のフロー出題分類：アルゴリズムとプログラミング > アルゴリズム
［出題：平成21年秋／AP午前問6］
並列処理の同期タイミングの直後にある双方の処理に注目！
正解は「イ」
これで解ける
1回1回の並列処理は、AまたはXで始まり、BまたはYで終わることが図から分かります。したがって、B、Yの次のA、Xは新たな回の開始を示します。また、1回の処理の中では、A→Bの順とX→Yの順は保持されます。このことに注目して、選択肢を見てみます。
- 選択肢ア
- B→（同期）→A→B→（同期）→Aと、2回の同期の間にX、Yが実行されていないため誤り。
- 選択肢イ
- B→（同期）→X→A→Yで成立するため正解。
- 選択肢ウ
- 同期の位置は、Aの前かXの前なので、次の2つが考えられる。
- （同期）→X→B→A→Yでは、B→Aなので誤り。
- X→B→（同期）→A→Yでは、同期前Xの後にYがなく、同期後Yの前にXがないので誤り。
- 選択肢エ
- 同期の位置として、次の2つが考えられる。
- Y→（同期）→X→B→Aでは、同期後B→Aなので誤り。
- Y→X→B→（同期）→Aでは、同期前Y→Xなので誤り。
以上から、「イ」が正解となる。
表の構成法と探索手法の組み合わせ
表の構成法と探索手法の組み合わせ出題分類：アルゴリズムとプログラミング > アルゴリズム
［出題：平成25年春／AP午前問5］
2分探索はソート済み。線形探索は並び順自由。ハッシュ探索は一発で発見（シノニムあり）。
正解は「ア」
理解を深める
2分探索は整列済みであることが条件です。したがってaのコード順に格納した探索表で利用しなければなりません。
線形探索は常に表の先頭から検索を行います。そのため、bの使用頻度順に格納された表であれば検索効率が良いといえます。
ハッシュ表探索は、探索対象のキー値を利用してハッシュ関数によって求められた位置を検索します。そのため、cのコードから一意に決まる場所に格納した探索表で利用すると検索効率が良いといえます。
平均比較回数を求める式（線形探索）
平均比較回数を求める式（線形探索）出題分類：アルゴリズムとプログラミング > アルゴリズム
［出題：平成24年春／AP午前問9］
線形探索の平均比較回数は「(N＋1)／2回」。
（Nが十分に大きい場合にはN／2回）
正解は「イ」
理解を深める
平均比較回数は、最小比較回数と最大比較回数の和を2で割ることで求められます。線形探索の場合、最小比較回数は1、最大比較回数は要素数となります（ただし、要素数が十分に大きい場合、最小比較回数の1は計算から除かれます）。
では、問題文の平均比較回数を求めます。まずn個のデータをm個ごとのブロックに分割するということで、ブロックの数はnmになり、ここで探索する場合の平均比較回数はn2mとなります。次にブロック内を線形探索しますが、このときの要素数はmです。そのため、平均比較回数はm2となります。そのため、合計の平均比較回数はm2＋n2mとなります。したがって、正解は「イ」です。
ハッシュ表によるデータの衝突条件
ハッシュ表によるデータの衝突条件出題分類：アルゴリズムとプログラミング > アルゴリズム
［出題：平成23年秋／AP午前問5］
計算式は、小さい具体値を埋めてみよう。
正解は「イ」
理解を深める
このような計算式が提示された問題は、具体的な数字を入れた表を作り、関係性を導き出すほうが早く正答に近づくことができます。ここではn＝4でxを1～9として、表を作成してみます。
この表から4つおきに衝突が発生していることが分かります。そのため、キー値の差がnの倍数であるときに衝突が発生することが分かります。したがって、正解は「イ」となります。
おわりに
今回取り上げた問題のキーワードは、以下のとおりです。
- M/M/1の待ち行列モデルの条件
- 相関係数
- 結果が等しくなる2つのアルゴリズム
- アルゴリズム
- 並列処理のフロー
- 表の構成法と探索手法の組み合わせ
- 平均比較回数を求める式（線形探索）
- ハッシュ表によるデータの衝突条件
解説からもわかると思いますが、アルゴリズムの問題は、正答にたどり着くまでに比較的時間がかかります。問題を見て、解けるきっかけが全く見つからないと感じたら、その問題は後回しにして、他の問題に取りかかるという判断も必要かもしれません（きっかけが見つかるとさらっと解けるとは思うのですが……）。
午前問題では1問1問の解答スピードが問われます。トレースに時間のかかるアルゴリズムの問題も、暗記していれば解ける用語の問題も、同じ1問です。ここで取り上げたスピードアンサーを使って、うまく解答のきっかけを見つけ出す力を身につけてください。
