このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
鉄道や道路の所要時間がわかっている時、ある都市から別の都市への最短の経 路を求める問題を考えましょう。 これはカーナビゲーションシステム、鉄道の乗り換え案内、インターネットの 制御などに応用できる問題です。 例えば次のような状況を考えましょう。 東京電機大学から渋谷に行くのに複数の経路が考えられます。 ここでは次の経路を考えてみましょう。
これらの関係を行列で表すことを考えます。 行と列をそれぞれの地点に対応させ、各成分にはおおよその所要時間を入れま す。また直接行けない地点間は∞で表します。 簡単のために直接行けても∞で表しているところもあります。 一方、乗換え時間は重要ですが、簡単のためにここでは無視します。
| 電機大 | 新お茶の水 | 大手町 | 神保町 | お茶の水 | 神田 | 表参道 | 代々木 | 原宿 | 渋谷 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 電機大 | - | 5 | 13 | 15 | 10 | 10 | ∞ | ∞ | ∞ | ∞ |
| 新お茶の水 | 5 | - | 3 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| 大手町 | 13 | 3 | - | 3 | ∞ | ∞ | 12 | ∞ | ∞ | ∞ |
| 神保町 | 15 | ∞ | 3 | - | ∞ | ∞ | 11 | ∞ | ∞ | ∞ |
| お茶の水 | 10 | ∞ | ∞ | ∞ | - | 3 | ∞ | 13 | ∞ | ∞ |
| 神田 | 10 | ∞ | ∞ | ∞ | 3 | - | ∞ | ∞ | ∞ | 25 |
| 表参道 | ∞ | ∞ | 12 | 11 | ∞ | ∞ | - | ∞ | 3 | 3 |
| 代々木 | ∞ | ∞ | ∞ | ∞ | 13 | ∞ | ∞ | - | 3 | ∞ |
| 原宿 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | 3 | 3 | - | 2 |
| 渋谷 | ∞ | ∞ | ∞ | ∞ | ∞ | 25 | 3 | ∞ | 2 | - |
このような状況でどの経路が最短かを計算させるプログラムを作りましょう。 ここで紹介する方法はダイクストラ法と呼ばれるものです。 この方法では電機大からすべての駅への所要時間が求まります。
#include <stdio.h>
#define NUM 10
#define HI_VALUE 9999
char *eki[NUM]={"電機大","新お茶の水","大手町","神保町","お茶の水",
"神田","表参道","代々木","原宿","渋谷"};
int length[NUM][NUM]={{0,5,13,15,10,10,HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE},
{5,0,3,HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE},
{13,3,0,3,HI_VALUE,HI_VALUE,12,HI_VALUE,HI_VALUE,HI_VALUE},
{15,HI_VALUE,3,0,HI_VALUE,HI_VALUE,11,HI_VALUE,HI_VALUE,HI_VALUE},
{10,HI_VALUE,HI_VALUE,HI_VALUE,0,3,HI_VALUE,13,HI_VALUE,HI_VALUE},
{10,HI_VALUE,HI_VALUE,HI_VALUE,3,0,HI_VALUE,HI_VALUE,HI_VALUE,25},
{HI_VALUE,HI_VALUE,12,11,HI_VALUE,HI_VALUE,0,HI_VALUE,3,3},
{HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,13,HI_VALUE,HI_VALUE,0,3,HI_VALUE},
{HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,3,3,0,2},
{HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,HI_VALUE,25,3,HI_VALUE,2,0}};
int main(void){
int dist[NUM],flag[NUM],path[NUM];
int i,j;
int index,min;
for(i=0;i<NUM;i++){
dist[i]=HI_VALUE; flag[i]=1;
}
dist[0]=0;path[0]=0;index=0;
for(i=0;i<NUM;i++){
min=HI_VALUE;
for(j=0;j<NUM;j++){
if(flag[j] && dist[j]<min){
index=j;
min=dist[j];
}
}
flag[index]=0;
if(min==HI_VALUE){
fprintf(stderr,"The graph is disconnected.\n");
return 1;
}
for(j=0;j<NUM;j++){
if((dist[index]+length[index][j])<dist[j]){
dist[j]=dist[index]+length[index][j];
path[j]=index;
}
}
}
for(j=0;j<NUM;j++){
printf("%s %d: ",eki[j],dist[j]);
index=j;
do{
printf("-%d- %s ",length[index][path[index]],eki[path[index]]);
index=path[index];
}while(index!=0);
printf("\n");
}
return 0;
}
ここで、 path[] 変数には、電機大から来る場合に直前に経由した駅を入れます。 そうすると、最短路が見つかった場合、目的地から順に電機大まで最短経路をた どることができます。
この講義の主な目的は、以下のようなことを学ぶことでした。
同じ目的であるプログラムは無限に存在します。したがって、作成したプログ ラムが正しいかどうかを調べるのに、特定のプログラムと一致するかどうかを 調べても意味がありません (従って、プログラムを作成する演習で答を提示しませんでした) 。 そこで、作成したプログラムが正しいかどうかを調べるには別の方法が必要で す。 本講義では容易な手法としてテストによる検証をとりあげました。 テストを行うには、入力と出力の正しい組み合わせを用意して、プログラムに 入力を与えた時、用意した出力と同じものが出力されるかを検証する必要があ ります。 但し、多くのプログラムは入力可能なパターンとして莫大な数がありますので、 実用的で完璧なテストは不可能です。 従って、どのような入出力パターンを用いるかは考える必要があります。 なお、近年のプログラム開発手法として、テスト駆動型と呼ばれる、プログラ ム開発に先だって自動テストプログラムを作ってからプログラムを作る手法が あります。 これらの手法は経験的に開発効率が良いことがわかっており、効率的な プログラミング手法であるXP(エクストリームプログラミング)やアジャイルコ ンピューティングでも採用されています。
一方、テストで誤りを発見した場合などで、その誤りを効率良く正していくこ とも考えなければなりません。 そのための手法として、プログラムを小さな部品ごとに分けて、各々をテスト する方法が考えられます。 各テストを完璧に行うことは不可能なので、部品ごとのテストが終った後も、 部品を組み合わせるごとにテストは必要ですが、誤りを見つけた時、誤りを探 す範囲を小さくできる利点があります。
C 言語をうまく利用するには、とにかくポインタを使いこなすことがすべてと言っても過言で はありません。 複雑なデータ構造も構造体とポインタを使用して作ることが重要でした。 さらに、特に取り上げませんでしたが、 ポインタの配列により文字列の配列を実現したり、関数のポインタにより名前 呼出しを行うことも実現可能です。
一方、C++ は C 言語と互換性を保ちながらも、C の文化であるポインタの多 用を捨てるような仕組みが多く組み込まれています。 そのうちの一つとして C++ にはテンプレートと呼ばれている総称機能があります。 これは型を引数として関数やクラスを定義して、宣言時に型を指定することに より特定の型に対する関数やクラスを得るというものです。 さらに、この機能を用いて良く使われる複雑なデータ構造を提供するのが STL(Standard Template Library)です。ここには、線形リストや順序木などが 定義されていて、格納したいデータ型(オブジェクトクラス)を指定すれば使用 できるようになります。 本講義で取り上げた線形リストや順序木などは STL で用意されているので、 構造体やポインタを使用して作る必要はありません。 また関数の呼び出し方も値呼び出しだけでなく、変数呼び出しが可能になった ため、関数呼び出しにわざわざポインタを渡す必要が無くなりました。
一方、 C++ の複雑さを取り除く形で改良された言語である Java 言語も C 言 語と良く似た構文を持ちながらも様々な工夫がされています。 Java はバージョン 1.4 以前と 2004 年に出たバージョン 5 ではプログラミ ング手法が大きく違います。 バージョン 5 では C++ と同様の総称がジェネリックスと言う名前で文法もほ ぼ同じ形で取り入れられています。 一方、 1.4 以前はジェネリックスがないため次のような手法を用います。 Java 言語では、 文字列型も含む全てのオブジェクトクラスは java.lang.Object 型のサブクラスになります。 但し、int や double などの基本型は例外となります。 あらゆるオブジェクトクラスが java.lang.Object 型のサブクラスとなるので、 オブジェクトへの参照は java.lang.Object 型で宣言された変数に代入するこ とができます。 これを利用することで、代入するものの型を定めなくてもオブジェクトの集ま りなどの構造を記述することができます。 C++ ではデータ構造に特定のオブジェクトを格納したい場合、そのオブジェク トのクラスに対してデータ構造を宣言してました。 一方 Java ではどんなオブジェクトでも java.lang.Object 型の変数に格納で きますので、java.lang.Object 型の変数を一つ格納できるデータ構造を作って おくことで、どんなオブジェクトでもデータ構造を利用することができます。 実際、java.util に線形リストや順序木などの複雑なデータ構造が提供されて いますが、格納したい値はjava.lang.Object 型の変数に格納するようになっ ています。 但し、この実装法は格納するデータの型の取り扱いが甘くなると言う欠点があ ります。つまり、データを取り出す時、元のオブジェクトクラスの型に キャストする必要があります。 さらに、基本データ型を格納できないため、int などを格納したい時は java.lang.Integer などのラッパークラスを用いる必要があります。 いずれにしろデータを格納する時に手数が増えます。 また、型のチェックが行われないので、取り出すデータの型が不整合でもコン パイル時に発見できません。
C 言語で導入されているポインタと言う演算可能なメモリへの参照は、 強力な機能を持つ反面、プログラムの動作を正しく保つことが難しくなると言 う欠点がありました。 そこで、C++ や Java ではなるべくポインタを使用しないよう、あらかじめデー タ構造が提供されるなど、工夫されています。しかし、複数のデータを持つ複 雑なデータ構造に対して、順番に要素を取り出したい時などポインタ的なもの が必要になってきます。 そこで、先頭や終りなどの特定のデータへの参照が取り出せ、演算として次 の要素をさせるだけという限定された演算のみが許されたイテレータと呼ばれ るものが用意されています。
プログラム開発において、与えられた問題を分解し、元の問題と同じ構造を発 見できれば、再帰という手法を用いてプログラムを書くことができます。
例えば、与えられたデータを整列する場合、整列された列はどの部分列を見て も整列されています。よってデータ列を半分にすれば、大きい列と小さい列に 分割できます。 従って、データ列を大きいものと小さいものとに半分に分割するような関数を 設計し、半分になった列それぞれに対して、同様な処理を繰り返すようにする と最終的にデータを整列できます(Quick Sort)。
このように、データの列に何らかの規則がありデータを分割しても成り立つ場 合、関数の中でデータを分割しながら同じ関数を呼び出すようにすると、シン プルなプログラムで複雑なデータを取り扱うことができます。 再帰は、このほか線形リストや順序木の処理などにも活用できます。
大量のデータを扱うのに、あらかじめ容量を決めなければいけない配列は使え ません。そこで使用したのが線形リストというデータ構造です。 これはメモリをあらかじめ確保するのではなく、必要に応じて必要な量だけメ モリを取得し、データを順に格納するものです。
C 言語で実現するには次のような、データとポインタを格納するような構造体 を作り、 malloc 関数でメモリ上に生成してはひとつひとつつなげて使いまし た。
struct node {
struct node *next;
int data;
};
線形リストは大量のデータを取り扱う仕組みのうち、もっとも簡単な構造をし てます。従って、検索などはデータ量に比例した時間かかります。 一方で、データの追加や削除は容易にできます。 これは配列とは異なる特徴を持っています。
なお、C++ では STL(Standard Template Library)に deque や list というテ ンプレートが存在し、また、 Java では java.util.ArrayList が存在します。 どちらも C 言語のようにポインタの操作やメモリの操作無しに、頂点を付け 加えたり削除したりできます。
数の決まっているものを順序に従って整列させるには、配列のソートを行いま す。 しかし、数の決まってないものを整列させるには、順序木を使います。 順序木は、二分木において、頂点のデータが左の子よりも大きく、右の子より 小さいものを言います。 このような木に対して、データを格納する場合、根の頂点から順にデータを比 較していくとデータを格納すべき場所を捜し出すことができます。 一方、木の左から順にデータを取り出すことで、いつでも整列した状態でデー タを取り出すことができます。 C 言語ではこの順序木を使うのに、自らの構造を指すことができるポインタを 二つ持つ構造体を使用しました。
struct node {
int data;
struct node *left,*right;
};
なお、値の整列は情報処理の基礎であり、多くのプログラミング言語で簡単に 利用できるようになっています(但し、内部では順序木を利用している)。 C++ では STL にある map や multimap で利用 できます。 また、Java 言語では java.util.TreeMap を使います。 しかし、大量のデータの入出力が発生する場合、効率良くデータをやりとりす るために、外部データベースの利用を考えた方が良い場合があります。
与えられたデータを読んで解釈するためには、そのデータの列の意味を計算す る必要があります。 そのために一般的に用いられるのが構文解析の手法です。 構文解析はインタプリタやコンパイラを作る時だけでなく、 一般のデータの入出力やインターネットにおける通信などにも利用されていま す。
構文解析では文法というデータ列を作るためのルールを与え、与えられたデー タ列がどのようなルールの組み合わせにより生成されたかを解析して意味を導 きます。 例えば、 Time flies like an arrow. というデータ列を読んだ時、これがど のような文法により生成されたかを解析し、その文法により各単語がどの品詞 になっているかを求め、その品詞での意味(time や flies や like は品詞に よって意味が異なる)を求めます。
一般に自然言語において、一つの文章の解析が前後の文章や予備知識などの条 件により異なってきます (Time flies like an arrow も複数通りの訳し方がありそのどれかを決定する のは与えられた文章以外の要因です)。 同じ文法要素がその前後の要素により解釈が異なる文法を文脈依存文法と言い ます。 文脈依存文法を現存する計算機で効率良く解析することは難しいです。 なるべく表現力が大きくしかも計算機で効率良く解析することができるような 文法の定義法が求められています。 文脈自由文法は比較的効率良く解析できる文法です。 文法の定義には、 Time や flies など文章を直接構成する終端記号と、名詞 や主語と言った文法の概念を表現する非終端記号を使います。 文脈自由文法では左辺に置ける非終端記号を一つに制限し、その左辺を書き換 える右辺には複数の非終端記号、終端記号を置くことができます。 例えば、英文→主語 動詞 のように文法を与えます。 このように左辺を右辺で書き 換える式で与える書き方をバッカスナウア記法と言います。 インターネットの規格が示される RFC ではしばしばこの記法が使われていま す。 電子メールや WWW のメッセージの書き方などが実際に表されています。
但し、文脈自由文法も特殊な形をしていないと効率良くプログラムに変換でき ません。 効率良く変換できる形の一つに LL(1) があります。 また、 yacc や JavaCC といった、バッカスナウア記法からそれを解釈するプ ログラムを生成するコンパイラコンパイラと呼ばれるプログラムがあります。 これらは LL(1) 文法を含むより複雑な形の文脈自由文法を解釈するプログラ ムを生成できます。
バッカスナウア記法をさらに A→bC という形だけに制限したものが正規文法 と呼ばれます。但し、一般的には、それと等価な文字と、選択記号と、繰返し 記号で表現される正規表現が多用されています。 この正規表現で表現できる文法は、状態遷移図であるオートマトンが受理でき る言語と一致します。 そして、正規表現からオートマトンへの変換方法が確立されているため、正規 表現で表せるものは簡単にプログラムで解析できます。
プログラム開発において、状態の解析は重要です。 状態遷移図を書くことで、状態の移り変わりに応じたプログラムの作成が容易 になります。
一般のフローチャートと似ていますが内容は大きく異なります。 フローチャートでは一つの図形がプログラム一行を表すことがあり、 また、入出力の仕様や、変数の値、関数呼び出しなど、プログラムを作成する 上で必要な情報のほとんど全て(さすがにファイルレイアウトまでは記入でき ませんが)を詰め込めます。 これはある意味一つのプログラム言語となっていて、別のプログラム言語で記 述するための共通言語としての役割を担うことになります。 但し、フローチャートはプログラミングスタイルを強要することができないの で、読み易く保守し易くプログラムを開発すると言う近年のプログラム開発か らは使いづらいツールになっています。
一方、状態遷移図に記入できるのは入力と状態と状態の移り変わり、それに加 えて出力や開始、終了状態だけです。 このような限定条件のもとで図を書くことにより、一つの状態は必ずしもプロ グラム一行に対応するわけではなく、プログラム内のまとまった一ブロックを 指すようになります。
一つの問題を解くプログラムは無限に存在します。 そのため、どのようなプログラムを作成するかについては価値観が必要になり ます。 「良いプログラム」にはいろいろな観点が存在しますが、その中には処理が高 速なプログラムというものがあるはずです。 但し、コンピュータのプログラムの速度を評価する時、プログラム自身が持つ数学的 な性質ゆえ、特別な測り方をしなければなりません。 例えば、ある計算機で特定のデータを入力した時にかかった実時間は、そのプ ログラムの評価にはならないことが証明されています。 また、いわゆるベンチマークテストと呼ばれる、定めた入力データによる計算 時間を自動的に測定するプログラムを動作させるものがありますが、これもそ れだけプログラムの動作を速くする不正がしばしば行われていて、信頼できる 評価にはなりません。
プログラムの評価をする場合、与える入力の長さを n とした時、計算時間を n の関数で求める必要があります。 但しその際、最も増え方の速い項を定数倍は無視して求めます。 これを関数のオーダを求めると言いますが、この方法であれば実際に高速なプ ログラムであることを示すことができます。