科目名 グラフと最適化
単位数 2.0
担当者 講師 上土井 陽子 
履修時期 前期
履修対象 3年
概要 情報工学,計算機科学のさまざまな分野において利用されている各種の最適化手法・アルゴリズムについて,広く概観することを目的とする.特に,組合せ最適化問題に対する各種の解法について述べる.また,発見的解法,近似解法,NP-完全,NP-困難の概念についても触れる.計算機科学に関する多くの最適化問題はグラフ上で定義されることが多く,よって,グラフに関する代表的な最適化問題を中心に概説する.この講義を通じ,VLSI設計やネットワーク接続などの応用分野から発生した対象問題に対するアルゴリズムの本質,問題を解くための基礎となる理論を理解し,自らが今後取り組む分野での諸問題を効率的に解くアルゴリズムを設計するための基礎を身につけた学生を育成することを目標とする.(授業形態:講義)
科目の到達目標 最適化問題とそれら問題を解くための基礎となる理論を理解することを目標とする.具体的には
1.組合せ最適化問題の難しさの表現法
2.代表的な組合せ最適化問題の厳密解法
3.多くの組合せ最適化問題に適用できる発見的解法の動作
を理解し,自らがアルゴリズムを設計できるようになることを目標とする.
受講要件 「データ構造とアルゴリズムI」を修得していること,「離散数学」,「データ構造とアルゴリズムII」を履修していることが望ましい.
事前・事後学修の内容 必要に応じて事前事後学習のための課題を課す.
講義内容 1.イントロダクションー組合せ最適化問題とはー
2.PとNP,判定問題,問題の帰着(充足可能性問題,巡回セールスマン問題)
3.線形計画問題
4.シンプレックス法
5.ネットワーク理論(1)(最大流問題)
6.ネットワーク理論(2)(最小カット問題)
7.ネットワーク理論(3)(最大マッチング問題)
8.組合せ最適化,近似解法,発見的手法(ナップサック問題)
9.中間まとめ
10.分枝限定法
11.切除平面法
12.動的計画法(最短路問題)
13.焼きなまし法
14.遺伝的アルゴリズム
15.アルゴリズムの設計と評価(最小頂点被覆問題)
評価方法 授業の受講状況や中間試験,期末試験,講義中に行う演習,レポート課題の結果により,総合的に判断する.
教科書等 教科書:久保幹雄著「組合せ最適化とアルゴリズム」(共立出版)
参考書:長尾智晴著「最適化アルゴリズム」(昭晃堂)
    柳浦睦憲,茨木俊秀共著「組合せ最適化ーメタ戦略を中心としてー」(朝倉書店)
担当者プロフィール 授業内容や宿題などに関する学生の個別学習相談を随時受け付けています。
下記の問合せ先まで連絡し,アポイントを取ってください.

問合せ先:情報科学部棟4階414号室 E-mail:yoko@hiroshima-cu.ac.jp
備考 【教職】高一種(数学)