科目概要

対象年度 2004
教育課程名 博士前期課程 専攻別科目
授業科目名 アルゴリズム論
Subject Name AdvancedAlgorisms
単位数 2
必修・選択の別 選択
対象学科・学年 情報工学専攻1年
開講時期 後期
授業方法 講義と実習
担当教官 畑中 雅彦(HATANAKA,Masahiko)(情報工学専攻 情報処理工学講座)
教官室番号 V-506
連絡先(Tel) 0143-46-5427
連絡先(E-Mail) hatanaka@wil.csse.muroran-it.ac.jp


シラバス

授業のねらい  問題を解くための具体的な手順がアルゴリズムであり、アルゴリズム論の対象となる問題は非常に多様である。この授業では、基本的で実用上も重要な問題として「グラフに関するアルゴリズム」を題材に、アルゴリズム中に存在する戦略や証明法からアルゴリズムのソースコード化までを、プログラミング実習を通して具体的に学ぶ.
授業の目標 1.グラフに関する主要なアルゴリズムを理解する. 

2.アルゴリズム中に存在する戦略や証明法について理解する. 
授業計画 第 1週 グラフの定義・用語とその表現法・データ構造について 
第 2週 グラフの探索法(深さ優先探索) 
第 3週 グラフの探索法(幅優先探索) 
第 4週 グラフの連結性の判定(連結成分,二重連結性,関節点検出) 
第 5週 グラフの連結性の判定(強連結性) 
第 6週 最短路の問題解法(DijkstraのアルゴリズムとFloydのアルゴリズム) 
第 7週 最小木の問題(PrimのアルゴリズムとKruskalのアルゴリズム) 
第 8週 ネットワーク流問題(Ford-Fulkerson 法)
第 9週 グラフのマッチング問題(安定結婚問題)
第10週 グラフに関するアルゴリズムの実習(1) 
第11週 グラフに関するアルゴリズムの実習(2) 
第12週 グラフに関するアルゴリズムの実習(3) 
第13週 グラフに関するアルゴリズムの実習(4) 
第14週 実習結果の発表(1) 
第15週 実習結果の発表(2) 
教科書及び教材  「グラフに関するアルゴリズム」の講義資料は、下記Webサーバで公開済み。各自、ネットワーク経由で入手して下さい。http://www.wil.csse.muroran-it.ac.jp/member/hatanaka/Algorithms_Graph.pdf 

(本資料はPDF形式になっており、PDFfilereader(AcrobatReader)が必要です。) 
参考書  石畑 清「岩波講座ソフトウェア科学3アルゴリズムとデータ構造」岩波書店 [付属図書館蔵]
成績評価方法 実習課題に対する発表結果および出席状況を考慮して、総合的に評価する。
履修条件等  実習では,C言語やJava言語などによるプログラミングの知識が必要ですが,授業時間でプログラミングそのものの学習は行いません。プログラミングについての演習が必要な受講生は、各自の責任で事前に自習して下さい。  
教官からのメッセージ
その他