応用技術者試験で勉強とばしそうな基礎編について、問題解きつつ知識確認しつつ解きます。
内容的にはほとんど基本情報技術者試験の内容。
２進数の浮動小数点の計算
2進数の小数点について
2進数の小数点の表現は、指数部が負で表される。
まず、２のべき乗の計算一覧。
$2^{-1} = 1/2 = 0.5$
$2^{-2} = 1/4 = 0.25$
$2^{-3} = 1/8 = 0.125$
$2^{-4} = 1/16 = 0.0625$
上記に基づけば、
10進数0.5であれば2進数では0.1、
10進数0.25であれば2進数では0.01、
10進数0.125であれば2進数では0.001
10進数0.0625であれば2進数では0.0001
と表記される。
これが例えば、10進数で$0.375$であれば、
2進数では
$10進数：0.25_{10} + 0.125_{10} = 0.375_{10}$
$2進数：0.01_{2} + 0.001_{2} = 0.011_{2}$
となる。
このように、$2^{-n}$同士の足し算で綺麗に表せるものもあれば、
逆に表せないものもある。
例えば、10進数で$0.45$であれば、
上の一覧で言うと、$2^{-4}=0.0625$よりも小さな値を足し合わせて、
理想的にはぴったりと$0.45$を求める必要があるが、先ほどの例ほどピタリと一致はできない。
このような値を「無限小数」という。
情報落ち
情報落ち、とは例えば
$0.1234 × 10^2$
$0.00001234 × 10^2$
を足し算したら、$0.12341234 × 10^2$となる。
これに有効桁数４ケタが指定されていれば、
$0.1234× 10^2$と、$0.00001234 × 10^2$の小さいほうが無視される。
これが情報落ち。
(R3春期 Q2 引用)
絶対値の非常に大きな数値と小さな数値の加算や減算を行ったとき，
小さい数値が計算結果に反映されないことによって発生する誤差
情報落ち対策
$1.000+0.001+0.001...+0.001$
上記を左から計算するとき、有効桁数４ケタとすれば、
$1.000+0.001=1.000$となる。$0.001$が仮に10個あって、$2.000$が正解だったとしても異なる結果となる。
対策として、数字が小さいほうから足し算をすることで、正しい結果が得られる。
$1.000+ (0.001+0.001...+0.001)$
$1.000+ 1.000=2.000$
2進数の正規化による計算
中学数学の復讐。
$0.0036×10^2 + 0.00036×10^3$
を計算しようと思ったら、
指数部の$10^2$をそろえてやって
$0.0036×10^2$と$0.0036×10^2$
となり、足し算ができる。このように指数をそろえてやることを正規化という。
２進数でも同様で、
$1.1×2^{-3}$と$1.0×2^{-4}$
であれば、指数が小さいほうを大きいほうに合わせて、
$1.1×2^{-3}$と$0.1×2^{-3}$
となる。
実際に一部例題を解いてみる。
${(1.1)_2×2^{-3} - (1.0)_2×2^{-4}} + (1.0)_2×2^{5}$
計算の練習がてら、応用技術者試験の問題の一部を計算してみる。
守るべき原則としては、
１．小さいものから足し算
２．正規化するときは指数が大きいものにあわせる。
{(1.1)_2×2^{-3} - (1.0)_2×2^{-4}} + (1.0)_2×2^{5}\\{(1.1)_2×2^{-3} - (0.1)_2×2^{-3}} + (1.0)_2×2^{5}\\
{(1.0)_2×2^{-3}} + (1.0)_2×2^{5}\\
{(0.00000001)_2×2^{5}} + (1.0)_2×2^{5}\\
{(1.00000001)_2×2^{5}}
仮想部＝小数点以下のビット数が
もしも８ビットなら情報落ちは発生しない。
もしも７ビットであるなら、
${(1.00000001)_2×2^{5}} $は８ビットなので、
${(0.00000001)_2×2^{5}} $は情報落ちとして無視されて、結果は
${(1.0000000)_2×2^{5}} $となる。
浮動小数点の形式
例題やりながら浮動小数点の形式についてみてみる。
図に示す16ビットの浮動小数点形式において，
10進数 0.25 を正規化した表現はどれか。ここで，正規化は仮数部の最上位けたが1になるように指数部と仮数部を調節する操作とする
$0.25_{10}$は、２進数では
$2^{-2}=1/4=0.25$より、$0.01$。
この数値を$× 2^{n}$の形式で表すのが正規化。
では、どのようなルールのもとで指数の数字を決定するか。
浮動小数点形式では、例えば$0.001101$なら、$0.1101×2^{-2}$のように、
小数点の部分の最上位(0除く)が先頭にくるように、指数を整えてやる。
よって、$0.01_{2}$を浮動小数点形式に正規化すると、
$0.01_{2} = 0.1_{2} × 2^{-1}$
ここで、問題文中にでる「符号」「指数部」「仮数部」について整理する。
符号 ：図の通り、正負を現す数字
指数部：正規化した時の$2^{n}$で言うところのn。
仮数部：「0.xxxxx」で言うところの「xxxxx」
上記を踏まえて、$0.25_{10} = 0.1 × 2^{-1}$で言うとそれぞれ、
符号 ：0.25は正なので「０」
指数部：
-1であるが、４ビットで２の補数で表すと、
1.$0001$を反転させて、$1110$。
2.これに1を加えて$1111$
仮数部：[0.1=0.10000000000]に対して[10000000000]が該当。
2進数の負の数
負の二進数$1101$があったとする。
２進数の負の表示方法は以下の通り。
絶対値に符号を付けた表現
先頭１桁目が1のときは負、0のときは正となる。
$1101$は、負の$101_{2} = 5_{10}$となる
よって「5」
1の補数
まず、対象のデータのビットを反転させる。
$1101_{2}$ → $0010_{2} = 2_{10}$
よって、「-2」
2の補数
まず、対象のデータのビットを反転させる。
$1101_{2}$ → $0010_{2} = 2_{10}$
これに１を加えたものが２の補数。
よって、「-3」
演算における誤差の種類
丸め誤差
例えば$0.010101111...$というデータに対して、有効桁数3ビットと指定されていた場合、
結果は、$0.010$となり、小さい部分はすべて「捨てられる」。この分の誤差を「丸め誤差」という。
R3春期 Q2引用
指定された有効桁数で演算結果を表すために，
切捨て，切上げ，四捨五入などで下位の桁を削除することによって発生する誤差
打ち切り誤差
演算中に、$1/3$を計算した時、無限に続く計算を途中で打ち切ります。
正しい結果$0.3333.....$と、$0.33$のように途中で打ち切られた結果の誤差、
これを「打切り誤差」という。
R3春期 Q2引用
無限級数で表される数値の計算処理を有限項で打ち切ったことによって発生する誤差
桁落ち
近しい数字で計算を行ったとき、
$0.3548 × 10^2 - 0.3525 × 10^2 = 0.0023 × 10^2$
となる。
この時、有効桁数4桁で統一していたとすると、
計算結果の有効桁数は2桁に減少する。
$0.0023 × 10^2$を正規化して、有効桁数を整えると、
$0.0023 × 10^2 = 0.2300 × 10^0$
となる。23の後ろの０を付与することになるが、
計算元のデータは有効桁数４桁にそろえるために、小さい部分を切り落としているため、
この０は厳密に言えば正しくない。
値の近いもの同士での差分で発生する誤差を「桁落ち」という。
R3春期 Q2引用
値のほぼ等しい二つの数値の差を求めたとき，有効桁数が減ることによって発生する誤差
ビット演算
計算そのものは単純だけれど、問題の理解がちょっと難しい。実際の例題を見る。
H31春期 Q1
0以上255以下の整数nに対して，
と定義する。next(n)と等しい式はどれか。ここで，x AND y 及び x OR y は，
それぞれxとyを2進数表現にして，桁ごとの論理積及び論理和をとったものとする。
ア.(n＋1) AND 255
イ.(n＋1) OR 255
解いてみる。
ア、イの計算結果とnextの計算結果が一致するかどうかが大事である。
AND,ORの２進数での計算方法を確認しつつ確かめる。
n=3としたとき。
$next()$の結果は、「4」になるが、ア、イはどうなるか確認する。
ア：(n＋1) AND 255
255は２進数で11111111、4は２進数で、11なので、
$011111111$
$000000011$
これをANDで計算すると、互いに1なら1、それ以外は0になるので
$000000011 = 4 $
となるので、４に関しては少なくとも誤りでない。
イ：(n＋1) OR 255
255は２進数で11111111、4は２進数で、11なので、
$011111111$
$000000011$
これをORで計算すると、どちらかに1があれば1になるので
$111111111 = 255 $
となるので、誤り。
この要領で、範囲の最小（０）最大（２５５）を計算して、
計算結果が本当に一致するかを確認する。
次の問題。
H20春期
16ビットの2進数 n を16進数の各けたに分けて，下位のけたから順にスタックに格納するために，
次の手順を4回繰り返す。a，b に入る適切な語句の組合せはどれか。ここで，xxxx16 は 16 進数 xxxx を表す。
ア． [a] : n AND $000F_{16}$ [b]:左に4ビット
イ． [a] : n AND $FFF0_{16}$ [b]:右に4ビット
まず問題の理解。
16ビットの2進数、例えば、
$1111 0101 0001 0011$
に対して、問題分の処理を行う。
そして行う操作は、下位の桁から順にスタックに格納、とある。
４回繰り返す、とあるので、16ビットのデータに対して１回あたり4ビット。
なので最初は、$1111 0101 0001 0011$の下位の４ビット$0011$を取り出すことから始まる。
回答群にある演算を実際にやってみる。
$1111 0101 0001 0011$
$0000 0000 0000 1111$
上記に対してAND演算を行うと、1になってる部分を抽出するような処理となり、
$0000 0000 0000 0011$
計算結果を見ると、取り出したいデータ$0011$と一致しているので、
下位４ビットの演算としてはこれが正しい。
次に、$0011$を取り出した後は、$0001$を取り出す必要がある。
なので、必要なのは、
$1111 0101 0001 0011$
これが、
$0000 1111 0101 0001$
となるような右へのシフト演算である。
よって回答は「ア」
待ち行列
客はどれくらい入って、同時に何人帰るのか。
これらをもとに、混雑状況とどれくらい時間がかかるかを求めるのが待ち行列。
基本知識
平均サービス率：μ「どれくらい客帰るの？」
単位時間あたりにさばける（外に出る）客の数。
10秒間に客を100人さばけるなら、100/10=10[人/秒]
平均到着率：λ「どれくらい客来るの？」
単位時間あたりに客が来る数。
7秒間に客が100人来るなら、100/7=14[人/秒]
利用率：ρ「どれくらい混んでるの？」
どれくらい込み合ってるかを計算する。
100人客が来て、同時に20人出ていったのなら、
混雑率もとい利用率としては、100/20=5。
同様に求めると、
ρ = \frac{(客が入ってくる)}{(客が帰る)}\\
ρ = \frac{(平均到着率)}{(平均サービス率)}\\
ρ = \frac{λ}{μ}
「今客はどれくらいいるの？」というのを式化したのがこの割合。
待ち時間：ρ
直感的には利用率ρが高いほど待ち時間は増えるし、少ないほど時間は減る。
これをド直球に式にするなら、
待ち時間 = \frac{ρ}{1-ρ}
となる。
古典的数学に基づく式化なので、
極端に言えば、グラフがこんな感じになるなら厳密に言えばこの式じゃなくてもよい。（極端）
「利用率ρが高いほど待ち時間は増えるし、少ないほど時間は減る」
これだけの性質なら、比例の直線でも良いように思えるが、
「利用率が極端に少ないときは時間は極端に少なくなる」
「利用率が極端に多いときは時間は極端に長くなる」
という性質を再現するにはこの式になる。
この式は、待ち行列に限らず、
「頻度が増える/減るほど、通常よりもさらに効率が悪化/改善する」
ようなものは、この古典的な式が適用されると思われる。
平均待ち時間：平均どれくらい待つの？
待ち時間は$\frac{ρ}{1-ρ}$で求まる。
では平均の待ち時間はいくつになるか。
客が待っている間の状態は、
店員がサービスを提供して、それが完了するを待っている状態になります。
単位時間あたりにさばける客の平均人数は「平均サービス率」で表される。
よって、サービスの提供時間は１人あたり平均$1/λ$時間かかることになる。
一人当たりの平均サービス時間が$1/λ$。
それを待っている時間を$\frac{ρ}{1-ρ}$。
これを掛け合わせたものが、平均待ち時間となる。
平均待ち時間 = \frac{ρ}{1-ρ} \frac{1}{λ}\\
平均待ち時間 = \frac{ρ}{1-ρ} 平均サービス時間\\
平均応答時間：平均どれくらい待つ＋サービス提供にどれくらい待つの？
客は結局全体でどれくらい待つのか。
先ほど求めた平均待ち時間は、列で待つ時間だけなので、
これにサービスを受ける時間を足してやればよい。
$平均応答時間 = 平均待ち時間 + 平均サービス時間$
$平均応答時間 = \frac{ρ}{1-ρ} 1/λ + 1/λ\ $
例題
例題を解いていく。
M/M/1の待ち行列モデルにおいて，窓口の利用率が25%から40%に増えると，平均待ち時間は何倍になるか。
平均待ち時間は、待ち時間に平均サービス時間を掛けたもの。
待ち時間ρは$\frac{ρ}{1-ρ}$、
平均サービス時間は、単位時間あたりの人数である平均サービス率に対して、逆数を取るので$\frac{1}{μ}$。
平均待ち時間=\frac{ρ}{1-ρ}\frac{1}{μ}
25%の場合は、
平均待ち時間=\frac{0.25}{1-0.25}\frac{1}{μ}\\
平均待ち時間=\frac{1}{3}\frac{1}{μ}
40%の場合は、
平均待ち時間=\frac{0.4}{1-0.4}\frac{1}{μ}\\
平均待ち時間=\frac{2}{3}\frac{1}{μ}
よって、２倍に代わる。
次の例題。
ATM(現金自動預払機)が1台ずつ設置してある二つの支店を統合し，
統合後の支店にはATMを1台設置する。統合後のATMの平均待ち時間を求める式はどれか。
ここで，待ち時間はM/M/1の待ち行列モデルに従い，平均待ち時間にはサービス時間を含まず，
ATMを1台に統合しても十分に処理できるものとする。
〔条件〕
1.平均サービス時間：Ts
2.統合前のシステムの利用率：両支店ともρ
3.統合後の利用者数は，統合前の両支店の利用者数の合計
平均待ち時間を求める式は、
$(平均待ち時間) = (待ち時間)×(平均サービス時間)$
繰り返しになるが、平均サービス率は
単位時間当たりにサービスを提供できる人数である「平均サービス率」
これの逆数が１人当たりのサービス平均時間になる。
統合前の利用率は、ρとあるので、統合前の平均待ち時間は$\frac{ρ}{1-ρ} T_{s}$
では統合後の平均待ち時間を考える。
利用率の式は、下記式で求まる。
(利用率_{before})= \frac{(単位時間当たりに客が来る率)}{(単位時間当たりに客が帰る率)}\\
(利用率_{before})= \frac{(平均到着率)}{(平均サービス率)}
「統合後の利用者数は，統合前の両支店の利用者数の合計」
ということを考えると、「単位時間当たりに客が来る」人数は統合後は二倍になる。
(利用率_{After})= \frac{(2 × 平均到着率)}{(平均サービス率)}
よって、「単位時間当たりに客が来る率」、もとい、平均到着率は２倍になる。
平均サービス率は、ATMは変化ないのでそのままなので、統合後の利用率は２倍になる。
したがって、統合後の平均待ち時間は$\frac{2ρ}{1-2ρ} T_{s}$
次の例題
コンピュータによる伝票処理システムがある。このシステムは，
伝票データをためる待ち行列をもち，M/M/1の待ち行列モデルが適用できるものとする。
平均待ち時間がT秒以上となるのは，処理装置の利用率が少なくとも何%以上となったときか。
ここで，伝票データをためる待ち行列の特徴は次のとおりである。
1.伝票データは，ポアソン分布に従って到着する。
2.伝票データをためる数に制限はない。
3.1件の伝票データの処理時間は，平均T秒の指数分布に従う。
平均待ち時間は下記式。
$平均待ち時間 = 待ち時間×平均サービス時間$
$平均待ち時間 = \frac{利用率}{1-利用率} ×\frac{1}{平均到着率}$
伝票の処理時間は平均T秒とのことなので、
$平均待ち時間 = \frac{利用率}{1-利用率} ×T$
問題は、平均待ち時間がT以上になる時の利用率について。
これを式にすれば、
T \geqq \frac{利用率}{1-利用率} ×T\\
1 \geqq \frac{利用率}{1-利用率} ×1\\
1-利用率 \geqq 利用率\\
利用率 \geqq 0.5
ということで回答は0.5．
確率
とりあえず例題。
3台の機械A，B，Cが良品を製造する確率は，それぞれ60%，70%，80%である。
機械A，B，Cが製品を一つずつ製造したとき，いずれか二つの製品が良品で残り一つが不良品になる確率は何%か。
良い確率のの否定より、悪い確率を求める。
良い確率：
A:0.6 B:0.7 C:0.8
悪い確率：
A:0.4 B:0.3 C:0.2
いずれか２つが良品、残りが不良品。
パターンとしては、
１．良：AB 悪：C 0.6×0.7×0.2=0.084
２．良：AC 悪：B 0.6×0.3×0.8=0.144
３．良：CB 悪：A 0.4×0.7×0.8=0.224
それぞれ足すと$0.452$。
続けて例題。
製品100個を1ロットとして生産する。一つのロットからサンプルを3個抽出して検査し，
3個とも良品であればロット全体を合格とする。100個中に10個の不良品を含むロットが合格と判定される確率は幾らか
100から3個拾う全パターンは、${}_100 \mathrm{C}_3 = \frac{100×99×98}{3×2×1} = 161700$
良品90個から３個拾うパターンは${}_90 \mathrm{C}_3 = \frac{90×89×88}{3×2×1} = 117480$
よって、$117480／161700$
続けて例題。
表は，ある地方の天気の移り変わりを示したものである。例えば，晴れの翌日の天気は，
40%の確率で晴れ，40%の確率で曇り，20%の確率で雨であることを表している。
天気の移り変わりが単純マルコフ過程であると考えたとき，雨の2日後が晴れである確率は何%か。
雨の二日後が晴れるパターンをすべて出す。
雨、晴、晴
雨、雨、晴
雨、曇、晴
上記パターンで同様に確率計算すればOK。
数学
非線形方程式の近似解法 ： ニュートン法
任意のポイントで接線を引いて、その接線の式より予測値を得る。
これを繰り返して、f(x)=0になる値にちかづける。
二項定理
(1+x)^{\alpha} = 1 + \alpha x + \frac{\alpha(\alpha-1)}{2!} + \cdots
このとき、$|x| << 1$であると、下記の式に近似される。
(1+x)^{\alpha} \approx 1 + \alpha x \cdots
この手の問題は実際に数値を入れて計算するのが一番と思われる。
相関係数
直線っぽくなれば相関がある。
例えば右肩上がりの直線なら、牛乳飲む量が増えるほど身長が伸びる。
左肩下がりの直線なら、牛乳飲む量が増えるほど髪の量が減る
等の相関があることになる。
https://aiacademy.jp/media/?p=939
#逆ポーランド記法
例題で学ぶ。
式A＋B×Cの逆ポーランド表記法による表現として，適切なものはどれか。
要素をくっつけて、演算子を後ろにつける、という法則で通常の四則演算の順番でとく。
$A+B×C$
$A+BC×$
$A+(BC×)$
$ABC×+$
#符号化
ハフマン符号
大事なことは、
出現頻度が高い文字は短く、頻度が少ないものは文字を長くする。
そして文字が一意であること。
これを満たしていればハフマン符号。
とりあえず例題を解く。
a，b，c，d の4文字からなるメッセージを符号化してビット列にする方法として
表のア～エの4通りを考えた。この表は a，b，c，d の各1文字を符号化するときのビット列を表している。
メッセージ中の a，b，c，d の出現頻度は，それぞれ，50%，30%，10%，10% であることが分かっている。
符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
イで言うと、
"0110"は、bcの解釈とadaの２つ解釈できるのでバツ。
一意なのはウ。
続けて例題。
四つのアルファベットa～d から成るテキストがあり，
各アルファベットは2ビットの固定長2進符号で符号化されている。
このテキストにおける各アルファベットの出現確率を調べたところ，
表のとおりであった。各アルファベットの符号を表のような可変長2進符号に変換する場合，
符号化されたテキストの，変換前に対する変換後のビット列の長さの比は，およそ幾つか。
ハフマン符号は可変長符号でもある。
a=0 (0.4)
b=10 (0.3)
c=110(0.2)
d=111(0.1)
変換前、の文字はすべて２ビット。
このときの平均は、
20.4 + 20.3 + 20.2 + 20.1 = 2
変換前、一文字当たりの平均は２ビット
変換後の場合は、
10.4 + 20.3 + 30.2 + 30.1 = 1.9
変換後、一文字当たりの平均は1.9ビット
返還前に対する返還後の比率は
1.9/2=0.95
BNF
とりあえず例題。
次に示す記述は，BNFで表現されたあるプログラム言語の構文の一部である。<パラメタ指定>として，適切なものはどれか。
<パラメタ指定>::＝<パラメタ>｜(<パラメタ指定>，<パラメタ>)
<パラメタ>::＝<英字>｜<パラメタ><英字>
<英字>::＝a｜b｜c｜d｜e｜f｜g｜h｜i
定義に当てはめていって、パラメタ指定になるかみてみます。
カッコの存在わすれがちなので注意。
ア．((abc，def)，ghi)
((パラメタ指定,パラメタ),パラメタ)
(パラメタ指定,パラメタ)
パラメタ指定
あってる。
イ．((abc，def))
((パラメタ,パラメタ))
((パラメタ指定,パラメタ))
(パラメタ指定)
カッコがとれない。ダメ
ウ．(abc，(def))
(パラメタ,(パラメタ))
ダメ