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

授業科目, www.kameda-lab.org 2007/06/20

本授業について

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

担当：亀田能成
教室：3L202
学期：１
コマ：火曜１・２

L棟５階の計算機システムにアカウントのない履修希望者は、３週目の授業までに申し出てください。アカウントを作成しないと実質上履修は不可能です。

日程

 1. 2007/04/17(Tue)
 2. 2007/04/24(Tue)
 3. 2007/05/01(Tue)
 4. 2007/05/08(Tue)
 5. 2007/05/15(Tue)
 6. 2007/05/22(Tue)
 7. 2007/05/29(Tue)
 8. 2007/06/05(Tue)
 9. 2007/06/12(Tue)
10. 2007/06/19(Tue)
--. 2007/06/26(Tue) (試験期間)

課題

提出方法

Web CT System ログインへ

課題等の提出は、２００６年度から筑波大学で全学的本運用が開始された WebCTシステム経由で全て行います。 WebCTシステムは今のところ学内からのみアクセス可能のようです（変更の可能性あり）。

履修登録が確定したあと、履修者には全員、WebCTのアカウント権限が付与されます。アカウント権限を割り当てられた学生のみがログインできます。

センターからのアナウンス

WebCTでは、アカウント名やパスワードが学情センターの教育用計算機システム(icho)と一致するようにしています。
学生のアカウント名は「小文字のs」＋「学籍番号の下7桁」で従前より変更ありません。「200501234」という学籍番号の学生のアカウント名は「s0501234」になります。
パスワードは統一認証システムのものを使いますので、忘れてしまった学生は学情センター(あるいは図書館)で再発行の手続きをしてください。

課題実施方法

課題の多くでは、Ｃプログラムの作成と実行が必要です。これらはL棟５階計算機システムのLinux環境を前提にします。 L棟５階計算機システムのLinux環境で意図したとおりの動作をすることを自分で確認してください。

課題提出方法についての一般的注意

C プログラムファイル
できるだけ１つのファイルにまとめてください。複数のプログラムファイルにまたがっている場合はそのことを必ず申告してください。なお、自動処理でコンパイルや実行テストを行うので、コンパイル不能・実行不能なソースが提出された場合、評価が不利になります。
実行結果
実行結果は別ファイルに吐き出して、それを提出してください。
論述課題
各回の指示に従って提出してください。
〆切
締切後の提出は最大で通常の半分程度の評価にしかならないと思っておいて下さい。（締切後しばらくすると受付は停止します。）
相談（グループワーク）
お互いに相談するのは構いませんが、プログラム自体は 各自で理解して書いて実行するように。相談した場合は、教えた側と教えた側でそれぞれ誰に教えた／教えられたかを書いておいて下さい。また、お互いに相談して似たものになってしまっている場合は、誰と相談しあったかを書いておいて下さい。事前申告があれば、よく似ていてもそのことに対する減点はせず、むしろ教えた側には加点します（教える側も責任と自覚をもって教えて下さい）。
配点
WebCT上で配点を示していますが、配点の見積を示したものであって、厳密なものではありません。

課題内容

第１回課題

★必修：課題１ａ★
幅優先探索のプログラムを改良して、最初のノードからの該当するノードまでの辺数毎に頂点を分けて表示するプログラムを書いて実行せよ。可能ならば各頂点にどの頂点から辿れるかも示せ。
参考：グラフ(3a, 3b, 3c)とそれぞれノード０から出発したときの出力例 ※あくまで「例」なのでこの通りである必要はない。

提出物〔１ａ－１〕：Ｃソースファイル（コメント必須）
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。

【注意】
●誰かに教えてもらった場合：
⇒その学生（氏名と９桁の学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行以上書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
●誰かに教えてあげた場合：
⇒その学生（氏名・学籍番号）をプログラム先頭に記すこと。
●お互いに相談した場合：
⇒教えてもらった・教えてあげたの例に準拠して提出してください。

提出物〔１ａ－２〕：プログラムの出力結果を保存したテキストファイル（グラフ3aだけで構いません）
※教員側で万一、コンパイルや実行に失敗した場合用です。

★必修：課題１ｂ★
Graph 3aにおいて、授業で説明したプログラムではノード０からの深さ優先探索では"01623754"となる。これに対して、深さ優先探索のままで出力順を"73245610"とするにはどうすればよいか。
- 提出物〔１ｂ－１〕：Ｃソースファイル（コメント必須）
  書き換えた場所が分かるようにコメントを挿入しておくこと。
★必修：課題１ｃ★
授業で説明した深さ優先探索・幅優先探索プログラムで全頂点をを数え上げるには、グラフが連結であり無向である必要がある。有向グラフではなぜいけないのか、理由を述べよ。
- 提出物〔１ｃ－１〕：テキストファイル
  ▼ヒント：論述でもよいですし、反例を示してもよいです。
☆発展：課題１ｄ☆
無向グラフとしてある木が与えられたとき、頂点数Ｎと辺数Ｍとの間の関係を式で示せ。次に、その式を満たす無向グラフが与えられたとき、それは必ず木であると言えるかどうかを理由と共に示せ。
- 提出物〔１ｄ－１〕：テキストファイル
  どうしても図を使いたければpdf(ないしword, powerpoint)で提出しても構いませんが、こちらで読めるかどうか保証はできません。
  ▼ヒント：論述でもよいですし、反例を示してもよいです。
提出期限
2006/5/15, 8:30 JST
提出方法
WebCTによる提出

第２回課題

★必修：課題２ａ★
授業中に紹介した最長経路問題を解くプログラムを改良して、グラフ中の「最長経路の値」と「最長経路を構成する頂点列」を表示できるようにし、実行せよ。
参考：グラフ(5-dash0, 5-dash1)とその出力例(コメント中に記載)
※あくまで「例」なので内容が正しければ表示の仕方がこの通りである必要はない。

提出物〔２ａ－１〕：Ｃソースファイル（コメント必須）
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。

【注意】
課題１ａと同じく、
誰かに教えてもらった場合、
誰かに教えてあげた場合、
お互いに相談した場合はその旨記述すること。

提出物〔２ａ－２〕：プログラムの出力結果を保存したテキストファイル（グラフ5-dash0だけで構いません）
※教員側で万一、コンパイルや実行に失敗した場合用です。

★必修：課題２ｂ★
授業中に紹介した最長経路問題を解くプログラムは、最長経路の計算をノードごとに進めていくところに無駄な処理がある。その部分を改良しなさい。
- 提出物〔２ｂ－１〕：Ｃソースファイル（コメント必須）
  書き換えた場所が分かるようにコメントを記述すること。
★必修：課題２ｃ★
最短経路問題において、辺の重みに０があるとどのような問題が発生するか説明せよ。また、辺の重みに負を許すとどのような問題が発生するか述べよ。
- 提出物〔２ｃ－１〕：テキストファイル
☆発展：課題２ｄ☆
実際の生活の中から最長経路問題が適用できる例を見つけ出し、それをグラフ化した上で、プログラムを用いて最長経路値と最長経路を求め、その解説をせよ。
- 提出物〔１ｄ－１〕：テキストファイル
  グラフの構造を図や行列で示し、どのような問題に対応するか説明せよ。
  また、結果を示し、その意味するところを述べよ。
- 提出物〔１ｄ－２〕：Ｃソースファイル（コメント必須）
  本課題を実現するのに用いたプログラムを提出すること。
提出期限
2006/5/22, 8:30 JST （5/23ではありません。注意！）
提出方法
WebCTによる提出

第３回課題

★必修：課題３ａ★
グラフ中の全ての頂点対について最短経路を求めるFloydのアルゴリズムについて、以下の課題を実施すること。

提出物〔３ａ－１〕：Ｃソースファイル（コメント必須）
授業中に説明したFloydのＣプログラムにおいて、全ての頂点対の最短経路値とその頂点リストがわかるような出力をする部分を書き加えて完成させよ。グラフの例と出力例は下記に掲載する。なお、経路がわかるような出力であれば、出力フォーマットは出力例に準じる必要はない。
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。

【注意】
課題１ａと同じく、
誰かに教えてもらった場合、
誰かに教えてあげた場合、
お互いに相談した場合はその旨記述すること。

提出物〔３ａ－２〕：プログラムの出力結果を保存したテキストファイル（下記グラフ７だけで構いません）
※教員側で万一、コンパイルや実行に失敗した場合用です。
参考
- グラフ７の隣接行列と出力例
- グラフ８の隣接行列と出力例

★必修：課題３ｂ★
Floydのプログラムについて、時間計算量、空間計算量を示せ（それぞれビッグオー表現を用いてよい）。計算の上でプログラム中のどの部分に注目しているかを示し、そこに注目した理由も述べること。
- 提出物〔３ｂ－１〕：テキストファイル

☆発展：課題３ｃ☆
確率積を経路として持つグラフに対して、その確率積が最大になるような経路を全ての頂点対に対して見つけ、その経路と確率積を表示するプログラムを作成・実行せよ。

提出物〔３ｃ－１〕：Ｃソースファイル（コメント必須）
グラフの例と出力例は下記に掲載する。なお、経路がわかるような出力であれば、出力フォーマットは下記例に準じる必要はない。
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
提出物〔３ｃ－２〕：プログラムの出力結果を保存したテキストファイル（下記例だけで構いません）
※教員側で万一、コンパイルや実行に失敗した場合用です。

参考
確率積用のグラフG9

SAMPLE

weight matrix

cost[i][j]

via[i][j]

経路表示例

G9 (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
以下略

提出期限
2007/6/5, 8:30 JST
提出方法
WebCTによる提出

第４回課題

★必修：課題４ａ★
授業中に説明したKnight's Tour（騎士の巡回）の解を求めるプログラムを用いて、チェス盤の１辺Nが5と6の場合について、経路の数を求めよ。スタート地点は(0,0)とする。また、そのときの時間計算量（制御ループの一番内側のif文の評価回数で表すものとする）を、桁あふれがないように注意しつつ求めよ。

提出物〔４ａ－１〕：Ｃソースファイル（コメント必須）
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。

【注意】
課題１ａと同じく、
誰かに教えてもらった場合、
誰かに教えてあげた場合、
お互いに相談した場合はその旨記述すること。

提出物〔４ａ－２〕：プログラムの出力結果を保存したテキストファイル
N=5, N=6の両方について、解の数と、時間計算量の評価回数、それに実行時間を示すこと。
提出物〔４ａ－３〕：時間計算量を測定するための評価回数カウントに関する工夫を述べたテキストファイル
N=5, N=6の両方について、解の数と、時間計算量の評価回数、それに実行時間を示すこと。
時間計算量は通常のint型を超える可能性に対して、プログラム上どのように工夫して桁あふれがないようにしているかを説明する。
必要であれば、ソースプログラムの一部を引用してよい。

★必修：課題４ｂ★
Closed Knight's Tour（騎士の周遊）とは、Knight's Tourに加えて、経路の最後のマスからスタート地点に１手で戻れる経路を求める問題である。チェス盤の１辺Nが5と6の場合について、この条件を満たす経路の数を求めよ。また、実行時間も示せ。

提出物〔４ｂ－１〕：Ｃソースファイル（コメント必須）
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
課題４ａから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
▼ヒント：終了判定が１つ増えることになります。

【注意】
課題１ａと同じく、
誰かに教えてもらった場合、
誰かに教えてあげた場合、
お互いに相談した場合はその旨記述すること。

提出物〔４ｂ－２〕：プログラムの出力結果を保存したテキストファイル
N=5, N=6の両方について、解の数と、時間計算量の評価回数、それに実行時間を示すこと。
提出物〔４ｂ－３〕：時間計算量の見積もりに関する考察を述べたテキストファイル
騎士の周遊(課題４ｂ)は騎士の巡回(課題４ａ)と比較して、時間計算量はどのようにとらえられるか説明せよ。

☆発展：課題４ｃ☆
下記に示すチェス盤では、移動できる部分をoで、移動できない部分をxで示している。このようなチェス盤に対する Closed Knight's Tour の解の総数を求める問題に対して、時間計算量を見積もった上で、プログラムを実行し、解の総数と時間計算量（評価回数）を求めよ。また、得られた結果と時間計算量の見積とのずれの理由を考察せよ。

提出物〔４ｃ－１〕：テキストファイル
まずマップごとに、経路数、時間計算量（if文の評価回数）、および解の例を３つ以上（どれでもよい）含めること。
そのあとで、時間計算量の見積もり方法について述べ、実際の値とのずれの理由について記せ。

マップ

o	o	o	o	o	o	x	x
o	o	o	o	o	o	x	x
o	o	o	o	o	o	x	o
x	o	o	o	o	o	x	x
x	o	o	o	o	o	o	x
x	o	x	x	x	x	x	x
x	x	o	o	o	o	x	x
o	x	x	x	x	x	x	x

o	o	o	o	o	o	x	x
o	o	o	o	o	o	x	x
o	o	o	o	o	o	x	o
o	o	o	o	o	o	x	x
o	o	o	o	o	o	o	x
x	o	x	x	x	x	x	x
x	x	o	o	o	o	x	x
o	x	x	x	x	x	x	x

o	o	o	o	o	o	x	x
o	o	o	o	o	o	x	x
o	o	o	o	o	o	x	o
o	o	o	o	o	o	x	x
o	o	o	o	o	o	o	x
x	o	x	x	x	x	o	x
x	x	o	o	o	o	x	x
o	x	x	x	x	x	x	o

o	o	o	o	o	o	o	o
o	o	o	o	o	o	o	o
o	o	o	o	o	o	o	o
o	o	o	o	o	o	o	o
o	o	o	o	o	o	o	o
x	x	x	x	x	x	x	x
x	x	x	x	x	x	x	x
x	x	x	x	x	x	x	x

o	o	o	o	o	o	o	o
o	o	o	o	o	o	o	o
o	o	o	o	o	o	o	o
o	o	o	o	o	o	o	o
o	o	o	o	o	o	o	o
x	x	x	x	x	x	x	x
x	x	o	o	o	o	x	x
x	x	x	x	x	x	x	x

提出期限
2007/6/19, 8:30 JST
提出方法
WebCTによる提出

第５回課題

★必修：課題５ａ★
授業中に説明した決定性有限オートマトンプログラムを、以下の状態遷移表に対応するように改良せよ。
state transition diagram A

提出物〔５ａ－１〕：Ｃソースファイル（コメント必須）
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。

【注意】
課題１ａと同じく、
誰かに教えてもらった場合、
誰かに教えてあげた場合、
お互いに相談した場合はその旨記述すること。

提出物〔５ａ－２〕：受理される入力文字列を示したテキストファイル
受理される入力文字列と受理されない入力文字列をそれぞれ３つ以上挙げよ。
このオートマトンはどのような文字列を受理するか説明せよ。

★必修：課題５ｂ★
任意の指定金額の支払いにおける硬貨枚数最小化問題について、greedy algorithmで最適解が得られる硬貨の組み合わせを以下の中から全て選び、その理由を述べよ。
(10,5,1) (10,7,3) (6,3,2) (9,6,1)
(10,8,1) ( 6,4,1) (6,3,1) (9,3,1)
- 提出物〔５ｂ－１〕：テキストファイル
  上記の硬貨の組み合わせの中で、Greedy algorithmでも最適解が出せる硬貨の組み合わせを全部示せ。
  その上で、Greedy algorithmでも最適解が出せるようにするには、一般的にどのような硬貨の組み合わせがよいのか説明せよ。

★発展：課題５ｃ★
授業中に説明した決定性有限オートマトンプログラムを、標準入力からアルファベット（小文字だけでよい）を受け取り、"hello", "hi", "hell"の３単語を受理するように構成しなおすこと。それぞれ受理時に何を受理したか表示できるようにしておくこと。

提出物〔５ｃ－１〕：Ｃソースファイル（コメント必須）
Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。

【注意】
課題１ａと同じく、
誰かに教えてもらった場合、
誰かに教えてあげた場合、
お互いに相談した場合はその旨記述すること。

提出物〔５ｃ－２〕：プログラムの出力結果を保存したテキストファイル
幾つかの入力文字列について、実行結果を示すこと。

提出期限
2007/6/26, 8:30 JST
提出方法
WebCTによる提出

授業内容

シラバス(知能システム主専攻)(2007/03/14)
シラバス(機能システム主専攻)(2007/03/14)

成績評価

kameda[at]iit.tsukuba.ac.jp