応用情報をとりたくて
きたる10月、応用情報技術者試験があります。ので、それまでの二か月間でひたすらに勉強し、その内容をまとめていきたいと思います。
今回は基礎理論・アルゴリズムとプログラミングの過去問の残り半分ほど解いたので、その分で出てきた単語をまとめます。
出てきた単語集(前回分)
正規分布、確率、モンテカルロ法
再帰的、再使用可能、再入可能、再配置可能、相関係数、ユークリッド互助法、 ハフマン符号化、幅優先と深さ優先探索、ディープラーニング、ベイズの定理、排他的論理和、リストの実現(配列orポインタ)、浮動小数の情報落ち、ハッシュ関数の衝突、完全二分木、ニュートン法、オイラー法、ガウスの消去法、シンプソン法、グラフと隣接行列、スタックとヒープ、BNF(バッカス・ナウア記法)、UTF-8、過学習、パリティチェック、有限オートマトン、ハミング符合、M/M/1待ち行列モデル、クイックソート、選択ソート、挿入ソート、バブルソート、BCD(Binary-coded decimal)
出てきた単語集(今回分)
逆ポーランド記法、カルノー図、桁落ち、丸め誤差、情報落ち、打ち切り誤差、値呼び出しと参照呼出し、双方向リスト、シェルソート、ヒープソート、マージソート、オーバーライド、オーバーロード、カプセルか、汎化、TOF(Time of Flight)センサー
今回分について、それぞれの用語解説
逆ポーランド記法：プログラムで処理しやすい形で計算を記述したもので、以下のように処理される。(参考)
- 逆ポーランド記法の計算式の先頭から順に1文字ずつ取り出す
- 取り出した文字が値ならスタックにプッシュする
- 取り出した文字が演算子ならスタックから2つのデータをポップし、両者の演算結果の値をスタックにプッシュする
- 1に戻って繰り返し、最後の文字を取り出して処理したらその時点でスタックに残っている一つの値が計算式の値となる。
例えば、ABCD-x+、というものがあった場合、まずABCDの順にスタックにプッシュされ、その後演算子-が出たので、C-Dを計算してスタックにプッシュし、その後演算子xが出たので、Bx(C-D)を計算してスタックにプッシュし、最後にAを足して、最終的にA+Bx(C-D)という計算式が得られる。
カルノー図：論理式簡略化に用いる図表。以下のルールに従って共通項を論理積として取り出し、その和を求めると簡略化された等価式になるもの
1/. グルーピングするセルの数字は全て1
2/. グルーピングするセルの数は2^nでなるべく広くとる
3/. カルノー図の左右上下は繋がっている。
(参考1,参考2)
桁落ち：値がほぼ等しいような数値の差を求めた際に、有効数字が大きく減ることで生じる誤差(0.377777-0.377776=0.100000*10^-6となるが、下5桁はあくまで正規化によって0を追加しただけであり、計算結果から導かれるものではない。)(参考)
丸め誤差：長い桁や無限行の少数を扱う際に、有限桁で表現するためにある桁以降の値を捨ててしまうことで生じる誤差(参考)
情報落ち：大きな値と小さな値を用いて加減算を行った際に、絶対値の小さな値が結果に反映されないことによる誤差(参考)
打ち切り誤差：途中で計算を打ち切ることで生じる計算結果と真の値の間の誤差(参考)
値呼び出しと参照呼出し：渡すときは同じだが、値呼び出しがその値のコピーを渡すのに対して、参照呼出しはその変数へのアドレスを渡すことになる。これによって、呼び出した関数内で変数の値を変えた場合に、それがもとの変数に影響しないか、するかが決定される。(参考)
参考：値渡しと参照渡しの話について
双方向リスト：要素、リスト上の次の要素、リスト上の前の要素の三つのリストによって実装される。
- 要素リスト
-
A[i] = Aのように、要素だけが入っている
-
- 次の要素リスト
-
next[i] = 3のように、A[i]の次はA[3]が要素になっているということを示している
-
- 前の要素リスト
-
prev[i] = 2のように、A[i]の前はA[2]が要素になっているということを示している
-
まとめると、要素リストに対して、その配列順を指定するリストが二つ存在するという形式
シェルソート：一定間隔ごとにグループを作り、間隔を徐々に狭めながら挿入ソートで並び変えるアルゴリズム。(参考)
ヒープソート：配列を木構造に入れ込み、親ノード>子ノードとなるように入れ変え続けることで整列させるアルゴリズム。(参考)
マージソート：配列を分割し、要素数が1になった段階で並び替えながら戻すことで整列させるアルゴリズム(参考)
オーバーライド：親クラスで定義したメソッドを継承した子クラスで書き換えること(参考)
オーバーロード：クラス内に引数の数や型が異なる同じ名前のメソッドを複数定義すること(参考)
カプセル化：オブジェクト内への、オブジェクト外からのアクセスを抑制する実装形式？(参考)
汎化：参考
TOF(Time of Flight)センサー：レーザー光が物体に反射して戻ってくるまでの時間を計測して距離を割り出す測定手法(参考)
まとめ
今回で、基礎理論・アルゴリズムとプログラミングの部分の過去問を一通りさらいました。BNFが本当に訳が分かっていませんが、今後も学習を継続していきたいと思います。