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

本授業について

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

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

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

日程

 1. 2006/04/18(Tue)
 2. 2006/04/25(Tue)
 3. 2006/05/02(Tue)
 4. 2006/05/09(Tue)
 5. 2006/05/16(Tue)
 6. 2006/05/23(Tue)
 7. 2006/05/30(Tue)
 8. 2006/06/06(Tue)
 9. 2006/06/13(Tue)
10. 2006/06/20(Tue)
--. 2006/06/27(Tue)

アップデート

• 2006/4/25の授業について
  深さ優先探索のプログラムにおいて、 visit()関数の型をint型で板書しましたが、 void型が正しいです。 （int型でも実行できますし問題ありませんが、 返値を利用していないので『正しい』プログラムではありません。）
  
• 課題１について（その１）
  階層表示の例が間違っていました。悩んでいた皆様、すみません。 間違っていた例が出力できるように工夫した人はそのままで構いません。 （課題1a-1,1a-2については再提出できるように設定を変えました。） [2006/5/16,19]
  
• 課題１について（その２）
  課題1d-2の提出エントリが出来ていませんでした。 直接成績評価には使いませんが、5/25まで提出できるように設定しました。[2006/5/19]
  
• 課題３について
  データサンプル１の女性No.2のPreference Orderが間違っていました。すみません。[2006/6/1]
  
• 課題４ｃについて
  WebCTのエントリがアクティブになってませんでした。課題４ｃについてのみ、6/23まで〆切を延長します。[2006/6/19]
  

課題

＝提出先＝

アカウントを割り当てられた学生のみがログインできます。
課題等の提出は、２００６年度から筑波大学で全学的本運用が開始された WebCTシステム経由で全て行います。 WebCTシステムは今のところ学内からのみアクセス可能のようです （変更の可能性あり）。
履修登録が確定したので、履修者には全員、WebCTのアカウント権限が付与されました [2006/05/11]。

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

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

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

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

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

＝課題内容＝

• 第１回課題
  こちらの整理の都合上、番号を振り替えました。
  
  
  • ★必修★課題１ａ：深さ優先探索のプログラムを改良して、頂点の出力毎に階層数も表示せよ。
    （グラフG3の例） 0[0], 1[1], 6[2], 2[3], 3[4], 7[5], 4[1], 5[2]（間違いでした）
    （グラフG3の例） 0[0], 1[1], 6[2], 2[3], 3[4], 7[5], 5[3], 4[4]
    ※深さ優先さえ満たされていれば必ずしもこの通りに出力する必要はない。
    • 提出物〔１ａ−１〕：Ｃソースファイル（コメント必須）
      ※Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
      ※改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
      

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

    • 提出物〔１ａ−２〕：プログラムの出力結果を保存したテキストファイル
      ※教官側で万一、コンパイルや実行に失敗した場合用です。
      
    
    
  • ★必修★課題１ｂ：木構造において、頂点数Ｖと辺数Ｅとの関係を式で示せ。
    
    • 提出物〔１ｂ−１〕：テキストファイル
      ※万一複雑な式を書く必要があるときは、Latexに準拠した形で書くこと。
      ▼ヒント：それほど難しい式ではありません。
      
    
    
  • ★必修★課題１ｃ：課題１ｂの式をグラフは必ず木であると言えるか。理由と共に示せ。
    
    • 提出物〔１ｃ−１〕：テキストファイル
      ▼ヒント：木は閉路(cycle)がないグラフとみなすことができます。
      
    
    
  • ★発展★課題１ｄ：ある無向グラフが与えられたときに、そのグラフがSpanning Treeであるかどうかを判定するプログラムを書け。
    
    • 提出物〔１ｄ−１〕：Ｃソースファイル（コメント必須）
      ※Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
      ※工夫した箇所について、説明をコメントの形でプログラム中に書き込むこと。
      

      【注意】 誰かに教えてもらった場合・教えた場合・互いに相談した場合： ⇒提出物〔１ａ−１〕と同じようにして下さい。

    • 提出物〔１ｄ−２〕：プログラムの出力結果を保存したテキストファイル
      ※参考資料のG3,G10,G11,G12に対して実行した結果を入れること。
      
    
    
  • 提出期限
    2006/5/18, 18:00 （少しだけ遅らせました）
  • 提出方法
    WebCTによる提出
  • 参考資料
    授業で用いたグラフ(G3)の隣接行列(N=8)
    グラフ(G10)の隣接行列(N=8)
    グラフ(G11)の隣接行列(N=8)
    グラフ(G12)の隣接行列(N=8)
    グラフG3/G10/G11/G12の図示
    
  
  
• 第２回課題
  
  
  
  • ★必修★課題２ａ：授業で説明した最長経路探索問題を解くプログラムについて、グラフ中の最長経路の値と、その経路とを出力するように改良せよ。
    （グラフG5の例） total cost = 8, path = 2->3->7
    ※値と経路とが分かるようになっていれば、必ずしもこの通りに出力する必要はない。
    • 提出物〔２ａ−１〕：Ｃソースファイル（コメント必須）
      ※Ｌ棟５階の計算機室で必ずコンパイルと実行ができること。
      ※授業で提示したプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
      

      【注意】 誰かに教えてもらった場合・教えた場合・互いに相談した場合： ⇒提出物〔１ａ−１〕と同じようにして下さい。

    • 提出物〔２ａ−２〕：プログラムの出力結果を保存したテキストファイル
      ※教官側で万一、コンパイルや実行に失敗した場合用です。
      
    
    
  • ★必修★課題２ｂ：トポロジカルソートのアルゴリズムについて、その時間計算量と空間計算量の考察をせよ。
    
    • 提出物〔２ｂ−１〕：テキストファイル
      ※必要であれば、あるグラフについて頂点数Ｎ、辺数Ｅと仮定すること。
      ※ビッグＯ表現を利用すること。
      
    
    
  • ★発展★課題２ｃ：授業で説明した最長経路探索問題を解くプログラムには、時間計算量的に無駄がある。それはどこか示せ。また、どう改良すれば削減できるかについても述べよ。
    
    • 提出物〔２ｃ−１〕：テキストファイル
      ※必要であればテキストファイル内にソースリストを含めてよい。
      
    
    
  • 提出期限
    2006/5/23, 午前8:30
  • 提出方法
    WebCTによる提出
  • 参考資料
    授業で用いたグラフ(G5)の隣接行列(N=8)
    
  
  
• 第３回課題
  
  
  
  • ★必修★課題３ａ：安定結婚問題を解くプログラムを、授業で配布した資料のアルゴリズムに基づいて実装せよ。
    安定結婚を満たす解（全ペア）と、求婚回数を出力すること。
    （もとの資料はUCBの下記の頁にある。必要であれば各自で参照のこと。）
    http://www.cs.berkeley.edu/~jfc/cs174lecs/lec7/lec7.html
    
    • 提出物〔３ａ−１〕：Ｃソースファイル（コメント必須）
      ※授業で提示したプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
      

      【注意事項】提出物〔１ａ−１〕に同じ。

    • 提出物〔３ａ−２〕：プログラムの出力結果を保存したテキストファイル
      ※教官側で万一、コンパイルや実行に失敗した場合用です。
      
    
    
  • ★発展★課題３ｂ：安定結婚問題を解くプログラムの実行過程で、「求婚回数(count_propose)」「求婚して承諾された回数(count_yes)」「求婚して断られた回数(count_no)」「離婚回数(count_divorce)」について表示するようにプログラムを改良せよ。
    また、そのとき、これらの４つの変数について、依存関係のある変数があるか、あるとすればそれはどれとどの変数か述べよ。
    さらに、それぞれの変数について、与えられたpreference orderが同一のとき、その値を小さくするにはどのような方法が考えられるか考察せよ。
    
    • 提出物〔３ｂ−１〕：Ｃソースファイル（コメント必須）
      【注意事項】提出物〔１ａ−１〕に同じ。
    • 提出物〔３ｂ−２〕：テキストファイル
      【注意事項】提出物〔１ａ−１〕に同じ。
    
    
  • 提出期限
    2006/6/6, 午前8:30
  • 提出方法
    WebCTによる提出
  • 参考資料
    安定結婚問題用のデータサンプル０(N=4)
    安定結婚問題用のデータサンプル１(N=8)
    
  
  
• 第４回課題
  
  
  
  • ★必修★課題４ａ：授業中に説明したKnight's Tour（騎士の巡回）の解を求めるプログラムを用いて、チェス盤の１辺Nが5と6の場合について、経路の数を求めよ。スタート地点は(0,0)とする。また、そのときの時間計算量（制御ループの一番内側のif文の評価回数で表すものとする）を、桁あふれがないように注意しつつ求めよ。
    
    • 提出物〔４ａ−１〕：Ｃソースファイル（コメント必須）
      ※授業で提示したプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
      

      【注意事項】提出物〔１ａ−１〕に同じ。

    • 提出物〔４ａ−２〕：プログラムの出力結果を保存したテキストファイル
      ※チェス盤の１辺の大きさと、そのときの経路数、時間計算量（if文の評価回数）、および解の例を３つ以上（どれでもよい）含めること。
      ※解のすべてを添付しないこと（数が多いので。）
      ※時間計算量は通常のint型を超える可能性があることに注意。
      
    • 提出物〔４ａ−３〕：時間計算量を測定するための工夫を述べたテキストファイル
      ※時間計算量は通常のint型を超える可能性に対して、プログラム上どのように工夫して桁あふれがないようにしているかを説明する。
      ※必要であれば、ソースプログラムの一部を引用してよい。
      
    
    
  • ★発展★課題４ｂ：Closed Knight's Tour（騎士の周遊）とは、Knight's Tourに加えて、経路の最後のマスからスタート地点に１手で戻れる経路を求める問題である。チェス盤の１辺Nが5と6の場合について、この条件を満たす経路の数を求めよ。また、実行時間も示せ（timeコマンドを利用して、実際の経過時間を示せ）。
    • 提出物〔４ｂ−１〕：Ｃソースファイル（コメント必須）
      【注意事項】提出物〔１ａ−１〕に同じ。
    • 提出物〔４ｂ−２〕：テキストファイル
      【注意事項】提出物〔４ａ−２〕に同じ。
    
    
  • ★発展★課題４ｃ：下記に示すチェス盤では、移動できる部分をoで、移動できない部分をxで示している。このようなチェス盤に対する Closed Knight's Tour の解の総数を求める問題に対して、時間計算量を見積もった上で、プログラムを実行し、解の総数と時間計算量（評価回数）を求めよ。また、得られた結果と時間計算量の見積とのずれの理由を考察せよ。
    • 提出物〔４ｃ−１〕：テキストファイル
      【注意事項】提出物〔１ａ−１〕に同じ。
      ※マップごとに、経路数、時間計算量（if文の評価回数）、および解の例を３つ以上（どれでもよい）含めること。
      ※そのあとで、時間計算量の見積もり方法について述べ、実際の値とのずれの理由について記せ。
      
    • マップ
      

      マップ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

      [マップZは普通の人にとって恐らく時間計算量サイズが大きすぎます]
    
    
  • 提出期限
    2006/6/20, 午前8:30
    2006/6/23, 午後23:55 （課題４ｃについてだけ延長します。）
  • 提出方法
    WebCTによる提出
  
  
• 第５回課題
  
  
  
  • ★必修★課題５ａ：授業中に説明した「問題の置き換え」を使って、ナップサック問題を最長経路問題における重み付き有向グラフに変換するプログラムを作成せよ。
    
    • 提出物〔５ａ−１〕：Ｃソースファイル（コメント必須）
      ※授業で提示したプログラムから改良・挿入した行について、説明をコメントの形でプログラム中に書き込むこと。
      

      【注意事項】提出物〔１ａ−１〕に同じ。

    • 提出物〔５ａ−２〕：Knapsack-Aに対する実行結果を保存したテキストファイル
      ※knapsack-A（授業中の問題と同一）について出力した結果を示せ。
      ※重み付き有向エッジについては、１行に１個ずつ「(j0,i0) (j1, i1) value」の形で記述せよ。
      ※エッジ記述行以外にはさまざまな情報を付加してよい。
      ※出力結果例をこちらに示す。この通りでなくてもよいが、エッジ記述行の書式だけは守ること。
      
    • 提出物〔５ａ−３〕：Knapsack-Bに対する実行結果を保存したテキストファイル
      ※knapsack-Bについて出力した結果を示せ。
      ※重み付き有向エッジについては、１行に１本ずつ「(j0,i0) (j1, i1) value」の形で記述せよ。
      ※エッジ記述行以外にはさまざまな情報を付加してよい。
      
    • 提出物〔５ａ−４〕：考察を記したテキストファイル
      ※このような重み付き有向グラフを隣接行列のデータ表現であらわそうとすると、どういう問題が発生するか述べよ。それを回避するための方法についても示せ。
      ※文章による説明だけでよい。
      
    
    
  • 提出期限
    2006/6/27, 午後17:00 （予定）
  • 提出方法
    WebCTによる提出
  
  

授業内容

• シラバスのコピー (知能システム主専攻)
• シラバスのコピー (機能システム主専攻)
  
• 【参考】 2006年度シラバス

成績評価