【基本情報技術者】アルゴリズムとプログラミングについて

GW明け一発目、アルゴリズムとプログラミングです。

私の得意分野です。

気合を入れて、やってみよー！

基本情報技術者～アルゴリズムとプログラミング～

データ構造の種類

データ構造には以下の5つの種類があります。

1. スタック
2. キュー
3. 配列
4. 連結リスト
5. 木構造

です。

それぞれについて、簡単に説明していきます。

スタック

スタックとは、最後に入れたデータを最初に取り出すデータ構造です。

スタックにデータを入力することを、「push（プッシュ）」といいます。スタックにAというデータを入力する際のコマンドは「push A」となります。

スタックからデータを取り出すことを「pop（ポップ）といいます。データを取り出す際のコマンドは「pop」です。「pop A」ではないので、間違えないようにしましょう。

キュー

キューとは、最初に入れたデータを最初に取り出すデータ構造です。

キューにデータを入力することを「enqueue（エンキュー）」といいます。キューにBというデータを入力する際のコマンドは「enqueue B」となります。

キューからデータを取り出すことを「dequeue（デキュー）」といいます。データを取り出す際のコマンドは「dequeue」です。スタックのときと同様に「dequeue B」とはならないので、間違えないようにしましょう。

配列

配列とは、データを表にしたデータ構造です。

1次元配列

配列のうち、要素が1列に並ぶ配列のことを1次元配列と呼びます。

例えば上の例で、配列Aから要素番号4のデータを取り出す場合、A[4]と記述します。

2次元配列

配列のうち、要素が縦横に並ぶ配列のことを2次元配列と呼びます。

横の並びを「行」と呼び、縦の並びを「列」と呼びます。上の例で、2次元配列Aから「2行目4列目」の要素「千葉県」を取り出すには、A[2, 4]と記述します。

連結リスト

連結リストとは、データを数珠つなぎに並べたデータ構造のことです。配列との違いは、連結リストにはデータにポインタが付き、ポインタによって次の要素のアドレスを知ることができます。

コンピュータは、ポインタに格納されたアドレスを辿って、目的のデータにアクセスするという仕組みになっています。

上の図を例にとると、「佐藤」というデータを持つ要素は「9番地」というポインタも持っています。このことから、「佐藤」の次のデータは9番地にある「鈴木」であるということがわかります。

配列と連結リストの違い

配列と連結リストは、どちらも「データが順番に並んでいる」という点は同じです。しかし、データへのアクセス方法が異なります。

配列

配列で「鈴木」のデータを探す場合、直接、A[4]と指定することができます。

連結リスト

一方、連結リストで「鈴木」のデータを探す場合、先頭1番地から見ていく必要があります。このケースですと「鈴木」は9番地にあることがわかりますね。

このような仕組みのため、配列はデータを取り出す速度が速く、連結リストは場合によっては時間がかる作りになっています。

ただし、配列にもデメリットがあります。それは、間にデータを挿入したり、削除を行なう場合です。データの挿入・削除では、配列は挿入・削除した後のデータをすべてずらさなければならない一方で、連結リストでは、ポインタを変更するだけで簡単に挿入・削除を行なうことができます。

まとめると、

配列は、参照・更新が速い
連結リストは、挿入・削除が速い

となります。

木構造

木構造とは、階層構造になっているデータ構造のことです。

これはファイル構造を木構造で示したものです。根が「ルートディレクトリ」、節が「ディレクトリ」、葉が「ファイル、または、データ」となります。

木構造の親子関係

木構造には親子関係があります。分岐元を「親」、分岐先を「子」と呼びます。

親は子をいくつでも持つことができますが、親が0～2個の子を持つ木構造を2分木（にぶんぎ）と呼び、親が0～3個の子を持つ木構造を3分木（さんぶんぎ）と呼びます。

さらにこの規則を一般化して、親が0～n個の子を持つ木構造をn分木と呼んでいます。つまり、分木とは、最大でいくつの子を持つかを表しています。

2分探索木

2分木の中でも、

左の子孫　＜　親　＜　右の子孫

という関係にあるものを、2分探索木と呼びます。ここでいう「子孫」とは「親よりも下にあるデータ」という意味です。

2分探索木として適切な例を以下に挙げます。左が適切な例で、右が誤った例です。

子孫の中では、

左の子孫　＜　親　＜　右の子孫

という関係にあったとしても、その更にひとつ上の親の子孫として見たときに、親　＞　右の子孫　となっていたり、その逆であったりするケースは2分探索木にはなり得ません。

2分探索木であることのメリットとしては、根から葉までの階層の数だけ値を調べれば、目的のデータを探せるという点です。

小休止！お試しトライ！過去問①

問1 スタック

問題
A、B、C、Dの順に到着するデータに対して、一つのスタックだけを用いて出力可能なデータ列はどれか。

平成29年度

ア．A、D、B、C
イ．B、D、A、C
ウ．C、B、D、A
エ．D、C、A、B

解答
ア．から順番に試していきます。

ア．Aを入れる、Aを出す、B、C、Dを入れる、Dを出す、Cを出す、Bを出すとなり、
A、D、C、B
としかならない。

イ．A、Bを入れる、Bを出す、C、Dを入れる、Dを出す、Cを出す、Aを出すとなり、
B、D、C、A
としかならない。

ウ．A、B、Cを入れる、Cを出す、Bを出す、Dを入れる、Dを出す、Aを出すとなり、
C、B、D、A
正解となる。

エ．A、B、C、Dを入れる、Dを出す、Cを出す、Bを出す、Aを出すとなり、
D、C、B、A
としかならない。

従って、ウ．が正解となります。

問2 キュー

問題
待ち行列に対する操作を、次の通り定義する。

平成30年度

　ENQ n：待ち行列にデータnを挿入する。
　DEQ：待ち行列からデータを取り出す。
空の待ち行列に対し、ENQ 1、ENQ 2、ENQ 3、DEQ、ENQ 4、ENQ 5、DEQ、ENQ 6、DEQ、DEQの操作を行った。次にDEQ操作を行ったとき、取り出されるデータはどれか。

ア．1
イ．2
ウ．5
エ．6

解答
指示通りにキューに値を詰めたり出したりしてみましょう。

①ENQ 1 → 1
②ENQ 2 → 21
③ENQ 3 → 321
④DEQ　 → 32
⑤ENQ 4 → 432
⑥ENQ 5 → 5432
⑦DEQ　 → 543
⑧ENQ 6 → 6543
⑨DEQ　 → 654
⑩DEQ　 → 65

ここで、DEQを行ったときに出力されるデータは、5となります。

従って、ウ．が正解となります。

アルゴリズムの基本

アルゴリズムとは、問題を解決するときの手段です。

アルゴリズムの表現方法には以下の4種類があります。

1. 文章（文字による表現）
2. 流れ図（図による表現）
3. 数式（関数による表現）
4. プログラム言語（コンピュータが理解できる言語による表現）

基本情報技術者試験では流れ図がよく出題されるとのことなので、流れ図の基本について触れておきましょう。

流れ図で使用する記号

基本情報技術者試験で出題される流れ図は、以下の5種類です。しっかりと覚えておきましょう。

記号	記号名	役割
	端子	流れ図の開始と終了を表す。記号の中に「開始」「終了」と記述する。
	処理	計算や値の代入などの処理を表す。例えば、AをBに代入するには「A→B」「B←A」と記述する。
	判断	処理を分岐するための条件を表す。出口に「Yes」「No」などの判定結果を記述する。
	線	処理の順番や流れを表す。処理が下から上へ戻る場合など、処理の流れがわかりづらいときは矢印で表現する。
	ループ端	ループ（繰り返し処理）の開始と終了を表す。

あとは様々な流れ図を見て、使い方を理解しましょう。また、流れ図などのアルゴリズムを完全に理解するために、トレース表の書き方などもマスターしておくと良いです。

小休止！お試しトライ！過去問②

問1 アルゴリズム（関数）

問題
整数x, y(x > y ≧ 0)に対して、次のように定義された関数F(x, y)がある。F(231, 15) の値は幾らか。ここで、x mod y は x を y で割った余りである。

平成28年度

ア．2　　イ．3　　ウ．5　　エ．7

解答
y = 0 となるまで、繰り返し処理が行われる関数であることがわかると思います。処理をトレース表などを用いて、1回ずつ記述していけば解けます。

F(231, 15)
(y ＞ 0 である)
x ＝ 15
y ＝ 231 ％ 15 ＝ 6

F(15, 6)
(y ＞ 0 である)
x ＝ 6
y ＝ 15 ％ 6 ＝ 3

F(6, 3)
(y ＞ 0 である)
x = 3
y = 6 ％ 3 ＝ 0

F(3, 0)
(y ＝ 0 である)
x = 3

y ＝ 0 のため、x = 3 が返ります。

従って、イ．が正解となります。

アルゴリズムの分類

基本情報技術者試験では、以下の3種類のアルゴリズムが出題されます。

1. 整列アルゴリズム（データを並べるためのアルゴリズム）
2. 探索アルゴリズム（データを見つけ出すためのアルゴリズム）
3. 再帰的アルゴリズム（処理の途中で自分自身を呼び出すアルゴリズム）

整列アルゴリズム

整列アルゴリズムには、以下の4種類があります。

1. バブルソート
2. 選択ソート
3. 挿入ソート
4. クイックソート

基本情報技術者試験では、ほとんどの場合、クイックソートが出題されます。

クイックソート

4　6　8　3　5　1　7　2　9

という数列があり、これを昇順（小さい順）に並べ替えるとします。このとき、基準値を適当に決めます。今回は「5」を基準値としてみます。

基準値より小さいものは左に、大きいものは右に並べ替えていきます。

4　1　3　2　5　6　8　7　9

5 を中心に左右で2つのグループができます。これはまだソートしきれていませんので、またそれぞれ基準値を決めて、ソートをしていきます。左のグループは「3」を、右のグループは「8」を基準値としてみます。

1　2　3　4

6　7　8　9

ここで、コンピュータ的には、1　2 と 6　7 の振り分けができていませんので、「2」「7」をそれぞれ基準値として、ソートを試みます。

1　2

6　7

その結果、わずか3段階の施行で以下のように数字を並べ替えることができました。

1　2　3　4　5　6　7　8　9

このクイックソートはもっとも高速なソート方法ですので、しっかりと覚えておきましょう。

探索アルゴリズム

探索アルゴリズムとは、特定のデータを探し出すアルゴリズムです。探索アルゴリズムには、以下の3つがあります。

1. 線形探索法
2. ハッシュ法
3. 2分探索法

基本情報技術者試験では、ハッシュ法と2分探索法が頻出されています。

ハッシュ法

ハッシュ法のアルゴリズムは、探索対象のデータをハッシュ値に変換して、このハッシュ値を元に目的のデータを見つけるという探索法です。

例えば、10の剰余、つまり x mod 10 のようなハッシュ関数により、データをハッシュ値に変換することができます。

32 という数字であれば、2 がハッシュ値になります。この 2 を元に、アドレス 2 に数値 32 を格納します。

ただし、このケースですと 32 も 42 も 52 もすべてハッシュ値は 2 となり、競合が起きていまいます。これでは効率が悪くなり、このようにハッシュ値が競合することが起こり得ることがハッシュ法の弱点ともなっています。

2分探索法

2分探索法とは、調べる範囲を半分に分割していくことで、素早く目的のデータを見つけ出すアルゴリズムです。

2分探索法には、以下の特徴があります。

1. データを、あらかじめ整列させておかなければならない
2. データを、2つに分けながら探索していく

ここで、1～9まで数値がならんでいる数列から、6というデータを見つけ出す方法を見ていきましょう。

1. 真ん中の数値（要素番号）を計算する
   (1 + 9) ÷ 2 ＝ 5
   要素番号 5 のデータは 5 で、この 5 と 6 を比較すると、6 は 5 より大きいため、左のグループには 6 が存在しないことがわかります。
2. 右半分の要素に対して 1．と同様の手順を行なう
   (6 + 9) ÷ 2 ＝ 7.5 ≒ 7
   ここでは切り捨てで 7 としましたが、切り上げで 8 としても構いません。そして、要素番号 7 のデータは 7 で、この 7 と 6 を比較すると、6 は 7 より小さいため、右のグループには 6 が存在しないことがわかります。
3. 左の要素に対して、同様の手順を行なう
   (6 + 6) ÷ 2 ＝ 6
   要素番号 6 に入っているデータは 6 です。比較を行い、6 と一致することがわかります。今回は3回の手順で6を見つけ出すことができました。

再帰的アルゴリズム

再帰的アルゴリズムとは、処理の途中で自分自身を呼び出すアルゴリズムです。「再帰」とは「繰り返し」という意味です。この再帰的アルゴリズムを使ったプログラムですが、設定を間違えると無限ループになる可能性のある、私の苦手とするジャンルになります。

基本情報技術者試験で使用される再帰的アルゴリズムは、以下の3つです。

1. 総和（1からnまでの総和を求める）
2. 剰余（わり算の余り。計算では mod が用いられる）
3. 階乗（1からnまでをすべてかけ算した数を求める）

総和

数式で総和を表現すると、次のようになります。

これは、1 から x までの総和 を表す式です。

オーダー（計算量）の求め方

アルゴリズムを完了するために必要な計算量のことを「オーダー」と呼びます。また、データ数と計算量の関係を表す記法のことを、オーダー記法と呼び、次のような記述の仕方をします。

O(計算量)

例えば、データの数 n が、2倍、3倍となったときに、計算量も2倍、3倍となるような場合のオーダーは、「O(n)」となります。

データの数 n が 2倍になったとき計算量が4倍、3倍になったとき計算量が9倍となるような場合のオーダーは、「O(n²)」となります。

1回で処理が終了する場合は、「O(1)」となります。

オーダーは、「これ以上大きくならない」という「最大の計算量」を表しています。

2分探索法のオーダーの求め方

基本情報技術者試験の問題では、よく2分探索法のオーダー（計算量）を求める問題が出るそうです。

2分探索法のオーダーは以下のとおりです。

O(log₂n)

これを元にして、例題を出してみます。

例題
2分探索を行なうときに、データが8個ある場合のオーダー（計算量）はいくつになるか？

解答
log₂n の式に当てはめて解きます。

log₂8 = log₂2³ = 3

従って、O(3)が正解となります。

アルゴリズム毎のオーダー

基本情報技術者試験では、2分探索法のオーダーを求める問題が頻出ですが、ハッシュ法や線形探索法、クイックソートのオーダーを求める問題が出題されることもあるので、それもついでに覚えておきましょう。

アルゴリズム	オーダー記法による計算量	計算量
ハッシュ法	O(1)	少ない 多い
2分探索法	O(log2n) または O(log n)
線形探索法	O(n)
クイックソート	O(n log n)

プログラムの性質（再帰）

プログラムには様々な性質があります。今回は、基本情報技術者試験でも出題されるという、再帰の性質について見ていきます。

1. 再帰（リカーシブ）
2. 再入可能（リエントラント）
3. 再配置可能（リロケータブル）
4. 再使用可能（リユーザブル）

再帰（リカーシブ）

再帰（リカーシブ）とは、プログラムの実行中に自分自身を呼び出すことができる性質です。

再入可能（リエントラント）

再入可能（リエントラント）とは、複数のプログラムから呼び出されても、正しく動作する性質です。例えば、プログラムA と、プログラムB が同時に プログラムC を呼び出してもプログラムC が正しく動作する場合、プログラムC を再入可能なプログラムであるといいます。

再配置可能（リロケータブル）

再配置可能（リロケータブル）とは、プログラムを主記憶装置のどこに配置しても実行できる性質です。通常のプログラムのほとんどが再配置可能プログラムです。

再使用可能（リユーザブル）

再使用可能（リユーザブル）とは、補助装置から一度でも主記憶装置に格納してしまえば、後は主記憶装置から何度でも繰り返し実行できる性質のことです。この性質を持つプログラムを再使用可能プログラムと呼びます。

紛らわしさともオサラバ！名称にJavaが含まれる用語一覧

最も有名なプログラム言語の1つとして、「Java」があります。
そして、この「Java」という単語が付く用語はたくさんあり、紛らわしさ全開です。そこで、よく使われる「Java」の付く用語をまとめてみました。

用語	解説
Java	コンピュータの機種やOSに依存しないソフトウェアを開発できるプログラム言語。
Javaアプリケーション	Javaで書かれたアプリケーションソフトウェア。
Javaアプレット	JavaアプレットはクライアントのWebブラウザ上で実行される。Javaで書かれたプログラム。
Javaサーブレット	JavaサーブレットはWebサーバー上で実行される。Javaで書かれたプログラム。
JavaBeans	Javaのプログラムでよく使われる機能を部品化し、再利用できるようにコンポーネント化するための仕様。
JavaScript	動的なWebページを作るためのプログラム言語。名前は似ているが、「Java」とはまったくの別物。

最後に

さて、GW一発目と書き出して始めたものの、書き上げるのに3日を要してしまいました。それだけボリュームのある内容とはなっていると思います。

ただ、その他の言語、Ajaxなどを端折ってはいます。端折った内容も学びたいという方にはこれ！

こちらが参考にさせていただいているテキストです。