応用情報技術者 まとめノート

0 / 527 正解 (0回答)
第1章

離散数学・基数変換・論理演算・誤差

0/14 正解
📖この章で学ぶこと

コンピュータが扱う離散数学の基礎を整理します。2進数・8進数・16進数といった基数の表現と相互変換、正負の数を扱う2の補数表現、浮動小数点数による実数の近似表現、AND・OR・NOT・XOR などの論理演算とブール代数、そして桁あふれ・丸め誤差・打切り誤差・情報落ち・桁落ちといった数値計算で発生する誤差の種類を学びます。応用情報の午前問題で毎回出題される最頻出論点です。

人間が日常使用する10進数に対し、コンピュータ内部では電圧の高低を0と1で表現するが用いられる。2進数の4桁は16進数のに対応するため、メモリアドレスやカラーコードなど人間が扱う際には16進数表記が多用される。例えば10進数の255は2進数で11111111、16進数ではと表記される。コンピュータで負の整数を表現する方式として最も広く採用されているのは表現である。2の補数はビット反転後に1を加えることで得られ、加減算回路を共通化できる利点がある。nビットの2の補数で表現できる整数の範囲はである。例えば8ビットでは -128 〜 +127 の範囲を表現できる。
📌ここがポイント

浮動小数点数は IEEE 754 規格に基づき「符号部・指数部・仮数部」の3要素で実数を近似する。単精度(32bit)は符号1+指数8+仮数23、倍精度(64bit)は符号1+指数11+仮数52。指数部にはバイアス(単精度は127)を加えた下駄履き表現が用いられる。仮数部の最上位ビット1は省略するケチ表現が標準。

実数を計算機内部で扱うため、IEEE 754 で規格化された形式が広く用いられる。単精度浮動小数点数(float)は32ビットで、内訳は符号部1ビット、指数部、仮数部23ビットである。倍精度(double)では64ビットで、指数部11ビット、仮数部52ビットとなる。論理演算において、両方が真のときのみ真となる演算を、少なくとも一方が真のとき真となる演算を OR（論理和）、両者が異なるとき真となる演算をという。XOR は同じ値同士でビット単位の XOR を取ると0になる性質から、暗号化やビット反転の用途で利用される。ブール代数におけるド・モルガンの法則は「NOT(A AND B) = (NOT A) OR (NOT B)」「NOT(A OR B) = (NOT A) AND (NOT B)」で表され、回路設計においてはゲートだけ、または NOR ゲートだけですべての論理回路を構成できる(完全系)という事実の基礎となる。半加算器は AND と XOR で構成され、全加算器は半加算器2個と OR ゲート1個で構成される。
🔥本試験頻出

誤差の分類は午前必出。①桁あふれ(オーバーフロー):表現範囲超過、②打切り誤差:無限級数を有限項で打ち切ったときの誤差、③丸め誤差:最下位ビット未満を四捨五入/切捨て、④桁落ち:値がほぼ等しい数同士の減算で有効桁が失われる、⑤情報落ち:絶対値が大きく異なる数の加減算で小さい値が無視される。

浮動小数点演算で値の近い2数の減算を行うと、有効桁数が大きく減少する誤差が発生する。これをという。一方、絶対値が極端に異なる2数を加減算した際に、小さい値が無視されてしまう誤差をと呼ぶ。さらに、無限級数を有限項で打ち切って計算する際に生じる誤差を打切り誤差、最下位桁未満を四捨五入や切捨てで処理する際に生じる誤差をと呼ぶ。集合論における要素数を求める際、有限集合 A, B について「|A ∪ B| = |A| + |B| − |A ∩ B|」が成り立つ。この公式は3集合以上では「包除原理」へと一般化される。また、集合の要素を 1 と 0 のビット列で表現することで、和集合は OR、積集合は AND、補集合は NOT としてで高速に計算できる。これは集合演算の実装手法として頻出。
1 / 30 章