応用情報知識メモ１１（プロセッサ基礎、プログラムの作り方、データ型、探索アルゴリズム、ソートアルゴリズム）

確認問題

以下にスラスラ答えられる人は読まなくても大丈夫。
・コンパイル形式、インタプリタ形式についてそれぞれ説明せよ。
・プリコンパイラ、クロスコンパイラ、ジェネレータについて説明せよ。
・コンパイルして実行されるまでの一連の流れを答えよ。ただし「リンカ」「ローダ」の用語を用いること。
・キュー、スタックについて説明せよ。
・数式[A+B×C] を逆ポーランド記法で表せ。
・ツリー構造の「二分木」「完全二分木」を説明せよ。可能なら具体的な図を示せ。
・二分探索木の走査方法について主なものを２つ答えよ。
・二分探索木の走査時、データの取り出し方によって先行順、中間順、後行順の３パターンに分かれる。それぞれの違いを説明せよ。
・データ探索アルゴリズムのハッシュ法において、シノニム発生時の対処法はオープンアドレス法とチェイン法がある。それぞれについて説明せよ。
・下記ソートアルゴリズムについて説明せよ。またそれぞれの計算量を答えよ。
＞バブルソート、選択ソート、挿入ソート、シェルソート、クイックソート、ヒープソート、マージソート

言語プロセッサ基礎

プログラミング言語はプロセッサにより翻訳されて実行される。事前コンパイルしてから実行する形式と、インタプリタによる実行形式の二つが主。
・コンパイラ：プログラミング言語を翻訳して機械語のプログラムを作成するもの。
・アセンブラ：アセンブラ言語を機械語に翻訳するもの。
・インタプリタ：ソースコードを上から翻訳しすぐ実行するもの。
・プリコンパイラ：定数の値を実数値に変換しておく、などの処理をするもの。
・クロスコンパイラ：コンパイラの動作環境とは異なる環境用のプログラムを生成するもの。Windowsでコンパイルを行い、スマホ向けのプログラムを作成したり。
・ジェネレータ：パラメータを与えることで自動的にプログラムを生成するもの。

コンパイル形式の全体像

コンパイルする際には下記の手順をふむ。
・字句解析：ソースコードを字句(トークン)に分割する。変数名、等号記号、数値…などに。
・構文解析：プログラム言語の構文規則に則っているかを確認する。構文木と呼ばれるデータ構造を生成する。
・意味解析：プログラムの仕様に沿っているかを確認し、中間コードを作成する。
・最適化：処理効率の高いコードに再構成する。例えば関数を呼び出している処理があれば、そこに関数のコードを直接書き込んで呼び出しの手間を省略したり、ループ処理を展開してべた書きしたり、計算できる箇所を予め計算しておいたり、など。
・コード生成：目的プログラムを作成する。

ここまでがコンパイル。これが終わってからリンカ、最後にローダの出番。
・リンカ：モジュールに分割されたソースコードを全部くっつけて統合する。予め全て結合しておく手法を静的リンク、実行時に呼び出されるものだけ結合する手法を動的リンクと呼ぶ。
・ローダ：リンカが作成したプログラムをメモリにロードする。以上。

構造化プログラミング

最上位の処理の流れをイメージしてから細部を作り込んでいく手法。当たり前のこと。

データの型（配列、リスト、キュー、スタック、木構造）

配列、リスト、キュー、スタック、について把握しておくこと。
リストについていくつか補足する。

リストのいろいろ

・単方向リスト：先頭から末尾までしか辿れない構造のリスト。項目の末尾に次の項目へのポインタが付与されているイメージ。
・双方向リスト：先頭から末尾まで辿ることも、末尾から先頭まで辿ることもできる構造のリスト。項目の先頭と末尾の両方にポインタが付与されているイメージ。
・循環リスト：単方向リストのうち、末尾の項目にもポインタが付与されていて先頭へと戻れるもの。つまり輪っか状になっている。

スタックの活用例：逆ポーランド記法

A+Bは「AB+」と表す。項１→項２→演算子、の順番にするということ。
例えばA-B×Cは「ABC×-」となる。
つまり逆ポーランド記法を人間が頭から読むときは、「項１、項２、演算子」のまとまりを発見し、それを演算する、というやり方となる。
これがスタックとどう関係するかというと、演算子が現れた時点での最新の２項を使用するわけだから、演算子を検知した場合、スタックしてきた項を２つ取り出して演算処理を行う、ということになる。

木構造（ツリー構造）

最上位の根（root）から派生して、そこから枝（branch）が伸び、節（節点、node）から更に枝（branch）が伸びていく構造。一番下の要素（そこから下に枝が伸びていないもの）を葉（leaf）と呼ぶ。
全体で「根＞節１＞節２＞…＞葉」という構造になるとき、根は節１の親であり、節１は根の子である、と表現する。
ツリー構造は、ファイルシステム（ドライブからフォルダ階層）、ドメイン名（yahoo.co.jpは、jp＞co＞yahooという構造）などに使われている。

木構造（ツリー構造）の二分木、完全二分木

節から伸びる枝が２本以下の場合、二分木と呼ぶ。
また、二分木構造の場合、要素数が３つの配列構造で表すことができる。
要素１は要素名、要素２は左の子要素へのポインタ、要素３は右の子要素へのポインタ。
完全二分木（Full Binary Tree）とは、二分木構造のうち、最下層の葉と、それ以外の葉との階層の差が１しかないものを指す。完全というとキレイな形に限定しているように思われるが、日本語の定義だとそうではない点に注意。

二分探索木

どの場所においても「左の子＜親＜右の子」という要素の関係性が成立するもの。２が根、１が左の子、３が右の子である状態など。

ヒープ構造

二分探索木とは異なり、左の子と右の子における大小は関係ない構造。下記２パターンに分かれる。
１、根が最小。親＜子がどの場所においても成り立つ。
２、根が最大。親＞子がどの場所においても成り立つ。

AVL木

二分探索木構造において、どの節点においても左部分木と右部分木の高さの差が１以下である構造。下記、参考PDFのURL。
PDFをみると分かる通り、見た目のキレイさには全く関係ない。

http://dopal.cs.uec.ac.jp/okamotoy/lect/2005/DSA/avl.pdf

二分探索木の走査方法

木構造からデータを検索する場合、深さ優先順、幅優先順の２パターンがある。正確に言えば、深さ優先順の場合でも「どのタイミングで要素を取り出すか」が３パターンある。
１、先行順（行きがけ順）：節点→左部分木→右部分木の順番。言い換えれば「根からスタートし、左に進み、要素を発見すればすぐに取り出す」感じ。
２、中間順（通りがけ順）：左部分木→節点→右部分木の順番。言い換えれば「根からスタートし、左に進み、左に進めなくなったところで要素を取り出す。その後節点に戻ったら左にはもう進んだので『左に進めない』と判断して節点を取り出し、右に進み、以下繰り返す」感じ。
３、後行順（帰りがけ順）：左部分木→右部分木→節点の順番。言い換えれば「根からスタートし、葉要素であるものを片っ端から取得し、それが終わったら葉を全部取得済みの親を取得する。以降繰り返す」感じ。

オーダ記法

これから探索アルゴリズム、ソートアルゴリズムを見ていく。そのとき重要な概念が「この処理にどのぐらいの時間がかかるのか」であり、それを数学的に表したのがオーダ記法である。
例えば計算量がNだとしたとき、O(N)と表記する。
ここで注意しなければならないのは、最高次数以外が省略されること、最高次数の係数は無視されること。例えば計算量が$${(n^2 + n) / 2}$$ のとき、オーダはO($${N^2}$$)と表記される。

データ探索アルゴリズム＋計算量(オーダ)

以降、要素の個数がNであると仮定して計算量を記述する。
なお計算量は「最悪のケース」で記述する点に注意。

線形探索法

配列があるとして、[0]から[n]までを順番に見ていくやり方。
計算量O(N)
最悪のケースは末尾に要素が格納されているケースなので、計算量はそのままNとなる。

二分探索法

要素が昇順もしくは降順にソートされている前提で行う探索。ここでは昇順に格納されている前提とする。
配列だとして、真ん中の要素を取り出して比較し、それより小さい要素が欲しい場合は、真ん中の要素から左にある部分の配列を対象に、今と同じ走査を行う。
計算量O($${\log_{2}{n}}$$)

ハッシュ法

ハッシュ計算でデータの格納位置を算出する。
計算量O(１)

ハッシュ法によるシノニム発生の対処法

ハッシュ法によって同値が算出されて値がかぶる場合の対処法は主に２つある。
１、オープンアドレス法：別のハッシュ関数を用いてアドレスを割り当てる方式。
２、チェイン法：同値の箇所を単方向のリストにして、リストの次の要素として追加する手法。「同じところに後ろにくっつける」イメージ。

ソートアルゴリズム＋計算量(オーダ)

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

端から要素同士を比較して必要なら入れ替えを行うソート方法。
計算量O($${n^2}$$)

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

例えば「最小の要素を探して先頭の要素と入れ替える」を端から順番に実行するようなソート方法。
計算量O($${n^2}$$)

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

端から「ここまでは整列済みの要素と見做し、次の要素が整列済みの中でどこに位置するかを調べてから指定の位置に挿入する」処理を繰り返すソート方法。先頭の要素を整列済み扱いとしたら、次の要素が「整列済み」の中でどこに位置するかを決めて必要ならソート処理を行う。次は先頭＋次の２要素を「整列済み」と見做し、３つ目の要素を対象に「整列済みの要素の中でどこに位置するか」を調べて・・・と繰り返す。
計算量O($${n^2}$$)

シェルソート

バブルソートとは異なり、比較処理を複数箇所で同時に行うことで高速性を実現したソート方法。
例えば要素が１６個あるとして、「４つごとの要素で比較」をする。
つまり[1,5,9,13] [2,6,10,14] [3,7,11,15] [4,8,12,16] の４つのグループに分けて、それぞれのデータ間でソートを行う。ソートができたら元の場所に戻し、次は「２つごとの要素で比較」をして・・・と繰り返し、最終的には取り出す間隔を１にして行う。
計算量O(n^(1.2))

クイックソート

中間値を決めて、それより小さいグループ、大きいグループに分ける。
この処理をどちらのグループでも行っていき、グループの要素数が１になればそのグループは処理終了とする。
計算量O（$${n\log_{2}{n}}$$）

ヒープソート

先頭を二分木構造の根と見做し、以降を二分木構造に落とし込んでいく手法。
計算量O（$${n\log_{2}{n}}$$）

マージソート

配列を二分割に分けていき、要素数が１になったら、要素１と要素２を比較してソートする。次は要素１と２の配列、要素３と４の配列を対象にソートをして・・・と繰り返す。
計算量O（$${n\log_{2}{n}}$$）