情報1

情報1
2006.11.13
第8回：作品づくりその2
1
レポート提出について
• 前回の授業を欠席した人，まだレポート課題を提出していな
い人は提出してください
–
–
–
–
–
–
籠島
山口
志賀
栗原
矢野
小出
• 注意
– データで持参した人はMoodleに提出すること
– 印刷して持ってきた人は前に提出すること
– 名前が書いてあるか確認すること！
2
レポート課題 (１)
•
「挿入ソート」まで終わったペア
–
課題1：
•
–
課題2：
•
–
アルゴリズムの授業で何が分かったかを説明して，感想を述べる
「最小値検索法」まで終わったペア
–
課題1：
•
–
–
Ｎ枚のカードを並び替えるのに必要な，比較回数を計算で求めなさい
課題2：
•
手作業によるカードの並び替え，フローチャートの作成が実装に役立ったか？
課題3：
•
•
手作業によるカードの並び替え，フローチャートの作成が実装に役立ったか？
課題3：
•
•
挿入ソートと最小値検索法のそれぞれの方法について，Ｎ枚のカードを並び替えるのに必要な，比較回数を
計算で求め，その回数の比較を行う
アルゴリズムの授業で何が分かったかを説明して，感想を述べる
何も終わらなかった(ToT)ペア
–
課題１：
•
–
実装をふり返り，何が一番難しかったか説明する
課題２：
•
アルゴリズムの授業で何が分かったかを説明して，感想を述べる
3
レポート課題 (２)
• 締め切り
– 11月6日の授業開始時
• 形式
– ワード等で作成するのが望ましい（手書きでもい
いが，読みやすいようにまとめること）
– A4の用紙を利用すること
– 課題1～3を分けて書くこと
– 2枚以上
4
最小値検索法の比較回数
• カードの枚数と比較回数
–
–
–
–
–
カードが1枚の場合→0回
カードが2枚の場合→1回
カードが3枚の場合→2+1回
カードが4枚の場合→3+2+1回
カードが5枚の場合→4+3+2+1回
• カードの枚数がN枚の場合
– (N-1)+(N-2)+(N-3)+…+1=N×(N-1)/2
– 比較回数はNの二乗に比例する
2
• 計算結果は(N -N)/2であるが，Nが十分に大きければ，N/2は無
視できる
• カードの枚数が二倍になると，時間は4倍かかる
5
挿入ソートの比較回数
•
カードの枚数と比較回数
–
–
–
–
カードが1枚の場合→多くても少なくても0回
カードが2枚の場合→多くても少なくても1回
カードが3枚の場合→多くて1+2回，少なくて2回
カードが4枚の場合→多くて1+2+3回，少なくて3回
– カードがランダムに並んでいれば，比較回数の平均は処理済束のカードの
枚数の半分になる
• 挿入すべきカードが先頭にあれば，毎回の比較は1回で済む
• 挿入すべきカードが末尾の場合，毎回の比較は処理済のカード枚数
•
カードの枚数がN枚の場合
– (N-1)+(N-2)+(N-3)+…+1=N×(N-1)/4
– 比較回数はNの二乗に比例する
2
• 計算結果は(N -N)/4であるが，Nが十分に大きければ，N/4は無視できる
• カードの枚数が二倍になると，時間は4倍かかる
• 比較回数からすると，最小値検索法の約2倍高速である
6
色々なソート
•
簡単だけど，低速
– バブルソート
2
• 動作時間：N
– 選択ソート（最小値検索法のこと）
2
• 動作時間：N
– 挿入ソート
2
• 動作時間：N
•
複雑だけど，高速
– マージソート
2
• 動作時間：N×logN
• 例：マージソートで40秒なら，挿入ソートは約28時間かかる
– シェルソート
2
• 動作時間： N×logN
• 発明した人/年：Donald L.Shell/1959年
– クイックソート
• 動作時間：Ｎ×logN
• 発明した人/年：C.A.R.Hoare/1962年
7
グラフ化
40
35
比較回数
30
N
Nの2乗
logN
1
25
20
15
10
5
0
1
2
3 4
5 6
7
8 9 10 11 12 13
項目数（N）
8
作品づくりについて（1）
• 今回は二人組のペアで挑戦する
– これまでのペアでもよいし，変更してもよい
– 役割分担をうまくしましょう
• 完全分業：グラフィックデザイナーとプログラマ
• 協調作業：ペアプログラミング
• 残り授業数は今回を含めて，3回
– 前回欠席した人
• 企画を考えて，計画を立てましょう
• 企画と計画のレビューが終わったら，製作にはいります
– それ以外の人
• 作業を進めましょう
9
作品づくりについて（2）
• 前半の講義をうまく活かしましょう
– 状態遷移図を使った設計を行う
• ゲーム全体の状態遷移
• あるオブジェクトの状態遷移
– 複数のオブジェクトを入れ物に入れて，検索や並
び替えを行う
• 応用例：時刻表検索システム
• 応用例：ハイスコアの保存
– 上記を取り入れた場合，作品の評価に加点をし
ようと思います
10
今日の作業（前回欠席した人）
• Step1. ペアの決定
– ペアを探しましょう
– ペアが決定したら，企画＆作業計画シートを前に取りに来てください
• Step2. 企画と作業計画のレビュー
– シートが埋まったら，手を挙げて教えてください
– レビューをします
• Step3. 作業時間
– 計画に従って作業を進めてください
– Squeakは最終作品用Squeakを使ってください
• Step4. 日誌を書いて終了
11
今日の作業（前回出席した人）
• Step1. 作業時間
– 計画に従って作業を進めてください
– Squeakは最終作品用Squeakを使ってください
• Step2. 日誌を書いて終了
12
今日の授業はおしまい
お疲れ様でした
13

Download Report