データ構造とアルゴリズム(2004年度)

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

本授業について

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

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

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


成績等


アップデート

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

課題

=提出方法について=

紙ベースでも構いませんが、可能な限り電子メールでの提出をお願いします。
基本的にプログラム提出なので、実験結果・考察・コメントは プログラム中の最初のコメント行として書き加えてください。
プログラムソースをテキストファイルとして電子メールの本文に入れてください。
HTMLメールや特定のアプリケーションに依存する形式(Wordなど)は使用しないで 下さい。
(必要があれば添付ファイルを使用してもよいですが、 私が閲覧できる保証はありません。)
下記の情報は必須ですので必ず付加してください。
【電子メール】 電子メールでのレポート提出サンプル
宛先(To): kameda@image.esys.tsukuba.ac.jp
件名(Subject): Algorithm Report 1.1 ←下記の指定した件名で!(自動処理するので件名が異なると見落とす可能性があります)

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

=提出時の技術的注意=

=課題内容=


告知

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

授業内容

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評価として単位は認定しない。レポート課題の評価次第では、補足的に試験を行うこともある。



●受講学生に望むこと:

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

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

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

●各週授業計画:

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

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

2004年度シラバスのコピー(PDF)


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