応用情報技術者 2009年秋期午前2 問06

問題文

流れ図で表される処理を複数回実行した場合、途中に出現し得る実行順序はどれか。ここで、二重線は並列処理の同期を表す。

🖊️ 解答を隠して解いてみる

選択肢

ア：B→A→B→A

イ：B→X→A→Y（正解）

ウ：X→B→A→Y

エ：Y→X→B→A

🔒 解説は解答すると表示されます

並列同期の実行順序【午前2解説】

正解の理由

図中の二重線は「並列処理の同期点（フォーク／ジョイン）」を示します。矢印の向きに従って各U字経路を辿ると、左側U内では下側の処理が先に、次に上側の処理が実行される（左では B→A）ことが読み取れます。一方、右側U内は上段が先、下段が後に実行される（右では X→Y）ので、1回の並列実行における内部順序は左が B→A、右が X→Y になります。

同期（ジョイン）により「同じ回の両枝が中央の二重線で必ず揃ってから次の回に進む」ため、複数回実行したときに途中に現れる実行順序は、上記の2つの鎖（B→A と X→Y）を合成した順序（＝これらの順序制約を満たすマージ）に限られます。与えられた選択肢のうち、これらの制約を満たし、かつ図中の経路と矛盾しない並びはイの B→X→A→Y のみです。よってイが正解です。

解法ステップ

矢印の向きを確認し、各U字経路の「先に実行される箱」を決める。
- 左U：Uの底部から上へ戻る向きになっており、下段(B) が先、上段(A) が後 → B→A。
- 右U：進入方向が上から下で上段(X) が先、下段(Y) が後 → X→Y。
二重線の意味を確認する（並列実行の同期）。同一回の両枝は同期点で揃うため、「一回分の左・右の処理群（それぞれ順序を保つ）」がまとまって現れる。
したがって、可能な実行順序は B→A と X→Y を順序を崩さずに合成したもの（トポロジカルソート）に限られる。
各選択肢が上記制約を満たすか検証する。結果、選択肢のうち条件を満たすのはイのみである。

選択肢別の誤答解説

ア: B→A→B→A
- 問題は「複数回実行した場合に途中に出現し得る実行順序」を問うていますが、図の並列な右枝（X,Y）が毎回必ず実行され同期するため、左だけが連続して現れる形（B,A,B,A のみ）が出ることはない（右側処理のX,Yが割り込むはず）。また、選択肢自体が同一枝内順序を破る形ではないにしても、右枝の処理が全く現れていないので図の構造と整合しない。
イ: B→X→A→Y
- 左枝の内部順序 B→A を満たし、右枝の内部順序 X→Y も満たしている。矢印方向・U字経路の位置関係からこの合成順序は実行可能であり、同期の条件とも矛盾しないため正解。
ウ: X→B→A→Y
- 一見、左が B→A、右が X→Y の順序を保っているように見えますが、図中の矢印・経路の接続位置を辿ると、右の上段(X) が左の下段(B) より早く実行されるルートは存在しないため不可。すなわち、U字の進入・復帰点の位置関係により B が先に来る必要があるため、この順序は図の経路と矛盾する。
エ: Y→X→B→A
- 右枝内順序 X→Y を破っている（Y が先に来ている）ため不正解。

（補足：ウについては「単に枝内順序を満たす」だけでは可否を判定できず、図の矢印の向き・経路上の先後を正確に追う必要がある点に注意してください。）

よくある誤解

矢印や箱の上下配置だけで「上が先／下が先」と決めつける誤解。重要なのは矢印の向き（経路の辿り方）で、U字の進入方向によって上下の実行順序が逆になることがある。
「枝内順序を保てばどの並びも可能」と誤解すること。並列の同期点や経路上の相対位置（どの処理が先に中央に戻るか）がさらに制約を与えるため、単純なトポロジカル合成だけで済まない場合がある。

補足コラム

並列処理図の読み取りは「局所的な順序（各枝内）」と「グローバルな同期・接続関係（フォーク／ジョインやループの入口・出口）」の両方を確認することが肝心です。特にU字やループ形状では「どちら方向に矢印が流れているか」を丁寧に追い、各ノードが「先に実行される側か後に実行される側か」を決める習慣をつけるとミスが減ります。

FAQ

Q. 矢印が小さくてどちら向きかわからない場合は？
A. 矢印が不鮮明なら「箱間の細線の接続順」「U字の折れ返し方向」「中央との結合点の向き」を総合して推定します。試験では図中に必ず一貫した向きが示されているので、全体を俯瞰して矛盾がない向きを選んでください。

Q. 同期点があると「必ず同時に実行開始／終了する」のか？
A. 同期（ジョイン）は「次工程に進む前に全ての並列枝が到達すること」を要求します。開始（フォーク）は同時に枝が分岐しますが、枝内の実行速度や経路長により各枝の各要素は時刻的にずれるため、見かけ上は混在した並びになることがあります。ただし“同じ回”の処理群が次の回の処理より前に完了することは保証されます。

関連キーワード: 並列処理、同期（ジョイン／フォーク）、フローチャート、トポロジカルソート、実行順序解析