Comments
Description
Transcript
テクノロジ系
Ｐａｒｔ.１ テクノロジ系 １．基礎理論 ０１ 基数変換 日常、私たちが使用している数の表現方法は、10 進数といい、０∼９の数字を使い 10 で桁上がりします。このとき、10 を基数と呼び、ｎ桁の整数は、一般に次のような意味を 持ちます。なお、ａ１∼ａｎは０∼９までの整数です。 ａｎａｎ-１…ａ３ａ２ａ１ ＝ａ１×10０＋ａ２×10１＋ａ３×10２＋…＋ａｎ-１×10ｎ−２＋ａｎ×10ｎ−１ また、ｎ桁の小数は、一般に次のような意味を持ちます。 0.ａ１ａ２ａ３…ａｎ-１ａｎ ＝ａ１×10−１＋ａ２×10−２＋ａ３×10−３＋…＋ａｎ-１×10−(ｎ−１)＋ａｎ×10−ｎ ① ｎ桁の整数を一般式で表現する。 例 1234＝４×10０＋３×10１＋２×10２＋１×10３ ② ｎ桁の小数を一般式で表現する。 例 0.1234＝１×10−１＋２×10−２＋３×10−３＋４×10−４ 10 進数（例） １．基数変換 １）10 進数からｎ進数へ 10 進数をｎ進数に変換する場合、整数部は基数ｎで割っていき、小数部は基数ｎを掛 けていきます。 例 (43)10 を４進数に変換する。 １．(43)10 を変換後の基数４で割り、商と余りを求める。 ２．上記 1 の商を基数４でさらに割り、商と余りを求める。これを商が０になるまで 繰り返す。 ３．除算の余りを計算とは逆の順番に並べる。 43÷４＝10 余り ３ 10÷４＝２ 余り ２ ２÷４＝０ 余り ２ (43)10＝(223)４ 10 進数からｎ進数へ（例） -2- ２）ｎ進数から 10 進数へ ｎ進数を 10 進数に変換する場合、ｎ進数の各桁に重み付けを行います。 例 (123.64)８を 10 進数に変換する。 １．整数部は下位の桁から順に８の０乗，１乗，２乗，…、小数部は上位の桁から順 に８の−１乗，−２乗，…の重み付けを行う。 ２．重み付けをした結果を加算する。 １ ２ ３． ６ ４ × × × × × ８２ ８１ ８０ ８-1 ８-2 ↓ ↓ ↓ ↓ ↓ 64 ＋16 ＋３＋0.75＋0.0625＝83.8125 (123.64)８＝(83.8125)10 ｎ進数から 10 進数へ（例） 例題１−１ ソフトウェア開発 平成 11 年春 問１ Ｒ進数ＸをＸＲと表すとき，Ａ９16＋Ｂ５16 の結果として，正しいものはどれか。 ア 101010110２ イ 436８ ウ 516８ エ 536８ 解答−エ 16 進数で表現された A9 と B5 を 10 進数に変換し、その和を求めます。 A916＝10×16１＋９×16０＝16910 B516＝11×16１＋５×16０＝18110 A916＋B516＝16910＋18110＝35010 求めた 10 進数を８進数に変換します。 350÷８＝43…６ 43÷８＝５…３ ５÷８＝０…５ よって、A916＋B516＝536８となります。 ここで演習１−１から１−４を解いて下さい -3- ２．有限小数と無限小数 有限桁の数字で表される小数を有限小数といい、有限小数では正確に表現できない小数 を無限小数といいます。代表的な無限小数に、円周率があります。 10 進数で有限小数である数も、２進数や８進数、16 進数では必ずしも有限小数になる とは限りません。例えば、10 進小数 0.8 を２進数に変換すると、 0.8＝0.5＋0.25＋0.03125＋0.015625＋… １ ２ ５ ６ 1 1 1 1 ＝ ＋ ＋ ＋ ＋… 2 2 2 2 と、１/２のべき乗をいくら加算しても 0.8 とはならず、有限小数では表現できません。８ 進数、16 進数で表現する場合も、同様になります。 例題１−２ ソフトウェア開発 平成 14 年春 問２ 基数変換に関する記述のうち，正しいものはどれか。 ア ２進数で有限小数である数は，10 進数でも必ず有限小数になる。 イ ８進数で有限小数である数は，２進数では必ずしも有限小数にならない。 ウ ８進数で有限小数である数は，10 進数では必ずしも有限小数にならない。 エ 10 進数で有限小数である数は，８進数でも必ず有限小数になる。 解答−ア 10 進小数を２進数で表現する場合、１/２のべき乗数の加算で表します。例えば、10 進 小数 0.75 を１/２のべき乗数の加算で表現した場合、 0.75＝0.5＋0.25＝１/２＋１/４＝(１/２)１＋(１/２)２ で、２進数では 0.11 と有限小数で表現されます。 しかし、10 進小数の 0.8 を１/２のべき乗数の加算で表現しようとしても、 0.8＝0.5＋0.25＋0.03125＋0.015625＋… ＝(１/２)１＋(１/２)２＋(１/２)５＋(１/２)６＋… と、１/２のべき乗をいくら加算しても有限小数では表現できません。 同様に、10 進小数を８進数で表現するには、その数値を１/８のべき乗の加算で考えて いけばよいのですが、２進数と同様に、１/８のべき乗をいくら加算しても有限の範囲で表 現できない数値があります。このように、10 進小数のほとんどが、２進数、８進数では無 限小数になってしまいます。逆に、２進数、８進数の有限小数は、10 進数でも必ず有限小 数となります。 ここで演習１−５、１−６を解いて下さい -4- ３．桁数 10 進数ｎ桁で表現できる値を、２進数に変換した場合、２進数の桁数ｍは、10 進数の 桁数ｎの約３倍となります。例えば、10 進数２桁の最大値 99 を２進数に変換した場合、 1100011 と７桁の数になります。 概ね、10 進数の桁数ｍと２進数の桁数ｎの関係は、次の式で表されます。 ｎ≒ｍlog10２ 例題１−３ 基本情報 平成 19 年春 問２ 正の整数の 10 進表示のけた数Ｄと２進表示のけた数Ｂとの関係を表す式のうち， 最も適 切なものはどれか。 ア Ｄ≒２log10Ｂ イ Ｄ≒10log２Ｂ ウ Ｄ≒Ｂlog２10 エ Ｄ≒Ｂlog10２ 解答−エ 10 進数Ｄけたで表現できる最大値は 10D−１、２進数Ｂけたで表現できる最大値は２B−１ ですので、次の関係式が成立します。 10D−１≒２B−１ 10D≒２B 選択肢が対数（log）の形式で表現されているので、両辺の関係を崩さぬように log を用 いた式に変換すると、log1010Ｄ≒log10２Ｂとなります。 log1010ＤはＤlog1010、log10２ＢはＢlog10２に置き換えられます。また、lognｎは１になり、 log1010 が１となるので、Ｄ≒Ｂlog10２となります。 ここで演習１−７、１−８を解いて下さい -5- ０２ 数値表現 １．浮動小数点数 コンピュータで実数を表現する際に利用する形式が、浮動小数点数です。 浮動小数点数は、小数点の位置を一定にしないで、別に小数点の位置を指示する数を併 記する方法です。具体的には、数値Ｘを「Ｘ＝Ｍ×ＢＥ」のように指数の形で表現します。 なお、Ｍを仮数、Ｂを底又は基数、Ｅを指数といいます。底には、一般に２又は 16 を使 用します。 しかし、小数点の位置を一定にしないので、同じ数値でも指数と仮数を調整すれば幾通 りにも表現が可能です。表現方法を統一するには、数値の最上位桁が小数点のすぐ上か下 に来るように小数点の位置を調整する必要があります。この動作のことを正規化といいま す。なお、正規化を行うことで有効数字の範囲を最大に保つことができます。 例 次の形式の浮動小数点数で(100)10 を表現する場合（底を２とした場合） Ｓ １ビット Ｅ ７ビット ▲ Ｍ 24 ビット Ｓ…仮数部の符号（正は０，負は１） Ｅ…指数 ２のべき乗で、負数は２の補数 Ｍ…仮数部の絶対値 …小数点 １．(100)10 をＭ×ＢＥの形式に変換する。 (100)10＝(01100100)２＝(01100100)２×２０ ２．仮数部の値が１／２≦Ｍ＜１の範囲に入っていない場合は正規化を行う。 (01100100)２×２０＝(0.11001)２×２７ ３．(0.11001)２×２７ Ｓ 0 Ｅ Ｍ 000 0111 1100 1000 0000 0000 0000 0000 浮動小数点数の計算（例） -6- 例題１−４ ソフトウェア開発 平成 18 年春 問１ 次の浮動小数点表示法がある。小数点は仮数の左にあり，指数は 64 の 下駄履き表現 であって，値は(−１)ｓ×0.f×２ｅ−64 である。二つの 16 進数 45BF0000 と 41300000 を，こ の浮動小数点表示法で表現された値として加算した結果はどれか。 31 30 ｓ 24 23 ０ ｅ ｆ 仮数部 指数部 符号 （正：０，負：１） ア 41EF0000 イ 45C20000 ウ 45EF0000 エ 86EF0000 解答−イ 二つの 16 進数を(−１)ｓ×0.f×２ｅ−64 の形に変換した後、加算を行います。 まず、45BF0000 を変換すると、 0.101111110000000000000000×２５ となります。 次に、41300000 を変換すると、 0.001100000000000000000000×２１ となります。 変換した二つの値を加算します。ただし、指数部の値が異なっていた場合、そのままで は計算できないので、指数を揃える必要があります。ここでは、二つ目の値の指数部を ２５にして加算を行います。 0.101111110000000000000000×２５＋0.000000110000000000000000×２５ ＝0.110000100000000000000000×２５ この結果を問題の図の形式に変換すると、イの 45C20000 となります。 ここで演習１−９から１−11 を解いて下さい -7- なお、底が２で、最上位ビットが仮数部の符号ビット（０は正，１は負） 、指数部が７ビ 、仮数部が 24 ビットの浮動小数点数において表示可能 ット（負数は２の補数方式で表示） な範囲は、次のとおりです。 負の最小値：(BFFFFFFF)16 ＝ −２63×(１−２−24) 負の最大値：(C0000001)16 ＝ −２−64×２−24 ＝ −２−88 正の最小値：(40000001)16 ＝ ２−64×２−24 ＝２−88 正の最大値：(3FFFFFFF)16 ＝ ２63×(１−２−24) −２63×（１−２−24） −２―88 ２―88 ２63×（１−２−24） ０ 表現不能 表現可能 表現不能 表現可能 表現不能 表現可能な範囲（例） ２．誤差 コンピュータは計算処理を有限の桁数で行うので、実数を扱うほとんどの計算では誤差 が生じます。その結果、計算によって求めた数値には、有効な桁と有効でない桁が含まれ ていることになります。 １）有効数字と有効桁 有効な桁を「有効数字」といい、その桁数を「有効桁数」といいます。 例） 数値例 有効桁数 1234 ４ 12.30 ４ 0.012 ２ 1200 ４又は２※ ※1.200×10３とすれば有効桁数４桁、 1.2×10３とすれば有効桁数２桁。 -8- ２）計算結果の有効桁数 計算処理において、計算対象となるそれぞれの数値の有効桁数が異なる場合には、以 下の規則に従って結果の有効桁数が決まります。 ①和、差の場合 結果の有効桁の末位（右端の桁の位）は、計算に使用された数値の中で末位が最高 のものと同じになります。 例）123.45＋10.1＝133.55 123.45 ：末位の桁の位は 10−２ 10.1 ：末位の桁の位は 10−１ 10−２＜10−１なので、結果の末位は 10−１となる。 よって、123.45＋10.1≒133.5（有効桁数４桁） ②積、商の場合 結果の有効桁数は、計算に使用された数値の中で有効桁数が最小のものと同じにな ります。 例）123.4×1.2 =148.08 123.4 ：有効桁数４桁 1.2 ：有効桁数２桁 ４＞２なので、結果の有効桁数は２桁となる。 よって、123.4×1.2≒150＝1.5×10２（有効桁数２桁） 例題１−５ ソフトウェア開発 平成 14 年春 問４ ６桁の有効数字をもつ数値Ａと，２桁の有効数字をもつ数値Ｂに対する四則演算の結果 を端数処理することにした。計算結果に対する有効数字の評価として，正しいものはどれ か。 ア Ａ＋Ｂを行った結果の有効数字は６桁である。 イ Ａ−Ｂを行った結果の有効数字は６桁である。 ウ Ａ×Ｂを行った結果の有効数字は２桁である。 エ Ａ÷Ｂを行った結果の有効数字は３桁である。 -9- 解答−ウ 有効数字は、 示されている数字のうち、 何桁目までが有効なのかを表す数字のことです。 有効数字の計算ルールは、次のとおりです。 ①加減算を行った結果の有効桁の末位（右端の桁の位）は、計算に使用された数値の中で 末位が最高のものと同じになります。 例 1.23456（有効数字６桁）＋87（有効数字２桁）＝88（有効数字２桁） 123,456（有効数字６桁）−1.2（有効数字２桁）＝123,455（有効数字６桁） ②乗除算を行った結果の有効桁数は、計算に使用された数値の中で有効桁数が最小のもの と同じになります。 例 1.23456（有効数字６桁）×3.4（有効数字２桁）＝4.1（有効数字２桁） 3.45678（有効数字６桁）÷1.2（有効数字２桁）＝2.8（有効数字２桁） ３）誤差の評価 誤差の大きさを見積もる方法には、相対誤差と絶対誤差の２種類があります。 名称 相対誤差 意味 真値に対する割合で示した誤差 ｜真値−近似値｜／｜真値｜ 真値が不明である場合には、 ｜測定値−近似値｜／｜測定値｜ 絶対誤差 真値との差の絶対値 ｜真値−近似値｜ 真値が不明である場合には、 ｜測定値−近似値｜ ４）誤差の種類と発生原因 代表的な誤差の種類とその発生原因を以下に示します。 ①丸め誤差 例えば１÷３＝0.33333…のように、コンピュータが記憶可能な桁数を超える計算 では、ある桁の次の桁以降に対して、切捨て、四捨五入、切上げなどの端数処理が行 われます。端数処理を行うことを「丸める」といい、このとき真値との間に生ずる誤 差を「丸め誤差」といいます。 ②打切り誤差 数学的には、次の式のように∞（無限大）の計算を含むものがあります。 ∞ ∫ sin x dx 0 これを数値計算によって求める場合、無限回の計算を行うことはできないので、あ - 10 - る時点で計算を止める（打切る）必要があります。このとき真値との間に生ずる誤差 を「打切り誤差」といいます。 ③桁落ち 絶対値がほぼ等しい同符号の数値の減算、又は異符号の数値の加算において、有効 数字の上位桁が相殺されてなくなり、有効桁数が減少することを「桁落ち」といいま す。 123.456 有効桁数６桁 −123.454 有効桁数６桁 0.002 有効桁数２桁 なお、桁落ちの本質的な問題点は、 「有効桁数の減少により、結果的にほとんど誤差 のみになってしまう」ことです。上記の例における 123.456 と 123.454 のどちらの値 も丸められていた場合、各数値自体に占める誤差の割合は 10−５（＝0.001％）程度で すが、減算の結果（0.002）は 100％誤差となります。 ④情報落ち 絶対値が著しく異なる数値の加算、又は減算においては、小数点の位置が揃うよう に絶対値の小さい数値を調節してから計算が行われます。この時、調節された値が有 効桁数を超えてしまう可能性があり、結果的に絶対値の小さい数値が無視されことが あります。これを「情報落ち」といいます。 0.123456×10６ 0.123456 ×10６ ０ ＋ 0.123454×10 ⇒ ＋0.000000123454×10６ 0.002 0.123456123454×10６ 無視される 例題１−６ ソフトウェア開発 平成 20 年秋 問２ けた落ちによる誤差の説明として，適切なものはどれか。 ア 値がほぼ等しい二つの数値の差を求めたとき，有効けた数が減ることによって発生 する誤差 イ 指定された有効けた数で演算結果を表すために，切捨て，切上げ，四捨五入などで 下位のけたを削除することによって発生する誤差 ウ 絶対値の非常に大きな数値と小さな数値の足し算や引き算を行ったとき，小さい数 値が計算結果に反映されないために発生する誤差 エ 無限級数で表される数値の計算処理を有限項で打ち切ったことによって発生する誤 差 - 11 - 解答−ア けた落ちは、絶対値のほぼ等しい同符号の二つの値の減算、あるいは異符号の二つの値 の加算を行った際に、有効桁数が減少することによって生じる誤差のことです。 イ 丸め誤差に関する記述です。 ウ 情報落ちに関する記述です。 エ 打切り誤差に関する記述です。 ここで演習１−12 から１−17 を解いて下さい - 12 - ０３ 集合 例えば、 「偶数の集まり」というように、同じ性質（この場合は２で割り切れる）をもつ 要素の集まりを集合といい、その要素を元といいます。 ある集合をＡ、また元をａとすると、その関係は次のように表されます。 元ａが集合Ａに含まれる場合：Ａ∋ａ 又は ａ∈Ａ ＿ また、全体集合をΩ、集合Ａに含まれない要素を補集合といいＡで表します。 更に、要素が何もない集合を空集合といい、φで表します。 １．部分集合と真部分集合 集合Ａの要素が集合Ｂにすべて含まれるとき、ＡをＢの部分集合といい、次のように表 します。 Ａ⊂Ｂ 又は Ｂ⊃Ａ なお、Ａ＝Ｂの場合も、集合Ａは集合Ｂの部分集合です。 また、集合Ａの要素は集合Ｂにすべて含まれますが、集合Ｂの要素の一部が集合Ａに含 まれないとき、ＡはＢの真部分集合といいます。 ２．集合演算 集合には、以下のような演算が用意されています。 １）和集合（Ａ∪Ｂ） ：集合Ａと集合Ｂをあわせた集合 Ａ Ｂ ２）積集合（Ａ∩Ｂ） ：集合Ａと集合Ｂの共通部分 Ａ Ｂ - 13 - ３）差集合（Ａ−Ｂ） ：集合Ａから集合Ｂを引いた集合 Ａ Ｂ ＿ ４）補集合（Ａ） ：全体から集合Ａを引いた集合 Ａ ＿ Ａ ３．集合演算の公式 集合演算では、次のような公式が成り立ちます。 法 則 交換法則 結合法則 分配法則 公 式 Ａ∪Ｂ＝Ｂ∪Ａ，Ａ∩Ｂ＝Ｂ∩Ａ Ａ∪(Ｂ∪Ｃ)＝(Ａ∪Ｂ)∪Ｃ， Ａ∩(Ｂ∩Ｃ)＝(Ａ∩Ｂ)∩Ｃ Ａ∪(Ｂ∩Ｃ)＝(Ａ∪Ｂ)∩(Ａ∪Ｃ)， Ａ∩(Ｂ∪Ｃ)＝(Ａ∩Ｂ)∪(Ａ∩Ｃ) 吸収法則 Ａ∪(Ａ∩Ｂ)＝Ａ，Ａ∩(Ａ∪Ｂ)＝Ａ 補法則 Ａ∪Ａ＝Ω，Ａ∩Ａ＝φ 同一法則 ド・モルガンの法則 ＿ ＿ Ａ∪Ａ＝Ａ，Ａ∩Ａ＝Ａ ＿＿＿ ＿ ＿ ＿＿＿ ＿ ＿ Ａ∪Ｂ＝Ａ∩Ｂ，Ａ∩Ｂ＝Ａ∪Ｂ 集合演算の公式 - 14 - 例題１−７ ソフトウェア開発 平成 19 年秋 問５ ＿ ＿ 全体集合Ｓ内に部分集合ＡとＢがあるとき，Ａ∩Ｂに等しいものはどれか。ここで，Ａ ＿ ∪ＢはＡとＢの和集合，Ａ∩ＢはＡとＢの積集合，ＡはＳにおけるＡの補集合，Ａ−Ｂは ＡからＢを除いた差集合を表す。 ＿ ＿ ア (Ａ∪Ｂ)−(Ａ∩Ｂ) イ (Ｓ−Ａ)∪(Ｓ−Ｂ) ウ Ａ−Ｂ エ Ｓ−(Ａ∩Ｂ) ＿ 解答−ウ ＿ ＿ Ａ∩Ｂは、Ａの補集合とＢの補集合の論理積です。これはド・モルガンの法則によって、 ＿＿＿ Ａ∪Ｂ、つまりＡとＢの否定論理和と同じです。これと等しい式は、ウとなります。 問題文 Ａ ア Ｂ ウ イ Ａ Ｂ Ａ Ｂ エ Ａ Ｂ ここで演習１−18 から１−23 を解いて下さい - 15 - Ａ Ｂ ０４ 論理演算 コンピュータで行う演算には、算術演算（加減乗除など）以外の演算として論理演算が あります。算術演算も論理演算も、論理回路を組み合わせて行われます。 １．論理回路 ある命題が何について述べているかよりも、そこに述べられていることが正しいか誤り かについてのみ考えていくと、結果は真又は偽のどちらかでしかありません。 例えば、 「偶数は２の倍数である」という命題は適切です。これを真といい、Ｔ又は１で 表します。それに対して「人間は植物である」という命題は適切ではありません。これを 偽といい、Ｆ又は０で表します。このような命題を表にまとめたものを真理値表といい、 このような演算を行うことを論理演算、 視覚的に表現したものをベン図といいます。 また、 論理演算を行うための回路を論理回路といいます。 １）OR 回路（論理和回路） OR 回路は、論理和を求めるための回路です。論理和は、二つの条件のいずれか一方 又は両方が真のときに結果が真になる演算です。なお、論理和を表すための記号として 「＋」 、 「∪」 、 「∨」などが用いられます。 真理値表 Ａ 0 0 1 1 回路図 Ｂ 0 1 0 1 Ａ＋Ｂ 0 1 1 1 ベン図 Ａ Ｂ 論理和の真理値表・回路図・ベン図 上図の左側の真理値表では、Ａ、Ｂという二つのビットに、０又は１が入力された場 合の結果を表しています。 ２）AND 回路（論理積回路） AND 回路は、論理積を求めるための回路です。論理積は、二つの条件がともに真の 、 「∩」 、 場合のみ、結果が真になる演算です。なお、論理積を表すための記号として「・」 「∧」などが用いられます。 - 16 - 真理値表 Ａ 0 0 1 1 回路図 Ｂ 0 1 0 1 ベン図 Ａ・Ｂ 0 0 0 1 Ａ Ｂ 論理積の真理値表・回路図・ベン図 ３）NOT 回路（論理否定回路） NOT 回路は、論理否定を求めるための回路です。論理否定は、与えられた条件が真 のとき、結果は偽に、条件が偽のとき、結果が真になる演算です。なお、論理否定を表 すための記号として「￣」 、 「￢」などが用いられます。 真理値表 回路図 ベン図 Ａ ＿ Ａ 0 1 Ａ 1 0 論理否定の真理値表・回路図・ベン図 ※ド・モルガンの法則 論理演算でも、集合におけるド・モルガンの法則が成り立ちます。 論理式の記号、論理和（∨）と論理積（∧） 、否定（￢）を用いた場合、ド・モルガン の法則は次のように記述されます。 ￢(Ａ∨Ｂ)＝￢Ａ∧￢Ｂ ￢(Ａ∧Ｂ)＝￢Ａ∨￢Ｂ なお、集合の記号を用いた場合には、次のように記述されます。 ＿＿＿ ＿ ＿ ＿＿＿ ＿ ＿ Ａ∪Ｂ＝Ａ∩Ｂ Ａ∩Ｂ＝Ａ∪Ｂ - 17 - 例題１−８ ソフトウェア開発 平成 15 年春 問６ 論理式￢(ｐ∧￢ｑ)をｐ→ｑと表記するとき，ｐ→ｑの真理値表はどれか。ここで， ∧ は論理積， ￢ は否定， １ は真， ０ は偽を示す。 ア ウ ｐ ｑ ｐ→ｑ ０ ０ １ １ ０ １ ０ １ ０ １ １ １ ｐ ｑ ｐ→ｑ ０ ０ １ １ ０ １ ０ １ １ ０ １ １ イ エ ｐ ｑ ｐ→ｑ ０ ０ １ １ ０ １ ０ １ １ ０ ０ １ ｐ ｑ ｐ→ｑ ０ ０ １ １ ０ １ ０ １ １ １ ０ １ 解答−エ ＿ ￢(ｐ∧￢ｑ)の表記方法の否定を、 ￢ から ￣ に変更すると、ｐ∧ｑと表すことが できます。この論理式を、ド・モルガンの法則により変形し、二重否定を外すと、次のよ うになります。 ＿ ＿ ＿ ＿ ｐ∧ｑ＝ｐ∨ｑ＝ｐ∨ｑ 変形した式のｐ、 ｑに１又は０を代入して真理値表を表現すると、 次のようになります。 ｐ ０ ０ １ １ ｑ ０ １ ０ １ ＿ ｐ＋ｑ １ １ ０ １ ここで演習１−24 から１−41 を解いて下さい - 18 - ４）EOR 回路（XOR 回路、排他的論理和回路） EOR 回路は、排他的論理和を求めるための回路です。排他的論理和は、二つの条件の うち、どちらか一方だけが真のとき、結果は真に、どちらも真あるいはどちらも偽のと き、結果は偽になる演算です。なお、排他的論理和を表すための記号として「○ ＋ 」など が用いられます。 真理値表 Ａ 0 0 1 1 回路図 Ｂ 0 1 0 1 ベン図 Ａ Ａ○ ＋Ｂ 0 1 1 0 Ｂ 排他的論理和の真理値表・回路図・ベン図 ５）NOR 回路（否定論理和回路） NOR 回路は、否定論理和を求めるための回路です。否定論理和は、論理和の結果の 否定を表す演算で、二つの条件がともに偽のときだけ、結果は真になります。 真理値表 Ａ 0 0 1 1 回路図 Ｂ 0 1 0 1 ベン図 ＿＿＿ Ａ Ａ＋Ｂ 1 0 0 0 Ｂ 否定論理和の真理値表・回路図・ベン図 ６）NAND 回路（否定論理積回路） NAND 回路は、否定論理積を求めるための回路です。否定論理積は、論理積の結果の 否定を表す演算で、二つの条件がともに真のときだけ、結果は偽になります。 真理値表 Ａ 0 0 1 1 回路図 Ｂ 0 1 0 1 ＿＿＿ ベン図 Ａ Ａ・Ｂ 1 1 1 0 否定論理積の真理値表・回路図・ベン図 - 19 - Ｂ 例題１−９ 応用情報 平成 21 年春 問 24 ＿ ＿ ＿ ＿ ＿ ＿ 論理式Ｘ＝Ａ・Ｂ＋Ａ・Ｂ＋Ａ・Ｂ＋Ａ・Ｂと同じ結果が得られる論理回路はどれか。 ここで， は論理積（AND） ， は論理和（OR） ， は否定論理積（NAND） ， は否定論理和（NOR）を表す。 ア Ａ Ｂ Ｘ イ Ａ Ｂ Ｘ ウ Ａ Ｂ Ｘ エ Ａ Ｂ Ｘ 解答−イ ＿ ＿ ＿ ＿ ＿ ＿ 論理Ｘ＝Ａ・Ｂ＋Ａ・Ｂ＋Ａ・Ｂ＋Ａ・Ｂ に結合法則を適用すると、 ＿ ＿ ＿ ＿ Ｘ＝Ａ・(Ｂ＋Ｂ)＋Ｂ・(Ａ＋Ａ) ＿ ＿ ＿ ＿ ＿ ＿ と変形できます。(Ａ＋Ａ)＝(Ｂ＋Ｂ)＝１で、Ａ・１＝Ａ，Ｂ・１＝Ｂなので、 ＿ ＿ Ｘ＝Ａ＋Ｂ となります。これにド･モルガンの法則を適用すると、 ＿ ＿ ＿＿＿ Ｘ＝Ａ＋Ｂ＝Ａ・Ｂ すなわち、否定論理積になります。 ここで演習１−42 から１−57 を解いて下さい - 20 - ０５ 確率 １．確率 確率とは、 「ある現象が起こる確かさの程度を割合で示したもの」です。起こり得るすべ ての場合の数をｎ、そのうち、事象Ａの起こる場合の数をａとしたとき、事象Ａの起こる 確率をＰ(Ａ)で表します。 Ｐ(Ａ)＝ａ÷ｎ なお、確率に関する公式には、次のようなものがあります。 １）加法定理 事象Ａと事象Ｂのうち、少なくともどちらか一方が起こる確率Ｐ(Ａ∪Ｂ)は、 Ｐ(Ａ∪Ｂ)＝Ｐ(Ａ)＋Ｐ(Ｂ)−Ｐ(Ａ∩Ｂ) と表されます。ここで、事象Ａと事象Ｂが排反事象（どちらか一方しか起こらない）な らば、 Ｐ(Ａ∪Ｂ)＝Ｐ(Ａ)＋Ｐ(Ｂ) となります。 ２）乗法定理 事象Ａと事象Ｂがともに起こる確率Ｐ(Ａ∩Ｂ)は、 Ｐ(Ａ∩Ｂ)＝Ｐ(Ａ)×Ｐ(Ｂ｜Ａ) と表されます。 Ｐ(Ｂ｜Ａ)は、事象Ａが起こったという条件の下で事象Ｂの起こる確率を表し、 「Ａの 下でのＢの条件付き確率」といいます。 事象Ｂの起こる確率が、事象Ａが起こるか起こらないかには依存せず、 ＿ Ｐ(Ｂ｜Ａ)＝Ｐ(Ｂ｜Ａ)＝Ｐ(Ｂ) が成り立つとき、 「事象Ａと事象Ｂは独立である」といい、このとき上式は、 Ｐ(Ａ∩Ｂ)＝Ｐ(Ａ)×Ｐ(Ｂ) となります。 ３）ベイズの定理 事象Ａ、Ｂが発生する確率をそれぞれＰ(Ａ)、Ｐ(Ｂ)、事象Ａが発生した下で事象Ｂが 発生する確率をＰ(Ｂ｜Ａ)としたときに、事象Ｂが発生した下で事象Ａが発生する確率 Ｐ(Ａ｜Ｂ)は、 Ｐ(Ａ｜Ｂ)＝Ｐ(Ｂ｜Ａ)×Ｐ(Ａ)÷Ｐ(Ｂ) で与えられます。 - 21 - 例題１−10 ソフトウェア開発 平成 14 年春 問６ ある工場では，同じ製品を独立した二つのラインＡ，Ｂで製造している。ラインＡでは 製品全体の 60％を製造し，ラインＢでは 40％を製造している。ラインＡで製造された製品 の２％が不良品であり，ラインＢで製造された製品の１％が不良品であることが分かって いる。いま，この工場で製造された製品の一つを無作為に抽出して調べたところ，それは 不良品であった。その製品がラインＡで製造された確率は何％か。 ア 25 イ 40 ウ 60 エ 75 解答−エ ラインＡで製品全体の 60％を製造しているので、1000 個の製品を製造したとき、ライン Ａでは 600 個製造されます。ラインＡで不良品が出る確率は２％なので、1000 個の製品を 製造したときのラインＡで生産された不良品の個数は、 600 個×２％＝12 個 となります。 同様に、ラインＢで製品全体の 40％を製造し、１％の不良品がでるので、1000 個の製品 を製造したときのラインＢで生産された不良品の個数は、 400 個×１％＝４個 となります。 全体で考えると、1000 個を製造した場合、ラインＡで 12 個、ラインＢで４個の合計 16 個の不良品が発生することになります。16 個のうち、ラインＡでは 12 個製造されている ので、その確率は、 12 個÷(12 個＋４個)×100＝75％ となります。 ここで演習１−58 から１−66 を解いて下さい - 22 - ４）マルコフ過程 未来の動作が現在の値だけで決定され、過去の動作とは関係がないという確率過程を マルコフ過程といいます。 例題１−11 ソフトウェア開発 平成 19 年春 問３ 表は，ある地方の天気の移り変わりを示したものである。例えば，晴れの翌日の天気は， 40％の確率で晴れ，40％の確率で曇り，20％の確率で雨であることを表している。天気の 移り変わりが単純マルコフ過程であると考えたとき，雨の２日後が晴れである確率は何％ か。 単位 ％ ア 15 翌日晴れ 翌日曇り 翌日雨 晴れ 40 40 20 曇り 30 40 30 雨 30 50 20 イ 27 ウ 30 エ 33 解答−エ 単純マルコフ過程とは、現在の状態が１回前の状態で決まるような確率の過程のことを いいます。ある日の天気が雨で、２日後の天気が晴れの時の組合せは、次の３通りがあり ます。それぞれの組合せの確率を加算すると、次のようになります。 (0.3×0.4)＋(0.5×0.3)＋(0.2×0.3)＝0.33 ある日 雨 翌日 ２日後 30％ 晴れ 40％ 50％ 曇り 30％ 20％ 雨 30％ ここで演習１−67 を解いて下さい - 23 - 晴れ ０６ 待ち行列 例えばスーパーマーケットのレジのように、一つ又はそれ以上の窓口にサービスを求め る客が行列を作って順番待ちを行うような場合、サービスを求める客が窓口に来る頻度や タイミングなどに応じて、どのように窓口を備えたらよいかが問題となります。このよう に窓口の度合いを変化させることで、 行列の長さや待ち時間がどのように変化するのかを、 数学モデルを使って解析する方法が、待ち行列理論です。 待ち行列問題の問題解決技法には、解析的技法とモンテカルロシミュレーション技法が あります。前者は待ち行列の発生を確定的モデルとして扱い最適解を得ようとする技法で す。後者は待ち行列モデルの実験を行い、その結果に対して確率的モデルを当てはめ、最 適解を得ようとするものです。 １．解析的技法 １）ケンドール記号 待ち行列を形成する要因には、次の四つがあります。 (ⅰ) 客の到着の仕方（Ｍ：ポアソン分布） (ⅱ) サービス時間の形態（Ｍ：指数分布） (ⅲ) 窓口の数（１：１個の場合） (ⅳ) 系の容量制限（∞：制限がない場合） この四つの要因を一定の表記法を用いて、次のように表します。この表記法をケンド ール記号といいます。 〔一般式〕 (ⅰ)／(ⅱ)／(ⅲ)（(ⅳ)） ２）ポアソン到着 客の到着間隔に規則性がなく、でたらめな場合をランダム到着、あるいはポアソン到 着といいます。 ３）サービス時間の形態 客１人に対するサービス時間が、客や時間帯によってまちまちであるような不規則な サービスの時間分布を指数分布といいます。 - 24 - ４）単一モデル（M/M/1）の公式 到着分布がポアソン分布に従うものとして、資源の平均到着数（到着率）をλと表し ます。一方、サービス時間の分布が指数分布に従うものとし、平均サービス率をμと表 します。 このとき、次のようになります。 ・平均到着時間間隔 Ta＝１／λ ・平均サービス時間 Ts＝１／μ ・利用率 ρ＝平均サービス時間×平均到着率 ＝平均サービス時間／平均到着時間間隔＝λ／μ ・待ち行列の長さ（サービス中を含む） L＝ρ／(１−ρ) ・待ち行列の長さ（サービス中を含まない） Lq＝ρ２／(１−ρ) ・平均待ち時間 Wq＝λ／μ(μ−λ)＝ρ／(１−ρ)×１／μ ＝ρ／(１−ρ)×Ts ・平均応答時間 W＝１／(μ−λ)＝１／(１−ρ)×１／μ ＝ρ／(１−ρ)×Ts＋Ts ＝Wq＋Ts 例題１−12 システム監査 平成 19 年春 問３ M/M/1 の待ち行列モデルにおいて，客の到着率が 0.5 人／秒で，窓口利用率が 0.2 であ るとき，窓口のサービス率は毎秒何人か。 ア 0.1 イ 0.4 ウ 2.0 エ 2.5 解答−エ 窓口利用率（ρ）＝平均サービス時間（Ts）×平均到着率（λ） 0.2＝Ts×0.5 Ts＝0.2÷0.5＝0.4 平均サービス率（μ）＝１／Ts ＝１／0.4＝2.5 ここで演習１−68 から１−88 を解いて下さい - 25 - ０７ 符号理論 符号理論は、情報を符号化する際の効率化と信頼性の理論です。効率化とは圧縮の理論 で、信頼性とは誤り制御の理論のことです。 １．情報の圧縮 情報（データ）量を減らすために、一部を省略することや、符号化する方法を変えるこ とを情報の圧縮といいます。画像や音声データは、そのまま符号化すると莫大な情報量に なってしまうので、情報の圧縮は通信回線や記憶媒体を効率良く使用するためには重要な 技術です。 圧縮の代表的な方法には、ハフマン符号化とランレングス符号化があります。 １）ハフマン符号化（Huffman encoding） ハフマン符号化は、 出現頻度がより高いデータに対してより短い符号を与えることで、 データ圧縮を行う方法です。ハフマン符号に変換する際に、作成される２分木をハフマ ン木といいます。 文字 発生確率 ａ 50％ ｂ 20％ ｃ 20％ ｄ 10％ 文字の出現頻度（例） メッセージ中の各文字列の出現頻度を元に、以下の手順で符号化を行います。 ① 各文字を節と考え、出現頻度の高い順に並べる。出現頻度が同じ場合には、どち らを先にしても良い。 ② 出現頻度の低い節を二つ取出しこれらを葉とした親節を新たに作成し、親節に葉 となる二つの節の出現頻度の和を記入する。 ③ ②で作成した木の出現頻度の低い文字の節に向かう枝に１、高い文字の節に向か う枝に０を与える。 なお、 出現頻度が同じ場合はどちらに１又は０を与えても良い。 ④ ③で作成した木を一つの節として考え、②、③を節の出現頻度が１となるまで繰 り返す。 - 26 - 1.0 0.5 0 0.5 ａ 1 0 1 0.2 ｂ 0 0.3 0.2 ｃ 1 0.1 ｄ ハフマン木（例） ⑤ 根からそれぞれの記号へたどる枝の値を書き出す。 ａ（0） ，ｂ（11） ，ｃ（100） ，ｄ（101） ハフマン符号によるメッセージのビット列の平均の長さを求めると、次のようになり ます。 平均の長さ＝ａのビット数×ａの出現頻度 ＋ｂのビット数×ｂの出現頻度 ＋ｃのビット数×ｃの出現頻度 ＋ｄのビット数×ｄの出現頻度 ＝１×0.5＋２×0.2＋３×0.2＋３×0.1 ＝1.8 ハフマン符号を使用しない場合には、４文字を区別するには２ビット（00，01，10， 11）必要ですが、ハフマン符号を使用した場合には 1.8 ビットあれば良いことが分かり ます。 - 27 - 例題１−13 ソフトウェア開発 平成 12 年春 問９ 次の表は，数字０∼９を符号化したビット表記と出現頻度である。数字１文字当たりの 平均ビット数はおよそ幾らか。 数字 ０ １ ２ ３ ４ ５ ６ ７ ８ ９ ア 2.8 ビット表記 0 10 1100 11010 11011 11100 11101 11110 111110 111111 イ 3.6 出現頻度（％） 40 19 10 5 5 5 5 5 3 3 ウ 4.4 エ 5.0 解答−ア 平均ビット数 ＝１×0.4＋２×0.19＋４×0.1＋(５×0.05)×５＋(６×0.03)×２ ＝0.4＋0.38＋0.4＋1.25＋0.36 ＝2.79 ≒2.8 ここで演習１−89 を解いて下さい ２）ランレングス符号化（run-length encoding） ランレングス符号化は、連続する同一の値を「データ×回数」という列（run）の長 さ（length）を示す情報に置き換える方法です。 例えば、 「AAAAABBBBCCCDDE」というデータ列であれば、A が５回、B が４回、 C が３回、D が２回、E が１回並んでいるので、 「A5B4C3D2E1」というデータ列に置 き換えることで、元のデータ列（15 文字）から置き換え後のデータ列（10 文字）に圧 縮します。 - 28 - 例題１−14 上級シスアド 平成 19 年秋 問 34 連続する同一の文字コード（１バイトコードとする）の長さから１を減じたものを１ バイトのバイナリで表し，その後に当該文字コードを配置する というデータ圧縮方式が ある。例えば，圧縮前に 16 進表示で， 41 41 41 41 41 42 43 43 43 43 43 43 であった 12 バイトの文字コードの列は，圧縮後に， 04 41 00 42 05 43 という６バイトで表され，この場合の圧縮率は 50％（６バイト÷12 バイト×100）となる ものとする。このとき，当該方式に関する記述のうち，適切なものはどれか。 ア 10 個の文字からなる文字列を圧縮したとき，最良の場合の圧縮率は最悪の場合の圧 縮率の５分の１である。 イ 圧縮後の長さが圧縮前の長さを上回ることはない。 ウ 一度に 256 バイト（256 の同じ文字）を２バイトに圧縮できるときが最大の圧縮率 なので，圧縮率が 0.7％以下の値になることはない。 エ 文字列に２回圧縮を行うと１回圧縮を行う場合の２分の１の圧縮率となる。 解答−ウ 最大の圧縮率は、 ２バイト÷256 バイト×100＝0.78125％ となるので、0.7％を下回ることはありません。 ア 10 個の文字からなる文字列を圧縮する場合、10 個の文字が全て同じときに圧縮率は最 良となり、２バイト÷10 バイト×100＝20％となります。逆に 10 個の文字がすべて異な るときに圧縮率は最悪となり、20 バイト÷10 バイト×100＝200％となります。したが って、最良の圧縮率は最大の圧縮率の 10 分の１となります。 イ 上記アの最悪の場合のように、 圧縮後の長さが圧縮前の長さを上回ることがあります。 エ 問題にある例で、２回圧縮します。 圧 縮 前：41 41 41 41 41 42 43 43 43 43 43 43 （12 バイト） 圧縮１回目：04 41 00 42 05 43 （６バイト） 圧縮率 ６÷12×100＝50％ 圧縮２回目：00 04 00 41 00 00 00 42 00 05 00 43 （12 バイト） 圧縮率 12÷６×100＝200％ このように、 ２回圧縮しても、 １回圧縮したときの圧縮率の２分の１にはなりません。 - 29 - ２．誤り制御の方法 誤り制御の方法には、パリティチェック方式、ハミング符号方式、CRC 方式などがあり ます。 １）パリティチェック方式 パリティチェック方式は、パリティビットと呼ばれる検査用のビットを元のデータに 付加することで、ビット誤りを検出する方式です。 パリティビットの付け方には、ビット列中の１の個数が偶数個になるように０又は１ を付加する偶数パリティと、奇数個になるように０又は１を付加する奇数パリティの二 つがあります。 また、チェック方式には、ビット列に対し垂直に求める垂直パリティチェックと、水 平に求める水平パリティチェックの二つの方法があります。 垂直パリティチェックあるいは水平パリティチェックを用いた場合、１ビットの誤り の検出は可能ですが、２の倍数個の誤りを検出することはできません。また、垂直パリ ティチェックと水平パリティチェックを組み合わせた場合、１ビットの誤りの訂正が可 能で、２ビットの誤りの検出ができます。 伝送文字列：Ｏ １ １ b3 １ １ 訂正すべきビット b5 ０ b6 ０ b7 １ b8 １ 垂直パリティビット Ｎ ０ １ １ １ ０ １ １ ０ Ｌ ０ ０ １ １ ０ ０ １ １ Ｉ １ ０ ０ １ ０ ０ １ １ Ｎ ０ １ １ １ ０ ０ １ ０ Ｅ １ ０ １ ０ ０ ０ １ １ １ １ １ １ ０ ０ ０ ０ 水平パリティビット １の個数が偶数個になっていない 水平垂直パリティ（偶数パリティ） （例） - 30 - 例題１−15 ソフトウェア開発 平成 19 年春 問 57 図のように 16 ビットのデータを４×４の正方形状に並べ，列と行にパリティを付加す ることによって何ビットまでの誤りを訂正できるか。ここで，図の網掛け部分がパリティ を表している。 １ ０ ０ １ ０ ア １ イ ２ ０ １ ０ １ ０ ０ １ １ ０ ０ ０ ０ ０ １ １ １ ０ １ １ ウ ３ エ ４ 解答−ア 水平垂直パリティビットが用いられているので、１ビットの誤りは検出だけでなく、位 置の特定が可能であり、訂正することができます。 １ ０ ０ １ ００ １１ １１ １０ ０ ０ ０ １ １ ０ １ １ ０００１ １ビット誤りの場合（ は誤ったビット） 一方、２ビットの誤りは、検出は可能ですが位置の特定ができないので訂正はできませ ん。 ここで演習１−90 から１−92 を解いて下さい - 31 - ２）ハミング符号方式 ハミング符号方式は、ハミング符号という冗長のビットを付加することで、ビットの 誤り検出と訂正を可能にした方式です。２ビットまでの誤りを発見でき、１ビットの誤 りを訂正することができます。ただし、訂正能力はそれほど高くはないので、頻繁に誤 りが発生するような場合は用いることができません。コンピュータの主記憶の誤り制御 などに採用されています。 例題１−16 ソフトウェア開発 平成 18 年春 問６ ハミング符号とは，データに冗長ビットを付加して，１ビットの誤りを訂正できるよう にしたものである。ここでは，Ｘ１，Ｘ２，Ｘ３，Ｘ４の４ビットからなるデータに，３ビッ トの冗長ビットＰ３，Ｐ２，Ｐ１を付加したハミング符号Ｘ１Ｘ２Ｘ３Ｐ３Ｘ４Ｐ２Ｐ１を考える。 付加ビットＰ１、Ｐ２、Ｐ３は，それぞれ Ｘ１◎Ｘ３◎Ｘ４◎Ｐ１＝０ Ｘ１◎Ｘ２◎Ｘ４◎Ｐ２＝０ Ｘ１◎Ｘ２◎Ｘ３◎Ｐ３＝０ となるように決める。ここで，◎は排他的論理和を表す。 このハミング符号 1110011 には１ビットの誤りが存在する。誤りビットを訂正した正し いハミング符号はどれか。 ア 0110011 イ 1010011 ウ 1100011 エ 1110111 解答−ア Ｘ１ Ｘ２ Ｘ３ Ｐ３ Ｘ４ Ｐ２ Ｐ１ ハミング符号 １ １ ０ １ Ｘ１◎Ｘ３◎Ｘ４◎Ｐ１ １ Ｘ１◎Ｘ２◎Ｘ４◎Ｐ２ １ １ Ｘ１◎Ｘ２◎Ｘ３◎Ｐ３ １ １ １ １ ０ ０ ０ １ ０ １ １ １ ＝１（誤り） ＝１（誤り） ＝１（誤り） 上記のように、三つの式がいずれも誤りとなります。これは三つの式に共通して使用さ れているＸ１が間違っていることを示しています。よって、ハミング符号 1110011 のＸ１に 当たる１を０に訂正することで、正しいハミング符号を得ることができます。 ここで演習１−93 から１−96 を解いて下さい - 32 - ３）CRC（Cyclic Redundancy Check）方式 CRC 方式は、データ列を一定の式（生成多項式）に見たて、特殊な演算により算出さ れた剰余を誤り検出、訂正用の符号とする方式です。この方式は、連続して発生する誤 り（バースト誤り）に対して有効で、複数のビット誤りの検出、訂正が可能です。 例題１−17 情報セキュリティ 平成 20 年春 問 17 誤り検出方式である CRC に関する記述として，適切なものはどれか。 ア 検査用データは，検査対象のデータを生成多項式処理して得られる１ビットの値で ある。 イ 受信側では，付加されてきた検査用データで検査対象のデータを割り，余りがなけ れば送信が正しかったと判断する。 ウ 送信側では，生成多項式を用いて検査対象のデータから検査用データを作り，これ を検査対象のデータに付けて送信する。 エ 送信側と受信側では，異なる生成多項式が用いられる。 解答−ウ CRC を用いた場合、送信側はデータと生成多項式から検査用のデータを作成し、それを データとともに送信します。 ア １ビットではなく、生成多項式の最高次数と同じ次数の値になります。 イ、エ 付加されてきた検査用データではなく、作成に用いたのと同じ生成多項式で検査 対象のデータを割ることで正否の判断を行います。 ここで演習１−97 を解いて下さい - 33 - ０８ BNF BNF（Backus-Naur-Form：バッカス記法）は、バッカスがプログラム言語 Algol60 の 構文規則の表記法として提案したものです。文字の並び方の規則を文字で定義し、反復や 選択なども適当な文字記号で表現します。文字だけで定義するので、簡潔に表現すること ができ、最終的な文の記述形式に近い表現となります。 BNF では、数字と英字を次のように記述します。 <数字> ::＝ ０｜１｜２｜３｜４｜５｜６｜７｜８｜９ <英字> ::＝ ａ｜ｂ｜ｃ｜…｜ｚ｜Ａ｜Ｂ｜Ｃ｜…｜Ｚ ::＝ は、 「左辺を右辺のように定義する」という意味で、 ｜ は、 「又は」という意 味です。したがって、<数字>であれば、 「<数字>を０∼９のいずれかと定義する」とあるの で、 「０∼９のいずれか一字が数字」と解釈することができます。 また、 １桁以上の<数字>で構成される<識別子>を定義する場合、 次のように表現します。 <識別子> ::＝ <数字>｜<識別子><数字> 例題１−18 ソフトウェア開発 平成 18 年春 問８ 次に示す記述は，BNF で表現されたあるプログラム言語の構文の一部である。<パラメ タ指定>として，正しいものはどれか。 <パラメタ指定> ::＝ <パラメタ> ¦ (<パラメタ指定>，<パラメタ>) <パラメタ> ::＝ <英字> ¦ <パラメタ><英字> <英字> ::＝ a ¦ b ¦ c ¦ d ¦ e ¦ f ¦ g ¦ h ¦ i ア ((abc，def)) イ ((abc，def)，ghi) ウ (abc) エ (abc，(def)) 解答−イ 選択肢イの中の(abc，def) がパラメタ指定で、ghi はパラメタです。両者を ( ) でくく ってカンマで区切っているので、パラメタ指定として成立します。 ア 内側の (abc，def) は パラメタ指定 の条件に合いますが、外側の ( ) の中にカン マで区切られる パラメタ がありません。 ウ ( ) の中にカンマで区切られる パラメタ が必要です。 エ (def) のように１個のパラメタが括弧でくくられることはありません。 ここで演習１−98 から１−102 を解いて下さい - 34 - ０９ ポーランド記法 ポーランド記法には、演算子の後に二つの変数（オペランド）を記述するポーランド記 法（前置記法）と、二つの変数の後に演算子を記述する逆ポーランド記法（後置記法）が あります。例えば、 算術式 ｘ＝ａ＊ｂ−ｃ／ｄ に対し、各記法に変換した場合、以下のようになります。 ポーランド記法（前置記法） ：＝ｘ−＊ａｂ／ｃｄ ：ｘａｂ＊ｃｄ／−＝ 逆ポーランド記法（後置記法） 例 数式「ｅ＝(ａ−ｂ)÷(ｃ＋ｄ)」を逆ポーランド記法の数式に変換する場合 １．ｅ＝(ａ−ｂ)÷(ｃ＋ｄ) 下線部分の「ａ−ｂ」を逆ポーランド記法の数式へ→「ａｂ−」これをＸとする。 ２．ｅ＝Ｘ÷(ｃ＋ｄ) 下線部分の「ｃ＋ｄ」を逆ポーランド記法の数式へ→「ｃｄ＋」これをＹとする。 ３．ｅ＝Ｘ÷Ｙ 下線部分の「Ｘ÷Ｙ」を逆ポーランド記法の数式へ→「ＸＹ÷」これをＺとする。 ４．ｅ＝Ｚ 下線部分の「ｅ＝Ｚ」を逆ポーランド記法の数式へ→ｅＺ＝ ５．Ｘ、Ｙ、Ｚを逆ポーランド記法の数式に置き換える。 （下線部は置き換えた部分） ｅＺ＝ → ｅＸＹ÷＝ → ｅＸｃｄ＋÷＝ → ｅａｂ−ｃｄ＋÷＝ 通常の数式から逆ポーランド記法の数式への変換（例） 例題１−19 ソフトウェア開発 平成 17 年春 問８ 式ａ＋ｂ×ｃの逆ポーランド表記法による表現として，正しいものはどれか。 ア ＋×ｃｂａ イ ×＋ａｂｃ ウ ａｂｃ×＋ 解答−ウ 問題の式は、次の手順で変換します。 ①ａ＋ｂ×ｃ→ａ＋ｂｃ× ②ａ＋ｂｃ×→ａｂｃ×＋ ここで演習１−103、１−104 を解いて下さい - 35 - エ ｃｂａ＋× １０ オートマトン オートマトンは、コンピュータそのものを数学的観点からモデル化し、問題解決のため のアルゴリズムを定式化したもので、出力が、入力と内部の状態によって決定するような ものをモデル化して表現します。 ある入力を得ると、計算（処理）を行い結果を出力するといった、事象の発生とその発 生事象に応じた動作を時系列的にモデル化したもののことです。 通常は、状態遷移図などによって、モデルを表現します。 １．有限オートマトン 通常は、 有限オートマトンは、 有限個の状態と遷移の組合せからなるモデルのことです。 開始状態を定めておき、そこから入力によって遷移を繰り返していき、入力が終了したと きに最終状態であれば、入力は受理されたことになります。 例題１−20 ソフトウェア開発 平成 18 年秋 問７ 次の表は，入力記号の集合が｛０，１｝ ，状態集合が｛ａ，ｂ，ｃ，ｄ｝である有限オー トマトンの状態遷移表である。長さ３以上の任意のビット列を左（上位ビット）から順に 読み込んで最後が 110 で終わっているものを受理するには，どの状態を受理状態とすれば よいか。 ア ａ イ ｂ ０ １ ａ ａ ｂ ｂ ｃ ｄ ｃ ａ ｂ ｄ ｃ ｄ ウ ｃ - 36 - エ ｄ 解答−ウ 最後の３ビットである 110 が入力される直前の状態をａ、ｂ、ｃ、ｄのそれぞれとして、 状態遷移表に基づいて遷移した場合、以下のようになります。 １ １ ０ ａ → ｂ → ｄ → ｃ ｂ → ｄ → ｄ → ｃ ｃ → ｂ → ｄ → ｃ ｄ → ｄ → ｄ → ｃ したがって、いずれの場合にも最終状態はｃなので、ｃを受理状態とします。 なお、 問題文で与えられた状態遷移表を基に状態遷移図を作成すると以下のようになり、 この状態遷移図を用いて確認をしても構いません。 ０ ａ ０ ｃ ０ １ ０ １ ｂ １ ここで演習１−105 から１−112 を解いて下さい - 37 - ｄ １