実質担当：亀田能成
教室：3L202
シラバス的内容については授業説明を参照下さい。
プログラム演習による課題提出が主体だったので、
ついてきてくれる学生とそうでない学生とがはっきり分かれましたが、
ついてきてくれた学生には内容を理解してもらえたと思います。
アンケートではいろいろな改善点の指摘や提案がありましたので、
来年以降役立てさせてもらいます。
特に要望が多かった「自分のプログラムは果たしてきちんと動いているのか？」
ということについては、もっと各自でも確認できるサンプルなどを用意して
いきたいと思います。
筑波大学赴任直後ということもあって、
必ずしも十分な授業準備ができていないときがありました。
この点については来年以降改善していきます。
【電子メール】
宛先(To)： kameda@image.esys.tsukuba.ac.jp
題名(Subject)： Algorithm Report x.x
←課題1.2なら"Algorithm Report 1.2"とする
◎締切後の提出は最大で通常の半分程度の評価にしかならないと思っておいて下さい。
◎プログラミング時にお互い相談するのは構いませんが、プログラム自体は独力で
書いて実行させること。
△実行時間の計測には time コマンドが使用できる。
△乱数の発生には random()関数が利用できる。
△乱数系列の再現性確保には srandom()関数が利用できる。
△始点は(0,0)としておくが、実は任意位置でよい。
全マス通過するので結果は同じである。
|
|
|
課題２は選択制です。どちらか１つをメールで提出してください。 課題２．２のほうが難易度が高いので、 こちらを選択した場合は加点を狙えます。 また、余裕のある人は２つ行ってもらっても構いませんが、 その場合は１つずつ別のメールで出してください。 ２つ行った場合の評価は、どちらかいいほうの評価＋αとなります。 必ずプログラムソースを送ること。
#define NC 999 /* It should be large enough. */
#define N 6
int arc[N][N] = {
/* src: 0 1 2 3 4 5 ...dst */
/* 0 */ { 0, NC, NC, 8, 15, NC},
/* 1 */ { 10, 0, 24, NC, 8, NC},
/* 2 */ { NC, NC, 0, NC, NC, 6},
/* 3 */ { NC, NC, NC, 0, 5, NC},
/* 4 */ { NC, NC, 12, NC, 0, 7},
/* 5 */ { NC, NC, 3, NC, NC, 0}
};
#define N 8
int arc[N][N] = {
/* 0 1 2 3 4 5 6 7 */
{0,4,0,0,2,0,0,0}, /* 0 */
{0,0,0,0,0,0,1,0}, /* 1 */
{0,0,0,3,0,0,3,0}, /* 2 */
{0,0,0,0,0,0,0,5}, /* 3 */
{0,0,0,0,0,2,0,0}, /* 4 */
{0,0,0,0,0,0,2,0}, /* 5 */
{0,0,0,0,0,0,0,1}, /* 6 */
{0,0,0,0,0,0,0,0} /* 7 */
};
#define N 17
int arc[N][N] =
{
/* 天久保 */ { 0, 15, 10, 5, 20, NC, NC, 20, NC, NC, NC, 10, NC, NC, NC, 3, NC,},
/* 一の矢 */ { NC, 0, 15, 20, 25, NC, 25, NC, NC, 15, 30, 5, 50, 30, NC, NC, NC,},
/* 桜 */ { 11, 9, 0, NC, NC, NC, NC, 18, NC, NC, 28, 6, 45, 30,120, NC, NC,},
/* 春日 */ { 6, 13, 8, 0, 22, NC, NC, NC, NC, NC, NC, 22, NC, NC, NC, 3, NC,},
/* 花畑 */ { 15, 5, 10, 20, 0, NC, NC, 5, NC, 5, NC, NC, NC, NC, NC, NC, NC,},
/* いんちん珍来 */ { 1, 10, 5, 12, 20, 0, 30, NC, NC, 5, NC, 9, NC, NC, 90, NC, NC,},
/* 竹園 */ { NC, NC, NC, NC, NC, 10, 0, NC, NC, NC, NC, NC, NC, NC, 80, NC, NC,},
/* 大穂 */ { NC, 14, 17, NC, 9, NC, 39, 0, NC, NC, NC, 23, NC, NC, NC, NC, NC,},
/* 二宮 */ { 20, 30, 25, 20, 40, 25, 10, 40, 0, NC, 30, 25, 70, 15, 50, 20, 15,},
/* 柴崎 */ { 9, 13, 1, 11, 20, 3, 30, NC, NC, 0, 30, NC, NC, NC,100, 7, NC,},
/* 土浦 */ { 68, 79, 72, 74, 92, 73, 49, NC, NC, NC, 0, 80, 98, 54,135, NC, NC,},
/* 筑波大 */ { 1, 7, 6, 5, 13, 5, 16, 14, NC, NC, 25, 0, 26, 10,120, 2, 8,},
/* 筑波山 */ { 25, 22, 18, 27, 20, 23, 40, 17, NC, 20, NC, 23, 0, 40, NC, 35, NC,},
/* 筑波センター */ { NC, NC, NC, 33, NC, NC, 10, NC, NC, NC, 30, NC, NC, 0, NC, 7, 2,},
/* 柏 */ { NC, 55, NC, NC, NC, NC, NC, NC, 42, NC, 39, NC, NC, 50, 0, 47, NC,},
/* 平砂 */ { NC, 15, NC, NC, 40, NC, NC, NC, NC, NC, NC, 5, 50, 20, 80, 0, NC,},
/* 吾妻 */ { NC, NC, NC, NC, NC, NC, NC, NC, NC, NC, 25, NC, 60, NC, 85, NC, 0,}
};
char *vname[] = {
"天久保", "一の矢", "桜", "春日", "花畑", "いんちん珍来", "竹園", "大穂", "二宮",
"柴崎", "土浦", "筑波大", "筑波山", "筑波センター", "柏", "平砂", "吾妻"};
#define N 4
#define E 6
#define X -1
int link[N][N] = {
{ 0, 9,50,23},
{ 9, 0,15, 8},
{50,15, 0,20},
{23, 8,20, 0}
};
科目番号/知的工学 3206/S513021
科目番号/機能工学 3240/S613021
英名 Data Structure and Algorithm
担当教官 亀田能成・丸山勉
研究室 3F309（亀田能成）
電話 5256（亀田能成）
Office Hour Weekday 10:00-18:00
e-mail kameda@image.esys.tsukuba.ac.jp
関連科目 計算機序論II(S511024/S611024)
プログラミング序論(S511034/S611034)
グラフ理論(S512041/S612041)
授業HPへのlink http://www.kameda-lab.org/lecture/course-a-j.html
●関連情報：
S513021(知的工学配当)とS613021(機能工学配当)とは同一授業である。
2003年度の授業については、
http://www.kameda-lab.org/lecture/2003-tsukuba-algorithm/index-j.html
を参照のこと。
●授業概要および学類教育目標との対応：
プログラミング序論を踏まえて、グラフ問題や組み合わせ問題をプログラミングで
どのように解決していけるかを学ぶ。それぞれの問題に合わせて、
プログラミング上で問題をどのように表すべきか、
実行時にどのような計算量的困難さが生じるかを認識・理解する。
●使用教科書、参考書：
教科書は使用しない。
参考書としては下記のものを挙げておく。
アルゴリズムとデータ構造―改訂C言語版（電気工学入門シリーズ）
平田 富夫 (著)
森北出版 ; ISBN: 462772652X ; 改訂版 版 (2002/09)
2,200円
アルゴリズムイントロダクション
第1巻 数学的基礎とデータ構造 ; ISBN: 4764902451 ; 3,600円
第2巻 アルゴリズムの設計と解析手法 ; ISBN: 476490246X ; 3,600円
第3巻 精選トピックス ; ISBN: 4764902478 ; 3,900円
Thomas H. Cormen (原著), Ronald L. Rivest (原著), Charles E. Leiserso (原著),
浅野 哲夫 (翻訳), 梅尾 博司 (翻訳), 和田 幸一 (翻訳), 岩野 和生 (翻訳), 山下 雅史 (翻訳)
近代科学社 ; (1995/12)
アルゴリズムC〈第3巻〉グラフ・数理・トピックス
Robert Sedgewick (原著), 野下 浩平 (翻訳), 佐藤 創 (翻訳), 星 守 (翻訳), 田口 東 (翻訳)
近代科学社 ; ISBN: 4764902575 ; 第3巻 (1996/10)
3,300円
●単位取得用件、成績評価基準：
ほぼ隔週でレポート課題を出す（2003年は５回）。
最低６割以上提出すること。６割提出していても不合格になることはある。
〆切を過ぎた提出に対しては、内容が良くとも評点は半分しか与えない。
2004年度以降も2003年度と同様に進むとは限らないが、
http://www.kameda-lab.org/lecture/2003-tsukuba-algorithm/index-j.html
に2003年度の課題が掲載されている。
なお、レポート課題の提出内容次第ではあるが、試験は行わないことを原則としている。
●受講学生に望むこと：
コンピュータがいくら高速になっても、依然として解けない問題は数多くあることと、
現実問題として下手なプログラミングと上手なプログラミングで解へ到達できるかどうかが
劇的に変わることを認識してもらいたい。
●受講学生の到達度目標レベル：
様々なグラフ問題・組み合わせ問題に対してプログラムが記述できるようになること。
どのような問題が計算困難で、どのような問題がそうでないかの知識を身につけること。
●各週授業計画：
（以下の各行は１週に対応しているわけではない。）
探索アルゴリズム（バックトラックアルゴリズム）Knight's tour
探索アルゴリズム（分岐限定アルゴリズム）N queen, Knapsack Problem
探索アルゴリズム（動的計画法）Knapsack Problem
探索アルゴリズム（動的計画法）行列積演算コスト評価
計算量・グラフとネットワークの表現
グラフの探索（深さ優先、幅優先）
グラフの探索（トポロジカルソート）
経路問題（最長経路問題、最短経路問題/Dijkstra）
経路問題（最短経路問題/Floyd）
マッチング（安定結婚問題）
問題の置換（Knapsack=最長経路問題）
貪欲法：Fractional Knapsack
貪欲法：Knapsack by Fully polynomial time approximation
近似アルゴリズム：Traveling Salesman Problemへの２近似解