久保幹雄 著
共立出版 2000年
パワーポイントスライド集
授業の概要 PowerPoint
Part 1 グラフ・アルゴリズム・計算量
Part 1では，グラフ，アルゴリズム，計算量の理論の基礎について書かれています．
- グラフ理論-オイラー閉路と最小木-
PowerPoint （新バージョン：練習問題を含む）
- グラフ理論-有向グラフと巡回セールスマン問題 –
PowerPoint （新バージョン：練習問題を含む） 追加資料（2008年AO入試模擬講義） - 計算量とアルゴリズム
PowerPoint
Part 2 線形計画
Part 2では，線形計画を例題を通して解説しています．特に，双対問題の意味と（絶対に失敗しない）導出方法に力点を置いています．
- 線形計画
PowerPoint練習問題 –PowerPoint - 双対問題
PowerPoint練習問題 –PowerPoint
Part 3 ネットワーク理論
Part 3では，最短路，最大流，最小費用流の3つの代表的なネットワーク問題に対するアルゴリズムを解説しています．特に，双対性によるアルゴリズムの自然な解釈に力点を置いています．
- 最短路
PowerPoint
補助資料 最短路問題をGurobiで解こう！
PowerPoint - 最大流
PowerPoint - 最小費用流
PowerPoint 宿題
Part 4 組合せ最適化
Part 4では，組合せ最適化に関するトピックスを扱っています．授業では，適当なトピックスを選択すると良いでしょう．
- 分枝限定法
PowerPoint - 多面体的アプローチ
PowerPoint - Lagrange緩和
PowerPoint - 動的計画
PowerPoint - 主・双対法
PowerPoint - 実験的解析
PowerPoint
誤植ならびに修正候補
- p.4 4行目：日本首相->日本の首相
- p.6 下から７行目：Euler閉路をもつ．->Euler閉路をもつ （図1.3)．
- p.29 図2.1 の牛肉の使用可能量 20 -> 30
- p.38 4行目：基底変数から->基底変数を
- p. 52 2行目：数式内 +7s2 -> -7s2
- p.73 表3.3のk=5の点3の値：4 → 6，同様に同ページの下から4行目：y3(5)=4 → y3(5)=6
- p.85 図3.12の修正：
枝(s,2)の容量：6 → 8，同図の枝(1,t)の容量：7 → 8 - p.92 図3.16が例題と違う問題になっているので，以下のように修正：
p.92 図3.16(a)～(f)の枝(s,2)の容量：6 → 8，同図(a)～(f)の枝(1,t)の容量：7 → 8
p.92 図3.16(a)のカット容量：5+6=11 → 5+8=13
p.92 図3.16(c)のカット容量：7+6=13 → 8+2+7=17（これも間違いです．8+8=16が正しい．）
p.92 図3.16(d)のカット容量：7+5=12 → 8+7=15（これ間違いです．8+5=13が正しい．）
p.92 図3.16(f)のカット容量：7+6=13 → 8+6=14 - p.131 下から3行目：仕様計算機->使用計算機
- p.151 5行目：GA Lib -> GA Lib. （省略形なのでピリオドを入れる．）
- p.157 5行目から：「１つの問題例ごとに一度だけ事前処理を行えば良い場合があるが，．．．」の部分： ちょっと分かりにくいのですが，たとえば巡回セールスマン問題の場合には，距離行列を事前に作成しておいて，それから構築法や改善法を行うことを意味します．
————————-以下第２刷の修正 - p.7 下から2行目：盤がn回のときの->盤がn枚のときの
- p.33 下から5行目：直線上の両端は端点である -> 線分の両端は端点である
- p.69 Bellman-Ford法の3行目から7行目を以下のように変更（改訂後も5行目が直っていない）3 yw(k+1):=yw(k) ,∀w ∈V
4 for all vw ∈E do
5 if yv(k)+cvw < yw(k+1) then
6 yw(k+1) :=yv(k)+cvw - p.73 Bellman-Ford法（完全版） の4行目から9行目を以下のように変更（改訂後も6行目が直っていない）4 yw(k+1):=yw(k) ,∀w ∈V
5 for all vw ∈E do
6 if yv(k)+cvw < yw(k+1) then
7 yw(k+1) :=yv(k)+cvw
8 prev(w) := v - （第１版の訂正が違っていました．）
p.92 図 3.16(c)のカット容量：8+8=16
p.92 図 3.16(d)のカット容量：8+5=13 - p.129 図 4.12 で、上から6行目 4 0 0 16 19 32 35 42 47 -> 4 0 0 16 19 32 35 39 44 (最後の２箇所が間違い）
- p.130 下から2行目：の中の最小のものである．-> の中の最大のものである．
- p.131 ２行目の式： =min …k=2,…,n -> =max … k=1,….,n
————————-以下第3刷の修正 - p.37 7行目：(0,0,60,0,-30) という座標->(0,0,60,0,0,-30) という座標
- p.57 下から７行目：-4,-7,-9の符号を反転-> -4,-7,-19の符号を反転
- p.89 図 3.14の右下の図：sから2への枝の残余容量が1，2からsへの枝の残余容量が7
- p.90 図 3.15：すべての図の点１の下の点の番号を点２にする．
- p.101 下から2行目：枝vw の費用c’wvは ->枝vw の費用c’vwは
- p.102 2行目：枝wv の費用c’vwは ->枝wv の費用c’wvは
- p.103 下から2行目：O(n^2 m^2 log n) -> O(n^2 m^3 log n)
- p.159 下から3行目：33: -> 36:
————————-以下第6刷の修正 - p. 39 14行目： x1+x2+x3=30 -> x3=30
- p. 41, 最終行：すべての基底変数，どの基底変数 ->すべての非基底変数，どの非基底変数
- p. 70 3行目：最適パスは s→2→1→r ->最適パスは s→2→1→t
- (8刷り)p. 69 3行目：Bellman-Ford法内 5行目：y_w(k) -> y_w(k+1)