授業の主題
|
|
|
|
基本的なグラフアルゴリズム，アルゴリズム設計の一般的な技法が本授業の主題である．
|
| |
|
|
学修目標（到達目標）
|
|
|
|
現実の問題においては，グラフ上の問題が現れることがよくある．そこで，代表的なグラフ問題のアルゴリズムについて学ぶ．また，アルゴリズム設計の一般的な技法を理解する．効率的なアルゴリズムを設計することが現状では困難な問題についても学ぶ．
|
| |
|
|
|
|
|
|
授業概要
|
|
|
第1回: グラフ: 次数，パス，閉路，木
第2回: グラフの表現: 隣接行列，接続行列，隣接リスト
第3回: グラフ探索: 深さ優先探索，幅優先探索
第4回: 最短路: ダイクストラ法
第5回: 最小全域木: プリム法，
第6回: 最小全域木: クラスカル法，Union-Find
第7回: アルゴリズムの設計技法: 貪欲法，分割統治法，再帰法，動的計画法
第8回: 問題の難しさ: P，NP，NP完全性，期末試験
|
| |
|
|
評価方法と割合
|
|
評価方法
|
|
|
次項の項目及び割合で総合評価し、次のとおり判定する。
「Ｓ（達成度90％～100％）」、「Ａ（同80％～90％未満）」、
「Ｂ（同70％～80％未満）」、「Ｃ（同60％～70％未満）」を合格とし、
「不可（同60％未満）」を不合格とする。（標準評価方法）
|
| |
|
|
|
|
|
|
授業時間外の学修に関する指示
|
|
予習に関する指示
|
|
|
|
次回の講義内容について配布プリントを読んでくること．
|
| |
|
予習に関する教材
|
|
オンデマンド教材（授業内容の全体）
|
| |
|
|
復習に関する指示
|
|
|
|
講義のあった当日に再度配布プリント・ノートにて復習すること．
|
| |
|
復習に関する教材
|
|
オンデマンド教材（授業内容の全体）
|
| |
|
|
教科書・参考書
|
|
参考書
|
|
|
|
|
4-627-70251-5
|
|
上野修一, 高橋篤司共著
|
|
森北出版
|
2005
|
|
|
|
4-563-00791-9
|
|
A.V.エイホ, J.E.ホップクロフト, J.D.ウルマン著 ; 大野義夫訳
|
|
培風館
|
1987
|
|
|
|
978-4-7649-0408-8
|
|
T. コルメン [ほか] 共著 ; 浅野哲夫 [ほか] 共訳
|
|
近代科学社
|
2013
|
|
|
|
|
|
|
オフィスアワー等（学生からの質問への対応方法等）
|
|
|
|
電子メールで受け付ける．
|
| |
|
|
履修条件
|
|
|
|
電子情報通信学類(43002)とフロンティア工学類(42152)の学生の履修を優先する．その他の学類の学生の履修は事前に担当教員に許可を得ること．
|
| |
|
|
|
|
|
|
その他履修上の注意事項や学習上の助言
|
|
|
|
配布プリントは，教科書というよりはノートであり，必ずしもこれだけを読んで学べるようには書かれていない．授業内容と併せて初めて役に立つものであるので，この点を十分意識して授業に臨まれたい．
|
| |
|
|
|
|
|
|
|
|
|