第１部　コンピュータ科学基礎

平成8春 1K 問5

アルゴリズムの計算量を表す方法の一つに、O記法(O-notation)がある。これは、問題のサイズを大きくしていったときの、漸近的計算量を示すものである。いま、サイズnの問題の計算量を表す関数F(n)がF(n)=2ⁿ+n²のとき、この関数のO記法はどれになるか。

ア　O(log₂n)
イ　O(n)
ウ　O(nlog₂n)
エ　O(n²)
オ　O(2ⁿ)

解答 オ

オーダに関する増加率の大きさには以下の関係がある。

O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n^c)<O(cⁿ)<O(n!)　(cは定数)

計算量のO記法は、定数や係数を除外して、最も増加率の大きい項だけで表す。

1999/10/24
そろそろバイクシーズンも終わり…

平成10春 1K 問7

集合Sの部分集合AとBがあるとき、A∩Bに等しいものはどれか。ここで、A、BはそれぞれA、BのSに対する補集合、X-Yは集合Xと集合Yの差集合を表している。
（注：Netscapeだとオーバーラインが出ないみたいなので、赤い文字のところは上に線があると思ってください。）

ア　(A∪B)-(A∩B)
イ　(S-A)∪(S-B)
ウ　A-B
エ　S-(A∩B)

解答 ウ

差集合：A-B = A∩B
(Aの補集合を取れば、問題と等しくなる。→A-B = A∩B)

ア：(A∪B)-(A∩B) = S-(A∩B)-(A∩B) = S-(A∩B) = エ
イ：(S-A)∪(S-B) = S-(A∩B) = エ ←分配法則

1999/08/14
Netscapeでオーバーライン出す方法ってあるのかな？

平成10秋 AE 問1

1ビットのパリティビットと７ビットのコードからなる8ビットのデータで、データの誤りが発生したときの記述として、適切なものはどれか。

ア　１ビットの誤りのときだけ、誤りを復元できる。
イ　誤りを復元することは、不可能である。
ウ　誤りを復元できるかどうかは、不明である。
エ　奇数ビットの誤りのときだけ、誤りを復元できる。

解答 イ

パリティビット

ビット列に対して１の個数が偶数（または奇数）となるように付加する。どのビットが誤りであるかは特定できないので、復元はできない。また、誤りが偶数個発生した場合は、検知もできない。

1999/07/31

平成10秋 2K 問2

五つの選択肢の中から正しいものを二つ選ぶ問題がある。解答者が無作為に二つを選んだ場合、二つとも正解である確率はいくらか。

ア　1/25
イ　1/20
ウ　1/10
エ　4/25

解答 ウ

順列

異なるn個のものからr個とって1列に並べたものを、n個のものからr個とった順列といい、その総数をnPrで表す。

組合せ

異なるn個のものから、順列を問題にしないで、r個とって1組としたものをn個のものからr個とった組合せといい、その総数をnCrと表す。

nPr = n(n-1)(n-2)…(n-r+1) = n!/(n-r)! (r個の積)
特にn=rのときに、nPr = n!

nCr = nPr/r! = n(n-1)(n-2)…(n-r+1)/r! = n!/(n-r)!r!

五つの選択肢から二つ選ぶ組合せ：nCr = ₅C₂ = ₅P₂/2! = 5*4/2 = 10
１０通りの中で、正解は1組だけだから 1/10

Updated 1999/08/01
この公式を調べるために、高校の問題集を買ってしまった
1999/07/21

平成8春 1K 問32

プログラム言語を手続き型、関数型、論理型、オブジェクト指向に分類したときの、正しい組み合わせはどれか。

解答 オ

手続き指向型プログラミング言語

手続き型：Fortran, COBOL, BASIC, Pascal, Ada

プログラムの命令を逐次与えながら一連の処理を実行する。

問題指向型プログラミング言語

関数型：LISP

関数を記述するプログラム。LISPはリスト構造を用いた処理に適した言語。

論理型：Prolog

宣言を記述するプログラム。Prologにはユニフィケーション（パターンマッチング）とバックトラッキング（自動検索）の機構がある。

オブジェクト指向：Smalltalk

データ主導の考え→データの抽象化や情報隠蔽化。

1999/07/19
LISPのソースってかっこだらけ

高度共通午前目次へ