授業開始前に "Username and password for data structures and algolithms" というタイトルのメールが届いているはずなので確認せよ.
以下の手順で授業用サーバへログインせよ.
ログインすると,自分のホームディレクトリにいるはずである. ターミナルの最下行の
jtXXXXXX@sirius:~$
をプロンプトという.プロンプトが出ているときはコマンド入力が可能である. 以下のようにキーボードから "ls" と入力し改行キーを押せ.
jtXXXXXX@sirius:~$ ls
これは ls というコマンドを実行する方法で,ls コマンドは 現在自分のいる「カレントディレクトリ」にあるファイル,ディレクトリの 一覧を表示するコマンドである.初期状態では以下のように結果が表示さる はずである.再びプロンプトが出力され,次の入力が可能な状態になっていることが 分る.
jtXXXXXX@sirius:~$ ls algo jtXXXXXX@sirius:~$
このディレクトリ(ホームディレクトリ,ログインしたときの初期位置) に授業専用のディレクトリを作成し,すべてのプログラムをそこで作成 するようにする.まず,ディレクトリの作成を行うために mkdir c というコマンドをターミナルに入力せよ.
jtXXXXXX@sirius:~$ mkdir c jtXXXXXX@sirius:~$
mkdir が「コマンド」,c は「引数」とよばれ, 今いるディレクトリに c という名前のディレクトリを作るコマンド となっている.できたかどうか ls コマンドで確認せよ.
jtXXXXXX@sirius:~$ ls algo c jtXXXXXX@sirius:~$
作成したディレクトリ c に移動して作業を行う.ディレクトリを 移動するコマンドは cd で,移動先を引数で与えるため,コマンドは 以下のとおりである.
jtXXXXXX@sirius:~$ cd c jtXXXXXX@sirius:~/c$
プロンプトの $ 記号の左に現在いるディレクトリ(カレントディレクトリ) が表示されている.この場所にはまだファイルが存在しないはずである. ls コマンドを実行して確認せよ.
プログラムの作成は emacs エディタで行う.プログラムの作成には emacs のようなテキストエディタとよばれるものが使われることが多い.
ここまでの作業を行うと自分のホームディレクトリの直下の c ディレクトリがカレントディレクトリになっているはずである. この場所に最初のプログラムとして画面に hello, world と出力する プログラム hello.c を作成する.ファイル名をまずターミナルから emacs コマンドを作成したファイル名を引数として入力する.(下図)
jtXXXXXX@sirius:~/c$ emacs hello.c
ここからはターミナル全体は emacs が支配することになる. emacs を終了し,プロンプトが現れるまで他のコマンドは入力できない.
emacs の操作方法は大学作成のコンテンツ, 「Emacs」 などを参照すること.情報はウェブ上にも多くの情報があるので参考にすること.
hello.c の内容は以下のものとする.マウスによるコピーアンドペーストで 先ほど開いた emacs を実行中の画面にコピーせよ.(マウスでコピーし, Tera Term の編集メニューから貼付けでコピーできる)
#include <stdio.h> int main(void) { printf("hello, world\n"); }
図1.1 hello.c
emacs でファイルを上書きセーブするにはコントロールキーを押したまま x キーを一回押して離し,次に s を一回押して離す.この操作を CTRL-x CTRL-s と書く.この操作を実行し,セーブせよ.
emacs を終了するには CTRL-x CTRL-c を実行する.このとき ファイルが未セーブであれば確認される.終了作業を行え.
emacs が終了すると再びプロンプトが表示され,コマンドが入力できる ようになっている.ls コマンドで hello.c が存在していることを確認せよ.
自分が作成した覚えのない hello.c~ や #hello.c# のような名前の ファイルができていることがある.これらは emacs がバックアップのために 自動的に保存したファイルである.例えばhello.c というファイルをエディットして 保存すると,一つ前に保存したバージョンが hello.c~ という名前で 保存される.また,長時間エディットしているとemacs は安全のために オートセーブを行うことがある.このときのファイル名は 本来のファイル名の前後に # をつけたものになる.正常に終了した 場合は自動的に消されるが強制終了があった場合このファイルが残る.
いずれも問題が起こったときのリカバーのために保存されるもので, 放置しても問題ない.気になるならファイルを消去する rm コマンドを 使って rm hello.c~ や rm '#hello.c#' と入力することで消去することが できる.
c プログラムはコンパイルして実行可能となる.コンパイルのコマンドは cc というコマンドで,ソースファイルを引数として与える.この場合は hello.c が存在するディレクトリで プロンプトが表示されているときに cc hello.c というコマンドを実行すればよい.実際にコマンドを実行せよ.
cc が何も画面に表示せずに終了(次のプロンプトが出る)すれば コンパイルは成功である.同じディレクトリに実行ファイルの a.out ができているはずなので確認せよ(以下の実行例)
jtXXXXXX@sirius:~/c$ ls a.out hello.c jtXXXXXX@sirius:~/c$
コンパイルに失敗し,エラーが出た場合は emacs で hello.c を 修正し,コンパイルを再実行せよ.
出来た a.out ファイルを実行するには ./a.out というコマンドを実行 する.以下のように出力されたら成功である.
jtXXXXXX@sirius:~/c$ ./a.out hello, world jtXXXXXX@sirius:~/c$
複雑なプログラムを作成するときは emacs で修正して コンパイル,実行を繰り返すことになる.Tera Term の 「ファイル」メニューから「セッションの複製」を選び, 2枚目のターミナルを開け,両方ともディレクトリ c に いる状態にして片方では emacs を起動させてままにして もう片方でコンパイル,実行を行うと効率が良い.
この授業はprintf,変数,ループ,配列,関数,構造体などの C言語の基本的なことを理解している学修者を対象としている. 全くの初学者はC言語初歩 を先に学習せよ.
アルゴリズムとは,問題の答えを求める 処理の手順のこと.問題はすでに厳密に定義されており, 処理の手順はコンピュータが実行可能なものであることが 前提.
プログラムを書くという行為は
の段階に分けられる.この授業では 3 番目を行う技術はすでに 修得しているという前提で 2 番目の段階を扱う.
Niklaus Wirth(ニクラウス・ヴィルト)の有名な言葉
アルゴリズム+データ構造=プログラム
計算機ができる前(1936年)に Alan Turing(アラン・チューリング)により 計算機のモデルであるチューリング機械が提案され,厳密に定義された問題であっても 計算機では計算できない問題が存在することが示された.
チューリング機械と計算可能性については 計算量理論入門の前半を参照.
計算量には時間に着目した時間計算量と, 使用メモリ量に着目した空間計算量がある. 多くの場合は時間計算量について議論する.
アルゴリズムだけでなくデータ構造の知識も必要.
オブジェクト指向プログラミングの普及などにより, 部品プログラムの使い回しが頻繁に行われるようになった.
部品の機能だけ知っていればなんとなくプログラムが書けてしまう.
アルゴリズムの選択により計算量は大きく変わるので今でも アルゴリズムの勉強は重要.
速いスーパーコンピュータと遅いPCとスピートの差は高々 数10万($10^5$)倍程度. 遅いアルゴリズムのプログラムをスーパーコンピュータで実行するより, 速いアルゴリズムをPCで実行するほうが速いことも多い.
ガイダンスで示した符号のアルゴリズムでは入力が 100 ビットのとき, PC でも良いアルゴリズムを使えば 60ナノ秒で計算できるのに 悪いアルゴリズムでは$10^{14}$年かかる. これを世界最速のスーパーコンピュータで計算しても $10^9$年かかる. これは太陽が活動を終了するまでの時間と同程度で,天文学的な時間である.
アルゴリズムとデータ構造の知識がないと 自分が作ったプログラムの性能の予想すらできない.
ベンチマークテストは細かい条件によって変わりすぎる.
細かいこと(計算機の速度や,コンパイラの最適化処理の性能など) によらないアルゴリズムの大局的な性能を表現するために 計算量という尺度を使う.
教科書 p.10 2.2 節では「計算量は入力データの大きさ $n$ の関数として 表現する」とあるが,「大きさ」と書くと数値の値の大きさのことか, 数値を表現するデータの大きさ(桁数など)のことか曖昧である. 「計算量は入力データのサイズ $n$ の関数として表現する」 とするほうがよい. 計算量は入力のサイズ $n$ の関数としておおまかに表される.計算量理論については 計算量理論入門の該当部分を参照.
何を「サイズ」$n$ にするかを確認することは重要である. 例えば多数の要素があって,それを大小の順に整列するアルゴリズムであれば 要素の個数をサイズ $n$ とするのが自然である.要素が $n$ 個のときに $n^2$ に比例する時間で整列できるアルゴリズムであれば $O(n^2)$ のアルゴリズムという.
一方,大きな数値 $x$ を入力として素数かどうかを判定する問題を考える. 低速だが単純な方法としてて 2 から順に $x-1$ までの値で割っていって 割り切れる数があるかどうかで素数かどうかを判定するアルゴリズムを考える. この場合,入力の値(判定したい値)が大きくなるほど割り算の回数が 増えるため,実行時間も大きくなる傾向がある. この場合,入力は 1 つの数の 2 進表現のデータなのでこの場合のサイズは 2 進表現の桁数と 考えるべきである. 入力の値が大きくなるとサイズである桁数も大きくなる. 順に割ってゆくアルゴリズムは,入力値の 値が $n$ であれば最悪 $n$ 回の割り算で判定できるので $O(n)$ のアルゴリズム,と考えるのは間違いである. 入力値のサイズは入力値の桁数 $n$ としなければいけない. 桁数が $n$ の数値は最大 $2^n$ 程度の値になるので $2^n$ 程度の割り算を行うことになる,つまり, 順に割ってゆく素数判定アルゴリズムの計算量は $O(2^n)$ が正しい.
アルゴリズムが同じであれば計算機の速度や,アルゴリズムをプログラムとして 実装する技術の差で定数倍の実行時間の差が生じる. 比例定数の違いは無視し,「計算時間は入力のサイズ $n$ の 2 乗に比例する」 という程度の精度で議論する.この時間計算量は $O(n^2)$ と 表される.(オーダー$n$二乗と読む)
オーダーは正確な計算回数の式から以下の簡易的な方法で求めることができる.
ガイダンスの符号のアルゴリズムの例ではアルゴリズム A の計算回数は $n2^{(n-1)}-1$, アルゴリズム B の計算回数は $6n-9$ であるからそれぞれ $O(n2^n)$と $O(n)$ となる.
領域計算量も同様にオーダーで表す.
計算量は入力サイズの関数であるが,同じサイズの入力でも 内容が違えば異なる可能性がある.
最悪の入力データの場合の計算量を最大計算量(worst-case complexity) すべての入力データに対する平均の計算量を 平均計算量(expected complexity)とよぶ. 最大計算量で議論されることがほとんどである.
List 2.1 は線形探索法のプログラム断片である. struct によるデータ構造の部分とアルゴリズム本体である線形探索部分だけ が書かれているのでこれに適宜メインルーチン等を加えなければ実行できない.
この教科書のサンプルコード は教科書発行元より電子データで提供されている. これをコピーして日本語文字コードを実習の 環境にあわせて変更したものを各受講生のホームディレクトリ直下の algo ディレクトリに置いている. c ディレクトリがカレントディレクトリである状態で ls ../algo というコマンドを実行してみよ. 用意されたファイルの一覧が見えるはずである.
サンプルファイルは一旦 c ディレクトリにコピーして書き加える形で利用する とよい.コピーを行うコマンドは cp で,2個引数をとり,第1引数が コピー元,第2引数がコピー先となる. 今回の場合は c ディレクトリで cp ../algo/list02_1.c mylist02_1.c コマンド を実行せよ.mylist02_1.c という名前でコピーされているはずなので, emacs mylist02_1.c で開いて以降の編集を行えばよい.
具体的に追加が必要なのはプログラムの最初に
#include <stdio.h>
図1.2 mylist02_1.c 先頭
を挿入することと,末尾にメインルーチンの例,
int main(void) { int k, data; table[0].key = 1; table[0].data = 1; table[1].key = 3; table[1].data = 2; table[2].key = 4; table[2].data = 3; table[3].key = 8; table[3].data = 4; table[4].key = 13; table[4].data = 5; table[5].key = 14; table[5].data = 6; table[6].key = 18; table[6].data = 7; table[7].key = 20; table[7].data = 8; table[8].key = 21; table[8].data = 9; table[9].key = 25; table[9].data = 10; n = 10; /* n にデータの個数を代入することが必要 */ k = 14; data = search(k); if (data == -1) { printf("見つからない\n"); } else { printf("data の値は %d です\n",data); } }
図1.3 mylist02_1.c 後半
を挿入することである.メインルーチン内では型だけ 与えられている構造体 table に 10 個の具体的なデータを 代入している.また,教科書本文のプログラムは変数 n にデータの総数が セットされていることが前提になっているため,メインルーチンで n = 10; としてセットしている.次に教科書で書かれている 検索関数 search に引数を 14 として呼出し,返り値を 変数 data に格納している.data の値を見れば あったか無かったかがわかるので確認して分岐させ出力している.
mylist02_01.c にこれらの追加を行って保存,コンパイルせよ. コンパイルエラーが起こればemacsに戻って修正する. エラーが出力されなければ正しくコンパイルされて新しいa.out に書き換えられている../a.out コマンドで実行してみよ. main の変数 k の値を書き変え, 10個のキー(この例では1,3,4,8,13,14,18,20,21,25)に 無いものや有るものを代入させて(k = 14; の 14 を別の数値にする) 出力を確かめよ.プログラムを 書き換えると毎回コンパイルを行わなければならない.
間違ったファイル名のファイルを作成した場合など, ファイルを消去したい場合は rm コマンドを使う. 「rm ファイル名」という書式で実行する. ディレクトリを消去したい場合は rmdir コマンドを使う. あるディレクトリとそのディレクトリ内部のファイルを 全て消去するときは「rmdir -r ディレクトリ名」という書式で 実行する.また「mv ファイル名1 ファイル名2」という コマンドで「ファイル名1」という名前のファイルを 「ファイル名2」という名前に変更することができる.
線形探索の計算量は $O(n)$
教科書 p.14 の上にある計算量の序列は見にくくなっている. 計算量が小さいものから並べると, \[ O(1), O(\log n), O(n), O(n\log n), O(n^2), O(n^3), \ldots , O(n^k), O(2^n) \] になるという意味である.
二分探索の計算量は $O(\log n)$
第 1 回課題「二分探索」 を提出せよ.