【基本情報技術者試験】基礎理論、アルゴリズムとプログラミング

# はじめに

こんにちは、エンジニア3年目の嶋田です。
まずは、この記事を開いていただきありがとうございます！

今日は基本情報技術者試験に出題される「基礎理論」と「アルゴリズムとプログラミング」について、私がきちんと理解しているか確認するためも含め、まとめていきたいと思います。

今後、少しの間はインプットとアウトプットを繰り返す為に基本情報技術者試験の内容が多くなるかもしれません🙇‍♂️

# 目次

- [基礎理論](#基礎理論)
    - [補数と減基数](#補数と減基数)
    - [ニュートン法](#ニュートン法)
    - [エラーチェック技術](#エラーチェック技術)
    - [A/D変換処理](#ad変換処理)
- [アルゴリズムとプログラミング](#アルゴリズムとプログラミング)
    - [データ構造](#データ構造)
    - [プログラムの性質](#プログラムの性質)
- [復習問題](#復習問題)
- [解答と解説](#解答と解説)
- [最後に](#最後に)
- [参考文献](#参考文献)

# 基礎理論

## 補数と減基数

補数とは、ある数に対して加算することで桁上がりが発生し、その結果最小の数になる数のことを指します。10進数では、10の補数を用いてマイナスの数を表現することができます。例えば、82から23を引きたい場合、23の補数である77を82に加えることで、159となり、最上位の桁を除くことで59、つまり82-23の結果を得ることができます。

2進数の場合、1の補数と2の補数があり、これらはそれぞれ減基数と通常の補数に相当します。1の補数はビット反転によって得られ、2の補数は1の補数に1を加えることで得られます。これらの補数を理解することは、コンピュータが内部で数値を処理する仕組みを理解する上で非常に重要です。

### 10進数での補数の例

- 4 の補数は 6 （10 - 4 = 6）
- 23 の補数は 77 （100 - 23 = 77）

## ニュートン法

ニュートン法は、非線形方程式の近似解を求めるための数値解析方法です。この方法は、方程式の接線の方程式を利用して、反復的に近似値を求めることにより、目的の方程式の解を見つけ出します。ニュートン法はその速度の速さから、工学や科学の分野で広く用いられています。

```python
# ニュートン法の簡単なコード例
def newton_method(f, df, x0, eps):
    """
    f  : 目的の関数
    df : f の導関数
    x0 : 初期推定値
    eps: 許容誤差
    """
    x = x0
    while abs(f(x)) > eps:
        x = x - f(x) / df(x)
    return x
```

## エラーチェック技術

データ通信において誤りを検出するための技術には、CRC方式、パリティチェック、垂直・水平パリティなどがあります。これらの技術は、データの信頼性を高めるために不可欠であり、特にデータ通信での誤りを検出し、正確なデータ転送を確保するために使用されます。

### パリティチェックの例

- 偶数パリティ：1の個数が偶数になるようにパリティビットを付加
- 奇数パリティ：1の個数が奇数になるようにパリティビットを付加

例えば、データビットが `100101` の場合、1 の個数は 3 つです。偶数パリティを適用する場合、1 の個数を偶数にするためにパリティビットとして `1` を追加します。結果、`1001011` となります。

## A/D変換処理

アナログ信号をデジタルデータに変換するプロセスは、標本化、量子化、符号化の3ステップで構成されます。

1. **標本化**：アナログ信号の強度を一定間隔で測定します。
2. **量子化**：測定した値を固定された範囲の値（通常は整数）に割り当てます。
3. **符号化**：量子化された値をデジタル信号（ビット列）に変換します。

このプロセスにより、アナログの現実世界の情報が、コンピュータやデジタルデバイスで扱える形に変換されます。

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

## データ構造

プログラミングにおいて、データを効率的に管理するためには適切なデータ構造を選択することが重要です。

- **スタック（LIFO）**：後入れ先出しの原則に基づくデータ構造です。最後に追加された要素が最初に取り出されます。
- **キュー（FIFO）**：先入れ先出しの原則に基づくデータ構造です。最初に追加された要素が最初に取り出されます。

これらの基本的なデータ構造の理解は、より複雑なデータ構造やアルゴリズムを学ぶ上での基礎となります。

## プログラムの性質

プログラミングにおける重要な概念には、以下のようなものがあります。

- **リエントラント（再入可能）**：複数のタスクから同時に安全に呼び出せる関数やプログラムの性質。
- **リカーシブ（再帰）**：自分自身を呼び出すことによって問題を解決するプログラムの手法。
- **リロケータブル（再配置可能）**：プログラムがメモリ内の任意の位置に配置されても正しく実行できる性質。

これらの性質を理解し、適切にプログラムに適用することで、より柔軟で再利用可能なコードを作成することができます。


# 復習問題
基礎理論とアルゴリズムとプログラミングに関する問題です。
今日の記事の分野の復習をしましょう！

## 問題1: 補数と減基数
10進数の数字58から数字34を引くために、10の補数を使用する場合、34の10の補数はいくつですか？

## 問題2: ニュートン法
ニュートン法を使用して、方程式 x^2 - 2 = 0 の解の1つを求める場合、初期値 x0 = 1.0 として、最初の反復での x の値はいくつですか？（ヒント：f(x) = x^2 - 2, f'(x) = 2x）

## 問題3: エラーチェック技術
データビット 1010010 に偶数パリティチェックを適用する場合、最終的なビット列は何になりますか？

## 問題4: A/D変換処理
アナログ信号をデジタル信号に変換する際に最初に行われるプロセスは何ですか？

1. 標本化
2. 量子化
3. 符号化
4. 変調

## 問題5: データ構造
以下の操作を行った場合、最後にスタックから取り出される値は何ですか？

1. 値 5 をスタックに追加
2. 値 10 をスタックに追加
3. 最上位の値をスタックから取り出し
4. 値 15 をスタックに追加

# 解答と解説

## 問題1の解答
34の10の補数を求めるためには、100 - 34 = 66 と計算します。よって、答えは**66**です。

## 問題2の解答
ニュートン法の式 x = x - f(x)/f'(x) を用いて計算します。f(x) = x^2 - 2, f'(x) = 2x として、x = 1 - (1^2 - 2)/(2*1) = 1.5。よって、最初の反復での x の値は**1.5**です。

## 問題3の解答
1010010 には3つの 1 が含まれており、偶数にするためには 1 を追加する必要があります。結果のビット列は **10100101**です。

## 問題4の解答
アナログ信号をデジタル信号に変換する際に最初に行われるプロセスは「標本化」です。正解は**1**です。

## 問題5の解答
操作を行うと、スタックは次のようになります：5 を追加 -> 10 を追加 -> 10 を取り出し -> 15 を追加。よって、最後に取り出される値は**15**です。

# 最後に
最後までお付き合いいただきありがとうございました。
基礎知識があるという証明、担保として資格はある方がいいな〜と最近思っています。
なので、未経験エンジニアの皆さん一緒に頑張りましょう！