基礎理論
コンピュータは数も文字も0と1で扱います。その表し方と計算のきまり、確率・統計、情報量、通信と制御の理論は、ほかの全単元で使います。
要点
離散数学
- 基数
- n進数の各桁の重みはnの累乗。2進数 1011 は 8＋2＋1＝11。
- 10進→2進は2で割った余りを下から並べる。2進4桁が16進1桁、3桁が8進1桁。
- 数値の表現
- 負の数は2の補数（全ビット反転して1を足す）。8ビットなら −128〜127。
- 小数は固定小数点数か浮動小数点数（符号・指数・仮数）。単精度は32ビット、倍精度は64ビット。
- BCDは10進1桁を4ビットで表す。パック10進数は1バイトに2桁を詰め、末尾4ビットが符号。
- 算術演算と精度
- 論理シフトは空いた桁に0を入れ、算術シフトは符号ビットを保つ。左へ1ビットで2倍、右へ1ビットで約1/2。
- 範囲を超えるとオーバーフロー、0に近すぎるとアンダーフロー。
- 近い値の引き算で有効桁が減るのが桁落ち、大きな数に小さな数を足して小さい方が消えるのが情報落ち。
- 集合と命題
- 和集合（A∪B）、積集合（A∩B）、補集合、部分集合をベン図で描いて確かめる。
- 真か偽かが決まる文が命題。命題を論理演算で組み合わせて扱うのが命題論理。
- 論理演算
- 論理積（AND）は両方1で1、論理和（OR）はどちらか1で1、排他的論理和（XOR）は異なるとき1。
- 否定論理積（NAND）と否定論理和（NOR）は、ANDとORの結果を否定（NOT）したもの。
- ド・モルガンの法則：NOT(A AND B)＝NOT A OR NOT B。真理値表で全通りを書けば確かめられる。
応用数学
- 確率
- 並べる数は順列、選ぶだけなら組み合わせ。どちらも階乗で計算する。
- 同時に起きない事象は確率を足す（加法定理）。独立な事象は掛ける（乗法定理）。
- Aが起きたときのBの確率が条件付き確率。原因と結果を逆向きにたどるのがベイズの定理。
- 値×確率の合計が期待値。二項分布・正規分布・ポアソン分布などの確率分布で表す。
- 統計
- 代表値は平均値・中央値・最頻値。ばらつきは分散と、その平方根の標準偏差。
- 相関係数は −1〜1。相関があっても因果とは限らない。第3の要因による見かけの相関が擬似相関。
- 回帰分析は説明変数から目的変数を予測する。仮説検定はp値が有意水準より小さいとき帰無仮説を棄却する。
- 数値計算
- 行列で連立一次方程式を表して解く。掛けると単位行列になるのが逆行列、行と列を入れ替えたのが転置行列。
- 対数（log₂8＝3）は情報量や計算量に出てくる。等差・等比・フィボナッチの各数列も扱う。
- 数値解析
- 二分法は解をはさむ区間を半分ずつ縮める。ニュートン法は接線とx軸の交点を次の近似値にする。
- 真の値との差が絶対誤差、それを真の値で割ると相対誤差。計算途中で丸め誤差や打切り誤差が出る。
- 数式処理
- 数値ではなく文字式のまま、因数分解・微分・積分をコンピュータで計算する。
- グラフ理論
- 点（頂点）と線（辺）でつながりを表す。向きのない無向グラフと、矢印の付いた有向グラフがある。
- 待ち行列理論
- M/M/1 は窓口1つのモデル。利用率 ρ＝平均到着率÷平均サービス率。
- 平均待ち時間＝ρ÷(1−ρ)×平均サービス時間。ρが1に近づくと急に長くなる。
- 最適化問題
- 条件を守りながら最大・最小を求める。線形計画法、PERT、最短経路問題が代表例。
- 小さな問題の答えを表に残して大きな問題を解くのが動的計画法。
情報に関する理論
- 情報理論
- 確率pで起きる事象の情報量は −log₂p ビット。起こりにくいほど大きく、確率1/8なら3ビット。
- 符号理論
- アナログ信号を標本化・量子化・符号化の順にデジタルへ変える（A/D変換）。
- データを短くするのが情報源符号化（例：ハフマン符号）、誤りに強くするのが通信路符号化。
- 文字の表現
- ASCIIは7ビットの英数字。日本語はJISコード・シフトJIS・EUC、世界の文字をまとめたのがUnicode（UCS）。
- ゾーン10進数は10進1桁を1バイトで表し、最下位バイトの上位4ビットに符号を入れる。
- 述語論理
- 「すべての x について」「ある x について」のように変数を含む文を扱う。関係データベースの問い合わせも、この考え方で説明できる。
- 一般的な規則から個別の結論を導くのが演繹推論、個別の例から規則を導くのが帰納推論。
- 形式言語
- 記号の並べ方の規則（文法）で言語を決める。BNFや構文図式で書き、正規表現や文脈自由文法がある。
- 演算子を後ろに置く逆ポーランド表記法では、(A＋B)×C を AB＋C× と書く。
- オートマトン
- 今の状態と入力で次の状態が決まる仕組み。有限オートマトンを状態遷移図や状態遷移表で表す。
- 計算量
- データ量nに対する手間をオーダー記法で表す。線形探索は O(n)、二分探索は O(log n)。
- AI（人工知能）
- 専門家の知識を知識ベースに入れ、推論エンジンで答えを出すのがエキスパートシステム。
- 機械学習には、正解付きで学ぶ教師あり学習、正解なしで分ける教師なし学習、報酬で学ぶ強化学習がある。
- 学習データだけに合いすぎるのが過学習。検証データや交差検証で見つける。
- ディープラーニングは多層のニューラルネットワーク。バックプロパゲーションで重みを直す。
- 画像はCNN、文や音声のような並びはRNN。文章を生成する大規模言語モデル（LLM）も生成モデルの一つ。
- コンパイラ理論
- 字句解析→構文解析→意味解析→最適化→コード生成の順に、原始プログラムを目的プログラムへ翻訳する。
- プログラム言語論
- 命令を順に書く手続型言語、関数を組み合わせる関数型言語、事実と規則を書く論理型言語、オブジェクト指向言語がある。
通信に関する理論
- 伝送路
- 一方向だけの単方向、交互に送る半二重、同時に両方向へ送る全二重。
- 変復調方式
- 搬送波の振幅を変えるAM、周波数を変えるFM、位相を変えるPM。アナログを0と1のパルス列にするのがPCM。
- 多重化方式
- 周波数の帯を分けるFDMと、時間を細かく区切って順番に使うTDM。
- 誤り検出・訂正
- パリティチェックは1の個数を偶数（または奇数）にそろえる。1ビットの誤りを見つけられるが、直せない。
- ハミング符号は1ビットの誤りの位置まで分かり、訂正できる。CRCやチェックサムは検出用。
- 信号同期方式
- 1文字ごとにスタートビットとストップビットではさむ調歩同期。
- 同期用の文字で合わせるSYN同期（キャラクタ同期）、特定のビット列で区切るフラグ同期もある。
計測・制御に関する理論
- 信号処理
- センサの信号をA/D変換して数値にし、フィルタリングで雑音を除く。出力側はD/A変換でアナログに戻す。
- 制御の仕組み
- 結果を測って目標との差を打ち消すのがフィードバック制御。乱れを先に測って補正するのがフィードフォワード制御。
- 結果を見ずに決めた手順で動かすのがオープンループ制御。決めた時間内に応答するためリアルタイムOSを使う。
- センサとアクチュエータ
- 温度はサーミスタ、磁気はホール素子、傾きや回転は加速度センサ・ジャイロセンサ、変形はひずみゲージで測る。
- アクチュエータは電気信号を動きに変える装置。モータ、油圧シリンダ、空気圧シリンダなど。
さわって確かめる
数の表し方・論理演算・誤り訂正を、次の3つで自分で動かします。結果の欄には、途中の計算も出ます。
1. 8ビットの数と2の補数
−13 を入れて、2の補数のビット列と、その作り方を確かめよう。
ビット（押すと 0 と 1 が切り替わる。下の数は重み）
2. 論理演算と真理値表
演算を選び、AとBを切り替えて、真理値表のどの行になるかを見よう。
入力
ド・モルガンの法則（どの行でも左右の2列が同じになる）
3. ハミング符号で1ビットの誤りを直す
送るデータ4ビットを決め、届いた7ビットのどれか1つを押して壊し、受け手が直せるか見よう。
送るデータ（d1〜d4）
届いた7ビット（押すと、通信の途中でそのビットが反転したことにする）
3問チェック
最初に選んだ答えで採点します。全問正解で、この単元に「済み」の印が付きます。
-
8ビットの2の補数で表した 11111010 は、10進数でいくつか。
- −5
- −6
- 250
- −122
答えと解説
正解はイ。先頭が1なので負の数。全ビットを反転すると 00000101、1を足すと 00000110＝6 なので −6。250 は符号なしとして読んだ値。
-
論理式 NOT(A OR B) と、AとBがどの値でも同じ結果になるものはどれか。
- (NOT A) OR (NOT B)
- (NOT A) AND (NOT B)
- A AND B
- (NOT A) AND B
答えと解説
正解はイ。ド・モルガンの法則で、ORの否定は「否定どうしのAND」になる。A＝0、B＝0のときだけ両方1、それ以外は両方0。
-
窓口が1つの受付に、客が平均して1時間に12人来る。1人の受付には平均4分かかる。M/M/1モデルで考えると、窓口に並んで待つ時間の平均は何分か。
- 3.2分
- 4分
- 16分
- 20分
答えと解説
正解はウ。平均サービス率は1時間に60÷4＝15人なので、利用率 ρ＝12÷15＝0.8。待ち時間＝0.8÷(1−0.8)×4分＝16分。20分は、待ち時間に受付の4分を足した「窓口を出るまでの時間」。