More than 1 year has passed since last update.

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

Last updated at 2023-05-31Posted at 2022-09-01

アルゴリズム

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

フローチャートと擬似言語

↑ アルゴリズムを簡単に記述する方法

フローチャート

記号を使ってアルゴリズムを記述する

アルゴリズムの制御構造

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

①順次　　　　　　　　　　　　　　　　　②選択　　　　　　　　　　　　　　　　　　　③繰り返し

選択　

・　双岐選択（二つの処理のうちどちらかを選択）　　　　・　多岐選択（三つ以上の処理のうちどれかを選択）

繰り返し

・　前判定繰り返し　　　　　　　　　　　　　　　　　　　　　　・　後判定繰り返し

擬似言語

データ構造

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

配列

同じデータ型のデータ（要素）を、連続して管理する
・　１次元配列 （データ取得　→ 添字　1つ）　　・ ２次元配列　（データ取得　→ 添字　2つ）

＊　データの個数が頻繁に変わるプログラムには向かない管理方法

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

キューとスタック

キュー（スーパーのレジ）

格納した順序でデータを取り出す方法
→ FIFO（First In First Out）：　最初に格納したデータを最初に取り出す

（入力されたデータが順番通りに処理される必要がある場面）

　ジョブ待ち　：　待ち行列
　GUIプログラム　：　マウスで操作した順番に処理
　プリンタ　：　印刷用のキューにたまったデータを順番に印刷
エンキュー（enqueue）：キューにデータを格納する
デキュー（dequeue）：　キューからデータを取り出す

スタック（エレベーター）

格納した順序とは逆の順序でデータを取り出す方法
→ LIFO（Last In First Out）：　最後に格納したデータを最初に取り出す
→ データ退避（割り込み時）に用いられる
（処理途中のデータ　→ スタック　→ 別の処理　→ さっきスタックしたデータを呼び出す）

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

木構造

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

（活用例）

ハードディスクのファイルシステム
インターネットのドメイン名
節（ノード）：　◯の部分
枝（ブランチ）：　節と節をつなぐ線
根（ルート）：　最上位の節　
葉（リーフ）：　最下位の節
親：　上位の節
子：　下位の節
左部分木：節の左側にぶら下がっている部分
右部分木：　節の右側にぶら下がっている部分

2分木

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

完全2分木

根から葉までの深さが全て等しい2分木
→ 深さが1だけ深い葉があり、木の左から詰められているものも含む

2分探索木

各節の値において「左の子　＜　親　＜　右の子」の大小関係をもつ2分木

＊　A₄＜　A₂＜　A₅＜　A₁＜　A₆＜　A₃＜　A₇
＊　根から葉に向かってデータを探索するときに使われる

根から順に各節の値と比較する

節の値と同じなら探索終了　→ 該当データあり
節の値より小さければ、左部分木へ移動
節の値より大きければ、右部分木へ移動

これを繰り返す
葉まで行っても一致しなければ探索終了　→ 該当データなし

ヒープ木

各節において「親　＜　子」または「親　＞　子」の大小関係をもつ完全2分木

＊　根　：　最小値（最大値）になる
＊　ヒープ木　：　データの整列で使われる

逆ポーランド記法

2分木を使って、節に演算子、葉に非演算子を書く方法（左部分木　→ 右部分木　→ 節点　の順で取り出す）
　　
＊（逆ポーランド記法）43 ＋ 21 ー ×
→ (4 + 3) × (2 ー 1)

＊　逆ポーランド記法：スタックを使って演算

非演算子はスタックにPUSH
演算子はスタックから2個のデータをPOP
計算結果をスタックにPUSH

データの整列

アルゴリズムで基礎的かつ単純なアルゴリズムがある　→ 整列

整列（ソート）　：　規則に従ってデータを並べ替えること
- 昇順：　小さい　→　大きい　に並べ替え
- 降順：　大きい　→　小さい　に並べ替え

基本交換法（バブルソート）

隣のデータを比較・交換する方法

基本選択法（選択ソート）

データの最小値（最大値）と先頭データを交換する方法

基本挿入法（挿入ソート）

データ列を「整列済み」と「未整列のも」に分け、未整列のものを整列済みの適切な位置に挿入する方法

その他の整列法

より高速なアルゴリズム

シェルソート

一定間隔で取り出した要素で部分列を作り、それぞれ整列して戻す方法

クイックソート

基準値を決めて、「それより小さい値」と「それより大きい値」でグループ分けする方法

ヒープソート

未整列の部分を木構造にして、最大値（最小値）を整列済みへと並べる方法

データの探索

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

線形探索法

先頭から順番に探す方法

番兵法

目的のデータを配列の最後に追加する方法
→　条件判定を簡単にする目的

線形探索法の探索回数

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

2分探索法

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

フローチャートであらわす

2分探索法の探索回数

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

ハッシュ探索法

目的のデータの場所（アドレス）を、関数を使って探す方法

＊　「12345」というデータも場所は「２」
→ シノニム　：　アドレスが衝突すること

ハッシュ法の探索回数

1回

プログラムの属性

プログラムに4つの性質を持たせることがある


再配置可能（リロケータブル）	メモリのどこに配置しても実行できる
再入可能（リエントラント）	複数のタスクを同時に使用可能
再使用可能（リユーザブル）	再ロードしなくても使用可能
再帰的（リカーシブ）	自分自身を呼び出せる

プログラム言語とマークアップ言語

プログラム言語

低水準言語（コンピュータが理解しやすい言語）

機械語　：　コンピュータが理解できる言語。「０」「１」で構成
アセンブラ言語　：　機械語を記号で置き換えた言語

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

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

言語プロセッサ

ソースコードを機械語に翻訳するプログラム

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

コンパイラ形式でのプログラム実行手順

コンパイラの仕事

コンパイル　：　ソースコード（高水準言語）から目的プログラムファイル（機械語）に変えること
コンパイラの手順

リンカの仕事

リンク　：　複数の目的プログラムなどから実行可能ファイルを生成すること

ローダの仕事

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

動的/静的リンキング

動的リンキング：　プログラム実行中　→ 必要なモジュールをリンク
静的リンキング：　プログラム実行前　→ モジュールをリンク

その他の言語プロセッサ

プロセッサ	処理
プリコンパイラ	ソースプログラム＋αプログラム　→ ソースプログラムのみに変換
クロスコンパイラ	別のコンピュータで実行できるプログラム生成
ジェネレータ	入力・出力をパラメータで指定　→ 自動的にプログラム生成
トランスレータ	ある処理系用のプログラム　→ 別の処理系用のプログラム
エミュレータ	他のコンピュータ用プログラム　→ 解読・実行

開発ツール

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

統合開発環境（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）：　動的に画面を再描画する仕組み

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up