データ構造とアルゴリズム（２００４年度）

授業科目, www.kameda-lab.org 2004/08/16

本授業について

本講義は２００４年度１学期に、筑波大学第三学群工学システム学類（知的工学システム・機能工学システム主専攻）の３年生を想定して開講されます。受講にあたっては、２年生３学期配当の「プログラミング序論」の知識が必要になりますが、「プログラミング序論」の単位が本講義単位取得の前提になっているわけではありません。

担当：亀田能成
教室：3L202

授業内容・シラバスについてはこちらを参照下さい。

成績等

アップデート

授業での記述に問題があったり、訂正があったりしたときにこちらに掲載します。

アップデート情報

課題

＝提出方法について＝

紙ベースでも構いませんが、可能な限り電子メールでの提出をお願いします。
基本的にプログラム提出なので、実験結果・考察・コメントはプログラム中の最初のコメント行として書き加えてください。
プログラムソースをテキストファイルとして電子メールの本文に入れてください。
HTMLメールや特定のアプリケーションに依存する形式(Wordなど)は使用しないで下さい。
（必要があれば添付ファイルを使用してもよいですが、私が閲覧できる保証はありません。）
下記の情報は必須ですので必ず付加してください。

氏名
学籍番号（９桁）
知的工学システム,機能工学システムの別

【電子メール】電子メールでのレポート提出サンプル
宛先(To)： kameda@image.esys.tsukuba.ac.jp
件名(Subject)： Algorithm Report 1.1 ←下記の指定した件名で！（自動処理するので件名が異なると見落とす可能性があります）

＝提出にあたっての一般的注意＝

締切後の提出は最大で通常の半分程度の評価にしかならないと思っておいて下さい。
プログラミング時にお互い相談するのは構いませんが、プログラム自体は 各自で理解して書いて実行させるように。
相談した場合は、教えた側と教えた側でそれぞれ誰に教えた／教えられたかを書いて置いて下さい。また、お互いに相談して似たものになってしまっている場合は、誰と相談しあったかを書いておいて下さい。事前申告があれば、よく似ていてもそのことに対する減点はしません。（教えた側には加点します。）

＝提出時の技術的注意＝

電子メールでは、本文にC Programの形式で送ってください。自動処理でコメントの抽出やコンパイルまで行うので、改行が妙なところに入っていたり、全角スペースがプログラム中に埋まっているとコンパイルエラーになり、評価が不利になる可能性があります。
Outlook/Outlook Expressユーザへ：一部のプログラムで自動コンパイルが落ちているのは、送信時にメールの設定が
Content-Type: text/plain; charset="iso-2022-jp"
Content-Transfer-Encoding: quoted-printable ←「7bit」が正しい
というように、quoted-printableになっているためです。次回からは設定を正しく設定しておいてください。（分からなければメーラを変えるなりgoogleで検索して自分で設定方法を調べるなどしてください。個別対応はしません。）

＝課題内容＝

第１回課題（プログラム１つと考察２つ）
【出題】2004/04/20(Tue)
【締切】2004/04/27(Tue),08:40 JST (到着必須) ☆紙の場合は授業前に提出
【件名】Algorithm Report 1

課題１．１：深さ優先探索プログラムの出力改良（必修）
深さ優先探索(2004/04/20の授業で提示)のプログラムにおいて、printf() 関数を適切な位置に埋めることで、深さ優先スパンニング木の生成結果を分かりやすく出力するプログラムに変更せよ。必要があればプログラムを書換え、変数・関数等を適当に追加してよい。

プログラムソースを送ること。
出力結果をプログラムソース内のコメント内に張り込み、簡単な解説を付け加えること。

サンプル名 SAMPLE A
授業と同一 SAMPLE B
edge[8][8]= {{0,1,0,0,1,0,0,0},
{1,0,0,0,0,0,1,0},
{0,0,0,1,0,0,1,0},
{0,0,1,0,0,0,0,1},
{1,0,0,0,0,1,0,0},
{0,0,0,0,1,0,1,0},
{0,1,1,0,0,1,0,1},
{0,0,0,1,0,0,1,0}}
{{0,1,0,0,1,0,1,0},
{1,0,1,0,1,1,0,0},
{0,1,0,1,0,0,1,0},
{0,0,1,0,0,0,0,0},
{1,1,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0},
{1,0,1,0,0,0,0,1},
{0,0,0,0,0,0,1,0}}

出力例
（この通りである必要は全くない） 0 -> 1 -> 6 -> 2 -> 3 -> 7
(6)-> 5 -> 4 0 -> 1 -> 2 -> 3
(2)-> 6 -> 7
(1)-> 4
(1)-> 5

課題１．２：連結グラフ判定アルゴリズム（必修）
深さ優先探索プログラムを応用すれば、入力されたグラフが連結グラフであるかどうかを判定するプログラムを作成することができる。そのアルゴリズムを考え、記述せよ（自由書式・日本語でよい）。
- 考察は1.のプログラムソース内のコメントに張り込むこと。
- プログラムを作成した場合は1.とのプログラムとの境界を明確にした上でメール本体につけて送ること。
課題１．３：連結成分カウントアルゴリズム（必修）
深さ優先探索プログラムを応用すれば、入力されたグラフに連結成分が幾つあるか数えるプログラムを作成することもできる。（連結成分とは、その成分内のどの頂点も幾つかの辺を経由してお互いに到達することができる部分グラフである。）そのアルゴリズムを考え、記述せよ（自由書式・日本語でよい）。
- 考察は1.のプログラムソース内のコメントに張り込むこと。
- プログラムを作成した場合は1., 2.とのプログラムとの境界を明確にした上でメール本体につけて送ること。

第２回課題
【出題】2004/05/11(Tue)
【締切】2004/05/18(Tue),08:40 JST (到着必須)
【件名】下記参照

課題２．１：経路表示を含むFloydアルゴリズムの実装（必修）
【件名:Subject】Algorithm Report 2.1
全点対について、最小経路を求めるFloydのアルゴリズムをCで作成し、実行結果を示せ。

実行結果は送付するプログラムのコメント行内に取り込んで送ること。
実行結果には、cost[i,j], div[i,j] および経路が存在する点対についての全経路を表示すること。

SAMPLE weight matrix cost[i,j] div[i,j] 経路表示例
A (N=6)
#define NC 999999 // Infinitely big number int w[N][N] = { { 0, NC, NC, 8, 15, NC}, { 10, 0, 24, NC, 8, NC}, { NC, NC, 0, NC, NC, 6}, { NC, NC, NC, 0, 5, NC}, { NC, NC, 12, NC, 0, 7}, { NC, NC, 3, NC, NC, 0}};

* - 23 8 13 20 10 * 18 18 8 15 - - * - - 6 - - 15 * 5 12 - - 10 - * 7 - - 3 - - *

0 -1 5 0 3 4 1 1 5 0 1 4 -1 -1 2 -1 -1 2 -1 -1 5 3 3 4 -1 -1 5 -1 4 4 -1 -1 5 -1 -1 5

0 => 1 [--] 0 => 2 [23] 0 3 4 5 2 0 => 3 [ 8] 0 3 0 => 4 [13] 0 3 4 0 => 5 [20] 0 3 4 5 1 => 0 [10] 1 0 1 => 2 [18] 1 4 5 2 （以下略）

B (N=12)
#define NC 999999 // Infinitely big number int w[N][N] = { { 0, 4,NC,NC, 3,NC,NC,NC,NC,NC,NC,NC}, { 4, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC,NC}, {NC, 1, 0, 1,NC,NC,NC, 2,NC,NC,NC,NC}, {NC,NC, 1, 0,NC,NC,NC,NC,NC,NC,NC,NC}, { 3,NC,NC,NC, 0, 1,NC,NC, 1,NC,NC,NC}, {NC,NC,NC,NC, 1, 0, 2,NC,NC, 2, 3,NC}, {NC, 2,NC,NC,NC, 2, 0,NC,NC,NC, 3,NC}, {NC,NC, 2,NC,NC,NC,NC, 0,NC,NC,NC,NC}, {NC,NC,NC,NC, 1,NC,NC,NC, 0,NC,NC,NC}, {NC,NC,NC,NC,NC, 2,NC,NC,NC, 0,NC,NC}, {NC,NC,NC,NC,NC, 3, 3,NC,NC,NC, 0, 1}, {NC,NC,NC,NC,NC,NC,NC,NC,NC,NC, 1, 0} };

* 4 5 6 3 4 6 7 4 6 7 8 4 * 1 2 5 4 2 3 6 6 5 6 5 1 * 1 6 5 3 2 7 7 6 7 6 2 1 * 7 6 4 3 8 8 7 8 3 5 6 7 * 1 3 8 1 3 4 5 4 4 5 6 1 * 2 7 2 2 3 4 6 2 3 4 3 2 * 5 4 4 3 4 7 3 2 3 8 7 5 * 9 9 8 9 4 6 7 8 1 2 4 9 * 4 5 6 6 6 7 8 3 2 4 9 4 * 5 6 7 5 6 7 4 3 3 8 5 5 * 1 8 6 7 8 5 4 4 9 6 6 1 *

0 0 1 2 0 4 1 2 4 5 5 10 1 1 1 2 5 6 1 2 4 5 6 10 1 2 2 2 5 6 1 2 4 5 6 10 1 2 3 3 5 6 1 2 4 5 6 10 4 6 1 2 4 4 5 2 4 5 5 10 4 6 1 2 5 5 5 2 4 5 5 10 1 6 1 2 5 6 6 2 4 5 6 10 1 2 7 2 5 6 1 7 4 5 6 10 4 6 1 2 8 4 5 2 8 5 5 10 4 6 1 2 5 9 5 2 4 9 5 10 4 6 1 2 5 10 10 2 4 5 10 10 4 6 1 2 5 10 10 2 4 5 11 11

0 => 1 [ 4] 0 1 0 => 2 [ 5] 0 1 2 0 => 3 [ 6] 0 1 2 3 0 => 4 [ 3] 0 4 0 => 5 [ 4] 0 4 5 0 => 6 [ 6] 0 1 6 0 => 7 [ 7] 0 1 2 7 0 => 8 [ 4] 0 4 8 0 => 9 [ 6] 0 4 5 9 0 => 10 [ 7] 0 4 5 10 0 => 11 [ 8] 0 4 5 10 11 1 => 0 [ 4] 1 0 1 => 2 [ 1] 1 2 1 => 3 [ 2] 1 2 3 1 => 4 [ 5] 1 6 5 4 1 => 5 [ 4] 1 6 5 1 => 6 [ 2] 1 6 1 => 7 [ 3] 1 2 7 （以下略）

課題２．２：確率積を経路として持つグラフに対するプログラム（自由）
【件名:Subject】Algorithm Report 2.2
確率積を経路として持つグラフに対する、FloydアルゴリズムをCで作成し、実行結果を示せ。辺の重みは0.0以上1.0以下とする。本課題は必修ではない。

経路コストは、その経路を構成する辺の確率の積で与えられる。
求める経路は、任意地点間の確率最大の経路である。
提出者は必ずメールの件名を正しく指定すること。
実行結果は送付するプログラムのコメント行内に取り込んで送ること。
実行結果には、cost[i,j], div[i,j] および経路が存在する点対についての全経路を表示すること。
定数NCがなぜ0.0であるのかと、w[i,i]が1.0でなくてはいけない理由を述べよ。

SAMPLE weight matrix cost[i,j] div[i,j] 経路表示例
A (N=6)
#define NC 0.0 float w[N][N] = { { 1.00, NC, NC, 0.08, 0.15, NC}, { 0.10, 1.00, 0.24, NC, 0.80, NC}, { NC, NC, 1.00, NC, NC, 0.60}, { NC, NC, NC, 1.00, 0.50, NC}, { NC, NC, 0.12, NC, 1.00, 0.70}, { NC, NC, 0.30, NC, NC, 1.00}};

****** ------ 0.0315 0.0800 0.1500 0.1050 0.1000 ****** 0.2400 0.0080 0.8000 0.5600 ------ ------ ****** ------ ------ 0.6000 ------ ------ 0.1050 ****** 0.5000 0.3500 ------ ------ 0.2100 ------ ****** 0.7000 ------ ------ 0.3000 ------ ------ ******

0 -1 5 0 0 4 1 1 1 0 1 4 -1 -1 2 -1 -1 2 -1 -1 5 3 3 4 -1 -1 5 -1 4 4 -1 -1 5 -1 -1 5

0 => 1 [------] 0 => 2 [0.0315] 0 4 5 2 0 => 3 [0.0800] 0 3 0 => 4 [0.1500] 0 4 0 => 5 [0.1050] 0 4 5 1 => 0 [0.1000] 1 0 1 => 2 [0.2400] 1 2 1 => 3 [0.0080] 1 0 3 （以下略）

第３回課題
【出題】2004/05/25(Tue)
【締切】2004/06/01(Tue),08:40 JST (到着必須)
【件名】下記参照
1. 課題３．１： N=6における騎士の周遊アルゴリズムの実装（必修）
  【件名:Subject】Algorithm Report 3.1
  騎士の周遊(Closed Knight's Tour)とは、騎士の巡回に加えて、最後のマスから開始位置に１手で戻れる経路を求める問題である。これを一辺が６マスの盤で実行せよ。
  - 求めた経路を全てプログラムのコメントに入れる必要はない。数例のみ入れること。
  - 解数はコメントとして書き込むこと。
  - 今後の参考までに、使用環境と実行時間を記述して頂けるとありがたい。UNIXではプログラムの実施時にtimeコマンドを併用すれば計測できる。
  - 授業で説明したプログラムに沿って実行した場合、非常に時間がかかる（５階計算機室のＰＣで６～８時間？）ので注意すること。
2. 課題３．２： N=6における騎士の周遊アルゴリズムの評価回数カウント（自由）
  【件名:Subject】Algorithm Report 3.2
  - 周遊経路を求める際に、飛び先の評価回数が何回になったかを出力するプログラムを書いて実行せよ。
  - 評価回数をコメントとして書き込むこと。
  - 回数の値は、通常のint型で表示できる数字より大きな表現になる。どのような見積もり（ないし工夫）をして非常に大きな数字に対応できるプログラムにしたかをコメント部に記述せよ。
3. 参考
  ６行５列のサイズでは解は１６通り、評価回数は８億回弱程度（プログラムによる）となる。Pentium-4/3.0GB程度で15秒程度。

第４回課題
【出題】2004/06/08(Tue)
【締切】2004/06/15(Tue),08:40 JST (到着必須)
【題目】【件名:Subject】Algorithm Report 4

課題４：行列の乗算回数の最小化を行い、その演算過程を示せ（必修）
乗算順序の表示は、((A(BC))((DE)F))、または ((1(23))((45)6))のようにすること。ただし、このように括弧で表現することが困難であれば、演算順序が何らかの形で分かるように出力するようにしてもよい。作成したプログラムに実験結果をコメントの形で挿入して提出すること。以下の表は解答サンプルである。

N as[...] Amount Operation
6 30, 35, 15, 5, 10, 20, 25 15125 ((A(BC))((DE)F))
7 20, 15, 30, 5, 300, 80, 21, 18 135840 ((A(BC))(((DE)F)G))
11 20, 22, 31, 800, 15, 1700, 50, 20, 11, 2, 30, 400 339284 ((A(B(C(D(E(F(G(HI))))))))(JK))
18 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11 694 (A(((BC)((DE)((FG)((HI)((JK)((LM)((NO)(PQ))))))))R))

第５回課題
【出題】2004/06/22(Tue)
【締切】2004/07/02(Fri),17:00 JST (到着必須)
【題目】下記参照

課題５．１：深さ優先探索アルゴリズムをもとにした巡回セールスマン問題の解法の実装（5.1/5.2のどちらか必修）
【件名:Subject】Algorithm Report 5.1
深さ優先探索アルゴリズムをもとにして、巡回セールスマン問題を解くプログラムを作成せよ。
- 下記例に対して、最小コストと求めたハミルトン経路を示すこと。
- 工夫した点をコメントに記述すること。
課題５．２：巡回セールスマン問題に対する２近似アルゴリズムの実装（5.1/5.2のどちらか必修）
【件名:Subject】Algorithm Report 5.2
最小コストスパニング木を利用した２近似アルゴリズムによるプログラムを作成せよ。
- 最小コストスパニング木を求める部分も作成すること。
- 最小コストスパニング木を求める部分は授業ではクラスカルのアルゴリズムを説明したが、他のアルゴリズムでもよい。
- 辺のソーティングについては、 N^2の計算コストがかかるアルゴリズムでもよい。
- 近似解とそのハミルトン経路を示すこと。
- 最適解との比較を行った場合は、最適解とその経路についても示し、本手法が確かに２近似であることも示せ（自由課題）。
注意
単位取得について、希望がある場合はメール中の目立つところに（前のほうに）その旨を申告してください。

参考
12-15頂点による完全グラフの例を挙げておきます。 14頂点以上については、指数時間プログラムのほうの実行時間は覚悟しておいてください。

課題5.1/5.2両用 SAMPLE_A

#define N 12
int w[N][N] = {
       A    B    C    D    E    F    G    H    I    J    K    L
A  {   0, 205, 241,  32, 253,  27,  89, 280, 163, 189, 105, 130 },
B  { 205,   0, 144,  16, 212, 133, 101, 272,  52, 295, 120,  67 },
C  { 241, 144,   0, 295,  30, 156,  42, 192, 259, 224, 126, 166 },
D  {  32,  16, 295,   0, 283, 180,  43, 186, 195, 180,  30,  59 },
E  { 253, 212,  30, 283,   0, 162,  96, 191,  90, 168,   3, 156 },
F  {  27, 133, 156, 180, 162,   0, 164, 152, 174, 207, 226, 235 },
G  {  89, 101,  42,  43,  96, 164,   0,  55, 160,  86, 158, 200 },
H  { 280, 272, 192, 186, 191, 152,  55,   0, 114, 249, 292,   8 },
I  { 163,  52, 259, 195,  90, 174, 160, 114,   0, 295, 241, 246 },
J  { 189, 295, 224, 180, 168, 207,  86, 249, 295,   0, 209, 234 },
K  { 105, 120, 126,  30,   3, 226, 158, 292, 241, 209,   0,  37 },
L  { 130,  67, 166,  59, 156, 235, 200,   8, 246, 234,  37,   0 }
};

課題5.1/5.2両用 SAMPLE_12

#define N 12
int w[N][N] = {
  {   0, 122,  73,  54,  50, 140, 130, 100,  36,  85, 139,  73 },
  { 122,   0,  50,  70, 108,  28,  14,  89, 100, 100,  32, 166 },
  {  73,  50,   0,  20,  72,  73,  61,  81,  51,  81,  67, 127 },
  {  54,  70,  20,   0,  63,  92,  81,  85,  32,  81,  85, 114 },
  {  50, 108,  72,  63,   0, 117, 112,  54,  71,  36, 135,  58 },
  { 140,  28,  73,  92, 117,   0,  14,  85, 124, 100,  51, 175 },
  { 130,  14,  61,  81, 112,  14,   0,  86, 112,  99,  40, 170 },
  { 100,  89,  81,  85,  54,  85,  86,   0, 108,  20, 121, 100 },
  {  36, 100,  51,  32,  71, 124, 112, 108,   0,  98, 112, 108 },
  {  85, 100,  81,  81,  36, 100,  99,  20,  98,   0, 130,  81 },
  { 139,  32,  67,  85, 135,  51,  40, 121, 112, 130,   0, 192 },
  {  73, 166, 127, 114,  58, 175, 170, 100, 108,  81, 192,   0 }
};

課題5.1/5.2両用 SAMPLE_13

#define N 13
int w[N][N] = {
  {   0, 120, 136,  91,  22,  32,  42, 104, 110, 108, 128, 120,  81 },
  { 120,   0,  91,  36, 130, 136,  98, 127,  10, 197,  92,  89, 100 },
  { 136,  91,   0,  73, 156, 130,  94, 197,  90, 240,  10, 173, 166 },
  {  91,  36,  73,   0, 104, 102,  63, 125,  28, 180,  71, 100,  94 },
  {  22, 130, 156, 104,   0,  50,  64,  89, 120,  86, 149, 114,  71 },
  {  32, 136, 130, 102,  50,   0,  40, 136, 126, 130, 121, 150, 112 },
  {  42,  98,  94,  63,  64,  40,   0, 130,  89, 150,  86, 130, 100 },
  { 104, 127, 197, 125,  89, 136, 130,   0, 120,  91, 193,  51,  32 },
  { 110,  10,  90,  28, 120, 126,  89, 120,   0, 188,  91,  85,  92 },
  { 108, 197, 240, 180,  86, 130, 150,  91, 188,   0, 233, 140, 102 },
  { 128,  92,  10,  71, 149, 121,  86, 193,  91, 233,   0, 171, 162 },
  { 120,  89, 173, 100, 114, 150, 130,  51,  85, 140, 171,   0,  45 },
  {  81, 100, 166,  94,  71, 112, 100,  32,  92, 102, 162,  45,   0 }
};

課題5.1/5.2両用 SAMPLE_14

#define N 14
int w[N][N] = {
  {   0,  73, 156, 130,  94, 197,  90, 240,  10, 173, 166, 175, 227, 234 },
  {  73,   0, 104, 102,  63, 125,  28, 180,  71, 100,  94, 140, 170, 170 },
  { 156, 104,   0,  50,  64,  89, 120,  86, 149, 114,  71,  50,  71,  85 },
  { 130, 102,  50,   0,  40, 136, 126, 130, 121, 150, 112,  45, 112, 133 },
  {  94,  63,  64,  40,   0, 130,  89, 150,  86, 130, 100,  82, 135, 148 },
  { 197, 125,  89, 136, 130,   0, 120,  91, 193,  51,  32, 136,  95,  70 },
  {  90,  28, 120, 126,  89, 120,   0, 188,  91,  85,  92, 161, 180, 175 },
  { 240, 180,  86, 130, 150,  91, 188,   0, 233, 140, 102, 100,  20,  22 },
  {  10,  71, 149, 121,  86, 193,  91, 233,   0, 171, 162, 166, 219, 228 },
  { 173, 100, 114, 150, 130,  51,  85, 140, 171,   0,  45, 164, 141, 120 },
  { 166,  94,  71, 112, 100,  32,  92, 102, 162,  45,   0, 120, 100,  85 },
  { 175, 140,  50,  45,  82, 136, 161, 100, 166, 164, 120,   0,  81, 110 },
  { 227, 170,  71, 112, 135,  95, 180,  20, 219, 141, 100,  81,   0,  36 },
  { 234, 170,  85, 133, 148,  70, 175,  22, 228, 120,  85, 110,  36,   0 }
};

課題5.1/5.2両用 SAMPLE_15

#define N 15
int w[N][N] = {
  {   0,  50,  64,  89, 120,  86, 149, 114,  71,  50,  71,  85,  22,  73,  86 },
  {  50,   0,  40, 136, 126, 130, 121, 150, 112,  45, 112, 133,  63,  76,  54 },
  {  64,  40,   0, 130,  89, 150,  86, 130, 100,  82, 135, 148,  63,  42,  92 },
  {  89, 136, 130,   0, 120,  91, 193,  51,  32, 136,  95,  70,  73, 104, 175 },
  { 120, 126,  89, 120,   0, 188,  91,  85,  92, 161, 180, 175, 102,  51, 180 },
  {  86, 130, 150,  91, 188,   0, 233, 140, 102, 100,  20,  22,  92, 150, 140 },
  { 149, 121,  86, 193,  91, 233,   0, 171, 162, 166, 219, 228, 142,  89, 163 },
  { 114, 150, 130,  51,  85, 140, 171,   0,  45, 164, 141, 120,  92,  92, 198 },
  {  71, 112, 100,  32,  92, 102, 162,  45,   0, 120, 100,  85,  50,  73, 156 },
  {  50,  45,  82, 136, 161, 100, 166, 164, 120,   0,  81, 110,  72, 110,  41 },
  {  71, 112, 135,  95, 180,  20, 219, 141, 100,  81,   0,  36,  81, 139, 120 },
  {  85, 133, 148,  70, 175,  22, 228, 120,  85, 110,  36,   0,  86, 141, 151 },
  {  22,  63,  63,  73, 102,  92, 142,  92,  50,  72,  81,  86,   0,  58, 106 },
  {  73,  76,  42, 104,  51, 150,  89,  92,  73, 110, 139, 141,  58,   0, 130 },
  {  86,  54,  92, 175, 180, 140, 163, 198, 156,  41, 120, 151, 106, 130,   0 }
};

試験
実施しません。

告知

課題そのものに直接お答えはできませんが、課題提出に関わるＣ言語のプログラミング相談を、不定期ながら開催します。TAが相談にのります。時間限定ですので注意してください。
希望者は、できる限り、事前にメール連絡（西崎(tanishi)、山本(haruyosh)、亀田(kameda)に @image.esys.tsukuba.ac.jpをつけて下さい）をお願いします。

2004/4/22(Thu), 17:00-18:00
　　場所：3L302（必要があれば5L502に移動することもあります）
　　ＴＡ：西崎（理工学研究科１年）担当予定
2004/4/23(Fri), 16:30-18:00
　　場所：3L302（必要があれば5L502に移動することもあります）
　　ＴＡ：山本（システム情報学研究科１年）担当予定

授業内容

2004/08/16現在。

科目番号/知的工学  3206/S513111
科目番号/機能工学  3240/S613111
英名               Data Structure and Algorithm
担当教官           亀田能成
研究室             3M304
電話               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

●関連情報：

同名の知的工学配当科目と機能工学配当科目は同一授業である。

●授業概要および学類教育目標との対応：

プログラミング序論を踏まえて、グラフ問題や組み合わせ問題をプログラ
ミングでどのように解決していけるかを学ぶ。それぞれの問題に合わせて、
プログラミング上で問題をどのように表すべきか、実行時にどのような計
算量的困難さが生じるかを認識・理解する。
本授業では、プログラミングに関する広範囲な知識を学び、諸君を専門的
なプログラミングへと円滑に導入する。また、例題を通じて問題解決の手
順を学ぶ。結果として、コンピュータを利用した情報処理能力と論理的・
数学的思考・解析能力を習得してもらう。

●使用教科書、参考書：

教科書は使用しない。参考書としては下記のものを挙げておく。
◎アルゴリズムとデータ構造―改訂C言語版（電気工学入門シリーズ）
平田富夫(著)森北出版(2002/09),ISBN:462772652X / 2,200円
◎アルゴリズムイントロダクション（全三巻）
Thomas H. Cormen 他(原著),浅野哲夫 他(翻訳),近代科学社(1995/12) 
[第1巻:数学的基礎とデータ構造,ISBN:4764902451 / 3,600円]
[第2巻:アルゴリズムの設計と解析手法,ISBN: 476490246X / 3,600円]
[第3巻,精選トピックス,ISBN: 4764902478 / 3,900円]
◎アルゴリズムC(第3巻)グラフ・数理・トピックス
Robert Sedgewick(原著),野下浩平 他(翻訳),近代科学社(1996/10),ISBN: 4764902575 / 3,300円



●単位取得用件、成績評価基準：

ほぼ隔週でレポート課題を出す。最低6割以上提出すること。
〆切を過ぎた提出に対しては、内容が良くとも評点は半分しか与えない。
成績評価は原則としてレポートのみで行い、レポート課題の評点総計が6割以上で合格（60%以上70%未満をC評価、70%以上80%未満をB評価、80%以上をA評価）とする。
60%未満はD評価として単位は認定しない。レポート課題の評価次第では、補足的に試験を行うこともある。



●受講学生に望むこと：

コンピュータがいくら高速になっても、依然として解けない問題は数多くあることと、現実問題として下手なプログラミングと上手なプログラミングで解へ到達できるかどうかが劇的に変わることを認識してもらいたい。

●受講学生の到達度目標レベル：

様々なグラフ問題・組み合わせ問題に対してプログラムが記述できるようになること。
どのような問題が計算困難で、どのような問題がそうでないかの知識を身につけること。

●各週授業計画：

概ね以下のような順で進むが、
以下の各項が必ずしも１週ずつに対応しているわけではない。

計算量とオーダー
グラフとネットワーク
　グラフとは
　グラフの探索
　　　深さ優先
　　　幅優先
　　　トポロジカルソート
　経路問題
　　　最長経路問題
　　　最短経路問題/Dijkstra
　　　最短経路問題/Floyd
　マッチング
　　　安定結婚問題
探索アルゴリズム
　バックトラックアルゴリズム
　　　Knight's tour
　　　N queen
　　　Knapsack Problem
　分岐限定アルゴリズム
　　　Knapsack Problem
　動的計画法
　　　Knapsack Problem
　　　行列積演算コスト評価
いろいろなアルゴリズム／置き換え・近似
　問題の置換・変換
　　　Knapsack=最長経路問題
　貪欲法
　　　Fractional Knapsack
　　　Knapsack by Fully polynomial time approximation
　巡回セールスマン問題
　　　最適解
　　　二近似アルゴリズム

【２００４年度シラバスのコピー(PDF)】

<kameda@image.esys.tsukuba.ac.jp>

サンプル名	SAMPLE A 授業と同一	SAMPLE B
edge[8][8]=	{{0,1,0,0,1,0,0,0}, {1,0,0,0,0,0,1,0}, {0,0,0,1,0,0,1,0}, {0,0,1,0,0,0,0,1}, {1,0,0,0,0,1,0,0}, {0,0,0,0,1,0,1,0}, {0,1,1,0,0,1,0,1}, {0,0,0,1,0,0,1,0}}	{{0,1,0,0,1,0,1,0}, {1,0,1,0,1,1,0,0}, {0,1,0,1,0,0,1,0}, {0,0,1,0,0,0,0,0}, {1,1,0,0,0,0,0,0}, {0,1,0,0,0,0,0,0}, {1,0,1,0,0,0,0,1}, {0,0,0,0,0,0,1,0}}
出力例（この通りである必要は全くない）	0 -> 1 -> 6 -> 2 -> 3 -> 7 (6)-> 5 -> 4	0 -> 1 -> 2 -> 3 (2)-> 6 -> 7 (1)-> 4 (1)-> 5

N	as[...]	Amount	Operation
6	30, 35, 15, 5, 10, 20, 25	15125	((A(BC))((DE)F))
7	20, 15, 30, 5, 300, 80, 21, 18	135840	((A(BC))(((DE)F)G))
11	20, 22, 31, 800, 15, 1700, 50, 20, 11, 2, 30, 400	339284	((A(B(C(D(E(F(G(HI))))))))(JK))
18	11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11, 2, 11	694	(A(((BC)((DE)((FG)((HI)((JK)((LM)((NO)(PQ))))))))R))