覚えるところをまとめました

本記事では応用情報技術者試験の覚えるところを中心にまとめています。自分の勉強用です。

コンピュータ科学基礎

有限オートマトン

状態遷移図を思い出す

浮動小数点の誤差

浮動小数の計算は有効数字の桁数が限られることで以下の誤差が生じる

丸め誤差: 小数点以下の桁数が長い値を、限られた桁数で近似することによって生じる誤差
情報落ち: 絶対値の大きい数と絶対値の小さな数との演算で絶対値の小さな数が切り捨てられることによって生じる誤差
桁落ち: 絶対値のほぼ等しい数同士の演算において、有効数字の桁数が減少する誤差

文字コード

ASCII: アルファベット、数字、特殊文字を表す 7ビット コード
Shift_JIS: 主に PC で利用
漢字や仮名を含めた日本語を表すことができる 16ビット コード
EUC-JP: 主に UNIX で利用
日本語を表すことができる 16ビット コード
Unicode: 世界各国の文字を統一して扱うための 16ビット コード。のちに 21ビット コードに拡張
UTF-8: ASCIIの互換性がある
Unicode を 8ビット単位で符号化するための文字コード
最もよく使われるといってもよい

水平垂直パリティ

行方向と列方向のパリティビットを追加して 1ビットの誤りを検知、訂正することができる。 1 の個数が

偶数の場合はパリティの値が 1
奇数の場合はパリティの値が 0

と覚える

CRC方式

ビット列を多項式とみなして、 生成多項式で除算 することで誤りを検知する。誤り検出符号は、予め、除算で誤りが出ないように付与しておく。誤りが出ていれば誤りが発生したと判断できる。

論理と集合

論理演算

論理演算とは、真また偽をとる値どおりの演算のこと。
AとB は真また偽をとる値をとる数（真 = 1, 偽 = 0とする場合がある）とする。

論理積: A かつ B。AとB 両方とも真の場合、論理積の結果は真となる
論理和: A または B。AとB 少なくとも一方が真の場合、論理和の結果は真となる。（両方1の場合も結果真）
排他的論理和: A とB 二者択一。AとB のどちらか一方が真の場合、排他的論理和の結果は真となる。それ以外（両方真、両方偽の場合結果偽。）

アルゴリズムとデータ構造

スタック

データの 後入れ先出し(LIFO) のこと。

逆ポーランド記法（後置記法）

逆ポーランド記法とは、数式などを記述する際に、演算子を被演算子（演算対象）の列の後に記す方式のこと。
スタックの考え方で計算可能

数値 ... スタックに格納
演算子 ... スタックから数値を2つPOPして計算し、計算結果をスタックに格納

(1+2)*3 は、逆ポーランド記法で 1 2 + 3 * と表される

1 2 + 3 *　の計算方法

1 をスタックへ格納
2 をスタックへ格納
+ 演算子が来たので、2, 1 を POP して、後から来た数字から前の数字を演算子(+)で計算計算した値(=3)は、スタックへ格納
3 をスタックへ格納
* 演算子が来たので、3, 3 をPOPして、3. と同様に計算。答えは 9

キュー

データの 先入れ先出し(FIFO) のこと。

探索アルゴリズム

線形探索

先頭から順番に探索

データ数に比例して計算量が増えるO_(n)

2分探索

要素がキー値の昇順または昇順に並んでいる配列において、　探索範囲を二分しながら指定されたキー値を持つ要素を探し出す

計算量は、 O_(logN)

ハッシュ探索

ハッシュ表を利用した探索。

計算量は、 O₁

整列アルゴリズム

整列とは、データをキー値の昇順あるいは降順に並べ替えること。

選択法

未整列領域の最大値または最小値を選び整列済み領域に追加

バブルソート

整列対象の隣接要素を比較し、逆順であれば交換することを繰り返す

挿入法

未整列領域から要素を一つ取り出し、取り出した要素を整列済みの連の適切な位置に挿入する

シェルソート

挿入法の改良。
配列から一定間隔ごとに要素を取り出し、取り出した要素を挿入法と同等の方法で整列する。
間隔は、徐々に小さくしながら繰り返す。

クイックソート

まず基準値を選択しておく。
基準値よりも小さい配列と大きい配列とに分割する。
小さい配列、大きい配列でまたそれぞれ基準値を決めて同様のことを再帰的に繰り返す

ヒープソート

未整列領域からヒープ(順序木)を作成する。次に最大値（または最小値）を取り出し確定領域に加える。再びヒープを再編成し、次の取り出しを行う。

アルゴリズムとプログラミング

プログラミング言語

リエントラント(Reentrant，再入可能): 各プロセスごとに変数部分を割り当てることで、複数のプロセスで同時に実行できる性質。
リユーザブル(Reusable，再使用可能): プログラムの主記憶への展開を初回実行時のみ行い、以後は何度でも正しく使用できる性質。
リカーシブ(Recursive，再帰可能): プログラム中において自分自身を呼び出すことが可能な性質。　
リロケータブル(Relocation，再配置可能): プログラムを主記憶上のどの位置においても処理が可能な性質。

ハードウェア

命令の実行過程

主記憶装置からプロセッサ委に取り込まれ実行される過程は以下

（主記憶装置） -> （命令フェッチ） -> （デコード） -> （オペランドアドレス算出） -> （オペランドフェッチ） -> （実行） -> （主記憶装置へ）

メモリアーキテクチャ

RAM (Random Access Memory)

DRAM

-	DRAM	SRAM
メモリセルの構成	コンデンサとMOSトランジスタ	フリップフロップ
アクセス速度	遅い	早い
集積度	高い	低い
主な用途	主記憶	レジスタ／キャッシュメモリ
製造コスト	低い	高い

応用情報技術者試験勉強用①