| 対象年度 | 2004 |
| 教育課程名 | 博士前期課程 専攻別科目 |
| 授業科目名 | アルゴリズム論 |
| Subject Name | AdvancedAlgorisms |
| 単位数 | 2 |
| 必修・選択の別 | 選択 |
| 対象学科・学年 | 情報工学専攻1年 |
| 開講時期 | 後期 |
| 授業方法 | 講義と実習 |
| 担当教官 | 畑中 雅彦（HATANAKA，Masahiko）（情報工学専攻 情報処理工学講座） |
| 教官室番号 | V-506 |
| 連絡先（Tel） | 0143-46-5427 |
| 連絡先（E-Mail） | hatanaka@wil.csse.muroran-it.ac.jp |
| 授業のねらい | 問題を解くための具体的な手順がアルゴリズムであり、アルゴリズム論の対象となる問題は非常に多様である。この授業では、基本的で実用上も重要な問題として「グラフに関するアルゴリズム」を題材に、アルゴリズム中に存在する戦略や証明法からアルゴリズムのソースコード化までを、プログラミング実習を通して具体的に学ぶ． |
| 授業の目標 | １．グラフに関する主要なアルゴリズムを理解する． ２．アルゴリズム中に存在する戦略や証明法について理解する． |
| 授業計画 | 第 １週 グラフの定義・用語とその表現法・データ構造について 第 ２週 グラフの探索法（深さ優先探索） 第 ３週 グラフの探索法（幅優先探索） 第 ４週 グラフの連結性の判定（連結成分，二重連結性，関節点検出） 第 ５週 グラフの連結性の判定（強連結性） 第 ６週 最短路の問題解法（DijkstraのアルゴリズムとFloydのアルゴリズム） 第 ７週 最小木の問題（PrimのアルゴリズムとKruskalのアルゴリズム） 第 ８週 ネットワーク流問題（Ford-Fulkerson 法） 第 ９週 グラフのマッチング問題（安定結婚問題） 第１０週 グラフに関するアルゴリズムの実習（1） 第１１週 グラフに関するアルゴリズムの実習（2） 第１２週 グラフに関するアルゴリズムの実習（3） 第１３週 グラフに関するアルゴリズムの実習（４） 第１４週 実習結果の発表（１） 第１５週 実習結果の発表（２） |
| 教科書及び教材 | 「グラフに関するアルゴリズム」の講義資料は、下記Webサーバで公開済み。各自、ネットワーク経由で入手して下さい。http://www.wil.csse.muroran-it.ac.jp/member/hatanaka/Algorithms_Graph.pdf （本資料はPDF形式になっており、PDFfilereader(AcrobatReader)が必要です。） |
| 参考書 | 石畑 清「岩波講座ソフトウェア科学３アルゴリズムとデータ構造」岩波書店 [付属図書館蔵] |
| 成績評価方法 | 実習課題に対する発表結果および出席状況を考慮して、総合的に評価する。 |
| 履修条件等 | 実習では，C言語やJava言語などによるプログラミングの知識が必要ですが，授業時間でプログラミングそのものの学習は行いません。プログラミングについての演習が必要な受講生は、各自の責任で事前に自習して下さい。 |
| 教官からのメッセージ | |
| その他 | |