応用情報をとりたくて~part1/n~

応用情報をとりたくて

きたる10月、応用情報技術者試験があります。ので、それまでの二か月間でひたすらに勉強し、その内容をまとめていきたいと思います。
今回は基礎理論・アルゴリズムとプログラミングの過去問を半分ほど解いたので、その分で出てきた単語をまとめます。

出てきた単語集

正規分布、確率、モンテカルロ法
再帰的、再使用可能、再入可能、再配置可能、相関係数、ユークリッド互助法、　ハフマン符号化、幅優先と深さ優先探索、ディープラーニング、ベイズの定理、排他的論理和、リストの実現(配列orポインタ)、浮動小数の情報落ち、ハッシュ関数の衝突、完全二分木、ニュートン法、オイラー法、ガウスの消去法、シンプソン法、グラフと隣接行列、スタックとヒープ、BNF(バッカス・ナウア記法)、UTF-8、過学習、パリティチェック、有限オートマトン、ハミング符合、M/M/1待ち行列モデル、クイックソート、選択ソート、挿入ソート、バブルソート、BCD(Binary-coded decimal)

それぞれの用語解説

モンテカルロ法：ランダムにn回シミュレーションを行い、確率を近似的に求めるもの。たとえば、円周率であれば一辺が2aの正方形とそこに内接する半径aの円を用意し、正方形内部にランダムに点を打ち、円内部の点に対して打点した数の比率がπ：4になることから近似値を計算できる手法。

プログラム構造の性質(参考)

• リエントラント(再入可能)
  • 実行中プログラムが同時に他プログラムから呼び出されても正常に処理できる
• リユーザブル(再使用可能)
  • メモリ上に読み込まれたプログラムが繰り返し利用可能
• リカーシブ(再帰可能)
  • 処理中に自分自身を呼び出し可能
• リロケータブル(再配置可能)
  • メモリ上のどこに配置されても実行できる

ハフマン符号化：文字列中の文字の出現確率に応じて符号化する方法の一つ(参考)

幅優先探索と深さ優先探索：根から近い順に階層ごとに探索する場合は幅優先、そうではなく根から出発して部分木の最も深いノードまで到達して、一つ前まで戻ってまた探索する場合は深さ優先探索(参考)
後行順の深さ優先探索：左のノードへの移動、右のノードへの移動、移動できなくなったらデータ出力、という形式で、 最後（左右両方のノードに移動できなくなったタイミング）にノードを訪問するタイミングが早い順に各ノードを探索していく方式 のこと(参考)

排他的論理和(XOR)：両者が一致する場合は0を、一致しない場合は1を返す

リストの実現(配列orポインタ)：配列とポインタとで以下の特徴があります。(参考)

• 配列
  • 任意のデータにワンステップで直接アクセスできる
  • 削除、挿入は後ろのデータをずらす必要があるため、処理に時間がかかる
  • あらかじめ領域を定義する必要がある
• ポインタ
  • ポインタをたどる必要があるため、データのアクセスは遅い
  • 削除、挿入はポインタを少し書き換えるだけでOKなので効率的に処理可能
  • 動的に領域を使える

浮動小数点演算における情報落ち：有効桁範囲外の小さな数字部分の情報が結果に反映されないこと(参考)

ハッシュ関数：任意データから別の値を得る操作(参考)

完全二分木：葉以外の接点は全て2つの子を持ち、根から葉までの深さが全て等しい木のことで、葉の数がnならそれ以外の接点はn-1存在する。(参考)

ニュートン法、オイラー法、ガウスの消去法、シンプソン法：数値計算の手法群

• ニュートン法
  • 微分方程式の解の一つを求める方法であり、代入、接線、軸との交点を新しく代入、のループを実施
• オイラー法
  • 微分方程式の数値的解法の一つであり、x_n+1 = x_n+ f'(x_n+h*n)を逐次的に計算することで近似値を得る方法(参考)
• ガウスの消去法
  • 連立方程式を解くための解法であり、連立方程式を行列で計算して、全ての行に対して掃き出しを行い、最終的に係数が対角成分のみの状態にして解を求める手法(参考)
• シンプソン法
  • 積分値を求める際に、非積分関数を二次関数に近似することで近似値を計算する方法(参考)

グラフと隣接行列：グラフはノードとエッジからなるものを指し、隣接行列によってノード同士の接続を表現する。([参考」(https://www.momoyama-usagi.com/entry/math-risan07))

スタックとヒープ：以下の特徴がある。(参考)

• スタック
  • 自動で割り当てられ、関数終了とともに自動で解放
  • 後入先出し(LIFO)
• ヒープ
  • 明示的に確保、解放が必須(ガベージコレクション)
  • 順序なし

BNF(バッカス・ナウア記法)：メタ言語？(参考)

UTF-8：ASCIIと互換性を持ち、同じ部分は1バイト(≠1bit)、違う部分は2~6バイトで表現する文字コード。UTF-8 with bomにすることで、明示的にUTF-8としてファイルを扱わせることができる。(参考1,参考2)

過学習(オーバーフィッティング)：機械学習において、モデルが訓練データに過剰に適合している状態

パリティチェック：一定長ビットごとにパリティビットを付与して、1の数が奇数/偶数になるようにすることで、ビット誤りを検出するもの。データブロック末尾にパリティビットを入れる方式を垂直パリティ、パリティブロックを追加する方式を水平パリティ、これらの融合を垂直水平パリティと呼ぶ。1ビットまでのエラーに対応可能(参考)

有限オートマトン：文字列を識別し、条件に一致する場合のみ受理するもの。開始状態から遷移し、最終的に受理状態集合に属する状態になれば受理する。(参考)

ハミング符合：パリティチェックより検査用ビットを増やすことで、エラー検出と同時に訂正も行える仕組み(参考)

M/M/1モデル：一つの窓口にランダムにやってくる利用者が各々ランダムな時間だけ窓口を占有するという状態をモデル化したものであり、平均待ち時間は利用率を用いて、平均サービス時間*利用率/(1-利用率)で表現される(参考)

クイックソート、選択ソート、挿入ソート、バブルソート：ソート方法は以下のようになっている。(参考)

• クイックソート
  • 基準値を選び、それに対しての大小でグルーピングして整列(分割棟統治法)
• 選択ソート
  • 最小値を選んで端に持ってきて、その後は未整理の要素から最小値を入れ替える形で端に持ってきて、を繰り返すソート方法
• 挿入ソート
  • 整列済みデータに対して、未整理データを一つ持ってきて、適切な位置に挿入することを繰り返すソート方法
• バブルソート
  • 隣り合ったデータを末尾から比較して、順序が逆になっているものを入れ替えることを繰り返すソート方法

BCD(Binary-coded decimal)：2進数4桁で10進数の1桁を表現する方法(参考)

まとめ

今回、過去問を解いて、出てきた単語を調べるという形式で実施しました。アルゴリズム面での知識が弱いので、そこの補強を頑張ろうと思いました。