○数値(と文字)を扱う 日常問題は実際は非常に複雑 行く、顔を洗うなどはできない ○コンピュータが直接に実行できることは何か アルゴリズムとは何か アルゴリズムを作るとはどういうことか 誰でも分かるように明確な作業手順を書く コンピュータにもわかるように書く コンピュータが直接に実行できることは何か ・記憶 数値を記憶すること ( 記憶場所が必要 ) ・転送 ( 代入 ) ある記憶場所から別の記憶場所へ数値を転送(コピー)すること ・演算 ( 数学関数 ) 記憶した数値どうしで演算を行なうこと ( その演算結果を記憶場所にしまうこと ) ・分岐 ( 制御の流れの変更 ) 演算結果により処理の順番(処理の流れ)を変えること ( 特別な場合として無条件に変えることも含む ) ( mule , mosaic , cp , sort , unix なども複雑な処理 みなこれらの作業 の組合せである )
◇下へ・上へ ○変数 数学でいう変数とは少し違う 変数：数値または文字を記憶する場所 機械語では場所はアドレス(番地)で表す アドレス(番地)＝記憶装置内の位置を表す数値 高級言語またはアルゴリズムでは変数につけた「名前」で表す ある値(一定の値、変数の値、計算結果)を変数に記憶させる。 ・転送(代入) 代入すると前の値は消える。そろばんのよう。 テキストでは := で表す。 多くのプログラミング言語では = で表す。 !等しいという意味ではない! (左辺) = (右辺) は、右辺の式を計算して、左辺の変数に代入することを 意味する。 i=j 変数 j の値を変数 i に代入する。 i=j+2 変数 j の値に2を加えた値を変数 i に代入する。 i=i+1 変数 i の値に1を加えた値を新たに変数 i に代入する。 i+1=j+2 左辺が変数でないので間違い(多くのプログラミング言語では) ・添字つき変数(配列)
: 一連のデータを扱う
( 数学では下つき添字で表すことが多いが、
ここでは C の配列の表記 x[i] を用いる )
(配列の詳しい説明はあとで行なう)
◇下へ・上へ ○題材 ・最大値、最小値を求める。 二つの数 三つの数 ・添字つき変数の総和を求める。
○反復の詳細 初期化、初期設定 増分処理 後処理 繰り返し条件判断 前判定 (後判定) フローチャートによる表現前判定(後判定) ○よくある間違い 総和の場合 「初期設定忘れ」 「s=0 をしない」 「一つ違いの誤り」 「i=0 から始める」「i <n の間繰り返す」 ○手続き(詳しくはあとで) 一旦ある処理をするアルゴリズムを作ると それを他の処理の一部として使える。
◇下へ・上へ アルゴリズムの定義 与えられた基本命令 転送(代入) 算術演算 論理演算(論理積論理和 否定) 大小相等の比較 と与えられた制御構造 逐次 選択 反復 (分岐) で構成されている アルゴリズムの要件 一般性 特定のデータだけで正しい答がでるようなものはだめ 明確性 いつだれがやっても同じデータに対しては同じ結果がでる。 停止性 基本命令の有限回の実行で終る
◇下へ・上へ ○演習 以下の中から選択。PAD で描く。 ( 手で紙に描けばよい ) a) 三 つの数 L,M,N の 中央値(median)を求めるアルゴリズムを作れ。 (テキスト演習2.17)( ヒント ) b)三つの整数 L,M,N の最大値と最小値(4) を参考に四つの数 K,L,M,N の最大値と最小値を求めるアルゴリズムを作れ。 ( ヒント ) c) b) の方法を参考に n 個の数 x[1]〜x[n]の最大値と最小値を求める アルゴリズムを作れ。( ヒント ) d) a の n乗を計算するアルゴリズムを作れ。 e) n の 階乗を計算するアルゴリズムを作れ。(テキスト演習2.19)
◇一覧へ・上へ ○レポート課題 (次回に紙で提出)(解答) 以下の手順をPADで描け。 ( pad2ps を用いてもよいし、手で描いてもよい。) 1. 次の2次方程式を解の公式を用いて解く手順を書け。 ( 第1回の課題 2 に対応する )
(a≠0)
( 具体的には判別式を用いて、解の種類を分類する。
複素数は、実部と虚部をそれぞれ求める。)
2.次にそれぞれの処理を行なうためのアルゴリズムについて、
PADの空欄を埋めてアルゴリズムを完成せよ。(いずれか一方を選択せよ。)
a) x[i] の平均と標準偏差を求める。
(データ数を n とする。)
b) 回帰直線を求める。
x[i],y[i]の n個のデータ点列から「適切な」直線(y=ax+b)の傾きa
と切片bを求める。