情報1 2006.10.16 第5回：アルゴリズムその2 1 2学期の授業内容 • 状態遷移の設計・実装 – 状態遷移図を使ったプログラムの設計方法 – 状態変数を使ったプログラムの実装方法 • 複数の要素を扱うアルゴリズムの設計・実装 – 並び替え（ソート） – 検索（サーチ） • ミニプロジェクト – 複数メンバーによる協調作業 – スケジューリングとProject Management 2 本日の授業内容 • 課題1「オリジナルアルゴリズム」の実験 – ペアでアルゴリズムを交換する – 各々，30枚の並び替えの実験をする – ワークシートに実験結果を記入する • 課題2「最小値検索法」の実装 – 最小値検索法をSqueak上に実装する – ペアで1つ実装すればよい • 課題1と2は同時並行で進めること（カードは一組しかないので，余っている人は実装に挑戦する） • 時間内に課題1と課題2の両方を提出すること 3 アルゴリズムとは？ • 「なんらかの問題を解くための手順」のことをアルゴリズムという – 今回の問題は「数字の書かれた30枚のカードを順番に並び替える」こと – 他の問題の例「数字の書かれた100枚のカードの最大値を検索する」 4 前回欠席した人 • 最小値検索法の実験をして，Squeak上で実装する • 課題1（オリジナルアルゴリズムの実験）は不要 5 課題1「オリジナルアルゴリズム」の実験 • ペアでワークシートを交換する • 相手が考案したオリジナルアルゴリズムでカードを並び替え，結果を記録する • 相手が考案したオリジナルアルゴリズムに関する考察を行う（最小値検索法，自分の考えたとの比較等） • カードはペアに一組しかないので，順番に実験を行うこと • 余っている人は課題2の最小値検索法の実装に挑戦すること 6 課題2「最小値検索法」の実装 • 別紙「最小値検索法実装シート」を参照のこと • この課題は，オリジナルアルゴリズムの考案とあわせて，中間試験と同じ比率で採点します 7 今日の授業はおしまいお疲れ様でした 8