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

# アルゴリズム
- **アルゴリズム**　：　問題を解くための手段、作業手順　例）　料理のレシピ
- **変数**　：　データを格納する箱
- **トレース**　：　アルゴリズムをたどって、変数の変化を追跡すること


## フローチャートと擬似言語
↑ アルゴリズムを簡単に記述する方法

### フローチャート
記号を使ってアルゴリズムを記述する
![フローチャート.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/c188e8d3-1ecd-22dc-a746-2ca0ea1da9a1.jpeg)

### アルゴリズムの制御構造
アルゴリズムは3つの制御構造からなる

①**順次**　　　　　　　　　　　　　　　　　②**選択**　　　　　　　　　　　　　　　　　　　③**繰り返し**
![アルゴリズム＿3つ＿制御構造.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/f796f99c-402f-c2dc-cae8-bc85931d2596.jpeg)

#### 選択　
・　**双岐選択**（二つの処理のうちどちらかを選択）　　　　・　**多岐選択**（三つ以上の処理のうちどれかを選択）
![選択＿双岐＿多岐.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/0ca379f5-ee85-402a-8fcf-81becc294dc8.jpeg)
#### 繰り返し
・　**前判定繰り返し**　　　　　　　　　　　　　　　　　　　　　　・　**後判定繰り返し**
![繰り返し＿前＿後判定.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/14399349-281c-9c66-4dd4-43b1b40dc377.jpeg)


### 擬似言語
![アルゴリズム＿擬似言語.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/bdde8c9f-c777-3660-28ae-7b98205a5eb1.jpeg)
























# データ構造
複数のデータを効率よく管理する方法
→ プログラムの特性にあったデータ構造をとる
→　配列・リスト・キューとスタック・木構造...

## 配列
同じデータ型のデータ（**要素**）を、連続して管理する
・　**１次元配列** （データ取得　→ 添字　1つ）          　　・ **２次元配列**　（データ取得　→ 添字　2つ）
![配列_1,2次元配列.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/7b21a1fb-bc50-a14c-c395-33548a525a4f.jpeg)
＊　データの個数が頻繁に変わるプログラムには向かない管理方法




















## リスト
**データ部**（データを記録する場所）と**ポインタ部**（データの格納位置）でデータを管理する方法
→ **ポインタをたどってデータを取得**（データとデータを数珠繋ぎにして管理する）
→ ポインタ部の示す方向が3種類

**単方向リスト**：次のデータの場所　　　**双方向リスト**：次と前のデータの場所　　　**環状リスト**：最後尾データが先頭のデータを指す
![リスト_単・双・環状.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/95d0fac6-2cdd-276c-7949-32ef8fef8ee7.jpeg)
単方向リストのイメージ
![単方向リスト_イメージ.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/3377b4fe-842b-9b14-34fa-ea187cb6e954.jpeg)

### 配列とリストの比較
||配列|リスト|
|:--|:--|:--|
|**格納領域**|連続領域に順番通り|非連続・非順番通りで可|
|**総データ数**|先に決定|変更可能|
|**データの挿入・削除**|後ろのデータもずらす（処理時間大）|前後のポインタのみ修正（処理時間小）|
|**データのアクセス**|添字でアクセス（早）|ポインタをたどる（遅）|





















## キューとスタック
### キュー（スーパーのレジ）
格納した順序でデータを取り出す方法
→ **FIFO（First In First Out）**：　最初に格納したデータを最初に取り出す

（入力されたデータが順番通りに処理される必要がある場面）
- 　ジョブ待ち　：　待ち行列
- 　GUIプログラム　：　マウスで操作した順番に処理
- 　プリンタ　：　印刷用のキューにたまったデータを順番に印刷
![キュー.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/ca361b26-61db-3799-1e6f-681c952f05eb.jpeg)

- **エンキュー（enqueue）**：キューにデータを格納する
- **デキュー（dequeue）**：　キューからデータを取り出す

### スタック（エレベーター）
格納した順序とは逆の順序でデータを取り出す方法
→ **LIFO（Last In First Out）**：　最後に格納したデータを最初に取り出す
→ データ退避（割り込み時）に用いられる
（処理途中のデータ　→ スタック　→ 別の処理　→ さっきスタックしたデータを呼び出す）
![スタック.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/05a49130-932e-a998-ffda-4833f6524ff8.jpeg)


- **プッシュ（push）**：　スタックにデータを格納すること
- **ポップ（pop）**：　スタックからデータを取り出すこと


























## 木構造
階層構造を効率よく管理する方法

（活用例）
- ハードディスクのファイルシステム
- インターネットのドメイン名
![木構造.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/771e0f70-d961-608d-cbad-49498ec5a25c.jpeg)
- **節（ノード）**：　◯の部分
- **枝（ブランチ）**：　節と節をつなぐ線
- **根（ルート）**：　最上位の節　
- **葉（リーフ）**：　最下位の節
- **親**：　上位の節
- **子**：　下位の節
- **左部分木**：節の左側にぶら下がっている部分
- **右部分木**：　節の右側にぶら下がっている部分

### 2分木
節から伸びる全ての枝が2本以下の木構造

#### 完全2分木
根から葉までの深さが全て等しい2分木
→ 深さが1だけ深い葉があり、木の左から詰められているものも含む
![完全2分木.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/c678727c-cde8-0528-0e26-485a891320a6.jpeg)

#### 2分探索木
各節の値において「左の子　＜　親　＜　右の子」の大小関係をもつ2分木
![2分探索木.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/af03b1e4-74b5-0da7-bc62-78a6cb720ffb.jpeg)
＊　A₄＜　A₂＜　A₅＜　A₁＜　A₆＜　A₃＜　A₇
＊　根から葉に向かってデータを探索するときに使われる
1. 根から順に各節の値と比較する
- 節の値と同じなら探索終了　→ 該当データあり
- 節の値より小さければ、左部分木へ移動
- 節の値より大きければ、右部分木へ移動
1. これを繰り返す
1. 葉まで行っても一致しなければ探索終了　→ 該当データなし


#### ヒープ木
各節において「親　＜　子」または「親　＞　子」の大小関係をもつ完全2分木
![ヒープ木.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/31a2b22a-619e-d445-1e84-d621f6433599.jpeg)
＊　根　：　最小値（最大値）になる
＊　ヒープ木　：　データの整列で使われる


### 逆ポーランド記法
2分木を使って、節に演算子、葉に非演算子を書く方法（左部分木　→ 右部分木　→ 節点　の順で取り出す）
　　![逆ポーランド記法.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/c0983c5d-89d4-1a86-7fb4-eee6a874a5c3.jpeg)
＊（逆ポーランド記法）43 ＋ 21 ー ×
→ (4 + 3) × (2 ー 1)

＊　逆ポーランド記法：スタックを使って演算
1. 非演算子はスタックにPUSH
1. 演算子はスタックから2個のデータをPOP
1. 計算結果をスタックにPUSH
![逆ポーランド記法_スタック.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/ccb8ee3f-f46c-4bdb-d356-9c36925f39f6.jpeg)





























# データの整列
アルゴリズムで基礎的かつ単純なアルゴリズムがある　→ 整列
- **整列（ソート）**　：　規則に従ってデータを並べ替えること
    - **昇順**：　小さい　→　大きい　に並べ替え
    - **降順**：　大きい　→　小さい　に並べ替え　


## 基本交換法（バブルソート）
隣のデータを比較・交換する方法
![基本交換法.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/d5627453-ddda-3b7d-a4fc-a617e8c3d682.jpeg)

## 基本選択法（選択ソート）
データの最小値（最大値）と先頭データを交換する方法
![基本選択法.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/387a40e1-0929-3e2f-4228-27f06b4abd7d.jpeg)

## 基本挿入法（挿入ソート）
データ列を「整列済み」と「未整列のも」に分け、未整列のものを整列済みの適切な位置に挿入する方法
![基本挿入法.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/68b38c81-f73f-7cc0-6437-56eb8cef683d.jpeg)

## その他の整列法
より高速なアルゴリズム

### シェルソート
一定間隔で取り出した要素で部分列を作り、それぞれ整列して戻す方法
![シェルソート.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/72c91e8a-9d56-1f22-d215-5ee9783af159.jpeg)

### クイックソート
基準値を決めて、「それより小さい値」と「それより大きい値」でグループ分けする方法
![クイックソート.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/d51df30b-4526-b50d-1f12-3cc119500677.jpeg)


### ヒープソート
未整列の部分を木構造にして、最大値（最小値）を整列済みへと並べる方法
![ヒープソート.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/35fd8889-f350-df84-0b47-6a82874bf8c5.jpeg)




































# データの探索
目的のデータを探し出すこと

## 線形探索法
先頭から順番に探す方法
![線形探索法.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/792bfd93-4a95-c3ca-5cd5-4bfb98e3995f.jpeg)


### 番兵法
目的のデータを配列の最後に追加する方法
→　条件判定を簡単にする目的
![番兵法.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/985adbf6-5896-f0b9-9e4a-7599c13ef4f1.jpeg)

#### 線形探索法の探索回数
**（１　＋　N）　/　２**
＊ 探索回数　：　最小1回　/　最大N回
→　最小と最大の平均

## 2分探索法
探索範囲を半分に限定しながら探す方法
→ データが**昇順・降順**で並んでいることが前提

フローチャートであらわす
![2分探索法.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/ab719345-e440-144a-b4a6-7a0cf5e2a43e.jpeg)

#### 2分探索法の探索回数
**log₂N**
→ 意味：Nは2の何乗か？
→　データ数が2倍になるにつき、探索回数が1回増える


## ハッシュ探索法
目的のデータの場所（アドレス）を、関数を使って探す方法
![ハッシュ法.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/d3b7aefe-2b3c-30bc-c90f-9964c9ba7a5e.jpeg)
＊　「12345」というデータも場所は「２」
→ **シノニム**　：　アドレスが衝突すること

#### ハッシュ法の探索回数
1回

































# プログラムの属性
プログラムに4つの性質を持たせることがある
|||
|:--|:--|
|**再配置可能（リロケータブル）**|メモリのどこに配置しても実行できる|
|**再入可能（リエントラント）**|複数のタスクを同時に使用可能|
|**再使用可能（リユーザブル）**|再ロードしなくても使用可能|
|**再帰的（リカーシブ）**|自分自身を呼び出せる|


































# プログラム言語とマークアップ言語
## プログラム言語
1. **低水準言語**（コンピュータが理解しやすい言語）
- **機械語**　：　コンピュータが理解できる言語。「０」「１」で構成
- **アセンブラ言語**　：　機械語を記号で置き換えた言語

2. **高水準言語**（人間が理解しやすい言語）

|種類|説明|
|:--|:--|
|**BASIC**|初心者向けの会話型言語|
|**COBOL**|事務処理計算に適した言語|
|**C**|システム記述に適した言語|
|**C++**|C言語にオブジェクト指向を加えた言語|
|**Java**|オブジェクト指向型言語|
|**Python**|人工知能などの開発に適した言語|
|**JavaScript**|動的なWebページの作成に適した言語|

### 言語プロセッサ
ソースコードを機械語に翻訳するプログラム
|種類|説明|
|:-:|:--|
|アセンブラ|アセンブラ言語を機械語に翻訳する|
|**インタプリタ**|ソースコードを1命令ずつ翻訳しながら実行する|
|**コンパイラ**|ソースコードを一挙に翻訳する|

### コンパイラ形式でのプログラム実行手順
![コンパイルの手順.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/4dbe29d1-50c3-46e8-4d32-2c263a3aa14e.jpeg)

#### コンパイラの仕事
**コンパイル**　：　ソースコード（高水準言語）から目的プログラムファイル（機械語）に変えること
コンパイラの手順
![コンパイラ_仕事.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/23b91c74-eef0-a210-18be-4de65360ec5a.jpeg)

#### リンカの仕事
**リンク**　：　複数の目的プログラムなどから実行可能ファイルを生成すること
![リンカの仕事.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2746950/f2a0a3ed-201c-569b-4434-b7a1521b60bb.jpeg)

#### ローダの仕事
**ロード**　：　実行可能ファイルをメモリに読み込ませること

#### 動的/静的リンキング
- **動的リンキング**：　プログラム実行中　→ 必要なモジュールをリンク
- **静的リンキング**：　プログラム実行前　→ モジュールをリンク
### その他の言語プロセッサ
|プロセッサ|処理|
|:--:|:--|
|**プリコンパイラ**|ソースプログラム＋αプログラム　→ ソースプログラムのみに変換|
|**クロスコンパイラ**|別のコンピュータで実行できるプログラム生成|
|**ジェネレータ**|入力・出力をパラメータで指定　→ 自動的にプログラム生成|
|**トランスレータ**|ある処理系用のプログラム　→ 別の処理系用のプログラム|
|**エミュレータ**|他のコンピュータ用プログラム　→ 解読・実行|


### 開発ツール
プログラムをより効率的に行うための開発ツール

#### 統合開発環境（IDE:Integrated Development Environment）
アプリケーション開発のためのソフトウェア・支援ツールをまとめたもの（Eclipseなど）

#### デバックツール
**デバック**　：　プログラムの誤り（**バグ**）を見つけて、取り除くこと
|デバックのツール|説明|
|:--|:--|
|**トレーサ**|プログラムの実行結果を時系列に出力|
|**スナップショットダンプ**|特定のプログラムを実行するごとに、指定のメモリ内容を出力|
|**メモリダンプ**|プログラムの異常終了時に、メモリやレジスタの内容を出力|
|**静的解析ツール**|プログラムを実行せずに、バグを解析する|

### 開発で使う専門用語
- **ビルド**：　コンパイル・リンク　→　実行可能ファイルを作ること
- マージ：　合体すること
- **継続的インテグレーション**
    - 分担したソースコードを共有の保管場所（リポジトリ）にマージ
    - ビルド・テストを繰り返す　→　**Jenkins**：　ビルド・テストを自動化するツール
- **デプロイ**：　実行可能ファイル　→ 実行環境にインストール　→ 使える状態にする
### 形式言語
特定の目的のために人為的に作られた言語

#### BNF記法（Backus-Naur Form）
＜S＞：：＝ ○ 　「Sは○と定義する」
＜S＞：：＝ ０１ | ０＜S＞1　　「Sは０１と定義する」　または　「Sは０＜S＞１と定義する」

#### 正規表現
[A - Z]+ [0 - 9]*　　「英大文字を一回以上、その後の数字を０回以上の文字列」
＜意味＞
→ [-] ：　カッコ内のどれかにあたる文字
→ ＊　：　文字を０回以上の繰り返し
→ ＋　：　文字を１回以上の繰り返し
＜正誤例＞
→ ◯ ：　「ANG０８」「TOKYO」
→ × ：　「２５AG」


## マークアップ言語
テキストにタグをつける言語

### SGML（Standard Generalized Markup Language）
電子的な文章の管理・交換をする言語
→ HTML・XMLのもと
#### HTML（Hyper Text Markup Language）
Webページを作成するためのマークアップ言語
HTML ：　文章構造を記述（見出し・段落など）
**CSS(Cascading Style Sheets)**　：　デザインを記述（文字の大きさ・色）
#### XML（eXtensible Markup Language）
**DTD**で記述　→　利用者独自のタグを定義できるマークアップ言語

＊　**Ajax**（JavaScript＋XML）：　動的に画面を再描画する仕組み