情報テクノロジー学科スレッド

550：名無しさん＠青学生：2003/07/23(水) 00:41: とりあえず情報数学２でそうなところ。
計算量とオーダ。これはノートどおりにやればできそう。
ユークリッドの互除法。returnの中身のプログラムは覚えといたほうがいい。それから簡単な数値例でも紙の上で実行できるように。
リスト構造、スタック、キュー。これは出方はよくわからんけどそれぞれの追加、削除のやり方、特徴とか、先入れ何たら、プッシュ、ポップ、などの専門用語は覚えておく。
中盤でやった～ソート系（マージソートまで）は実際に数値が与えられて、それを答案用紙上で再現しろとか、アルゴリズムの考察とか、あとプログラムの穴埋めが考えられるので、ここらは頭の中でイメージできるようにしとくのがいいかも。実際ここら辺はどうやって出るかわからん。
ツリーの２つ、二分探索木とヒープはそれぞれの特徴を説明できるように、それとそれぞれの追加、削除の再現ができるように。
２分探索木のほうは削除が１葉のみ。２子が一つある場合。３子が二つある場合。に場合わけされてるから注意。
ここでヒープの応用としてヒープソートが出てくるけど、１、データのすべてを”ヒープの追加”の定義に従って構築。２、一つずつ削除（削除したものを順番に並べていく）。でオッケー。
線形探索、２分探索は最後にやった平均探索回数らへんが重要かも。
ハッシュ法。これはmodが出せるようにしといたほうがいいと思う。例えばx=123,M=10だとh(123)=123%10=3だとか。あとは基本的なアルゴリズムの説明かな。あと授業中にやった例とか。
最後は線形探索、２分探索（整列済み）それぞれの平均探索回数。これはでそうだね。答えから書くと、
平均探査回数：線形探索→(n+1)/2、２分探索→logn
だけど、両方とも導けるようにしといたほうがいいね。特に２分探索は出るって言ってたぞ。先生が。たぶん。で、やり方だけど線形探索はようわからんから期待値を求める感じでおれはやってる。
1*1/n+2*1/n+...+n*1/n=1/n*Σi=(n+1)/2
２分探索もよくわからん。こっちは計算で無理やり出した。ノートのまんまでいくと
平均探索回数＝（比較の全回数）/n、k=log(n+1)
比較の全回数＝Σi*2^(i-1)=Aとすると、（Σはi=1からkまで）
A=1+2*2^1+3*2^2+.....+(k-1)*2^(k-2)+k*2^(k-1)
2A=1*2^1+2*2^2+.....+(k-1)*2^(k-2)+k*2^(k-1)
A-2A={1+2^1+2^2+.....+2^(k-1)}-k*2^k
-A={a=1,r=2,k項の等比数列の和}-k*2^k=2^k-1-k*2^k
A=2^k*(k-1)+1=2^(log(n+1))*(log(n+1)-1)+1=(n+1)log(n+1)-n
平均探索回数=(n+1)*log(n+1)/n-1=（近似）logn
あとはデータの個数がｋ倍になったとき平均探索回数が何倍になるかとかも出そう。
こんなんでどうでしょう？

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）