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

本授業について

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

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

日程

 1. 2005/04/19(Tue)
 2. 2005/04/26(Tue)
 3. 2005/05/02(Mon)
 4. 2005/05/10(Tue)
 5. 2005/05/17(Tue)
 6. 2005/05/24(Tue)
 7. 2005/05/31(Tue)
 8. 2005/06/07(Tue)
 9. 2005/06/14(Tue)
10. 2005/06/21(Tue)
--. 2005/06/28(Tue)

アップデート

• アップデート情報

課題

＝提出先＝

アカウントを割り当てられた学生のみがログインできます。
課題等の提出は、２００５年度から筑波大学で試験運用が開始される WebCTシステム経由で全て行います。WebCTシステムは本年度は学内からのみ アクセス可能です。 履修登録が確定後、履修者には全員、WebCTのアカウントが付与されます。

＝課題実施方法について＝

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

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

＝課題内容＝

• 第１回課題
  深さ優先探索アルゴリズムを、再帰呼び出しを用いずに作成する。 作成するプログラムは、授業で説明した再帰呼び出しによる深さ優先探索アルゴリズムと同じ出力ができること。
  • 提出物
    • 課題1-a：Ｃソースファイル提出
      再帰呼び出しを用いずに深さ優先探索するプログラムを書くこと。
      Ｌ棟５階の計算機室でコンパイルと実行ができること。
      
      • 【注意】誰かに教えてもらった場合：
        その学生（氏名・学籍番号）をプログラム先頭に記し、さらにプログラム中コメントを使って、教えてもらったところの解説を数行で書き込むこと。（教えてもらった部分の解説コメントのないプログラムは全く評価しません。「全体です」のようなコメントの場合も同じです。）
        
      • 【注意】誰かに教えてあげた場合：
        その学生（氏名・学籍番号）をプログラム先頭に記すこと。
      • 【注意】お互いに相談した場合：
        教えてもらった・教えてあげたの例に準拠して提出してください。
    • 課題1-b：実行結果と解説の提出
      標準出力等に出力される実行結果をテキストファイルに保存して提出。
      その実行結果に対して、実行結果に続けてコメント・考察を書きなさい。
    • 課題1-c：計算量の見積
      提出したプログラムについて、時間計算量と空間計算量の見積をしなさい。
      
      1. 見積の対象となる行を示し、なぜその行を選んだのか理由を書く。
      2. グラフの頂点数をN、辺数をMとし、オーダー表記で「時間」計算量を示す。その根拠も説明すること。
      3. グラフの頂点数をN、辺数をMとし、オーダー表記で「空間」計算量を示す。その根拠も説明すること。
  • 提出期限
    2005/5/20, 午後17:00 (変更しました)
  • 提出方法
    WebCTによる提出（5/13の10時前頃に各人にメールを送りました。そのメールが届いていない学生のアカウントはWebCT上で作成されていません。履修しているはずなのにメールを受け取っていない人が近くにいれば私まで至急連絡するように伝えてください。なお、名簿は5/8時点でのTWINS情報から作成しています。）
  • 参考資料
    授業で用いた隣接行列(N=8)

• 第２回課題
  ある頂点から任意頂点への最短経路を求めるDijkstraのアルゴリズムについて、以下の課題をこなすこと。
  • 提出物
    • 課題2-a：Ｃソースファイルの提出
      授業中に説明したDijkstraのＣプログラムに、全ての頂点への最小コスト経路がわかるような出力が出来るような部分を書き加えて完成させよ。グラフの例と出力例は別途Webに掲載する。なお、経路がわかるような出力であれば、出力は出力例に準じる必要はない。（誰かに教えてもらった場合・教えてあげた場合・相談した場合は第１回課題と同様に記すこと。）
    • 課題2-b：Ｃプログラムの改善に関する考察
      授業で説明したDijkstraのアルゴリズム説明に対して、授業で説明したＣプログラムの実装はその通りに実装していない部分がある。そこがどの部分かを示し、アルゴリズム説明の通りにＣプログラムを修正するにはどうすればよいか示せ。Ｃプログラム中で修正すべき行がどこかを、その前後１０行程度と共に示すこと。また、可能なら修正版のプログラムも示せ。
    • 課題2-c：グラフのエッジの重みは正でなくてはいけない理由
      最短経路を求めるためには、有向グラフのエッジの重みは正でなくてはいけない。その理由を、もし重みに０が含まれる場合や負が含まれる場合を考えて何がどうまずいのか説明せよ。
  • 提出期限
    2005/05/24, 午前08:30
  • 提出方法
    WebCTによる提出
  • 参考資料
    グラフG6の例
    グラフG7の例
    

• 第３回課題
  グラフ中の全ての頂点対について最短経路を求めるFloydのアルゴリズムについて、以下の課題をこなすこと。
  • 提出物
    • 課題3-a：Ｃソースファイルの提出
      授業中に説明したFloydのＣプログラムにおいて、全ての頂点対の最短経路がわかるような出力が出来るような部分を書き加えて完成させよ。グラフの例と出力例は別途Webに掲載する。なお、経路がわかるような出力であれば、出力は出力例に準じる必要はない。（誰かに教えてもらった場合・教えてあげた場合・相談した場合は第１回課題と同様に記すこと。）
    • 課題3-b：DijkstraのプログラムとFloydのプログラムの計算コストに関する考察
      Dijkstraのプログラム(第２回課題で用いたもの)とFloydのプログラムについて、時間計算量、空間計算量を示せ（それぞれビッグオー表現を用いてよい）。計算の上でプログラム中のどの部分に注目しているかを示し、そこに注目した理由も述べること。さらに二つのプログラムの計算量を比較し、どのようなことが導けるか記述せよ。
  • 提出期限
    2005/05/31, 午前08:30
  • 提出方法
    WebCTによる提出
  • 参考資料
    グラフG6の例
    グラフG7の例
    

• 第４回課題
  Knight's Tour（邦題では騎士の巡回や騎士の巡礼と訳される）に関連して、以下の必須課題を全て行うこと。発展課題はボーナス課題なのでしなくともよい。各課題について教えた・教わった・共同で取り組んだ場合は第１〜３回の各課題同様に相手の氏名・学籍番号をプログラム冒頭に示すこと。
  • 提出物
    • 課題4-a：【必須】Knight's Tourの解の総数の算出
      授業中に説明したKnight's TourのＣプログラムを用いて、チェス盤の１辺Nが5と6の場合について、経路の数を求めよ。スタート地点は(0,0)とする。また、実行時間も示せ（timeコマンドを利用して、実際の経過時間を示せ）。
    • 課題4-b：【必須】Closed Knight's Tour（騎士の周遊）における解の総数算出
      Closed Knight's Tour（騎士の周遊）とは、Knight's Tourに加えて、経路の最後のマスからスタート地点に１手で戻れる経路を求める問題である。チェス盤の１辺Nが5と6の場合について、この条件を満たす経路の数を求めよ。また、実行時間も示せ（timeコマンドを利用して、実際の経過時間を示せ）。
    • 課題4-c：【発展】Knight's Tour, Closed Knight's Tourにおける時間計算量の測定
      課題4-a,4-bにおいて、解の総数を求めるのに必要だった時間計算量（制御ループの一番内側のif文の評価回数を数えるのが普通である）を求めよ。評価回数は、通常のint型で表示できる数字より大きな値になる。どのような見積もり（ないし工夫）をして非常に大きな数字 に対応できるプログラムにしたかをプログラム中のコメント部に記述せよ。
    • 課題4-d：【発展】大きな盤サイズのClosed Knight's Tourに対する時間計算量の予想
      課題4-cの結果から、N=7, N=8（チェス盤の正しい）についてどれほど計算時間が必要になりそうかを予想する式を立て、その立式の説明をせよ。
    • 課題4-e：【発展】変形版 Closed Knight's Tourの解の総数
      下記に示すチェス盤では、移動できる部分をoで、移動できない部分をxで示している。このようなチェス盤に対する Closed Knight's Tour の解の総数を求める問題に対して、課題4-d同様に計算時間を見積もった上で、プログラムを実行し、解の総数、時間計算量（評価回数）を求めよ。得られた結果と計算時間の見積とのずれの理由を考察せよ。
    • 課題4補：【補足】Knight's Tourプログラム提出
      課題4-aで用いたプログラムを提出してください。実行結果が想定している場合と異なるときの参考にします。（このソース自体には採点はしません。） [2005/6/21まで]

      マップG	マップJ	マップM	マップN	マップZ
      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

      [2005/06/06,マップZは普通の人にとって恐らく時間計算量サイズが大きすぎます]
  • 提出期限
    【必須課題】2005/06/14, 午前08:30
    【発展課題・補足】2005/06/21, 午前08:30 (WebCTの設定に不備があったので、発展課題についてのみ１週間〆切を延ばします。)
    
  • 提出方法
    WebCTによる提出
  • 参考
    ６行５列の長方形な盤を作成して(0,0)からスタートした場合、Knight's Tourは4542経路、Closed Knight's Tourは16経路。また、Knight's Tour時の評価回数は789,901,968回。ただし、評価回数のほうはプログラム依存でかつ評価位置をどこに設定するかで変わるので正確にこの値になるとは限らない。

• 第５回課題
  
  • 提出物
    • 課題5-a：【必須】Ｃソースファイルの提出（Knapsack/DP）
      物体の重複選択を許すKnapsack問題について、動的計画法に基づく解法をＣプログラムを実装せよ。出力には、最大価値とその最大価値を実現する物体の選択個数を表示すること。（誰かに教えてもらった場合・教えてあげた場合・相談した場合は第１回課題と同様に記すこと。）
    • 課題5-b：【発展】Ｃソースファイルの提出（Knapsack/FPTAS）
      Knapsack問題に対して、FPTASアルゴリズムに基づくＣプログラムを実装せよ。また、εの値をいろいろと変えて（３種類以上）、時間計算量（プログラム中の特定行の通過回数で評価）がどのように変化するかを調べよ。また、最適解を求め、ε変化に対して近似解がどのように変化するかを調べよ。
  • 提出期限
    2005/06/29, 午後18:00
  • 提出方法
    WebCTによる提出
  • 課題5-aに対する問題例
    

      N = 10, W_LIMIT = 199
      0: v =   5, w =  56      1: v =  83, w =  46      2: v =  56, w =  20
      3: v =  19, w =  99      4: v =  75, w =  49      5: v =  35, w =  65
      6: v =  14, w =  25      7: v =  95, w =  32      8: v =  58, w =  37
      9: v =  80, w =  31
      ＜出力例＞
      ID=9 x 1, ID=7 x 4, ID=2 x 2
      total max value = 572, weight = 199
    

• 授業評価アンケートのお願い
  WebCT上に授業評価アンケートを掲載しました。（授業中に時間が取れなくてできなかった分です。）ご協力をお願いします。[2005/6/21]

• 試験
  実施しません。レポート課題の評価次第では、一部の学生に補足的に呼び出しを行うことがあります。その際はＬ棟５階計算機システムのメールアカウントにメールします。

授業内容

科目番号/知的工学  3206/S543111
科目番号/機能工学  3240/S643111
英名               Data Structure and Algorithm
担当教官           亀田能成
研究室             3M304
電話               5256
Office Hour        Weekday 10:00-18:00
e-mail             kameda@image.esys.tsukuba.ac.jp
関連科目           計算機序論II
                   プログラミング序論
                   グラフ理論
授業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
　巡回セールスマン問題
　　　最適解
　　　二近似アルゴリズム

成績評価