学類 講義ノート
学類 講義ノート
久野 誉人
takahito*cs.tsukuba.ac.jp (内線5540, 3F932; "*"は"@")

解析 I (H25)

  1. 10月1日: 高校積分の復習(教科書: p.1-20)
  2. 10月8日: 初等関数の微分法(教科書: p.21-40)
  3. 10月15日: 数列と関数の極限(教科書: p.41-48)
  4. 10月22日: 実数体の完備性(教科書: p.49-56)
  5. 10月29日: 微分の定義と性質(教科書: p.57-62)
  6. 11月12日: 高階導関数とテイラーの定理(教科書: p.63-77)
  7. 11月19日: テイラーの定理の応用,一様連続(教科書: p.78-88)
  8. 11月26日: 定積分の定義と性質(教科書: p.89-98)
  9. 12月3日: 定積分の諸定理,対数・指数関数(教科書: p.99-108)
  10. 12月10日: 広義積分,面積・長さ・体積(教科書: p.109-138)



フレッシュマンセミナー (H25)

スライド: スケジュール,プレゼンテーションのテーマなど



システム数理 II

パート1 (p.1 - 22)
  1. 線形計画問題
  2. シンプレックス法の基本アイデア
パート2 (p.23 - 48)
  1. シンプレックス法の収束性と初期化
  2. 線形計画問題の双対性
パート3 (p.49 - 62)
  1. 最短路問題とダイクストラ法
  2. ナップサック問題と動的計画法


付録A「数理計画法の参考書について」
付録B 「Blandのピボット選択規則の正当性」
付録C 「演習問題のヒント」



ソフトウェアサイエンス実験/情報メディア実験
--- メタヒューリスティクスと巡回セールスマン問題 ---

つくば市内にはコンビニエンス・ストアがいったい何件あるだろう?

大学のサークルに入ってきた新入生が先輩から,つくばセンターのローソンを出発し,市内のコンビニ一件一件を巡ってそのサークルのポスターを貼り,再び先輩の待つセンターのローソンに戻ってくるように頼まれたとしよう. この新入生の移動距離を最小にするようなコンビニの巡回順序を決める問題が巡回セールスマン問題であり,答を求めることが困難な問題のチャンピオンである.
 仮に市内のコンビニの数がたった20件しかないとしても,巡回順序は全部で

(20 - 1)! = 121645100408832000

通りもあるので,1秒間で1億通りの距離を計算できても,その新入生の在学中には最小距離の巡回順序を求めることはできない. 38年後,ようやく答の見つかるころには,新入生の息子が大学生になって父親と同じサークルに入部しているかもしれない. そのときのコンビニの数が倍に増えていたとしたら,父親としてはサークルからの退部を勧めるだろう.

この例で,巡回セールスマン問題のセールスマン役を任されているのが新入生である. こんなことを新入生に頼むのは先輩のイジメにも等しいが,実際には20件くらいの問題は短時間で厳密に解けるし,コンビニが数百件あっても近似解ならばパソコンで数秒とかからずに求めることができる. その近似算法をいくつかプログラムし,計算時間や近似精度の点でどの算法がもっとも優れているかを明らかにするのが,この課題の目的である.

テキスト1 (p.1 -- 8)
  1. 巡回セールスマン問題の定義と種類
  2. 単純な厳密算法
  3. 動的計画法による厳密算法
  4. ヒューリスティクス概観
  5. 実用的なヒューリスティクス
テキスト2 (p.9 -- 15)
  1. 禁断探索法
  2. 焼き鈍し法
  3. 課題と参考


GNU Octave上でのコンテスト

MATLABクローンのGNU Octaveは,行列演算などには滅法便利だが,巡回セールスマン問題のように離散的な問題を解くには全くといって良いほど向いていない. しかし,ランダムに問題を生成させたり,それをバイナリーコードで解いて統計を求めたりと,計算実験のための「作業台」と考えれば十分に役立てることができる. 例えば,C++のプログラム「tspenumerate.cc」とCのプログラム「enumerate.cc」(拡張子はC++だが,中身はC)をくっつけて

mkoctfile -o enumerate.oct tspenumerate.cc enumerate.cc

とコンパイルすれば,Octave上で実行できるユークリッド巡回セールスマン問題のための列挙法コード「enumerate.oct」を生成できる. Octave上で都市の座標を縦に並べたn×2行列Cを

[v, t] = enumerate(C);

のように「enumerate.oct」に与えると,都市の数nが10程度なら,あっという間に最適な巡回路tとその長さvを返してくれるはずである. この列挙法の本体はCでいい加減に書いた「enumerate.cc」なので,これさえもっと効率の良いヒューリスティク法に替えれば,はるかに大きな問題を処理することも可能だ. そこで,課題で作成したプログラムを利用し,Octave上でTSPLIBのテスト問題やランダムに生成した問題を解き,CPU時間や解の精度を競うコンテストを予定している.



H25年度の実施に関する連絡事項




インターンシップI, II





情報科学概論

  1. 計画数学への招待 -- 数理計画法とは何ぞや?
  2. 計画数学への招待 -- 筑波大生K君の冒険
  3. 計画数学への招待2 -- 筑波大生K君の挑戦
  4. H.18年度版計画数学への招待 -- 筑波大生K君の冒険
  5. H.18年度版計画数学への招待2 -- 筑波大生K君の挑戦



線形代数 I (H24)




計画数学

  1. 線形計画問題
    付録A「数理計画法の参考書について」
  2. シンプレックス法の基本的アイディア
  3. シンプレックス法の収束性と初期化
  4. 線形計画問題の双対性
  5. グラフとネットワーク流
  6. 最短路問題
  7. 最大流問題
  8. 組合せ最適化・整数計画問題

付録B 「Blandのピボット選択規則の正当性」
付録C 「演習問題のヒント」



計算幾何

  1. 計算幾何学とは
  2. 計算効率の評価
  3. ユークリッド空間の集合と性質(その1)
  4. ユークリッド空間の集合と性質(その2)
  5. 凸包問題
  6. ボロノイ図



ホーム