出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．
この授業は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 コマンドを使う． あるディレクトリとそのディレクトリ内部のファイルを 全て消去するときは「rm -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 回課題「二分探索」 を提出せよ．