順列・組合せとは？

順列・組合せの意味

n個からr個を取り出すとき、並べる順序を区別するのが順列 nPr＝n!/(n−r)!、区別しないのが組合せ nCr＝n!/{r!(n−r)!}。場合の数の見積りや計算量の評価で使う。

順列・組合せの具体例

n人が総当たりで対戦する組合せは nC2＝n(n−1)/2。8人なら28通り。n×nの表で i>j となる要素の個数も同じ式で求まる。

順列・組合せは試験でどう引っ掛けられる？

「総当たり」「ペアを作る」はほぼ必ず nC2。順列で計算して2倍の値を選ばせる選択肢が用意されていることが多い。

順列・組合せと関連する用語

• 期待値
• 待ち行列理論

順列・組合せが出た過去問

• DBMSをシステム障害発生後に再立上げするとき、ロールフォワードすべきトランザクションとロールバックすべきトランザクションの組合せとして、適切なものはどれか。こ…

  正解：ロールフォワード：T2，T5／ロールバック：T6

  要点：CP後のコミット済みは前進、未コミット更新は後退復帰

  再立上げ時は、チェックポイント以降にコミットされたトランザクションをログから前進復帰（ロールフォワード）し、障害時点で未コミットのものを後退復帰（ロールバック）する。チェックポイント前にコミット済みのT1は既に反映されているため対象外、更新を伴わない読取りだけのT3・T4は取り消す変更がないためロールバック不要である。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問10（IPA）

• 並列処理方式であるSIMDの説明として，適切なものはどれか。

  正解：単一命令ストリームで複数のデータストリームを処理する方式

  要点：フリンの分類、SIMDは1命令を複数データに一斉適用する

  フリンの分類では命令ストリーム数とデータストリーム数の組合せで並列処理方式を分ける。SIMD（Single Instruction Multiple Data）は1つの命令を複数のデータに同時に適用する方式で、ベクトル演算やGPU、マルチメディア拡張命令に使われる。単一命令・複数データという名称そのものが定義である。

  出典：平成28年度 春期 高度共通_午前I試験 am1 問4（IPA）

• 関係R（ID, A, B, C）のA, Cへの射影の結果とSQL文で求めた結果が同じになるように、aに入れるべき字句はどれか。ここで、関係Rを表Tで実現し、表T…

  正解：DISTINCT

  要点：関係の射影は重複を除く集合演算、SQLではDISTINCTが必要

  関係モデルの射影は結果を集合として扱うため、重複する組は取り除かれる。表TのA、C列を取り出すと同じ組合せが重複して現れるので、SQLでは重複行を除くDISTINCTを指定しないと射影の結果と一致しない。SQLの既定はALLで重複をそのまま残す。

  出典：平成29年度 秋期 高度共通_午前I試験 am1 問9（IPA）

• 1桁の2進数A, Bを加算し、Xに桁上がり、Yに桁上げなしの和（和の1桁目）が得られる論理回路はどれか。

  正解：論理回路ア

  要点：半加算器は桁上げ＝AND、和＝XORで構成する

  1桁の2進数2つを加算する回路は半加算器であり、桁上げ（キャリー）Xは両方が1のときだけ1になるので論理積（AND）、桁上げなしの和Yは入力が異なるときだけ1になるので排他的論理和（XOR）で得られる。真理値表で確認すると、1+1＝10（X=1, Y=0）、1+0＝01（X=0, Y=1）、0+0＝00となり、この組合せが成り立つ。

  出典：平成30年度 秋期 高度共通_午前I試験 am1 問7（IPA）

• データベースシステムにおいて、二つのプログラムが同一データへのアクセス要求を行うとき、後続プログラムのアクセス要求に対する並行実行の可否の組合せのうち、適切なも…

  正解：後続共用×先行共用=○、後続共用×先行排他=×、後続排他×先行共用=×、後続排他×先行排他=×

  要点：共用ロック同士だけ並行可、排他が絡めば必ず待ち

  データベースのロックでは、共用（共有）ロックは読取り同士なので複数のプログラムが同時にかけられるが、排他ロックは更新のためのもので、他のどのロックとも両立しない。したがって「先行も後続も共用」の組合せだけが並行実行可能で、どちらかに排他が含まれる残り3通りは待たされることになる。

  出典：平成30年度 秋期 高度共通_午前I試験 am1 問10（IPA）