テクノロジ系基礎理論基礎理論

離散数学

2進数
- 符号なしの2進整数の最大値
  １バイトのデータで0のビット数と1のビット数が等しいもの(11110000)を符号なしの2進整数として見たとき、10進整数として表すと240となる
- 8ビットで表される符号なし2進数xが16の倍数であるかどうかを調べる方法
  xと2進数00001111のビットごとの論理積をとった結果が0である
基数
- 基数変換
  2進数の有限小数は、10進数にしても必ず有限小数になる
- 実数aをa=f x r^eと表す浮動小数点表示
  fを仮数、eを指数、rを基数という
数値表現
- 負の整数を表現する代表的な方法
  - 1の補数
    各ビットの0,1を反転させたもので、一番左のビットが符号ビットとなる(0の場合は正、1の場合は負)
    8ビットの場合-127～+127を表現できるが、2通りの0が生じる
  - 2の補数
    1の補数に1を加えたもの、一番左のビットが符号ビットとなる(0の場合は正、1の場合は負)
    8ビットの場合-128～+127を表現できる
    - 2進数の表現で、2の補数を使用する理由
      減算を、負数の作成と加算処理で行うことができる
  - 絶対値に符号をつける(左端ビットが0の場合は正、1の場合は負など)
  - 浮動小数点表示法における仮数が正規化されている理由
    有効数字の桁数を最大に保つため
- 固定小数点
  - 10進数-5.625を、8ビット固定小数点形式による2進数で表したもの(小数点位置は3ビット目と4ビットの間とし、負数には2の補数表現を用いる)
    10100110
演算精度
- 桁落ち
  値がほぼ等しい浮遊小数点数同士の減算において、有効桁が減るために発生する誤差
- 桁上げ
  浮動小数点表示において、仮数部の最上位桁が０以外になるように、桁あわせする操作
- 近似値
  - 必要とされる誤差の範囲内で、ある数を表しているとして構わない数値
  - 近似値の求め方
    - (1+α)^n の計算を1+n×αで近似計算が出来る条件
      |α|が1に比べて非常に小さい
- 情報落ち
  - 浮動小数点演算において、絶対値の大きな数と絶対値の小さな数の加減算を行ったとき、絶対値の小さな数の有効桁の一部又は全部が無視され結果に反映されないこと
  - 数多くの数値の加減算を行う場合、情報落ちを防ぐには、絶対値の小さなものから順番に計算するとよい
- 丸め誤差
  浮動小数点形式で表現された数値の演算結果において、数表現の桁数に限度があるので、最下位けたより小さい部分について四捨五入や切り上げ、切捨てを行うことによって生じる
- 打ち切り誤差
  全ての演算が終了する前に、あらかじめ指定されたルールよって演算が打ち切られ生じる誤差
- 絶対誤差
  近似値から真値を代数的に引いて得られる誤差
- 相対誤差
  真の値に対する誤差の割合
集合
- 和両立である関係RとSがあるとき、-は差演算、∩は共通集合演算とすると、R∩SとR-(R-S)は等しい
- (X∩Y)はXとYの共通部分(積集合)、(X∪Y)はX又はYの少なくとも一方に属する部分(和集合)とするとき、二つの集合AとBについて、常に成立する関係
  (A∩B)はAの部分集合である
ベン図
- 集合の関係や範囲を図式化したもの
- 黒色で塗りつぶした部分の検索条件
  (not A) and B and C

論理演算

論理積(AND)A・B

A	B	出力
0	0	0
0	1	0
1	0	0
1	1	1

論理和(OR)A+B
X OR Y =(X NAND Y)NAND(Y NAND Y)

A	B	出力
0	0	0
0	1	1
1	0	1
1	1	1

否定(NOT)A

A	出力
0	1
1	0

否定論理積(NAND)A・B

A	B	出力
0	0	1
0	1	1
1	0	1
1	1	0

二つの入力と一つの出力を持つ論理回路で、二つの入力A,Bがともに1のときだけ出力Xが0になる
X NAND Y = NOT(X AND Y)
X =A・ B + A ・ B+ A・ B

否定論理和(NOR)A+B

A	B	出力
0	0	1
0	1	0
1	0	0
1	1	0

排他的論理和(XOR)A・B＋A・B

A	B	出力
0	0	0
0	1	1
1	0	1
1	1	0

相補演算
任意のオペランドに対するブール演算Aの結果とブール演算Bの結果が互いに否定の関係にあるとき、AはBの(又はBはAの)相補演算であるという

命題
判断を言語で表したもので、真または偽という性質をもつもの

応用数学

数値解析
- N個の観測値の平均値を算出する式
  SはN個の観測値の和(S>0)
  [X]はX以下で最大の整数
  平均値は、小数第1位を四捨五入して整数値として求める
  [S/N+0.5]
数式処理
- 四則演算の式の書き方
  - 前置記法：演算子をオペランドの前に書く方法
  - 中置表表記法：演算子をオペランドの間に書く方法
  - 後置表記法(逆ポーランド表記法 / 逆ポーランド記法)：演算子をオペランドの後に書く方法
    - 例
      - A＋B×C　→　ABC×＋
      - ((E－F)÷G)＋((C－D)÷(A＋B))　→　EF－G÷CD－AB＋÷＋
      - Y＝A－B)×C　→　YAB－C×＝
      - Y＝(A＋B)×(C－D÷E)　→　YAB＋CDE÷－×＝
      - E＝(A＋B)×(C－D)　→　EAB＋CD－×＝
グラフ理論
- 隣接行列
  - ｎ個の節点から成るグラフの接点ViとVjを結ぶ枝が存在するときは第i行第j列と第j行第i列の要素が1となり、存在しないときは0となるn行ｎ列の行列
  - 隣接行列Aで表されるグラフ
待ち行列理論
- 窓口業務において、来訪者の到着状況に応じた窓口数とサービス時間を解析するときに用いる理論
- M/M/1の待ち行列モデル
  - サービス時間
    指数分布
  - 一定時間内に到着する客数の分布
    ポアソン分布
- 平均到着率(サービス率)　λ＝件数/単位時間
- 平均サービス時間(平均サービス率)　μ＝1/平均処理時間(サービス)
- 呼量　a＝λ/μ
- 利用率　ρ≦１
  ρ＝(件数×平均処理時間)/単位時間
  ＝平均到着数/平均サービス数
  ＝λ/μ
- 平均待ち数＝ρ/(1-ρ)
- 平均待ち時間＝平均待ち数×平均サービス時間
  ＝(ρ/1-ρ)×(1/μ)
- 平均応答時間＝平均待ち時間+平均サービス時間
  ＝(ρ/1-ρ)(1/μ)+(1/μ)
  ＝1/(μ-λ)
- 待ち行列モデルの適用事例
  - 電話の平均受け付け回数、平均対応時間などを基に、問い合わせに対応するサービスデスクの要員数を決定する
  - プリンタの印刷要求から印刷完了までの所要時間を待ち行列理論を適用して見積もる場合のM/M/1の待ち行列モデル
  - 条件に当てはまるもの
    - 印刷の緊急性や印刷量の多さにかかわらず、先着順に印刷する
  - 条件に反するもの
    - 一部のクライアントは、プリンタの空き具合を見ながら印刷要求する
    - 印刷待ちの文書データがプリンタのバッファサイズを越えるときは、一時的に受付を中断する
    - 一つの印刷要求にかかわる時間は、印刷の準備に要する一定時間と、印刷量に比例する時間の合計である

情報に関する理論

符号理論
- ランレングス符号化
  文字列中で同じ文字が繰り返される場合、繰り返し部分をその反復回数と文字の組に置き換えて文字列を短くする方法
- ハフマン符号
  出現頻度の高い文字に短い符号を割当てることで、データの圧縮を行う手法
形式言語
- BNF(Backus-Naur Form ；バッカス・ナウア記法)
  文脈自由文法を定義するために使われるメタ言語
  - 終端記号
    形式文法における生成規則の記述に使われる記号で、文法で生成される文字列の一部を構成する要素
  - 非終端記号
    形式文法における生成規則の記述に使われる記号で、文法の生成規則内で使われる変数名で、他の非終端記号や終端記号に置換されて文字列を生成する
- 命令語
  命令の種類によっては、オペランドがないものもある

計算量(オーダー)

アルゴリズムにおいて、解に至るまでに必要な操作回数
オーダ表記
アルゴリズムの処理時間や問題の計算時間を比較するときに使用するアルゴリズムがこれより遅くならないという計算量の上限値
例
相違なるn個のデータが昇順に整理された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾だけを線形探索することによって、目的のデータの存在するブロックを探し出す。次に該当ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式。ここでmは十分大きく、nはmの倍数とし、目的のデータは必ず表の中に存在する
(m/2)+(n/2m)

探索の平均計算量が最も小さい探索手法と表の組み合わせ

探索手法	探索表の種類
2分探索	コード順に格納した探索表
線形探索	コードの使用頻度順に格納した探索表
ハッシュ表探索	コードから一意に決まる場所に格納した探索表

人工知能
- エージェント(自律エージェント)
  以下の動作をする
  1. 利用者から仕事を託され、ネットワーク内でその仕事を処理するのに必要な場所(サーバ)を自立的にめぐって、仕事を片付ける
  2. すべての仕事が終了した時点で利用者の下に返る
  3. ネットワーク内に送出された後、返ってくるまで、利用者はネットワークにアクセスする必要はない
コンパイラ理論
- 最適化
  - プログラムコードを解析して実行時の処理効率を高め、実行時間を短縮できるオブジェクトコードを生成する
  - 定数が格納される変数を追跡し、途中で値が変更されないことが確認できれば、その変数を定数で置き換えることで目的プログラムの実行時間を短くする
  - プログラムの実行時間を短縮する
- 定数の畳込み
  オブジェクトコードの所要記憶容量が削減できる
プログラミング言語論・意味論
- 論理型プログラミング
  プログラムに”事実”と”規則”を記述し、プログラム言語の処理系が持つ導出原理によって結論を得るプログラミングパラダイムであって、エキスパートシステムの開発に適している
- あるプログラム言語の解説書の中に次の記述があるとき、この記述中の"良いプログラム"がもっている特長
  
  [記述]
  このプログラム言語では、関数を呼び出すときに引数を保持吸うためにスタックが使用される。
  引数で受け渡すデータを、どの関数からでも参照できる共通域に移せば、
  スタックの使用量を減らすことができるが、"良いプログラム"とはみなされないこともある。
  特徴：プログラムの一部(モジュール)を変更しても、残りの部分への影響が少ない
- 関数型プログラミング
  関数は入力を受けて出力するが、同じ入力に対して異なる出力をするような内部状態を一切持たない
- 手続き型プログラミング
  プロシージャ、ルーチン、サブルーチン、メソッド、関数など実行すべき一連の計算ステップをプログラム実行中の任意の時点で呼び出して処理を行う

通信に関する理論

伝送理論
- 伝送路
  - ツイストペアケーブル
    - カテゴリ5EのUTPケーブルは1000BASE-Tで利用される非シールドより対線であり、2本の銅線が4対収められている
    - 10BASE-T
      2対のUTPケーブルを使用し、最大距離は100mである
    - 100BASE-T
      媒体アクセス方式は、10BASE-Tと同じCSMA/CDである
    - 100BASE-TX
      より対線4ペアのうち1ペアを送信、1ペアを受信に使用し、残り2ペアは未使用
    - 1000BASE-T
      カテゴリ5eまたはカテゴリ6のケーブルを使用する
      カテゴリ5又はそれ以上のUTPケーブルを使用する
      4対のUTPケーブルを使用し、最大距離は100mである
      1000BASE-TXと通信方式が異なるためクロスケーブルの結線は異なる
    - 1000BASE-TX
      10BASE-Tと100BASE-TXで使用するクロスケーブルの送信ペアと受信ペアの結線は1000BASE-Tと同じなので、100BASE-TXの機器でも使用できる
    - 1000BASE-LX
      IEEE802.3のCSMA/CD方式のLAN
      シングルモード光ファイバケーブルを使用し、最大距離は5kmである
    - 10GBASE-SR/SW
      マルチモード光ファイバケーブルを使用し、最大距離は400mである
- 変復調方式
  - CCK(Complementary Code Keying)
    ビット列のデータ信号を電波に対応付けるための変調方式
    無線LANの標準仕様であるIEEE802.11bで採用されている
- 多重化方式
  - TDM(Time Division Multiplexing ；時分割多重)
    信号を一定の間隔だけずらすことで複数の回線を1本の回線にまとめる技術
    タイムスロットと呼ばれる単位で分割して、同一周波数において複数の通信を可能にする
  - TDMA(Time Division Multiple Access ；時分割多元接続)
    タイムスロットを割り当てられたノードだけが送信を行う
  - OFDM(Orthogonal Frequency-Division Multiplexing)
    直交周波数分割多重方式
    高速無線通信で使われている多重化方式で、データ信号を複数のサブキャリアに分割し、各サブキャリアが互いに干渉しないように配置する方式
  - CDM(Code Division Multiplex)
    符号分割多重化
    無線通信の通信方式の一つ
    発信者の音声信号には符号が付けられ、他の発信者の音声信号と合成されて受信側に送る方式
    携帯電話などの無線通信に使われる方式
- 誤り検出・訂正
  - CRC方式(巡回冗長検査)
    - 送信側ではビット列をある生成多項式で割った余りをそのビット列に付加して送信し、受信側では受信したビット列が同じ生成多項式で割り切れるか否かで誤りの発生を判断する誤り検査方式
    - 送信側では、生成多項式を用いて検査対象のデータから検査用のデータを作り、これを検査対象のデータに付けて送信する
    - 生成多項式がｎ次の場合、長さｎ以下のバースト誤りをすべて検出できる
    - 巡回符号
      CRCで用いるコード
  - パリティチェック方式
    - パリティビットを用いた誤り検出方式
    - 誤り検出は可能だがデータ誤りを復元することは不可能
    - 水平パリティ
      検査したいデータをマトリクス状に並べ、その行と列にパリティを付けたうちの列に付けられるパリティ
    - 垂直パリティ
      検査したいデータをマトリクス状に並べ、その行と列にパリティを付けたうちの行に付けられるパリティ
      1ビットの誤りを検出できる
    - 奇数パリティ
      2進数の0と1のうち1の個数が必ず奇数になるようにパリティビットを付加する方式
      7ビットのコードと1ビットのパリティビットからなる8ビットのデータで発生した誤りを復元することは不可能である
  - チェックサム
    データを数値とみなして合計を取ったもので、データの受信後に同じ計算をして一致するか確認することで誤りを検出する
- 信号同期方式
  - 調歩同期式
  - キャラクタ同期

計測・制御に関する理論

信号処理
フィードバック制御
外乱による影響を検知してから修正動作を行う
フィードフォワード制御
出力に変動を起こさせるような外乱を予測し、前もって打ち消してしまう制御方式
各種制御
- 非同期信号を同期化する方法
  Dフリップフロップを2段にして、初段の出力を2段目でもう一度受けなおす
センサ・アクチュエータの種類と動作特性
- アクチュエータ
  ロボットなどの制御システムを構成する
  機械・機構を物理的に動かす
- フォトカプラ
  他の装置からシリアルインタフェースを介して入力されたノイズの影響で、システムが誤動作するようになった場合の対策として他の装置とアイソレーションする場合に使用するデバイス
- DCモータ
  - PWM制御方法
    パルスのデューティ比によって、モータの回転数を制御する
    スイッチングノイズを発生することがある
- インクリメンタルエンコーダ
  位置決めセンサに用いる
  回転方向を知るために出力信号が2相になっている
- 温度センサ
  測温抵抗体は電気抵抗を利用したセンサであり、高精度の工業計測に用いられる
- ウォッチドッグタイマ
  あらかじめ設定された一定時間内にタイマがクリアされなかった場合、システム異常とみなしてシステムに通知する
  ハードウェアタイマでCPUのリセット信号を発生させるようにしておき、ハードウェアタイマで設定した時間が経過する前にプログラムでハードウェアタイマをリセットする

テクノロジ系 基礎理論 基礎理論

離散数学

応用数学

情報に関する理論

通信に関する理論

計測・制御に関する理論

テクノロジ系基礎理論基礎理論