- 4月13日: 時間計算量の比較
次の n の関数をGNUPLOTでプロットして振る舞いを比較せよ。
- n の範囲や軸のスケール(線形、対数など)は適当に調整すること。
- メールの件名を「kadai01」とし、プロットした図(PNGフォーマット)を電子メールの添付ファイルで提出する。
- 締切: 4月26日(月)
[参考] プロット結果の保存
- 4月20日: 配列
配列がメモリ上にどのように配置されるか調べる。
- char, int, short, long, long long, float, double の各データ型について、それぞれ要素数5の配列を定義し(例 char array[5];)、すべての要素の先頭アドレスを表示する。
[参考]
- 変数 a のアドレスは &a で表される。
- 配列の先頭アドレスは配列名(char array[5]; なら array、定数)で参照可能[参考図]。
- アドレスは符号無 long 型の整数なので、printf の出力指示子は %lx を用いて出力する。
- メールの件名を「kadai02」とし、プログラムソースと出力結果を電子メールの添付ファイル(共にテキストファイル)で提出する。
- 締切: 5月10日(月)
- 4月27日: 連結(線形)リスト
連結リストに対する基本的な処理を行う
- 授業内容(4月26日)の訂正
- プログラムを完成する。
- 実行してキーボードから次の4組のデータを入力する。
| Product | Price |
|---|
| Hamburger | 220 |
| Cheese-burger | 240 |
| Fried-potato | 120 |
| Apple-pie | 150 |
- プログラムソースと実行結果を電子メールの添付ファイル(共にテキストファイル)で提出する。
- メールの件名を「kadai03」とし、本文中に学籍番号、氏名を明記すること。
- 締切: 5月17日(月)
練習課題: 課題のプログラムと同様の動作をするプログラムを、連結リストではなく配列を用いて作成する。
- 提出する場合は件名を「kadai03-2」とし、プログラムソースと実行結果を電子メールの添付ファイル(共にテキストファイル)で提出する。
- 5月11日: ハノイの塔
ハノイの塔を解くプログラムをスタックを用いて作成する
- プログラムを完成させて、円盤の枚数を5にして実行する。
- プログラムソースを添付ファイルで、実行結果をコピー&ペーストでメールの本文中に貼り付けて提出する。
- メールの件名を「kadai04」とし、本文中に学籍番号、氏名を明記すること。
- 締切: 5月24日(月)
- 5月18日: ハノイの塔の時間・空間計算量(練習課題)
ハノイの塔を解くプログラムの時間計算量と空間計算量を調べる
- 時間計算量、空間計算量をそれぞれ、while ループの実行回数、プログラムが実際に使用するスタックのサイズとして求める。
- 上記二つの量を円盤の枚数毎に求め、横軸に円盤枚数(1-30)をとって図にプロットする。
- メールの件名を「kadai04-2」とし、プルグラムソース、結果のデータ、プロットした図(PNGフォーマット)の三つを電子メールの添付ファイルで提出する。
- 本文中に学籍番号、氏名を明記し、結果に対する考察を添えること。
- 締切: 5月24日(月)
- 5月25日: キューを用いた木の幅優先探索
キューを用いて木の幅優先探索を行うプログラムを作成する[資料]
- プログラムを完成させる。
- プログラムソースを添付ファイルで、実行結果をコピー&ペーストでメールの本文中に貼り付けて提出する。
- メールの件名を「kadai05」とし、本文中に学籍番号、氏名を明記すること。
- 締切: 5月31日(月)
- 6月1日: 再帰を用いた木の深さ優先探索
再帰を用いて木の深さ優先探索を行うプログラムを作成する(kadai05と同じ木を使う)
[解説]木のなぞり
- プログラムを完成させる。
- プログラムソースを添付ファイルで、実行結果をコピー&ペーストでメールの本文中に貼り付けて提出する。
- メールの件名を「kadai06」とし、本文中に学籍番号、氏名を明記すること。
- 締切: 6月7日(月)
- 6月8日: 線形探索と二分探索
線形探索と二分探索の時間計算量を比較する
- プログラムを完成させる。
- データをダウンロードしてそれぞれの探索を実行し、探索の結果(配列のインデックス)と完了するまでのステップ数を求める。
- 横軸にデータ数、縦軸にステップ数の平均をプロットする。
- プログラムソース、探索の結果をまとめた表(例)、プロット図をそれぞれ添付ファイルで提出する。
- メールの件名を「kadai07」とし、本文中に学籍番号、氏名を明記すること。
- 締切: 6月14日(月)
- 6月15日: ハッシュ法によるデータ探索
ハッシュテーブルへのデータの格納とハッシュ法によるキー探索
- データの格納および探索のプログラムを完成させる。
- 格納データおよび探索キーは kadai07 のものを使用する。
- 01000.dat から 10000.dat までの 10 個のファイルのデータをそれぞれハッシュテーブルに格納し、ファイルに保存する(ファイル名は自分で決める)
- 保存したハッシュテーブルファイルから、queries.list に記載のクエリーを探索する。
- プログラムソース、探索の結果をまとめた表(例)、探索が終了するまでのステップ数をまとめた表(形式は上と同じ)をそれぞれ添付ファイルで提出する。
- メールの件名は「kadai08」とし、本文中に学籍番号、氏名を明記すること。
- 締切: 6月21日(月)
- 6月22日: 選択ソートと挿入ソート
選択ソートと挿入ソートによりデータをソートし、そのプロセスを比較する
- 6月29日: クイックソート
クイックソートによりデータをソートし、そのプロセスを確認する
- 7月6日: マージソート
マージソートによりデータをソートし、そのプロセスを確認する
練習課題: 選択ソート、挿入ソート、クイックソート、マージソートの4つのアルゴリズムの実行時間を測定し、時間計算量の比較をする
- 7月13日: 動的計画法
動的計画法を用いてナップザック問題を解く
- アルゴリズム
- プログラムを完成させる。
- プログラムソースと、下記のサンプルデータのうち sample8.dat に対する実行結果(例)を、それぞれ添付ファイルで提出する。
- メールの件名を「kadai12」とし、本文中に学籍番号、氏名を明記すること。
- 締切: 7月26日(月)
- 7月20日: 全数探索によるナップザック問題の解法(練習課題)
全数探索を用いてナップザック問題を解き、動的計画法の場合と実行時間を比較する
- プログラムを完成させる。
考え方
- 配列Z[] (荷物 i をナップザックに入れるときZ[i]=1, 入れないときZ[i]=0)に関して探索木を用いて探索する。
- 木のレベルを1ずつ増加させた再帰呼出しを用いて、深さ優先探索(行きがけ順)を行う。
アルゴリズム
- sample1.dat 〜 sample5.dat に対して実行し、横軸に荷物数、縦軸に実行時間をとって結果をGNUPLOTでプロットする。プロットした図はPNGフォーマットで保存すること。
- 提出する場合は件名を「kadai12-2」とし、プログラムソース、sample5.dat に対する実行結果、実行時間をプロットした図を、それぞれ添付ファイルで提出する。
- 本文中に学籍番号、氏名を明記し、動的計画法を用いた場合と実行時間を比較して考察を加えること。
- 締切: 7月23日(金)
- 7月27日: 部分和問題
全数探索(バックトラック法)および分枝限定法を用いて部分和問題を解き、実行時間を比較する
- プログラム[全数探索][分枝限定法]を完成させる。
- sample1.dat 〜 sample9.dat に対してそれぞれ実行し、実行時間を下記の様式の表にまとめる。
| サンプルデータ |
|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
| 全数探索 | | | | | | | | | |
|---|
| 分枝限定法 | | | | | | | | | |
|---|
- それぞれのプログラムソース、sample5.dat に対するそれぞれの実行結果、上記の表、をそれぞれ添付ファイルで提出する。
- メールの件名を「kadai13」とし、本文中に学籍番号、氏名を明記するとともに、結果に対する考察を加えること。
- 締切: 8月2日(月)
