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

目次

応用情報技術者試験（レベル３）シラバス－情報処理技術者試験における知識・技能の細目－ Ver. 7.0 に基づき，「アルゴリズムとプログラミング」の対策ノートを作成した。

• データ構造
• アルゴリズム
• プログラミング
• プログラム言語
• その他の言語
• 本稿の参考文献

データ構造

(1) データ構造

データ構造は，プログラムで使用するデータを扱うための枠組みのことである。

(2) データ構造の種類

① 配列

配列（array）とは、複数のデータを連続的に並べたデータ構造。各データをその配列の要素といい、自然数などの添字（インデックス）で識別される。

多次元配列（multidimensional array）

プログラミング言語などが扱うデータ構造の一つで、配列の各要素が配列に、その要素がさらに配列になっているような入れ子構造の配列データのこと。

単純な配列（1 次元配列）では配列の各要素にそれぞれ値が格納されているが、多次元配列では配列の各要素が配列に、その要素がさらに配列に…という具合に配列が何段階にも入れ子構造になっている。入れ子が何段階になっているかを次元の数で表し、配列の要素が配列になっているものを 2 次元配列、その要素がさらに配列になっているものを 3 次元配列、というように呼ぶ。

静的配列（static array/固定長配列/fixed-length array）

配列変数のうち、宣言時に要素数を指定し、以降は長さを変更できないものを静的配列という。動的配列が登場するまでは配列といえば静的配列のことだったため、昔からある言語では仕様上は静的配列しか用意されていないこともある。

動的配列（dynamic array/可変長配列/variable-length array）

動的配列とは、プログラミングで用いられる配列変数の一種で、長さ（要素数）が固定的に決まっておらず、実行時に必要に応じて要素を追加、削除することができるもの。

② リスト

リストはデータの構造を連結したデータ構造で，リストの最小単位となる要素はデータ部とポイント部で構成される。データ部にはデータ自体を格納し，ポイント部には次の要素の場所に格納する。このポインタをたどることで，個々の要素にアクセスすることができる。

リストの種類には，ポインタの向きによって，単方向リスト，双方向リスト，環状リストがある。

線形リスト

線形リストとは，線形で表現されるリスト構造の総称で，一般的には隣接するデータ同士をポインタで連結して表現する。

ポインタを用いた線形リストには，ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である，という特徴がある

③ スタックとキュー

スタック

スタック（stack）とは，後に格納したデータから順に取り出す。後入先出型（LIFO : Last In First Out）のデータ構造である。スタックにデータを格納することを push（プッシュ），スタックからデータを取り出すことを pop（ポップ）と呼ぶ。

キュー

キュー（queue）とは，先に格納したデータから順に取り出す，先入先出型（FIFO : First In First Out）のデータ構造である。キューへデータを格納することを enqueue（エンキュー），キューからデータを取り出すことを dequeue（デキュー）と呼ぶ。

④ 木構造

木構造（tree structure）とは、データ構造の一つで、一つの要素（ノード）が複数の子要素を持ち、一つの子要素が複数の孫要素を持ち、という形で階層が深くなるほど枝分かれしていく構造のこと。木が幹から枝、枝から葉に分岐していく様子に似ているためこのように呼ばれる。

2 分木（binary tree）

二分木とは、データ構造の一つである木構造（ツリー構造）のうち、どの親ノードも二つ以下の子ノードを持つもの。子が $N$ 個以下に制限された N 分木（N-ary tree）のうち最も単純な構造の木である。

完全 2 分木（perfect binary tree），全二分木（full binary tree）

二分木のうち、（子のない葉ノードを除く）子を持つノードの子の数がすべて二個ずつであるようなものを「全二分木」（full binary tree）、全二分木のうちすべての葉ノードの深さが揃っているものを「完全二分木」（perfect binary tree）という。

バランス木（balanced tree），平衡木

木構造のうち、根ノードから子を持たない末端の要素（葉ノード）までの高さ（深さ）がなるべく等しくなるように構築されたものを「平衡木」（へいこうぎ/balanced tree：バランス木）という。

根からどの葉まで辿ってもほぼ同じ数のノードを経由するため、探索などの処理をする際に平均の計算時間を短縮することができる。木を平衡に保つには、ノードの挿入や削除が行われる際に再構築して高さが等しく保たれるようにする処理が必要となる。

2 分探索木

すべての節において，「左側の子の値 < 節の値」「節の値 < 右側の子の値」という大小関係を持つ木を 2 分岐探索木と呼び，探索を効率的に行うことができる。下図は，1 ～ 9 の数字が各節に格納された 2 分岐探索木である。

2 分岐探索木からデータを探索する場合，探索データと節の値を比較し，その結果によって，次の処理を行う。

• 対象データの値 > 節の値 → 右部分木をたどり，探索を続行。
• 対象データの値 < 節の値 → 左部分木をたどり，探索を続行。
• 対象データの値 = 節の値 → 探索を終了。

葉に達した時点で一致しない場合は，探索対象データが存在しないことになるため，探索を終了する。

深さ優先探索（DFS : Depth-First Search），縦型探索

深さ優先探索とは、グラフや木構造を探索するためのアルゴリズムの一つで、それ以上先に進めない行き止まりのノードに出くわすまで経路を戻らずに隣接ノードを進んでいく方式。

試行錯誤しながら条件を満たす解に到達する方法であり，場合分けを行い深さ優先で探索し，解が見つからなければ一つ前の場合分けの状態に後戻りする。

幅優先探索（BFS : Breadth-First Search），横型探索

幅優先探索とは、グラフや木構造を探索するためのアルゴリズムの一つで、探索を開始する頂点から近い順に探索する方式。

アルゴリズム

(1) 流れ図

アルゴリズムを表記するための方法として，手続きの種類を表す記号を組み合わせて処理の流れを視覚化する流れ図（フローチャート）がある。流れ図の表記方法は JIS 規格（JIS X 0121-1986）で定義されている。

(2) 代表的なアルゴリズム

① 整列・併合・探索のアルゴリズム

整列（sort : ソート）は，ある基準に従ってデータを並び替える操作のことである。探索は，データの集合に目的のデータが存在するかを調べる処理である。

データ整列方法は，逐次添加法，分割統治法，データ構造の利用などの種類に分割される。

バブルソート（bubble sort），単純交換法 / 隣接交換法 / 基本交換法

バブルソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの最も基本的な手法の一つで、端から順番に隣接する要素同士を比較・交換していくもの。

最良の場合の計算時間は $O(n)$ と高速だが，最悪の場合の計算時間は $O(n^2)$ となり，平均して高速な手法とは言えない。ただし，要素の比較・交換は順序を問わず並列化しやすいという特徴があり，多数の処理装置で分散して処理することで高速化することができる。

マージソート（merge sorting），併合ソート / 併合整列法

マージソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの一つで、データ列を細かく分割し、整列しながら次第に併合（merge）していくもの。

平均計算時間も最悪計算時間も $O(n\log{n})$ となる極めて高速なソートアルゴリズムだが、元のデータ列の他に作業用の記憶領域を必要とする。実装上の配慮により、同じ大きさの要素の順序が入れ替わらない安定ソートとすることができる。

挿入ソート（insertion sort），基本挿入法 / インサーションソート / 単純挿入法

挿入ソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの最も基本的な手法の一つで、未整列の要素を一つずつ、整列済みの列の適切な位置に挿入していくもの。

$n$ 番目の値を挿入する際、それが整列済みの列の中で最も小さければ先頭の値との 1 回の比較で挿入位置が決定できるが、最も大きければ整列済みの値の数（$n-1$ 回）だけ比較を繰り返さなければならない。

すなわち、要素が整列済みに近い状態ならば高速に整列を完了できる（最良計算時間は $O(n)$）が、逆順に並んでいる場合はとてつもない回数の比較が必要（最悪計算時間は $O(n^2)$）となってしまう。

シェルソート（Shell sort）

シェルソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの最も基本的な手法の一つで、挿入ソートを改良したもの。1959年にアメリカのコンピュータ科学者ドナルド・シェル（Donald Shell）が考案した。

ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。シェルソートによる整列の手順を示す。

1. H ← データ数 ÷ 3 とする
2. データ列を，互いに H 要素分だけ離れた要素の集まりからなる部分列と死，それぞれの部分列を，挿入法を用いて整列する。
3. H ← H ÷ 3 とする
4. H が 0 であればデータ列の整列は完了し，0 でなければ ２． に戻る。

最良の場合の計算時間は挿入ソートと同じ $O(n)$ と高速で、挿入ソートでは逆順の場合に $O(n^2)$ かかっていた最悪の場合の計算時間が $O(n\log_{2}{n})$ で済むという利点がある。間隔の選び方によって性能は異なり、適切な間隔の決定方法について様々な手法が提唱されている。

クイックソート（quick sort）

中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様な処理を繰り返す。1960年に英コンピュータ科学者アントニー・ホーア（Charles Antony Richard Hoare）氏が考案した。

$n$ 個の要素をソートする計算量は最良でも平均でも $O(n\log{n})$ と高速だが、最悪の場合は $O(n^2)$ になってしまう欠点もある。元のデータ列を格納した領域以外に別の記憶領域を必要としない内部ソートだが、通常は関数の再帰呼び出しを用いて実装するため実用上はスタックの容量が $O(\log{n})$ だけ必要となる。交換の際に同じ値の前後の順は保存されないため安定ソートではない。

ヒープソート（heap sort）

ヒープソートは，未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。具体的には，未整列データを「親の値 ≤ 子の値」(または「親の値 ≥ 子の値」)の関係をもつ順序木として表現し、整列後の根の値（最小値または最大値）を取り出すことを繰り返して整列を行う方法である。

平均計算量が $O(n\log{n})$ と最も速いソート法の一つで、元のデータ順の影響も受けにくいが、実際にはクイックソートの方が高速になるとされる。

線形探索法

線形探索法とは、探索対象データの先頭から 1 つずつ順番に比較することによって目的のデータを探す方法である。線形探索法では、$N$ 個のデータの中から目的のデータを探すときの平均比較回数は $\displaystyle \frac{N-1}{2}$ 回である。

ハッシュ表探索

ハッシュ表は、キーから算出されたハッシュ値を添え字とする配列で、キーと値の組を複数個格納するデータ構造である。

ハッシュ表探索では、あるキーに対応するデータを取り出すときに、キー値にハッシュ関数を適用して得られたハッシュ値を使うことで格納アドレスを一意に特定し、目的のデータをすばやく参照することができる。ハッシュ関数からハッシュ値を計算する速度はほぼ一定のであるため、データを参照する速度は表に格納されているデータ数の多寡に関わらずほぼ一定になる。

② 再帰のアルゴリズム

プログラミングの分野で、関数やメソッドなどの処理内容の記述の中に、自身の呼び出しを行なうコードが含まれることを「再帰呼び出し」（recursive call：リカーシブコール）、そのような関数を「再帰関数」（recursive function）という。また、そのような構造を用いて記述されるアルゴリズムを「再帰的アルゴリズム」（recursive algorithm）という。

再帰呼び出し（recursive call）

コンピュータプログラム中で外部から呼び出し可能な関数やプロシージャ（手続き）、メソッドなどが、その内部で自身を呼び出すことを再帰呼び出しという。

再使用可能プログラム

再使用可能プログラムは実行の始めに変数を初期化する，又は変数を初期状態に戻した後にプログラムを終了する。

再帰的プログラム

自分自身を呼び出すことができるプログラムは，再帰的であるという。このようなプログラムを実行するときは，スタックに局所変数，仮引数及び戻り番地を格納して呼び出し，復帰するときは LIFO (Last In First Out) 方式で格納したデータを取り出して復元する必要がある。

if n=0
				then
					1
				else
					return n × fact(n-1)

③ グラフのアルゴリズム

深さ優先探索

深さ優先探索（DFS : depth first search）とは，とにかく行けるところまで行って，それ以上進めなくなったら一歩戻ってそこから探索する，という探索方法。

幅優先探索

幅優先探索（BFS : breath first search）とは，出発点に近い点から順に探索する，という探索方法

最短経路探索

グラフ理論における最短経路問題（shortest path problem）とは，重み付きグラフの与えられた 2 つのノード間を結ぶ経路の中で，重みが最小の経路を求める最適化問題である。

④ 文字列処理のアルゴリズム

文字列照合

文字列照合とは，ある文章の中に指定した文字列が含まれているかどうか，文字列検索を行うことをいう。文字列探索のアルゴリズムは，なるべく探索を早く終えるための工夫がされている。

KMP 法（クヌース・モリス・プラット法）

KMP 法は，このアルゴリズムの発案者である 3 人（D. E. Knuth, J. H. Morris, V. R. Pratt）の名前から名付けられている。文章と探索文字列を先頭から 1 文字ずつ比較するのはナイーブ法と同じだが，探索文字列を右へ移動する際の文字数に工夫がある。KMP 法は，文章の中に探索文字列の先頭から合致する位置を記憶することで，不要な比較を省略する。

BM 法（ボイヤ・ムーア法）

BM 法は，このアルゴリズムの発案者である 2 人（R.S. Boyer と J. S. Moore）から名付けられている。BM 法が，ナイーブ法や KMP 法と異なり，BM 法は探索文字列を後方から比較する。

⑤ ファイル処理のアルゴリズム

⑥ 近似アルゴリズム

⑦ 確率アルゴリズム

⑧ 遺伝的アルゴリズム

生物の進化を模倣した方法であり，与えられた問題の解の候補を記号列で表現して，それを遺伝子に見立てて突然変異，交配，とう汰を繰り返して逐次的により良い解に近づける。

⑨ 自然言語処理のアルゴリズム

⑩ データ圧縮のアルゴリズム

ランレングス法（RLE : Run Length Encoding）

ランレングス圧縮とは、最も基本的な圧縮アルゴリズムの一つで、連続して現れる符号を、繰り返しの回数を表す値に置き換える方式。圧縮によって内容を損なわない可逆圧縮を行う。

ハフマン法

ハフマン符号とは、1952年にデビット・ハフマン（David Albert Huffman）氏が考案した、可逆圧縮アルゴリズムの代表的な方式の一つ。現代でもファイル圧縮や画像ファイル形式など様々な場面で応用されている。

⑪ 図形に関するアルゴリズム

Z バッファ法（Z-buffering）

Z バッファ法とは、3 次元グラフィックス（3DCG）の描画処理で視点から見て隠れている部分を除外する手法の一つで、各画素に奥行きに関する情報を持たせ、重なり合う位置にある画素同士の奥行きを比較して手前のものだけを描画する手法。奥行き情報を保持するメモリ領域を「Z バッファ」という。

レイトレーシング法（ray tracing）

レイトレーシングとは、3 次元グラフィックス（3DCG）の描画手法の一つで、視点に届く光線を物体や光源まで逆にたどり、途中の描画面における各画素の色を決定する方式。

⑫ 記憶域管理アルゴリズム

要求に応じて可変量のメモリを割り当てるメモリ管理方式がある。要求量以上の大きさをもつ空き領域のうちで最小のものを割り当てる最適適合（best-fit）アルゴリズムを用いる場合，空き領域を管理するためのデータ構造として，メモリ割当て時の平均処理時間が最も短いものは，空き領域の大きさをキーとする 2 分探索木である。

(3) アルゴリズム設計

再帰

再帰とは、実行中に自分自身を呼び出すことをいい、再帰呼出しを行っても正しい結果を返すことができる性質をもつプログラムを「再帰的プログラム」という。

分割統治法

全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。

分割限定法

起こり得る全てのデータを組み合わせ，それぞれの解を調べることによって，データの組合せのうち無駄なものを除き，実際に調べる組合せ数を減らす方法である。

局所探索法

与えられた問題を直接解くことが難しいときに，幾つかに分割した一部分に注目し，とりあえず粗い解を出し，それを逐次改良して精度の良い解を得る方法である。

貪欲法（グリーディ法）

まずは問題全体のことは考えずに，問題をある尺度に沿って分解し，各時点で最良の解を選択し，これを繰り返すことによって，全体の最適解を得る方法である。

プログラミング

(1) プログラミング

プログラミング（programming）とは、コンピュータに意図した動作を行わせるために、まとまった処理手順を作成し、与えること。作成された手順のことをコンピュータプログラム（computer program）あるいは単にプログラムという。プログラミングを行う人や職種のことをプログラマ（programmer）という。

① プログラミング作法とコーディング標準

② プログラム構造

オーバーライド

スーパークラスで定義されたメソッドをサブクラスで再定義することである。

オーバーロード

あるクラス内で引数や型が異なる同じ名前のメソッドを使用することである。

#sample
	string date(string format); //現在時刻を書式化して返す
	string date(string format, int time_stamp); //指定時刻で
	array date(array format, array time_stamp); //配列で一括処理

③ データ型

データ型（data type）とは、プログラミング言語などが扱うデータをいくつかの種類に分類し、それぞれについて名称や特性、範囲、扱い方、表記法、メモリ上での記録方式などの規約を定めたものである。

整数型（integer type），int 型

整数型とは、プログラミング言語などで用いられるデータ型の一つで、整数の値を格納できるもの。多くの言語に実装されている最も基本的なデータ型で、ビット長や符号の有無などにより複数の種類に分かれている場合もある。

$n$ ビットの 2 の補数表現で扱える範囲は，$-2^{n-1}$ ～ $2^{n-1}-1$ である。8 ビットの 2 の補数表現で扱える範囲は，-128 ～ 127 となる。

論理型（boolean type）

ブーリアン型とは、プログラミング言語などに用意されているデータ型の一つで、「真」（true）と「偽」（false）の二種類の値だけを取りうるもの。

文字型（character type）

文字型とは、C 言語などに用意されている基本的なデータ型の一つで、一文字分の文字コードを格納するためのもの。

④ Web プログラミング

リッチクライアント（rich client）

リッチクライアントとは、Web アプリケーションのクライアントとして、Web ブラウザで単純な Web ページを表示する方式を超える表現力や操作性を備えたシステムを用いること。専用のアプリケーションソフトを利用する場合と Web ブラウザで高度な機能や拡張技術を用いる場合がある。

Ajax (Asynchronous JavaScript + XML)

Ajax とは、ある Web ページを表示した状態のまま、別のページや再読込などを伴わずに Web サーバ側と通信を行い、動的に表示内容を変更する手法。ページ上でプログラムを実行できるプログラミング言語 JavaScript の拡張機能を用いる。

Apache

Apache とは、世界的に最も普及している Web サーバ（HTTP サーバ）ソフトウェアの一つ。Apache Software Foundation（Apache ソフトウェア財団）が開発しており、オープンソースソフトウェアとして公開している。

JSP (Java Server Pages)

JSP とは、Web ページ内に Java プログラムを埋め込み、これをサーバ上で実行して結果を反映したページを動的に生成することができる技術。

WebSocket

WebSocket は、Web アプリケーションにおいてクライアント（Webブラウザ）と Web サーバの間で効率的な双方向通信を実現するプロトコルである。

WebSocket を使用したデータ通信では、まず HTTP の手順に則り、クライアントとサーバで 1 組の HTTP 通信を交して WebSocket 用の通信路を確立する。その後は HTTP の手順に縛られず、1 つの TCP コネクション上でデータのやり取りが行えるようになっている。この仕組みによりオーバヘッドが少なくなり、リアルタイム性が必要とされるシステムを効率的に実現できるようになる。

SPA (Single Page Application)

シングルページアプリケーションとは、Web アプリケーションの構成法の一つで、Web ブラウザ側でページの移動を行わず、最初に読み込んだ Web ページ上のスクリプトがサーバとの通信や画面遷移を行う方式。

(2) 文法の表記法

EBNF

BNF に繰り返しや省略可能などの記法を追加したものを拡張 BNF（拡張 BN 記法/EBNF：Extended BNF）という。現在では単純な BNF よりも EBNF を用いるほうが一般的となっている。ISO/IEC 14977 などの標準規格が定義されているが、様々な亜種や独自拡張も多い。

プログラム言語

(1) プログラム言語の種類と特徴

プログラム言語の種類と特徴を以下に示す。プログラミング言語を選ぶにあたり考慮すべきことは，言語特性だけでなく，自社の特性（リソースや得意分野）も考慮する。

① プログラム言語の変遷と分類

手続型言語（procedural language）

手続き型言語とは、プログラミング言語の分類の一つで、コンピュータが実行すべき命令や手続きを順に記述していくことでプログラムを構成する言語。

関数型言語（functional language）

関数型言語とは、プログラミング言語の分類の一つで、プログラム中の処理や制御を関数の定義と適用の組み合わせとして記述していくもの。そのようなスタイルでコードを記述することを「関数型プログラミング」（functional programming）という。

オブジェクト指向言語（object-oriented language）

オブジェクト指向言語とは、プログラミング言語のうち、互いに関連するデータの集合とそれらに対する手続き群をひとまとめにした「オブジェクト」（object）をプログラムの基本的な構成単位として扱うことができるもの。

スクリプト言語（scripting language）

スクリプト言語とは、プログラミング言語の一種で、オペレーティングシステム（OS）やアプリケーションソフトの動作や機能などをプログラムの形で記述できるもの。転じて、実行可能形式への変換作業などを省略・自動化したり、少ない記述量でも実行できるなど、仕様や開発手順が簡略化された言語の総称を表すこともある。

② 手続型言語

Fortran (Formula Translating System)

Fortran とは、科学技術計算などでよく用いられるプログラミング言語の一つ。1957 年に IBM 社が開発したもので、世界で最初の高水準（高級）プログラミング言語である。

手続き型の言語で、複素数型を組み込みデータ型として利用できたり、数式を数学での表現に近い形で記述できるなど、数値計算プログラムを記述しやすいようにできている。また、科学技術分野で長年用いられてきたことから数値計算ライブラリなどが豊富に蓄積・整備されている。

COBOL (COmmon Business Oriented Language)

COBOL とは、会計処理や事務処理に適したプログラミング言語の一つ。コンピュータが企業や行政機関の事務処理に応用され始めた 1960 年代から使われている言語で、現在でも、長年使われている企業の会計システムなどで広く利用されている。

汎用の手続き型プログラミング言語で、英文に似た語彙や構文を採用しているのが大きな特徴。例えば、「変数 X に 1 を足す」という処理は、数式に近い記法を採用する他の多くの言語では「X=X+1」といったように記述するが、COBOL ではこれを「ADD 1 TO X」と、処理内容を英文で記述したような表記が可能となっている（数式を利用した構文も用意されている）。

これにより、処理内容を厳密に英文で定義・記述することができれば、これを元に容易に COBOL プログラムを作成することができ、また、出来上がったプログラムは英文を読み下すように内容を理解することできる。一方、他の言語に比べ記述が冗長になりがちで、他言語に親しんだ開発者などは構造の把握がしにくいと感じることもある。また、処理内容によっては、冗長さのために一見して何をしようとしているのか分かりにくい難解なコードとなってしまうこともある。

PL/I (Programming Language/I)

PL/I とは、主に大型コンピュータのソフトウェア開発などに用いられる、汎用の手続き型プログラミング言語の一つ。最初の仕様は 1964 年に IBM 社が公開した。

Pascal

Pascal とは、主にコンピュータ科学の教育などに用いられるプログラミング言語の一つ。1968 年にスイスのコンピュータ科学者ニクラウス・ヴィルト（Niklaus Wirth）氏によって考案された。命名の由来は 17 世紀の著名なフランスの哲学者ブレーズ・パスカル（Blaise Pascal）。

BASIC (Beginners’ All-purpose Symbolic Instruction Code)

BASIC とは、プログラミングの入門・教育のためによく利用された汎用の手続き型プログラミング言語の一つ。1964 年に米ダートマス大学のジョン・ケメニー（John G. Kemeny）氏、トーマス・カーツ（Thomas E. Kurtz）氏によって考案された。

C (C language)

C 言語とは、広く普及している手続き型の高水準プログラミング言語の一つ。汎用的な言語で様々な分野で広く利用されているが、特にハードウェアを直接制御するプログラムの開発で利用される機会が多い。

R

R 言語（アール）は，次の特徴をもつプログラム言語及び実行環境であって，オープンソースソフトウェアとして提供されている。

• 統計解析や機械学習の分野に適している。
• データ分析，グラフ描画などの，多数のソフトウェアパッケージが提供されている。
• 変数自体には型がなく，変数に代入されるオブジェクトの型は実行時に決まる。

③ オブジェクト指向言語

Java

Java とは、様々な分野で人気の高いオブジェクト指向プログラミング言語の一つ。旧サン・マイクロシステムズ（Sun Microsystems）社が開発したもので、同社を買収した米オラクル（Oracle）社が開発を引き継いでいる。

C++

C++ 言語とは、広く普及しているオブジェクト指向型の高水準プログラミング言語の一つで、C 言語を拡張したもの。

④ スクリプト言語

ECMAScript

標準化団体 Ecma International（エクマ・インターナショナル）が策定している、いわゆる JavaScript の標準規格を ECMAScript（エクマスクリプト）という。ECMA-262 として規格書が発行されており、同様のものが ISO/IEC 16262 や JIS X 3060 としても標準化されている。

Perl (Practical Extraction and Report Language)

Perl とは、簡潔な記述や柔軟性、拡張性の高さが特徴的な高水準のプログラミング言語の一つ。いわゆるスクリプト言語あるいは軽量言語（LL：Lightweight Language）の草分けの一つで、UNIX 系 OS を中心に広く普及している。

PHP (PHP : Hypertext Preprocessor)

PHP とは、Web サーバの機能を拡張し、動的に Web ページを生成するために用いられるプログラミング言語の一つ。いわゆるスクリプト言語あるいは軽量言語（LL：Lightweight Language）の一つで、実行環境を Web サーバに組み込んで利用されることが多い。

C 言語や Java、Perl の影響を受けた記法や構文を採用した手続き型のプログラミング言語で、平易な仕様で学習しやすく、簡潔な記述でプログラムを開発することができる。

クラスを用いたオブジェクト指向や例外処理などに対応しているほか、標準で外部のデータベースシステム（DBMS）へ接続する機能が提供され、データベースと連携した Web アプリケーションを容易に開発することができる。

Python

Python（パイソン）は，1991 年にグイド・ヴァンロッサム氏によって開発された汎用の高水準プログラミング言語である。コードブロックのインデントが構文規則となっていることがソースコード上の特徴である。小さなプログラムから大規模なシステムまで，そしてデスクトップアプリケーションから Web アプリケーションの開発まで様々な場面で使用されている（"YouTube" や "Dropbox" などが有名）。簡潔な文法と使いやすさ，対応するプラットフォームの多さ，優れたライブラリの存在等により、AI 開発に適した言語としても人気が過熱している。

オブジェクト指向のプログラム言語であり，クラスや関数，条件文などのコードブロックの範囲はインデントの深さによって指定する仕様である。

if 条件式:
	処理1
	処理2
else:
	処理3

Ruby

Ruby とは、まつもとゆきひろ（Matz）氏が開発を創始した著名なオブジェクト指向プログラミング言語。主な処理系（実行環境）としてソースコードをそのまま実行に移せるインタプリタを採用したスクリプト言語の一種である。

TypeScript

TypeScript は Web プログラミングで用いられ，変数の静的型付けができる。なお，静的型付けを行うプログラム言語では，コンパイル時に変数名の誤り，誤った値の代入などが発見できる。

⑤ 共通言語基盤（CLI : Common Language Infrastructure）

米マイクロソフト（Microsoft）社が推進する .NET の実行環境（CLR）および対応プログラムの記述言語（CIL）の標準仕様を定めた規格。同社による実装を .NET Framework という。

機種や OS に依存しないプログラムの開発・実行環境を実装するために必要な諸技術の仕様を定めている。.NET プログラムの配布形式である CIL（Common Intermediate Language/共通中間言語/MSIL/IL）の仕様と、開発に用いるプログラミング言語に求められる共通仕様、実行環境（CLR）が実装すべき仕様を定めている。

(2) プログラム言語の制御構造

プログラム構造によって生じる特性には，次の 4 つがある。

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

プログラム内で使用する変数部分を各プロセスごとに割り当てることで、複数のプロセスで同時に使用できる特性。

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

主記憶へのプログラムの展開を初回実行時のみ行い、それ以降はロードせずとも何度でも正しく使用できる特性。

リカーシブ（Recursive，再帰可能）

プログラム中において自分自身を呼び出すことができる特性。

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

プログラムを主記憶上のどの位置においても正しく実行できる特性。

(3) プログラム言語の記憶域

ヒープ

プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある。サブルーチンからの戻り番地の退避にはスタック領域が使用され，割当てと解放の順序に関連がないデータにはヒープ領域が使用される。

スタック領域とヒープ領域の違いは，以下の通り。

スタック領域

一般にコールスタック・制御スタックと呼ばれている。LIFO 方式で構成されプログラムの実行中サブルーチンの情報を記憶しておくメモリ領域。サブルーチン終了後の戻りアドレスや局所変数などを保持する。

ヒープ領域

2つのラベルを持つ双方向リストで構成されプログラム上から動的（任意）に確保できるメモリ領域。動的にメモリ取得・解放を繰り返すことによりメモリ上にどこからも参照されない領域（ガベージ）が発生する。

(4) プログラム言語の記述

その他の言語

(1) マークアップ言語

① HTML

マークアップ言語とは、コンピュータによって処理される人工言語の種類の一つで、データ中に特定の記法を用いて何らかの情報を埋め込むためのもの。テキスト（文字）データ中に特定の記号で囲まれたタグ（tag）と呼ばれる表記を用いて構造や見栄えなどを記述するものがよく知られるが、バイナリデータ中に埋め込むものなど、様々な種類がある。

DTD（Document Type Definition：文書型定義）

DTD とは、SGML や XML、HTML などのマークアップ言語で記述された文書の冒頭などに記載される、その文書で用いる要素などを定義した部分。また、そのような宣言文を記述するための記法や文法を定めた言語（スキーマ言語）。

SGML (Standard Generalized Markup Language)

SGML とは、文書の構造やデータの意味などを記述するマークアップ言語を定義することができるメタ言語の一つ。

② XML

XML（eXtensible Markup Language）は，ユーザが独自に定義したタグを用いて文書構造を記述するマークアップ言語である。XML では各データを要素（Element）と呼び，要素名と属性名（Attribute）をつけたタグで挟んで表現する。要素を自由に追加することができ，入れ子構造にもできるので，汎用性が高いという特徴がある。

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
	<root>
		<child attr="value">TEXT</child>
	</root>

DOM（Document Object Model）

HTML や XML で記述された各要素をアプリケーションプログラムから取り扱うための API である。DOM をスクリプトや CSS で操作することでインタラクティブな表現が可能になる。

SOAP

SOAP は、ネットワークを介して、他のコンピュータ上にあるアプリケーションやサービスと XML データをやり取りするための RPC プロトコルである。

SVG (Scalable Vector Graphics)

SVG とは、XML の記法を用いて画像を図形の集合として表現する記述言語の一つ。2 次元のベクター形式の画像ファイル形式の一つでもあり、ファイルに保存する場合の標準の拡張子は「.svg」。

XML Schema

XML 文書の構造を定義するスキーマ言語の一つで、Web 技術の標準化を進める W3C（World Wide Web Consortium）が勧告したもの。

XML の記法や文法を用いて具体的な対象や目的のための応用言語を定義する枠組みで、SGML で標準的に用いられた DTD を置き換える目的で策定された。主に DTD の欠点の克服を企図した仕様となっており、XML Schema 自身が XML 文法に従って記述される（DTD は SGML とは異なる記法を用いる）ため、XML の解釈や処理のためのプログラムを使い回すことができる。

また、DTD にはない属性値のデータ型の指定が可能になったほか、名前空間（ネームスペース）に対応し、複数の異なる言語を同じ文書内で共存させ、要素ごとに言語を切り替えて用いることができる。

SMIL (Synchronized Multimedia Integration Language)

動画や音声などのマルチメディアコンテンツのレイアウトや再生のタイミングをXMLフォーマットで記述するためのW3C勧告。

③ XHTML

XHTML (Extensible HyperText Markup Language) とは、Web ページの記述などに用いられるマークアップ言語である HTML（HyperText Markup Language）を XML の仕様に従って定義しなおした言語。Web 関連技術の標準化を推進する W3C（World Wide Web Consortium）によって規格の策定が行われた。

④ スタイルシート

CSS（Cascading Style Sheets : 段階スタイルシート）

CSS とは、Web ページの要素の配置や見栄えなどを記述するための言語。HTML 文書に追加して見た目をコントロールすることができ、文書の外部から読み込んで適用することも HTML データ中に埋め込んで記述することもできる。テキストファイルの記述した場合の標準のファイル拡張子は「.css」。

XSL（Extensible Stylesheet Language：拡張可能なスタイルシート言語）

XSL とは、XML 文書の構造を表示や印刷に適した状態に整え、また、その見栄えを定義するマークアップ言語。

(2) その他の言語

DDL（Data Definition Language：データ定義言語）

DDL とは、コンピュータで用いられる人工言語の分類の一つで、データを格納するための構造を定義するための言語。

JSON

JSON（JavaScript Object Notation，ジェイソン）とは、以下のように ":"（コロン）で連結した名前と値の組を ","（カンマ）で区切って指定するデータ形式である。

{
 名前1: 値1,
 名前2: 値2,
 名前3: [値5, 値6],
 名前4: {名前7: 値7, 名前8: 値8}
}

値には、単純なスカラ値や真偽値のほか、配列やオブジェクトを指定できるため，多次元配列や複雑なオブジェクトを表現することができる。元来は、JavaScript の書式のサブセットという位置付けだったが、軽量であり汎用的に使用できるため RFC 8259 として標準化され、多くのプログラム言語で利用可能になっている。XML に代わって、WebAPI や Ajax でのデータの受け渡しにもよく利用される。

YAML (YAML Ain’t Markup Language)

YAML とは、何らかの構造を持つデータ集合を簡素な文字列の並びとして表記するための記法を定めたデータ形式の一つ。ソフトウェアの設定ファイルの記述や異なるソフトウェア間のデータ交換などでよく用いられる。

本稿の参考文献

• 安藤正芳，武部健一，原田英生，清水美樹，「日経BPパソコンベストムック　難しそうなプログラミングをやさしく教えてくれる本」，日経BP社，2017年1月27日
• 廣野豪，「Python で学ぶアルゴリズムの教科書　一生モノの知識と技術を身につける」，インプレス，2021年3月21日